Agrupamiento espectral

Métodos de agrupamiento

Un ejemplo de gráfico conexo, con 6 vértices.

Partición en dos gráficos conectados

En las estadísticas multivariadas , las técnicas de agrupamiento espectral hacen uso del espectro ( valores propios ) de la matriz de similitud de los datos para realizar una reducción de la dimensionalidad antes de agruparlos en menos 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 la aplicación a la segmentación de imágenes, la agrupación espectral se conoce como categorización de objetos basada en segmentación .

Definiciones

Dado un conjunto enumerado de puntos de datos, la matriz de similitud puede definirse como una matriz simétrica , donde representa una medida de la similitud entre puntos de datos con índices y . El enfoque general para el agrupamiento espectral es utilizar un método de agrupamiento estándar (hay muchos métodos de este tipo, k -medias se analiza a continuación) en vectores propios relevantes de una matriz laplaciana de . Hay muchas formas diferentes de definir un laplaciano que tienen diferentes interpretaciones matemáticas, y por lo tanto el agrupamiento también tendrá diferentes interpretaciones. Los vectores propios que son relevantes son los que corresponden a varios valores propios más pequeños del laplaciano, excepto el valor propio más pequeño que tendrá un valor de 0. Para la eficiencia computacional, estos vectores propios a menudo se calculan como los vectores propios correspondientes a los varios valores propios más grandes de una función del laplaciano. ${\displaystyle A}$ ${\displaystyle A_{ij}\geq 0}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle A}$

Matriz laplaciana

Un sistema de resorte bidimensional.

Se sabe bien que la agrupación espectral está relacionada con la partición de un sistema de masa-resorte, donde cada masa está asociada con un punto de datos y cada rigidez de resorte corresponde a un peso de un borde que describe una similitud de los dos puntos de datos relacionados, como en el sistema de resorte . Específicamente, la referencia clásica ^[1] explica que el problema de valor propio que describe los modos de vibración transversal de un sistema de masa-resorte es exactamente el mismo que el problema de valor propio para la matriz laplaciana gráfica definida como

${\displaystyle L:=D-A}$,

¿Dónde está la matriz diagonal? ${\displaystyle D}$

${\displaystyle D_{ii}=\sum _{j}A_{ij},}$

y A es la matriz de adyacencia .

Las masas que están estrechamente 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 vectores propios correspondientes a los valores propios más pequeños del gráfico laplaciano se pueden utilizar para agrupar significativamente las masas. Por ejemplo, suponiendo que todos los resortes y las masas son idénticos en el sistema de resortes bidimensional representado, uno esperaría intuitivamente que las masas conectadas más flojas en el lado derecho del sistema se moverían con la mayor amplitud y en la dirección opuesta al resto de las masas cuando el sistema se sacude, y esta expectativa se confirmará analizando los componentes de los vectores propios del gráfico laplaciano correspondientes a los valores propios 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 hacer que las entradas diagonales de la matriz laplaciana sean todas unitarias, y también escalar las entradas fuera de la diagonal en consecuencia. En un gráfico ponderado, un vértice puede tener un grado alto debido a una pequeña cantidad de aristas conectadas pero con pesos grandes, así como también debido a una gran cantidad de aristas conectadas con pesos unitarios.

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

${\displaystyle L^{\text{norm}}:=I-D^{-1/2}AD^{-1/2}.}$

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

El laplaciano normalizado de paseo aleatorio (o por la izquierda) se define como

${\displaystyle L^{\text{rw}}:=D^{-1}L=I-D^{-1}A}$

y también se puede utilizar para agrupamiento espectral. Un algoritmo matemáticamente equivalente ^[3] toma el vector propio correspondiente al valor propio más grande de la matriz de adyacencia normalizada de caminata aleatoria . ${\displaystyle u}$ ${\displaystyle P=D^{-1}A}$

El vector propio del laplaciano normalizado simétricamente y el vector propio del laplaciano normalizado por la izquierda están relacionados por la identidad ${\displaystyle v}$ ${\displaystyle u}$ ${\displaystyle D^{-1/2}v=u.}$

Análisis de conglomeradosa través de incrustación espectral

Conociendo la matriz de vectores propios seleccionados, se realiza un mapeo —denominado incrustación espectral— de los puntos de datos originales a un espacio vectorial dimensional utilizando las filas de . Ahora el análisis se reduce a agrupar vectores con componentes, lo que se puede hacer de varias maneras. ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle V}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle V}$ ${\displaystyle k}$

En el caso más simple , el vector propio único seleccionado , llamado vector de Fiedler , corresponde al segundo valor propio más pequeño. Usando los componentes de uno se pueden colocar todos los puntos cuyo componente en es positivo en el conjunto y el resto en , de esta manera 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 de masa-resorte: en el modo de vibración de baja frecuencia que representa el vector de Fiedler , un grupo de puntos de datos identificados con masas fuertemente conectadas entre sí se moverían juntos en una dirección, mientras que en el grupo complementario los puntos de datos identificados con las masas restantes se moverían juntos en la dirección opuesta. El algoritmo se puede usar para la agrupación jerárquica al particionar repetidamente los subconjuntos de la misma manera. ${\displaystyle k=1}$ ${\displaystyle v}$ ${\displaystyle v,}$ ${\displaystyle v}$ ${\displaystyle B_{+}}$ ${\displaystyle B_{-}}$ ${\displaystyle v}$

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

Algoritmos

Algoritmo básico

1. Calcular el Laplaciano (o el Laplaciano normalizado) ${\displaystyle L}$
2. Calcular los primeros vectores propios (los vectores propios correspondientes a los valores propios más pequeños de ) ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle L}$
3. Considere la matriz formada por los primeros vectores propios; la fila -ésima define las características del nodo del gráfico ${\displaystyle k}$ ${\displaystyle l}$ ${\displaystyle l}$
4. Agrupe los nodos del gráfico en función de estas características (por ejemplo, utilizando la agrupación k-means )

Si la matriz de similitud aún no se ha construido explícitamente, la eficiencia del agrupamiento espectral se puede mejorar si la solución al problema de valor propio correspondiente se realiza de manera libre de matriz (sin manipular explícitamente o incluso calcular la matriz de similitud), como en el algoritmo de Lanczos . ${\displaystyle A}$

En el caso de gráficos de gran tamaño, el segundo valor propio de la matriz laplaciana del gráfico (normalizada) suele estar mal condicionado , lo que conduce a una convergencia lenta de los solucionadores iterativos de valores propios. El preacondicionamiento es una tecnología clave que acelera la convergencia, por ejemplo, en el método LOBPCG sin matriz . La agrupación espectral se ha aplicado con éxito en gráficos grandes identificando primero su estructura de comunidad 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 dimensión como la incrustación localmente lineal para reducir errores causados ​​por ruido o valores atípicos. ^[5]

Costos

Al denotar el número de puntos de datos por , es importante estimar la huella de memoria y el tiempo de cálculo, o el número de operaciones aritméticas (OA) realizadas, como una función de . Sin importar el algoritmo de agrupamiento espectral, los dos elementos principales costosos son la construcción del laplaciano gráfico y la determinación de sus vectores propios para la incrustación espectral. El último paso (determinar las etiquetas a partir de la matriz -por- de vectores propios) es típicamente el menos costoso, ya que solo requiere OA y la creación de solo un vector -por- de las etiquetas en la memoria. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle kn}$ ${\displaystyle n}$ ${\displaystyle 1}$

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

Construyendo un gráfico laplaciano

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

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 manera equivalente los vectores propios correspondientes a los valores propios más grandes de la matriz de adyacencia normalizada, sin siquiera hablar de la matriz laplaciana.

Las construcciones ingenuas de la matriz de adyacencia de grafos , por ejemplo, utilizando el núcleo RBF, la hacen densa, por lo que requieren memoria y AO para determinar cada una de las 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 por elemento, ^[7] es decir, no se puede interpretar como una similitud basada en la distancia. ${\displaystyle n^{2}}$ ${\displaystyle n^{2}}$ ${\displaystyle n^{2}}$

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

Cálculo de vectores propios

El costo de calcular la matriz -por- (con ) de vectores propios seleccionados del laplaciano del grafo es normalmente proporcional al costo de multiplicación de la matriz laplaciana del grafo -por- por un vector, que varía en gran medida si la matriz laplaciana del grafo es densa o dispersa. Para el caso denso, el costo es . El costo muy comúnmente citado en la literatura proviene de la elección y es claramente engañoso, ya que, por ejemplo, en un agrupamiento espectral jerárquico determinado por el vector de Fiedler . ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k\ll n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{3})}$ ${\displaystyle k=n}$ ${\displaystyle k=1}$

En el caso escaso de la matriz laplaciana del grafo -por- con entradas distintas de cero, el costo del producto matriz-vector y, por lo tanto, de calcular la matriz -por- con de vectores propios seleccionados es , con el consumo de memoria también solo — ambos son los límites bajos óptimos de complejidad de la agrupación de puntos de datos. Además, los solucionadores de valores propios sin matriz como LOBPCG pueden ejecutarse eficientemente en paralelo, por ejemplo, en múltiples GPU con memoria distribuida, lo que da como resultado no solo agrupaciones de alta calidad, por las que la agrupación espectral es famosa, sino también un rendimiento superior. ^[8] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle O(n)}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k\ll n}$ ${\displaystyle O(n)}$ ${\displaystyle O(n)}$ ${\displaystyle n}$

Software

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

Relación con otros métodos de clusterización

Las ideas detrás del agrupamiento espectral pueden no ser obvias de inmediato. Puede ser útil destacar las relaciones con otros métodos. En particular, se puede describir en el contexto de los métodos de agrupamiento kernel, que revelan varias similitudes con otros enfoques. ^[15]

Relación cona-medio

El problema de k -medias del núcleo ponderado ^[16] comparte la función objetivo con el problema de agrupamiento espectral, que se puede optimizar directamente mediante métodos multinivel. ^[17]

Relación con DBSCAN

En el caso trivial de determinar componentes de gráficos conectados (los grupos óptimos sin bordes cortados), la agrupación espectral también está relacionada con una versión espectral de la agrupación DBSCAN que encuentra componentes conectados por densidad. ^[18]

Medidas para comparar agrupamientos

Ravi Kannan, Santosh Vempala y Adrian Vetta ^[19] propusieron una medida bicriterio para definir la calidad de un agrupamiento determinado. Dijeron que un agrupamiento era un agrupamiento (α, ε) si la conductancia de cada grupo (en el agrupamiento) era al menos α y el peso de los bordes entre grupos era como máximo una fracción ε del peso total de todos los bordes en el gráfico. También analizaron dos algoritmos de aproximación en el mismo artículo.

Historia y literaturas afines

La agrupación espectral tiene una larga historia. ^{[20] [21] [22] [23] [24] [2] [25]} La agrupación espectral como método de aprendizaje automático fue popularizada 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 una serie de aplicaciones aparentemente diferentes 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 que se utilizan en sociología y economía. ^{[26] [27]}

Véase también

• Propagación por afinidad
• Análisis de componentes principales del núcleo
• Análisis de conglomerados
• Teoría de grafos espectrales

Referencias

1. Demmel, J. "CS267: Notas para la clase 23, 9 de abril de 1999, Particionado de gráficos, parte 2".
2. 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 la segmentación mediante paseos aleatorios", Neural Information Processing Systems 13 (NIPS 2000), 2001, págs. 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). "Agrupamiento espectral utilizando el método Nystrom". IEEE Transactions on Pattern Analysis and Machine Intelligence . 26 (2): 214–25. doi :10.1109/TPAMI.2004.1262185. PMID  15376896. S2CID  2384316.
7. Wang, S.; Gittens, A.; Mahoney, MW (2019). "Agrupamiento escalable de K-medias de kernel con aproximación de Nystrom: límites de error relativo". Revista de investigación en aprendizaje automático . 20 : 1–49. arXiv : 1706.02803 .
8. Acer, Seher; Boman, Erik G.; Glusa, Christian A.; Rajamanickam, Sivasankaran (2021). "Sphynx: un particionador de gráficos multi-GPU paralelo 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. Agrupamiento".
10. Knyazev, Andrew V. (2003). Boley; Dhillon; Ghosh; Kogan (eds.). Solucionadores propios preacondicionados modernos para segmentación de imágenes espectrales y bisección de grafos. Agrupamiento 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 en múltiples escalas Preacondicionamiento multiescala para calcular 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). Partición de gráficos espectrales multiescala y segmentación de imágenes. Taller sobre algoritmos para conjuntos de datos masivos modernos, Universidad de Stanford y Yahoo! Research.
13. "Agrupamiento - API basada en RDD - Documentación de Spark 3.2.0".
14. "Kernlab: laboratorio de aprendizaje automático basado en kernel". 12 de noviembre de 2019.
15. Filippone, M.; Camastra, F.; Masulli, F.; Rovetta, S. (enero de 2008). "Un estudio de los métodos kernel y espectrales para la agrupación" (PDF) . Reconocimiento de patrones . 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 vectores propios: un enfoque multinivel". IEEE Transactions on Pattern Analysis and Machine Intelligence . 29 (11): 1944–1957. 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 el agrupamiento espectral (PDF) . LWDA. págs. 330–334.
19. Kannan, Ravi; Vempala, Santosh; Vetta, Adrian (2004). "Sobre agrupamientos: buenos, malos y espectrales". Revista de la ACM . 51 (3): 497–515. doi :10.1145/990308.990313. S2CID  207558562.
20. Cheeger, Jeff (1969). "Un límite inferior para el valor propio 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 de computadoras basados ​​en vectores propios de matrices de conexiones". Boletín de divulgación técnica de IBM .
22. Fiedler, Miroslav (1973). "Conectividad algebraica de grafos". Revista matemática checoslovaca . 23 (2): 298–305. doi : 10.21136/CMJ.1973.101168 .
23. Guattery, Stephen; Miller, Gary L. (1995). "Sobre el rendimiento de los métodos de partición de gráficos espectrales". Simposio anual ACM-SIAM sobre algoritmos discretos .
24. Daniel A. Spielman y Shang-Hua Teng (1996). "Trabajos de particionamiento espectral: gráficos planares y mallas de elementos finitos". Simposio anual IEEE sobre fundamentos de la informática .
25. Ng, Andrew Y.; Jordan, Michael I.; Weiss, Yair (2002). "Sobre el agrupamiento espectral: análisis y un algoritmo" (PDF) . Avances en sistemas de procesamiento de información neuronal .
26. DeMarzo, PM; Vayanos, D.; Zwiebel, J. (1 de agosto de 2003). "Sesgo de persuasión, influencia social y opiniones unidimensionales". 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 afecta la homofilia a la velocidad de aprendizaje y a 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.