Agrupamiento Espectral
- Propuesto por
- Ng, A. Y.; Jordan, M. I.; Weiss, Y.
- Año
- 2002
- Tipo
- Graph-based clustering (spectral method)
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
El Agrupamiento Espectral es un algoritmo de aprendizaje no supervisado basado en grafos, formalizado por Ng, Jordan y Weiss en 2002, que mapea puntos de datos a un espacio de autovalores de baja dimensión derivado del Laplaciano del grafo de similitud antes de aplicar k-medias.
Esta incrustación espectral hace posible recuperar agrupaciones de forma arbitraria —anillos, crecientes, espirales entrelazadas— que los métodos basados en distancia euclidiana fallan consistentemente en separar.
La intuición detrás del método
El algoritmo k-medias estándar particiona el espacio por distancia en línea recta, por lo que solo puede encontrar cúmulos convexos y aproximadamente esféricos. El Agrupamiento Espectral evita esto al considerar primero los datos como una red: cada punto es un nodo y las aristas entre nodos tienen un peso que refleja cuán similares son los dos puntos. Los agrupamientos corresponden a regiones de la red que están densamente conectadas internamente pero débilmente conectadas con el resto. La matriz Laplaciana del grafo codifica esta estructura de conectividad, y sus autovectores más pequeños actúan como un sistema de coordenadas suave que estira los datos de modo que los agrupamientos bien separados terminen muy alejados, incluso cuando estaban enredados en el espacio original. Un simple paso de k-medias en ese nuevo sistema de coordenadas los separa limpiamente.
Historia
Los fundamentos teóricos del agrupamiento espectral se remontan al trabajo de Fiedler de 1973 sobre la conectividad de grafos y el autovalor de conectividad algebraica. Shi y Malik (2000) introdujeron el enfoque en la visión por computadora a través de su criterio de cortes normalizados para la segmentación de imágenes. Ng, Jordan y Weiss (2002) presentaron un algoritmo limpio y de propósito general en NIPS —el que ahora se cita con más frecuencia— junto con un análisis de teoría de perturbaciones que explica cuándo y por qué funciona el método. El tutorial de Von Luxburg de 2007 en Statistics and Computing unificó las formulaciones en competencia, aclaró el papel de la normalización Laplaciana y se convirtió en la referencia estándar para los profesionales. El agrupamiento espectral ocupa ahora un lugar central en el currículo de aprendizaje automático y sigue siendo un tema de investigación activo, con trabajos en curso sobre aproximaciones escalables, kernels robustos y extensiones a grafos y variedades.
Cuándo usarlo
El Agrupamiento Espectral es adecuado cuando los agrupamientos en los datos son no convexos, no linealmente separables o están conectados por puentes delgados que los métodos de partición euclidiana no pueden detectar —ejemplos comunes incluyen agrupamientos en forma de anillo, espirales entrelazadas y segmentos de imágenes. Es apropiado cuando la similitud por pares entre puntos puede calcularse de manera significativa (ya sea a partir de un kernel sobre características crudas o de una matriz de afinidad pre-suministrada), y cuando el número de agrupamientos k se conoce o puede estimarse a partir de la heurística del eigengap. El método no requiere suposiciones distribucionales sobre las formas de los agrupamientos. Las limitaciones prácticas incluyen memoria cuadrática en el número de puntos (para la matriz de afinidad completa) y tiempo cúbico para la autodescomposición, lo que hace que la formulación estándar sea costosa más allá de aproximadamente 10,000 puntos. Métodos aproximados (Nystrom, grafos dispersos, SVD aleatorizado) extienden su alcance a conjuntos de datos más grandes.
Limitaciones y consideraciones
- La construcción de la matriz de afinidad completa n x n requiere O(n^2) de memoria y O(n^3) de tiempo para la autodescomposición, lo que hace que el algoritmo ingenuo sea inviable para conjuntos de datos grandes.
- Los resultados son sensibles a la elección del ancho de banda sigma del kernel y a la estrategia de construcción del grafo; elecciones deficientes pueden fusionar o fragmentar agrupamientos.
- La inicialización de k-medias en la incrustación espectral introduce aleatoriedad; diferentes ejecuciones pueden producir particiones diferentes.
- No escala bien a espacios de características de muy alta dimensión sin una cuidadosa selección del kernel.
- Proporciona solo etiquetas de agrupamiento; no ofrece un modelo generativo ni una extensión natural fuera de la muestra para nuevos puntos.
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Detecta agrupamientos de forma arbitraria, incluyendo configuraciones no convexas y no linealmente separables que superan a k-medias y a los modelos de mezcla Gaussiana.
- Puede operar sobre cualquier matriz de similitud por pares, no solo distancias euclidianas, lo que lo hace aplicable a grafos, cadenas y otros datos estructurados.
- La heurística del eigengap proporciona una guía principista basada en datos para elegir el número de agrupamientos k.
- Fundamentado en una rica teoría espectral de grafos, lo que permite un análisis formal de la convergencia y la calidad de los agrupamientos.
- Conceptualmente simple y fácilmente implementable utilizando bibliotecas estándar de álgebra lineal.
Aplicaciones
- Segmentación de imágenes: partición de píxeles o superpíxeles en regiones perceptualmente coherentes utilizando similitud de características a nivel de píxel.
- Detección de comunidades en redes sociales y biológicas donde la conectividad por pares en lugar de los vectores de características define la estructura.
- Bioinformática: agrupación de genes o proteínas por similitud de perfiles de expresión, donde los agrupamientos de expresión rara vez son convexos en el espacio génico.
- Procesamiento del lenguaje natural: agrupamiento de documentos u oraciones utilizando kernels de similitud semántica.
- Visión por computadora: segmentación de movimiento y partición de nubes de puntos donde los límites de los agrupamientos son irregulares.
- Análisis exploratorio de datos: revelación de estructuras de agrupamiento no obvias antes de aplicar métodos confirmatorios.
Cómo funciona
Cómo funciona
Se construye una matriz de similitud (afinidad) por pares W a partir de los datos. La opción más común es el kernel Gaussiano (RBF), que asigna un peso alto a pares cercanos y un peso cercano a cero a los distantes. El parámetro de ancho de banda sigma controla la rapidez con la que la similitud decae con la distancia; elegirlo bien es crítico. Alternativamente, se puede usar un grafo de k-vecinos más cercanos para representaciones más dispersas en conjuntos de datos grandes.
Fórmula
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)La matriz de grados D es la matriz diagonal cuya i-ésima entrada es la suma de la i-ésima fila de W. A partir de W y D se forma el Laplaciano del grafo normalizado (simétrico) L_sym. Esta matriz captura la estructura completa de conectividad del grafo de similitud; su espectro de autovalores revela cuántos agrupamientos naturales contiene el conjunto de datos y cuán limpiamente están separados.
Fórmula
L_{\mathrm{sym}} = D^{-1/2}(D - W)D^{-1/2} = I - D^{-1/2}W D^{-1/2}Se calculan los k autovectores correspondientes a los k autovalores más pequeños de L_sym. Estos autovectores forman las columnas de la matriz de incrustación U, que tiene una fila por punto de datos. En este espacio espectral k-dimensional, los puntos que pertenecen al mismo agrupamiento se acercan, incluso si estaban intercalados en el espacio de características original.
Fórmula
L_{\mathrm{sym}}\, u = \lambda u \quad \Rightarrow \quad U = [u_1,\, u_2,\, \ldots,\, u_k]Cada fila de U se divide por su norma euclidiana para proyectar los puntos incrustados en la hiperesfera unitaria. Esta normalización, introducida por Ng, Jordan y Weiss, elimina diferencias de escala espurias entre autovectores y asegura que el paso posterior de k-medias se centre en la estructura angular de la incrustación en lugar de en la magnitud.
Fórmula
T_{ij} = U_{ij} \Big/ \left(\sum_{j'} U_{ij'}^2\right)^{1/2}Se aplica el agrupamiento k-medias estándar a las filas de la matriz de incrustación normalizada T. Debido a que la incrustación espectral ya ha desenredado la geometría de los agrupamientos, k-medias encuentra particiones significativas incluso para formas de agrupamiento no convexas. Las etiquetas de los agrupamientos se mapean luego a los puntos de datos originales.
Errores comunes
- Elección de sigma sin validación cruzada principista o autoajuste; un ancho de banda demasiado pequeño crea un grafo desconectado, mientras que uno demasiado grande fusiona agrupamientos distintos.
- Omitir la normalización de las filas de la matriz de afinidad antes de k-medias (el paso de normalización de filas de Ng et al. es esencial para la estabilidad).
- Ignorar el eigengap: usar un k fijo sin inspeccionar el espectro de autovalores a menudo conduce a una sub- o sobre-segmentación.
- Aplicar el algoritmo completo a conjuntos de datos con decenas de miles de puntos sin cambiar a una variante aproximada o dispersa.
- Confundir Laplacianos no normalizados (L = D - W) y normalizados (L_sym, L_rw), lo que puede cambiar sustancialmente las asignaciones de agrupamientos.
Preguntas frecuentes
¿Cómo elijo el número de agrupamientos k?
La heurística del eigengap es la guía estándar: calcule los autovalores del Laplaciano normalizado en orden ascendente y busque la brecha más grande entre autovalores consecutivos. El índice en el que ocurre esta brecha sugiere el número natural de agrupamientos. Cuando el eigengap es ambiguo, los enfoques basados en la estabilidad —ejecutar el algoritmo para varios valores de k y comparar las asignaciones de agrupamientos entre perturbaciones— pueden ayudar.
¿Cómo debo establecer el ancho de banda sigma del kernel Gaussiano?
Una heurística común es la mediana de las distancias por pares en el conjunto de datos, o un esquema de autoajuste de vecinos más cercanos (Zelnik-Manor & Perona, 2004) que asigna un ancho de banda local a cada punto. En la práctica, sigma debe validarse inspeccionando la conectividad del grafo de afinidad resultante: cada punto debe tener al menos unos pocos vecinos de alto peso, y el grafo no debe fragmentarse en componentes aislados.
¿Por qué es necesario el paso de normalización de filas?
Los autovectores del Laplaciano pueden diferir sustancialmente en escala. Sin normalizar cada fila de la matriz de incrustación a longitud unitaria, el paso de k-medias puede estar dominado por autovectores con magnitudes grandes e ignorar componentes informativos pero de menor magnitud. La normalización de filas introducida por Ng, Jordan y Weiss mapea todos los puntos a la esfera unitaria para que k-medias responda a la geometría angular de la incrustación.
¿Puede el agrupamiento espectral manejar conjuntos de datos muy grandes?
No en su forma ingenua, que requiere O(n^2) de memoria y O(n^3) de tiempo de autodescomposición. Para n grande, los remedios estándar incluyen: construir un grafo disperso de k-vecinos más cercanos en lugar de una matriz de afinidad completa; usar la aproximación de Nystrom para estimar autovectores a partir de una submuestra; o aplicar SVD aleatorizado. Estos métodos aproximados recuperan la mayor parte de la precisión a una fracción del costo.
Métodos relacionados
Fuentes
Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On Spectral Clustering: Analysis and an Algorithm. Advances in Neural Information Processing Systems, 14, 849–856.
Abrir referencia de la publicaciónCopiado.von Luxburg, U. (2007). A Tutorial on Spectral Clustering. Statistics and Computing, 17, 395–416.
Abrir referencia DOICopiado.Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905.
Abrir referencia DOICopiado.