Agrupamiento espectral

Las técnicas de agrupación espectral utilizan el espectro ( valores propios ) de la matriz de similitud de los datos para realizar la reducción de la dimensionalidad antes de la agrupación en espacios de menor dimensión. La matriz de similitud se proporciona como entrada y consiste en estimaciones cuantitativas de la similitud relativa de cada par de puntos en los datos.

Cuando se aplica a la segmentación de imágenes, el agrupamiento espectral se conoce como agrupamiento de características basado en segmentación .

Algoritmos

Dado un conjunto enumerado de puntos de datos, la matriz de similitud se puede definir como una matriz simétrica donde los elementos representan una medida de similitud entre puntos de datos con índices y . El principio general del agrupamiento espectral es usar el método de agrupamiento estándar (existen muchos métodos de este tipo, el método de k-medias se analiza a continuación ) en los vectores propios significativos de la matriz de Kirchhoff de la matriz . Hay muchas formas diferentes de definir la matriz de Kirchhoff, que tiene diferentes interpretaciones matemáticas, por lo que la agrupación también tendrá diferentes interpretaciones. Los vectores propios significativos son aquellos que corresponden a los valores propios más pequeños de la matriz de Kirchhoff, con la excepción de los valores propios 0. Por eficiencia computacional, estos vectores propios a menudo se calculan como vectores propios correspondientes a algunos de los valores propios más grandes de un función de la matriz de Kirchhoff. $A$ $A_{ij}\geq0$ $i$ $j$ $A$

Una técnica para el agrupamiento espectral es el algoritmo de sección normalizada (o algoritmo de Shi-Malik ) propuesto por Jiambo Shi y Jitendra Malik [1] , un método ampliamente utilizado para la segmentación de imágenes . El algoritmo divide los puntos en dos conjuntos en función del vector propio correspondiente al segundo valor propio más grande de la matriz de Kirchhoff normalizada simétricamente dada por la fórmula ${\ estilo de visualización (B_{1},B_{2})}$ $v$

L^{\text{norma}}:=ID^{-1/2}AD^{-1/2},

donde esta la matriz diagonal $D$

D_{ii}=\sum_{j}A_{ij}.

El algoritmo matemáticamente equivalente [2] utiliza un vector propio correspondiente al valor propio más grande de la matriz de paseo aleatorio de Kirchhoff normalizada . El algoritmo Meil-Shi ha sido probado en el contexto de mapas de difusión , que se ha encontrado que tienen conexiones con la mecánica cuántica computacional [3] . $P=D^{-1}A$

Otra posibilidad es utilizar la matriz de Kirchhoff dada por la expresión

{\ estilo de visualización L: = DA}

en lugar de una matriz de Kirchhoff simétricamente normalizada.

La partición se puede hacer de varias maneras, como calcular la mediana de los componentes del segundo vector propio más pequeño y colocar todos los puntos en , cuyas componentes en son mayores que , el resto de los puntos se colocan en . El algoritmo se puede utilizar para la agrupación jerárquica mediante la partición secuencial de subconjuntos de forma similar. $metro$ $v$ $B_1$ $v$ $metro$ $B_{2}$

Si la matriz de similitud aún no se ha construido algebraicamente, la eficiencia del agrupamiento espectral se puede mejorar si la solución del problema correspondiente, la búsqueda de valores propios, se lleva a cabo mediante un método sin matriz (sin manipulación explícita o incluso cálculo de la matriz de similitud), como el algoritmo de Lanczos . $A$

Para gráficos de gran tamaño, el segundo valor propio de la matriz de Kirchhoff (normalizada) del gráfico a menudo está mal condicionado , lo que lleva a una convergencia lenta de los métodos iterativos de búsqueda de valores propios. El preacondicionamiento es una técnica clave para mejorar la convergencia, por ejemplo, en el método LOBPCG sin matriz . El agrupamiento espectral se ha aplicado con éxito a gráficos grandes, primero mediante el reconocimiento de la estructura de una comunidad de red y luego mediante el agrupamiento de la comunidad [4] .

El agrupamiento espectral está estrechamente relacionado con la reducción de la dimensionalidad no lineal y las técnicas de reducción de la dimensionalidad, como el anidamiento localmente lineal, se pueden usar para reducir el error del ruido o el valor atípico en las observaciones [5] .

El software gratuito para implementar el agrupamiento espectral está disponible en grandes proyectos de código abierto como Scikit-learn [6] , MLlib para el agrupamiento basado en pseudovalores propios utilizando el método de iteración de potencia [7] , el lenguaje R [8] .

Relación con k -medias

El problema de k -medias con un núcleo no lineal es una extensión del problema de k -medias en el que los puntos de entrada se asignan de forma no lineal en un espacio de características de alta dimensión mediante una función de núcleo . El problema de k -medias ponderadas con un núcleo no lineal amplía el problema aún más al especificar el peso de cada grupo como un valor inversamente proporcional al número de elementos del grupo, $k(x_{i},x_{j})=\varphi ^{T}(x_{i})\varphi (x_{j})$ $w_{r}$

\max _{\{C_{s}\}}\sum _{r=1}^{k}w_{r}\sum _{x_{i},x_{j}\in C_{r }}k(x_{i},x_{j}).

Sea una matriz de coeficientes normalizados para cada punto de cualquier grupo, donde , si , y 0 en caso contrario. Sea la matriz kernel para todos los puntos. Un problema ponderado de k medias con un núcleo no lineal con n puntos y k conglomerados se define como un problema de maximización $F$ ${\ Displaystyle F_ {ij} = w_ {r}}$ ${\ estilo de visualización i, j \ en C_ {r}}$ $k$

\max _{F}\operatorname {traza} \left(KF\right)

bajo condiciones

{\displaystyle F=G_{n\veces k}G_{k\veces n}^{T))

G^{T}G=E

Al mismo tiempo Además, hay una restricción en los coeficientes $\operatorname {rango} (G)=k$ $F$

F\cdot \mathbf {1} =\mathbf {1}

donde es un vector de unidades. $\mathbf{1}$

F^{T}\mathbf {1} =\mathbf {1}

La tarea se puede convertir en

\max _{G}\operatorname {traza} (G^{T}G).

Este problema es equivalente al problema del agrupamiento espectral cuando se relaja la restricción. En particular, un problema de k -medias ponderadas con un núcleo no lineal se puede reformular como un problema de agrupamiento espectral (partición de gráficos) y viceversa. La salida del algoritmo son vectores propios que no satisfacen las restricciones sobre las variables indicadoras definidas por el vector . Por lo tanto, se requiere un procesamiento posterior de los vectores propios para que las tareas sean equivalentes [9] . La transformación del problema de agrupamiento espectral en un problema ponderado de k -medias con un kernel no lineal reduce significativamente los costos computacionales [10] . $F$ $F$

Medidas para comparar el agrupamiento

Ravi Kannan, Santosh Vempala y Adrian Wetta [11] propusieron una medida bicriterio para determinar la calidad del agrupamiento. Dicen que un agrupamiento es un agrupamiento (α, ε) si la conductividad de cada grupo es al menos α y el peso de los bordes entre grupos no excede la fracción ε del peso de todos los bordes en el gráfico. En el mismo artículo, también consideran dos algoritmos de aproximación.

Véase también

Método de propagación por proximidad
Método del componente principal nuclear
análisis de conglomerados
Teoría de grafos espectrales

Notas

↑ Shi, Malik, 2000 .
↑ Meila, Shi, 2001 , pág. 873–879.
↑ Scott, Therani, Wang, 2017 , pág. 1-17.
↑ Zare, Shooshtari, Gupta, Brinkman, 2010 , pág. 403.
↑ Arias-Castro, Chen, Lerman, 2011 , p. 1537-1587
↑ 2.3. Agrupación en clústeres: documentación de scikit-learn 0.20.2 . Consultado el 28 de junio de 2017. Archivado desde el original el 15 de mayo de 2015. (indefinido)
↑ Clustering - API basada en RDD - Documentación de Spark 2.4.0 . Consultado el 28 de junio de 2017. Archivado desde el original el 3 de julio de 2017. (indefinido)
↑ Kernlab del paquete CRAN . Consultado el 28 de junio de 2017. Archivado desde el original el 27 de junio de 2017. (indefinido)
↑ Dhillon, Guan, Kulis, 2004 , pág. 551–556.
↑ Dhillon, Guan, Kulis, 2007 , pág. 1-14.
↑ Kannan, Vempala, Vetta, 2000 , pág. 497–515.

Literatura

Marina Meila, Jianbo Shi. Segmentación del Aprendizaje por Paseos Aleatorios // Sistemas de Procesamiento de Información Neural . - 2001. - V. 13 (NIPS 2000). Archivado el 10 de diciembre de 2015 en Wayback Machine .
Jianbo Shi, Jitendra Malik. Cortes Normalizados y Segmentación de Imágenes // Transacciones IEEE en PAMI. - 2000. - agosto ( vol. 22 , número 8 ).
TC Scott, Madhusudan Therani, Xing M. Wang. Agrupación de Datos con Mecánica Cuántica // Matemáticas. - 2017. - V. 5 , n. 1 . — P. 1–17 . doi : 10.3390 / math5010005 .
Habil Zare, P. Shooshtari, A. Gupta, R. Brinkman. Reducción de datos para agrupamiento espectral para analizar datos de citometría de flujo de alto rendimiento // BMC Bioinformatics. - 2010. - T. 11 . - art. 403 . -doi : 10.1186/ 1471-2105-11-403 . —PMID 20667133 .
E. Arias-Castro, G. Chen, G. Lerman. Agrupamiento espectral basado en aproximaciones lineales locales. // Revista Electrónica de Estadística. - 2011. - T. 5 . - S. 1537-1587 . -doi : 10.1214 / 11-ejs651 .
ES Dhillon, Y. Guan, B. Kulis. Kernel k -means: agrupamiento espectral y cortes normalizados // Actas de la décima conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento y minería de datos. - 2004. - S. 551-556.
Inderjit Dhillon, Yuqiang Guan, Brian Kulis. Cortes de gráficos ponderados sin vectores propios: un enfoque multinivel // Transacciones IEEE sobre análisis de patrones e inteligencia artificial. - 2007. - noviembre ( vol. 29 , número 11 ). -doi : 10.1109/ tpami.2007.1115 .
Ravi Kannan, Santosh Vempala, Adrian Vetta. Sobre agrupamientos: Bueno. Malo y Espectral // Diario de la ACM. - 2000. - T. 51 . -doi : 10.1145/ 990308.990313 .