Hispanopedia Wiki
Articulo de referencia

Agrupamiento espectral

Un ejemplo de grafo conectado, con 6 vértices. Partición en dos grafos conectados En estadística multivariante , las técnicas de agrupamiento espectral utilizan el espectro ( va...

Hispanopedia WikiContenido en espanolLectura gratuita
Un ejemplo de grafo conectado, con 6 vértices.
Partición en dos grafos conectados

En estadística multivariante , las técnicas de agrupamiento espectral utilizan el espectro ( valores propios ) de la matriz de similitud de los datos para reducir su dimensionalidad antes de agruparlos en un número menor de dimensiones. La matriz de similitud se proporciona como entrada y consiste en una evaluación cuantitativa de la similitud relativa de cada par de puntos en el conjunto de datos.

En su aplicación a la segmentación de imágenes, la agrupación espectral se conoce como categorización de objetos basada en la segmentación .

Definiciones

Dado un conjunto enumerado de puntos de datos, la matriz de similitud puede definirse como una matriz simétrica.A{\displaystyle A}, dóndeAij≥0{\displaystyle A_{ij}\geq 0}representa una medida de la similitud entre puntos de datos con índicesi{\displaystyle i}yj{\displaystyle j}. El enfoque general para la agrupación espectral consiste en utilizar un método de agrupación estándar (existen muchos métodos de este tipo; k -medias se analiza más adelante ) sobre los vectores propios relevantes de una matriz laplaciana deA{\displaystyle A}Existen diversas formas de definir un laplaciano, cada una con distintas interpretaciones matemáticas, por lo que la agrupación también tendrá diferentes interpretaciones. Los autovectores relevantes son aquellos que corresponden a los autovalores más pequeños del laplaciano, excepto el autovalor más pequeño, que tendrá un valor de 0. Para optimizar la eficiencia computacional, estos autovectores suelen calcularse como los autovectores correspondientes a los autovalores más grandes de una función del laplaciano.

matriz laplaciana

Un sistema de resortes bidimensional.

Se sabe que el agrupamiento espectral se relaciona con la partición de un sistema masa-resorte, donde cada masa se asocia con un punto de datos y cada rigidez del resorte corresponde a un peso de una arista que describe la similitud de los dos puntos de datos relacionados, como en el sistema de resortes . Específicamente, la referencia clásica [ 1 ] explica que el problema de valores propios que describe los modos de vibración transversales de un sistema masa-resorte es exactamente el mismo que el problema de valores propios para la matriz laplaciana del grafo definida como

L:=D−A{\displaystyle L:=DA},

dóndeD{\displaystyle D}es la matriz diagonal

Dii=∑jAij,{\displaystyle D_{ii}=\sum _{j}A_{ij},}

y A es la matriz de adyacencia .

Las masas que están firmemente conectadas por los resortes en el sistema masa-resorte evidentemente se mueven juntas desde la posición de equilibrio en modos de vibración de baja frecuencia, de modo que los componentes de los autovectores correspondientes a los autovalores más pequeños del laplaciano del grafo pueden usarse para agrupar significativamente las masas. Por ejemplo, suponiendo que todos los resortes y las masas son idénticos en el sistema de resortes bidimensional que se muestra, uno esperaría intuitivamente que las masas conectadas más débilmente en el lado derecho del sistema se muevan con la mayor amplitud y en la dirección opuesta al resto de las masas cuando el sistema se agita, y esta expectativa se confirmará al analizar los componentes de los autovectores del laplaciano del grafo correspondientes a los autovalores más pequeños, es decir, las frecuencias de vibración más pequeñas .

Normalización de la matriz laplaciana

El objetivo de la normalización es lograr que todos los elementos de la diagonal de la matriz laplaciana sean unitarios, escalando también los elementos fuera de la diagonal de forma correspondiente. En un grafo ponderado, un vértice puede tener un grado elevado debido a un número reducido de aristas conectadas pero con pesos elevados, al igual que debido a un gran número de aristas conectadas con pesos unitarios.

Una técnica popular de agrupamiento espectral normalizado es el algoritmo de cortes normalizados o algoritmo de Shi-Malik introducido por Jianbo Shi y Jitendra Malik , [ 2 ] comúnmente utilizado para la segmentación de imágenes . Este algoritmo divide los puntos en dos conjuntos.(B1,B2){\displaystyle (B_{1},B_{2})}basado en el vector propiov{\displaystyle v}correspondiente al segundo valor propio más pequeño del laplaciano normalizado simétrico definido como

Lnorma:=I−D−1/2AD−1/2.{\displaystyle L^{\text{norma}}:=ID^{-1/2}AD^{-1/2}.}

El vectorv{\displaystyle v}es también el vector propio correspondiente al segundo valor propio más grande de la matriz de adyacencia normalizada simétricamente. D−1/2AD−1/2.{\displaystyle D^{-1/2}AD^{-1/2}.}

El laplaciano normalizado de paseo aleatorio (o izquierdo) se define como

Lrw:=D−1L=I−D−1A{\displaystyle L^{\text{rw}}:=D^{-1}L=ID^{-1}A}

y también puede utilizarse para la agrupación espectral. Un algoritmo matemáticamente equivalente [ 3 ] toma el vector propio.tú{\displaystyle u}correspondiente al mayor valor propio de la matriz de adyacencia normalizada del paseo aleatorioPAG=D−1A{\displaystyle P=D^{-1}A}.

El vector propiov{\displaystyle v}del laplaciano normalizado simétricamente y el vector propiotú{\displaystyle u}Los laplacianos normalizados de la izquierda están relacionados por la identidadD−1/2v=tú.{\displaystyle D^{-1/2}v=u.}

Análisis de clústeres mediante incrustación espectral

Conociendo elnorte{\displaystyle n}-por-k{\displaystyle k}matrizV{\displaystyle V}de vectores propios seleccionados, mapeo —llamado incrustación espectral— del originalnorte{\displaystyle n}Los puntos de datos se realizan a unk{\displaystyle k}espacio vectorial de dimensión utilizando las filas deV{\displaystyle V}. Ahora el análisis se reduce a agrupar vectores conk{\displaystyle k}componentes, lo cual puede hacerse de diversas maneras.

En el caso más simplek=1{\displaystyle k=1}, el vector propio único seleccionadov{\displaystyle v}, llamado vector de Fiedler , corresponde al segundo valor propio más pequeño. Usando los componentes dev,{\displaystyle v,}uno puede colocar todos los puntos cuyo componente env{\displaystyle v}es positivo en el conjuntoB+{\displaystyle B_{+}}y el resto enB−{\displaystyle B_{-}}, de esta forma se biparticiona el gráfico y se etiquetan los puntos de datos con dos etiquetas. Este enfoque basado en signos sigue la explicación intuitiva de la agrupación espectral a través del modelo masa-resorte: en el modo de vibración de baja frecuencia que el vector de Fiedlerv{\displaystyle v}Representa que, en un clúster, los puntos de datos identificados con masas fuertemente conectadas entre sí se moverían juntos en una dirección, mientras que en el clúster complementario, los puntos de datos identificados con las masas restantes se moverían juntos en la dirección opuesta. El algoritmo puede utilizarse para la agrupación jerárquica mediante la partición repetida de los subconjuntos de la misma manera.

En el caso generalk>1{\displaystyle k>1}Se puede utilizar cualquier técnica de agrupamiento vectorial, por ejemplo, DBSCAN .

Algoritmos

Algoritmo básico
  1. Calcula el laplaciano L{\displaystyle L}(o el laplaciano normalizado)
  2. Calcula el primerok{\displaystyle k}vectores propios (los vectores propios correspondientes a losk{\displaystyle k}valores propios más pequeños deL{\displaystyle L})
  3. Consideremos la matriz formada por la primera k{\displaystyle k} vectores propios; el l{\displaystyle l}La fila -th define las características del nodo del gráfico.l{\displaystyle l}
  4. Agrupe los nodos del grafo en función de estas características (por ejemplo, utilizando el algoritmo de agrupamiento k-means ).

Si la matriz de similitudA{\displaystyle A}Si aún no se ha construido explícitamente, la eficiencia del agrupamiento espectral puede mejorarse si la solución al problema de valores propios correspondiente se realiza de forma independiente de la matriz (sin manipular explícitamente ni siquiera calcular la matriz de similitud), como en el algoritmo de Lanczos .

Para grafos de gran tamaño, el segundo autovalor de la matriz laplaciana (normalizada) del grafo suele estar mal condicionado , lo que provoca una convergencia lenta de los solucionadores iterativos de autovalores. El precondicionamiento es una tecnología clave que acelera la convergencia, por ejemplo, en el método LOBPCG sin matriz . El agrupamiento espectral se ha aplicado con éxito en grafos grandes identificando primero su estructura de comunidades y luego agrupando las comunidades. [ 4 ]

La agrupación espectral está estrechamente relacionada con la reducción de dimensionalidad no lineal , y se pueden utilizar técnicas de reducción de dimensionalidad como la incrustación lineal local para reducir los errores debidos al ruido o a los valores atípicos. [ 5 ]

Costos

Denotando el número de puntos de datos pornorte{\displaystyle n}, es importante estimar el consumo de memoria y el tiempo de cómputo, o el número de operaciones aritméticas (OA) realizadas, en función denorte{\displaystyle n}. Independientemente del algoritmo de agrupamiento espectral, los dos elementos principales costosos son la construcción del laplaciano del grafo y la determinación de suk{\displaystyle k}vectores propios para la incrustación espectral. El último paso: determinar las etiquetas a partir de lanorte{\displaystyle n}-por-k{\displaystyle k}matriz de autovectores: suele ser la menos costosa, ya que solo requiereknorte{\displaystyle kn}AO y creando solo unnorte{\displaystyle n}-por-1{\displaystyle 1}vector de las etiquetas en memoria.

La necesidad de construir el laplaciano del grafo es común a todos los métodos de agrupamiento basados ​​en distancia o correlación. El cálculo de los autovectores es específico únicamente del agrupamiento espectral.

Construcción del laplaciano del grafo

El laplaciano del grafo puede construirse, y comúnmente se construye, a partir de la matriz de adyacencia. La construcción puede realizarse sin matriz, es decir, sin formar explícitamente la matriz del laplaciano del grafo y sin AO. También puede realizarse en lugar de la matriz de adyacencia sin aumentar el consumo de memoria. De cualquier manera, los costos de construir el laplaciano del grafo están esencialmente determinados por los costos de construir la matriz de adyacencia.norte{\displaystyle n}-por-norte{\displaystyle n}matriz de adyacencia de grafos.

Además, un laplaciano normalizado tiene exactamente los mismos vectores propios que la matriz de adyacencia normalizada, pero con el orden de los valores propios invertido. Por lo tanto, en lugar de calcular los vectores propios correspondientes a los valores propios más pequeños del laplaciano normalizado, se pueden calcular de forma equivalente los vectores propios correspondientes a los valores propios más grandes de la matriz de adyacencia normalizada, sin siquiera mencionar la matriz laplaciana.

Las construcciones ingenuas de la matriz de adyacencia del grafo , por ejemplo, utilizando el núcleo RBF, la hacen densa, lo que requierenorte2{\displaystyle n^{2}}memoria ynorte2{\displaystyle n^{2}}AO para determinar cada uno de losnorte2{\displaystyle n^{2}}entradas de la matriz. El método de Nystrom [ 6 ] se puede utilizar para aproximar la matriz de similitud, pero la matriz aproximada no es positiva elemento a elemento, [ 7 ] es decir, no se puede interpretar como una similitud basada en la distancia.

Los algoritmos para construir la matriz de adyacencia del grafo como una matriz dispersa se basan típicamente en una búsqueda del vecino más cercano , que estima o muestrea un vecindario de un punto de datos dado para los vecinos más cercanos, y calcula las entradas no nulas de la matriz de adyacencia comparando solo pares de los vecinos. El número de vecinos más cercanos seleccionados determina así el número de entradas no nulas, y a menudo es fijo para que la huella de memoria de lanorte{\displaystyle n}-por-norte{\displaystyle n}La matriz de adyacencia del grafo es soloO(norte){\displaystyle O(n)}, soloO(norte){\displaystyle O(n)}Se necesitan operaciones aritméticas secuenciales para calcular elO(norte){\displaystyle O(n)}Entradas distintas de cero, y los cálculos se pueden ejecutar fácilmente en paralelo.

Cálculo de vectores propios

El costo de calcular elnorte{\displaystyle n}-por-k{\displaystyle k}(conk≪norte{\displaystyle k\ll n}) matriz de autovectores seleccionados del laplaciano del grafo es normalmente proporcional al costo de la multiplicación de losnorte{\displaystyle n}-por-norte{\displaystyle n}Matriz laplaciana del grafo por un vector, que varía enormemente dependiendo de si la matriz laplaciana del grafo es densa o dispersa. Para el caso denso, el costo es, por lo tanto,O(norte2){\displaystyle O(n^{2})}El costo, citado con mucha frecuencia en la literatura,O(norte3){\displaystyle O(n^{3})}proviene de elegirk=norte{\displaystyle k=n}y es claramente engañoso, ya que, por ejemplo, en un agrupamiento espectral jerárquicok=1{\displaystyle k=1}según lo determinado por el vector de Fiedler .

En el caso escaso de lanorte{\displaystyle n}-por-norte{\displaystyle n}Matriz laplaciana del grafo conO(norte){\displaystyle O(n)}entradas no nulas, el costo del producto matriz-vector y, por lo tanto, de calcular elnorte{\displaystyle n}-por-k{\displaystyle k}conk≪norte{\displaystyle k\ll n}La matriz de autovectores seleccionados esO(norte){\displaystyle O(n)}, con el consumo de memoria también es limitadoO(norte){\displaystyle O(n)}— ambos son los límites inferiores óptimos de complejidad de la agrupaciónnorte{\displaystyle n}puntos de datos. Además, los solucionadores de valores propios sin matrices, como LOBPCG, pueden ejecutarse eficientemente en paralelo, por ejemplo, en múltiples GPU con memoria distribuida , lo que da como resultado no solo clústeres de alta calidad, por los que es famoso el agrupamiento espectral, sino también un rendimiento superior. [ 8 ]

Software

El software libre que implementa la agrupación espectral está disponible en grandes proyectos de código abierto como scikit-learn [ 9 ] usando LOBPCG [ 10 ] con precondicionamiento multigrid [ 11 ] [ 12 ] o ARPACK , MLlib para agrupación de pseudovectores propios usando el método de iteración de potencia , [ 13 ] y R . [ 14 ]

Relación con otros métodos de agrupamiento

Las ideas que subyacen al agrupamiento espectral pueden no ser inmediatamente obvias. Puede resultar útil destacar las relaciones con otros métodos. En particular, se puede describir en el contexto de los métodos de agrupamiento de núcleos, lo que revela varias similitudes con otros enfoques. [ 15 ]

Relación con k -medias

La agrupación espectral está estrechamente relacionada con el algoritmo k-means , especialmente en la forma en que se asignan los clústeres. Si bien ambos métodos difieren fundamentalmente en sus formulaciones iniciales (la agrupación espectral se basa en grafos y k-means en centroides), la conexión se hace evidente cuando se analiza la agrupación espectral desde la perspectiva de los métodos de kernel .

En particular, el algoritmo k-means con kernel ponderado proporciona un puente teórico clave entre ambos. El k-means con kernel es una generalización del algoritmo k-means estándar, donde los datos se mapean implícitamente a un espacio de características de alta dimensión mediante una función kernel, y la agrupación se realiza en ese espacio. La agrupación espectral, especialmente las versiones normalizadas, realiza una operación similar mapeando los datos de entrada (o nodos del grafo) a un espacio de menor dimensión definido por los autovectores del laplaciano del grafo . Estos autovectores corresponden a la solución de una relajación del corte normalizado u otros objetivos de partición de grafos .

Matemáticamente, se puede demostrar que la función objetivo minimizada por el agrupamiento espectral es equivalente a la función objetivo del algoritmo k-medias con núcleo ponderado en este espacio transformado. Esto se estableció formalmente en trabajos como [ 16 ] , donde demostraron que los cortes normalizados son equivalentes a una versión ponderada del algoritmo k-medias con núcleo aplicada a las filas de la matriz de autovectores del laplaciano normalizado.

Debido a esta equivalencia, el agrupamiento espectral puede considerarse como la aplicación del algoritmo k-means de kernel en el espacio propio definido por el laplaciano del grafo . Esta perspectiva teórica tiene implicaciones prácticas: el paso final del agrupamiento espectral generalmente implica ejecutar el algoritmo k-means estándar sobre las filas de la matriz formada por los primeros k vectores propios del laplaciano. Estas filas pueden interpretarse como la incrustación de cada punto de datos o nodo en un espacio de baja dimensión donde los clústeres están mejor separados y, por lo tanto, son más fáciles de detectar para k-means.

Además, se han desarrollado métodos multinivel para optimizar directamente esta función objetivo compartida. Estos métodos funcionan reduciendo iterativamente el tamaño del grafo para disminuir el tamaño del problema, resolviéndolo en un grafo inicial y luego refinando la solución en grafos sucesivamente más finos. Esto conduce a una optimización más eficiente para problemas a gran escala, al tiempo que se conserva la estructura global preservada por la incrustación espectral. [ 17 ]

Relación con DBSCAN

La agrupación espectral también está conceptualmente relacionada con DBSCAN (agrupación espacial basada en densidad de aplicaciones con ruido), particularmente en el caso especial donde el método espectral se utiliza para identificar componentes de grafos conectados. En este caso trivial, donde el objetivo es identificar subconjuntos de nodos sin aristas que los interconecten, el método espectral se reduce efectivamente a un enfoque de agrupación basado en conectividad, muy similar a DBSCAN. [ 18 ]

DBSCAN funciona identificando regiones conectadas por densidad en el espacio de entrada: puntos que son alcanzables entre sí a través de una secuencia de puntos vecinos dentro de un radio especificado (ε), y que contienen un número mínimo de puntos (minPts). El algoritmo destaca por descubrir agrupaciones de forma arbitraria y por separar el ruido sin necesidad de especificar el número de agrupaciones de antemano.

En el agrupamiento espectral, cuando el grafo de similitud se construye utilizando un criterio de conectividad estricto (es decir, adyacencia binaria basada en si dos nodos se encuentran dentro de una distancia umbral), y no se aplica normalización al laplaciano, la estructura propia resultante del laplaciano del grafo revela directamente los componentes desconectados del mismo. Esto refleja la capacidad de DBSCAN para aislar componentes conectados por densidad . Los autovectores de orden cero del laplaciano sin normalizar corresponden a estos componentes, con un autovector por región conectada.

Esta conexión se hace más evidente cuando el agrupamiento espectral se utiliza no para optimizar una partición suave (como minimizar el corte normalizado), sino para identificar componentes conexas exactas , lo que corresponde a la forma más extrema de agrupamiento basado en la densidad, donde solo se agrupan los nodos conectados directa o transitivamente. Por lo tanto, en este caso, el agrupamiento espectral se comporta como una versión espectral de DBSCAN , especialmente en grafos dispersos o al construir grafos de vecindad ε.

Mientras que DBSCAN opera directamente en el espacio de datos mediante estimaciones de densidad, el agrupamiento espectral transforma los datos en un espacio propio donde se enfatizan la estructura global y la conectividad . Ambos métodos son de naturaleza no paramétrica y ninguno presupone formas de clúster convexas, lo que refuerza aún más su coherencia conceptual.

Medidas para comparar agrupaciones

Ravi Kannan, Santosh Vempala y Adrian Vetta [ 19 ] propusieron una medida bicriterio para definir la calidad de una agrupación dada. Indicaron que una agrupación era (α, ε) si la conductancia de cada clúster (en la agrupación) era al menos α y el peso de las aristas entre clústeres era como máximo ε fracción del peso total de todas las aristas en el grafo. En el mismo artículo, también analizan dos algoritmos de aproximación.

El agrupamiento espectral tiene una larga historia. [ 20 ] [ 21 ] [ 22 ] [ 23 ] [ 24 ] [ 2 ] [ 25 ] El agrupamiento espectral como método de aprendizaje automático fue popularizado por Shi y Malik [ 2 ] y Ng, Jordan y Weiss. [ 25 ]

Las ideas y las medidas de red relacionadas con la agrupación espectral también desempeñan un papel importante en varias aplicaciones aparentemente distintas de los problemas de agrupación. Por ejemplo, las redes con particiones espectrales más fuertes tardan más en converger en los modelos de actualización de opiniones utilizados en sociología y economía. [ 26 ] [ 27 ]

Véase también

Referencias

  1. ↑ Demmel, J. "CS267: Apuntes para la clase 23, 9 de abril de 1999, Particionamiento de grafos, Parte 2" .
  2. 1 2 3 Jianbo Shi y Jitendra Malik, "Cortes normalizados y segmentación de imágenes" , IEEE Transactions on PAMI, vol. 22, n.º 8, agosto de 2000.
  3. ↑ Marina Meilă y Jianbo Shi, " Aprendizaje de segmentación mediante paseos aleatorios ", Neural Information Processing Systems 13 (NIPS 2000), 2001, pp. 873–879.
  4. ↑ Zare, Habil; Shooshtari, P.; Gupta, A.; Brinkman, R. (2010). "Reducción de datos para agrupamiento espectral para analizar datos de citometría de flujo de alto rendimiento" . BMC Bioinformatics . 11 403. doi : 10.1186/1471-2105-11-403 . PMC 2923634. PMID 20667133 .  
  5. ↑ Arias-Castro, E.; Chen, G.; Lerman, G. (2011), "Agrupamiento espectral basado en aproximaciones lineales locales.", Electronic Journal of Statistics , 5 : 1537–87 , arXiv : 1001.1323 , doi : 10.1214/11-ejs651 , S2CID 88518155 
  6. ↑ Fowlkes, C (2004). "Agrupación espectral mediante el método de Nystrom" . IEEE Transactions on Pattern Analysis and Machine Intelligence . 26 (2): 214– 25. Bibcode : 2004ITPAM..26..214F . doi : 10.1109/TPAMI.2004.1262185 . PMID 15376896. S2CID 2384316 .  
  7. ↑ Wang, S.; Gittens, A.; Mahoney, MW (2019). "Agrupamiento K-Means de núcleo escalable con aproximación de Nystrom: límites de error relativo". Journal of Machine Learning Research . 20 : 1–49 . arXiv : 1706.02803 .
  8. ^ Acer, Seher; Boman, Erik G.; Glusa, Christian A.; Rajamanickam, Sivasankaran (2021). "Sphynx: un particionador de gráficos paralelo de múltiples GPU para sistemas de memoria distribuida". Computación Paralela . 106 102769. arXiv : 2105.00578 . doi : 10.1016/j.parco.2021.102769 . S2CID 233481603 . 
  9. ↑ "2.3. Agrupación" .
  10. ↑ Knyazev, Andrew V. (2003). Boley; Dhillon; Ghosh; Kogan (eds.). Solucionadores de valores propios precondicionados modernos para la segmentación de imágenes espectrales y la bisección de grafos . Agrupación de grandes conjuntos de datos; Tercera Conferencia Internacional IEEE sobre Minería de Datos (ICDM 2003) Melbourne, Florida: IEEE Computer Society. págs. 59–62 . 
  11. ↑ Knyazev, Andrew V. (2006). Segmentación de imágenes espectrales multiescala. Preacondicionamiento multiescala para el cálculo de valores propios de laplacianos de grafos en la segmentación de imágenes . Taller de aprendizaje rápido de variedades, WM Williamburg, VA. doi : 10.13140/RG.2.2.35280.02565 .
  12. ↑ Knyazev, Andrew V. (2006). Particionamiento de grafos espectrales multiescala y segmentación de imágenes . Taller sobre algoritmos para conjuntos de datos masivos modernos, Universidad de Stanford y Yahoo! Research.
  13. ↑ "Agrupación - API basada en RDD - Documentación de Spark 3.2.0" .
  14. ↑ "Kernlab: Laboratorio de aprendizaje automático basado en kernels" . 12 de noviembre de 2019.
  15. ↑ Filippone, M.; Camastra, F.; Masulli, F.; Rovetta, S. (enero de 2008). "Una revisión de los métodos kernel y espectrales para la agrupación" (PDF) . Pattern Recognition . 41 (1): 176– 190. Bibcode : 2008PatRe..41..176F . doi : 10.1016/j.patcog.2007.05.018 .
  16. ↑ Dhillon, IS; Guan, Y.; Kulis, B. (2004). "Kernel k -means: agrupamiento espectral y cortes normalizados" (PDF) . Actas de la décima conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos . págs. 551–6 . 
  17. ↑ Dhillon, Inderjit; Guan, Yuqiang; Kulis, Brian (noviembre de 2007). "Cortes de grafos ponderados sin autovectores: un enfoque multinivel". IEEE Transactions on Pattern Analysis and Machine Intelligence . 29 (11): 1944– 1957. Bibcode : 2007ITPAM..29.1944D . CiteSeerX 10.1.1.131.2635 . doi : 10.1109 / tpami.2007.1115 . PMID 17848776. S2CID 9402790 .   
  18. ↑ Schubert, Erich; Hess, Sibylle; Morik, Katharina (2018). La relación de DBSCAN con la factorización matricial y la agrupación espectral (PDF) . LWDA. págs. 330–334 . 
  19. ↑ Kannan, Ravi; Vempala, Santosh; Vetta, Adrian (2004). "Sobre los agrupamientos : buenos, malos y espectrales". Journal of the ACM . 51 (3): 497– 515. doi : 10.1145/990308.990313 . S2CID 207558562 .  
  20. ↑ Cheeger, Jeff (1969). "Una cota inferior para el autovalor más pequeño del laplaciano". Actas de la Conferencia de Princeton en honor del profesor S. Bochner .
  21. ↑ Donath, William; Hoffman, Alan (1972). "Algoritmos para la partición de grafos y lógica computacional basados ​​en autovectores de matrices de conexiones". Boletín de divulgación técnica de IBM .
  22. ↑ Fiedler, Miroslav (1973). "Conectividad algebraica de grafos" . Czechoslovak Mathematical Journal . 23 (2): 298– 305. Bibcode : 1973CzMJ...23..298F . doi : 10.21136/CMJ.1973.101168 .
  23. ↑ Guattery, Stephen; Miller, Gary L. (1995). "Sobre el rendimiento de los métodos de partición de grafos espectrales". Simposio anual ACM-SIAM sobre algoritmos discretos .
  24. ↑ Daniel A. Spielman y Shang-Hua Teng (1996). "El particionamiento espectral funciona: grafos planares y mallas de elementos finitos". Simposio anual del IEEE sobre fundamentos de la informática .
  25. 1 2 Ng, Andrew Y.; Jordan, Michael I.; Weiss, Yair (2002). "Sobre la agrupación espectral: análisis y un algoritmo" (PDF) . Avances en sistemas de procesamiento de información neuronal .
  26. ↑ DeMarzo, PM; Vayanos, D.; Zwiebel, J. (2003-08-01). "Persuasion Bias, Social Influence, and Unidimensional Opinions" . The Quarterly Journal of Economics . 118 (3). Oxford University Press: 909– 968. doi : 10.1162/00335530360698469 . ISSN 0033-5533 . 
  27. ↑ Golub, Benjamin; Jackson, Matthew O. (26 de julio de 2012). "Cómo la homofilia afecta la velocidad de aprendizaje y la dinámica de mejor respuesta". The Quarterly Journal of Economics . 127 (3). Oxford University Press (OUP): 1287– 1338. doi : 10.1093/qje/qjs021 . ISSN 0033-5533 .