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 la reducción de 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 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, dónde representa una medida de la similitud entre puntos de datos con índices y . El enfoque general para la agrupación espectral es utilizar un método de agrupación estándar (existen muchos de estos métodos, k -medias se discuten 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, por lo que la agrupación también tendrá diferentes interpretaciones. Los autovectores que son relevantes son los que corresponden a varios autovalores más pequeños del Laplaciano, excepto por el autovalor más pequeño que tendrá un valor de 0. Para la eficiencia computacional, estos autovectores a menudo se calculan como los autovectores correspondientes a los autovalores más grandes de un función del laplaciano.
Es bien sabido que la agrupación espectral se relaciona con la división de un sistema masa-resorte, donde cada masa está asociada con un punto de datos y cada rigidez de resorte corresponde al peso de un borde que describe una similitud de los dos puntos de datos relacionados. 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 masa-resorte es exactamente el mismo que el problema de valor propio para la gráfica matriz laplaciana definida como
- ,
dónde es la matriz diagonal
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 los modos de vibración de baja frecuencia, de modo que los componentes de los autovectores correspondientes a los autovalores más pequeños del gráfico Laplaciano pueden usarse para fines significativos. agrupamiento de las masas.
Una técnica de agrupación espectral relacionada popular es el algoritmo de cortes normalizados o el algoritmo Shi-Malik introducido por Jianbo Shi y Jitendra Malik, [2] comúnmente utilizado para la segmentación de imágenes . Divide puntos en dos conjuntosbasado en el vector propio correspondiente al segundo valor propio más pequeño del laplaciano simétrico normalizado definido como
Un algoritmo matemáticamente equivalente [3] toma el vector propio correspondiente al valor propio más grande de la matriz de adyacencia normalizada de recorrido aleatorio.
Conociendo los vectores propios, la partición se puede realizar de varias formas, como calculando la mediana de los componentes del segundo vector propio más pequeño , y colocando todos los puntos cuyo componente en es mayor que en , y el resto en . El algoritmo se puede utilizar para la agrupación jerárquica dividiendo repetidamente los subconjuntos de esta manera.
Algoritmos
- Algoritmo básico
- Calcule el Laplaciano (o el laplaciano normalizado)
- Calcule el primero autovectores (los autovectores correspondientes a la valores propios más pequeños de )
- Considere la matriz formada por la primera vectores propios; la-th fila define las características del nodo gráfico
- Agrupe los nodos del gráfico en función de estas características (p. Ej., Utilizando agrupación de k-means )
Si la matriz de similitud aún no se ha construido explícitamente, la eficiencia de la agrupación espectral puede mejorarse si la solución al problema de valor propio correspondiente se realiza de manera libre de matrices (sin manipular explícitamente o incluso calcular la matriz de similitud), como en el algoritmo de Lanczos .
Para gráficos de gran tamaño, el segundo valor propio de la matriz laplaciana del gráfico (normalizado) suele estar mal condicionado , lo que lleva a una convergencia lenta de los solucionadores de valores propios iterativos. 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 la estructura de su 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 local-lineal para reducir errores de ruido o valores atípicos. [5]
Software libre para implementar la agrupación espectral está disponible en grandes proyectos de código abierto como scikit-learn [6] utilizando LOBPCG [7] con multigrid acondicionamiento previo , [8] o ARPACK , MLlib para pseudo-vector propio agrupamiento utilizando el método de las potencias método, [9] y R . [10]
Relación con otros métodos de agrupación
Las ideas detrás de la agrupación 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 agrupación en clústeres del núcleo, lo que revela varias similitudes con otros enfoques. [11]
Relación con k -medios
El problema de k- medias del kernel es una extensión del problema de k- medias donde los puntos de datos de entrada se mapean de forma no lineal en un espacio de características de mayor dimensión a través de una función de kernel. El problema de las k medias del kernel ponderado amplía aún más este problema al definir un peso para cada grupo como el recíproco del número de elementos en el grupo,
Suponer es una matriz de los coeficientes de normalización para cada punto de cada conglomerado Si y cero en caso contrario. Suponeres la matriz del núcleo para todos los puntos. El kernel ponderado k significa un problema con n puntos y k conglomerados se da como,
tal que
tal que . Además, existen restricciones de identidad en dada por,
dónde representa un vector de unos.
Este problema se puede reformular como,
Este problema es equivalente al problema de la agrupación espectral cuando las restricciones de identidad en están relajados. En particular, el problema de k- medias ponderadas del kernel se puede reformular como un problema de agrupamiento espectral (partición de gráficos) y viceversa. La salida de los algoritmos son vectores propios que no satisfacen los requisitos de identidad para las variables indicadoras definidas por. Por lo tanto, se requiere un posprocesamiento de los autovectores para la equivalencia entre los problemas. [12] Transformar el problema de agrupamiento espectral en un problema de k- medias ponderadas del kernel reduce en gran medida la carga computacional. [13]
Relación con DBSCAN
La agrupación en clústeres espectral también está relacionada con la agrupación en clústeres DBSCAN , que encuentra componentes conectados por densidad. Los componentes conectados corresponden a grupos espectrales óptimos (sin cortes de bordes); y DBSCAN usa un gráfico vecino asimétrico con bordes eliminados cuando los puntos de origen no son densos. [14] Por lo tanto, DBSCAN es un caso especial de agrupamiento espectral, pero que permite algoritmos más eficientes (el peor de los casos, en muchos casos prácticos mucho más rápido con índices).
Medidas para comparar agrupaciones
Ravi Kannan, Santosh Vempala y Adrian Vetta [15] propusieron una medida de bicriterio para definir la calidad de una agrupación determinada. 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 ε fracción del peso total de todos los bordes en el gráfico. También miran dos algoritmos de aproximación en el mismo artículo.
Soluciones aproximadas
La agrupación espectral es computacionalmente costosa a menos que el gráfico sea escaso y la matriz de similitud se pueda construir de manera eficiente. Si la matriz de similitud es una matriz de núcleo RBF, la agrupación espectral es costosa. Hay algoritmos aproximados para hacer que la agrupación espectral sea más eficiente: método de potencia, [16] método Nystrom, [17] etc. Sin embargo, investigaciones recientes [18] señalaron los problemas con la agrupación espectral con el método Nystrom; en particular, la matriz de similitud con la aproximación de Nystrom no es elementalmente positiva, lo que puede ser problemático.
La agrupación espectral tiene una larga historia. [19] [20] [21] [22] [23] [2] [24] La agrupación espectral como método de aprendizaje automático fue popularizada por Shi & Malik [2] y Ng, Jordan y Weiss. [24]
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 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 opinión utilizados en sociología y economía. [25] [26]
Ver también
- Propagación de afinidad
- Análisis de componentes principales del kernel
- Análisis de conglomerados
- Teoría de grafos espectrales
Referencias
- ^ J. Demmel, [1] , CS267: Notas para la Conferencia 23, 9 de abril de 1999, Partición de gráficos, Parte 2
- ^ a b c Jianbo Shi y Jitendra Malik, "Cortes normalizados y segmentación de imágenes" , Transacciones IEEE en PAMI, vol. 22, No. 8, agosto de 2000.
- ^ Marina Meilă & Jianbo Shi, " Segmentación de aprendizaje por paseos aleatorios ", Sistemas de procesamiento de información neuronal 13 (NIPS 2000), 2001, págs. 873–879.
- ^ Zare, Habil; P. Shooshtari; A. Gupta; R. Brinkman (2010). "Reducción de datos para la agrupación espectral para analizar datos de citometría de flujo de alto rendimiento" . BMC Bioinformática . 11 : 403. doi : 10.1186 / 1471-2105-11-403 . PMC 2923634 . PMID 20667133 .
- ^ Arias-Castro, E. y Chen, G. y Lerman, G. (2011), "Agrupación espectral basada en aproximaciones lineales locales", Electronic Journal of Statistics , 5 : 1537-1587, arXiv : 1001.1323 , doi : 10.1214 / 11-ejs651 , S2CID 88518155CS1 maint: varios nombres: lista de autores ( enlace )
- ^ http://scikit-learn.org/stable/modules/clustering.html#spectral-clustering
- ^ Knyazev, Andrew V. (2003). Eigensolvers modernos preacondicionados para la segmentación de imágenes espectrales y la bisección de gráficos . Taller sobre agrupación de grandes conjuntos de datos Tercera Conferencia Internacional IEEE sobre Minería de Datos (ICDM 2003).
- ^ Knyazev, Andrew V. (2006). Partición y segmentación de imágenes de gráficos espectrales multiescala . Taller sobre algoritmos para conjuntos de datos masivos modernos Stanford University y Yahoo! Investigación .
- ^ http://spark.apache.org/docs/latest/mllib-clustering.html#power-iteration-clustering-pic
- ^ https://cran.r-project.org/web/packages/kernlab
- ^ Filippone M., Camastra F., Masulli, F., Rovetta, S. (enero de 2008). "Una encuesta de kernel y métodos espectrales para la agrupación". Reconocimiento de patrones . 41 (1): 176-190. doi : 10.1016 / j.patcog.2007.05.018 .CS1 maint: varios nombres: lista de autores ( enlace ) CS1 maint: fecha y año ( enlace )
- ^ Dhillon, IS y Guan, Y. y Kulis, B. (2004). "Kernel k -medios: agrupamiento espectral y cortes normalizados". Actas de la décima conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos . págs. 551–556.CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Dhillon, Inderjit; Yuqiang Guan; Brian Kulis (noviembre de 2007). "Cortes de gráficos ponderados sin vectores propios: un enfoque multinivel". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 29 (11): 1944-1957. CiteSeerX 10.1.1.131.2635 . doi : 10.1109 / tpami.2007.1115 . PMID 17848776 . S2CID 9402790 .
- ^ 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.
- ^ Kannan, Ravi; Vempala, Santosh; Vetta, Adrian (2004). "Sobre agrupaciones: bueno, malo y espectral". Revista de la ACM . 51 (3): 497–515. doi : 10.1145 / 990308.990313 . S2CID 207558562 .
- ^ Boutsidis, Christos (2015). "Agrupación espectral a través del método de energía demostrablemente" (PDF) . Congreso Internacional de Machine Learning .
- ^ Fowlkes, C (2004). "Agrupación espectral mediante el método Nystrom" . Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 26 (2): 214-25. doi : 10.1109 / TPAMI.2004.1262185 . PMID 15376896 . S2CID 2384316 .
- ^ S. Wang, A. Gittens y MW Mahoney (2019). "Agrupación de K-Means de kernel escalable con aproximación de Nystrom: límites de error relativo". Revista de investigación sobre aprendizaje automático . 20 : 1-49. arXiv : 1706.02803 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Cheeger, Jeff (1969). "Un límite inferior para el valor propio más pequeño del Laplacian". Actas de la Conferencia de Princeton en honor al profesor S. Bochner .
- ^ William Donath y Alan Hoffman (1972). "Algoritmos de partición de gráficos y lógica informática basados en vectores propios de matrices de conexiones". Boletín de divulgación técnica de IBM .
- ^ Fiedler, Miroslav (1973). "Conectividad algebraica de gráficos" . Revista matemática checoslovaca . 23 (2): 298-305. doi : 10.21136 / CMJ.1973.101168 .
- ^ Stephen Guattery y Gary L. Miller (1995). "Sobre el rendimiento de los métodos de partición de gráficos espectrales". Simposio anual ACM-SIAM sobre algoritmos discretos .
- ^ Daniel A. Spielman y Shang-Hua Teng (1996). "Obras de particionamiento espectral: gráficos planos y mallas de elementos finitos". Simposio anual de IEEE sobre fundamentos de la informática .
- ^ a b Ng, Andrew Y y Jordan, Michael I y Weiss, Yair (2002). "Sobre agrupamiento espectral: análisis y un algoritmo" (PDF) . Avances en sistemas de procesamiento de información neuronal .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ 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 . Prensa de la Universidad de Oxford (OUP). 118 (3): 909–968. doi : 10.1162 / 00335530360698469 . ISSN 0033-5533 .
- ^ Golub, Benjamín; 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 . Prensa de la Universidad de Oxford (OUP). 127 (3): 1287-1338. doi : 10.1093 / qje / qjs021 . ISSN 0033-5533 .