Agrupamiento espectral

En estadísticas multivariantes y  agrupamiento de los datos, las técnicas agrupamiento espectral hacen uso del  espectro (valores propios) de la matriz  de similitud de los datos para realizar reducción de dimensionalidad antes de la agrupación en un menor número de dimensiones. La matriz de similitud se proporciona como una entrada y consta de 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 la imagen, la agrupación espectral se conoce como categorización basada en la segmentación.

Algoritmos 

Dado un conjunto enumerado de puntos de datos, la matriz de similitud se puede definir como una matriz simétrica , donde  representa una medida de la similitud entre los puntos de datos con índices  y .

Una de las técnicas de agrupamiento espectral es el algoritmo de cortes normalizados o algoritmo Shi-Malik, introducido por Jianbo Shi y Jitendra Malik, comúnmente utilizado para  segmentación de imágenes. Se divide en dos conjuntos de puntos  basado en el  autovector  correspondiente a la segunda más pequeño  autovalor de la Matriz laplaciana define como

 ,

donde  es la matriz diagonal

Un algoritmo matemáticamente equivalente toma el vector propio correspondiente a la mayor valor propio de la matriz laplaciana normalizada .

Otra posibilidad es utilizar la matriz laplaciana definida como
 
en lugar de la  matriz laplaciana normalizada .

El particionamiento se puede hacer de varias maneras, tales como mediante el cálculo de la mediana  de los componentes del vector propio segundo más pequeño , y la colocación de todos los puntos cuyo componente en  es mayor que  en , y el resto en . El algoritmo puede ser utilizado para la agrupación jerárquica mediante la partición repetidamente los subconjuntos de esta manera.

Como alternativa a la informática sólo un vector propio,  k  vector propio s para algunos  k , se calculan, y luego otro algoritmo (por ejemplo, k-medias) se utiliza para puntos de racimo por su respectiva  k  componentes de estos vectores propios.

La eficiencia de agrupamiento espectral se puede mejorar si la solución al problema de valor propio correspondiente se realiza en un  moda de matriz libre, es decir, sin manipular de forma explícita o incluso el cálculo de la matriz de similitud, como, por ejemplo, en el Algoritmo de Lanczos.

Para gráficos de gran tamaño, el segundo valor propio de la gráfica (normalizado) es a menudo mal condicionada la matriz laplaciana, lo que lleva a reducir la velocidad de convergencia de valores propios solucionadores iterativos.  preacondicionamiento es una tecnología clave acelerar la convergencia, por ejemplo, en el LOBPCG método de matriz libre. Agrupamiento espectral se ha aplicado con éxito en grandes gráficos identificando primero su estructura de la comunidad, y luego agrupar comunidades

Agrupamiento espectral está estrechamente relacionado con reducción de dimensionalidad no lineal, y las técnicas de reducción de dimensiones tales como la incrustación localmente lineal se pueden utilizar para reducir los errores de ruido o valores atípicos.
Un código de fuente abierta está disponible en

Relación con  k  - means 

El kernel  k  - means problema es una extensión de la  k  - significa problema en el que los puntos de datos de entrada se asignan de forma no lineal en un espacio de características de dimensiones superiores a través de una función kernel . El núcleo ponderada  k  - significa problema adicional se extiende este problema mediante la definición de un peso  para cada grupo como el recíproco del número de elementos en el cluster,
 

Supongamos  es una matriz de los coeficientes de la normalización para cada punto para cada grupo  si  y cero en caso contrario. Supongamos  es la matriz del kernel para todos los puntos. El núcleo ponderada  k  - significa un problema con n puntos y clusters k se da como,
 

de tal manera que,
 

tal que . Además, hay identidad limita en  dada por,
 
donde  representa un vector de unos.
 
Este problema puede ser refundida como,

Este problema es equivalente al problema de agrupamiento espectral cuando las limitaciones de identidad en  están relajados. En particular, el núcleo ponderada k - significa problema puede ser reformulada como un problema de agrupamiento espectral (particionamiento gráfico) y viceversa. La salida de los algoritmos son vectores propios que no cumplan los requisitos de identidad para las variables indicadoras definidos por . Por lo tanto, se requiere de post-procesamiento de los vectores propios de la equivalencia entre los problemas.
Transformar el problema de agrupamiento espectral en un kernel ponderada  k  - significa problema se reduce en gran medida la carga computacional

Medidas para comparar clusterings 
Ravi Kannan, Santosh Vempala y Adrian Vetta en el siguiente documento propuso una medida bicriteria para definir la calidad de una agrupación determinada. Dijeron que una agrupación fue una (α, ε) -clustering si el  conductancia de cada grupo (en el clustering) fue al menos α y el peso de los bordes inter-cluster era como máximo ε fracción del peso total de todos los bordes en el gráfico. También se fijan en dos algoritmos de aproximación en el mismo papel.

Referencias 

Algoritmos de agrupamiento