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 $A$, donde $A_{ij}\geq 0$ representa una medida de la similitud entre los puntos de datos con índices $i$ y $j$.

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 $(B_{1},B_{2})$ basado en el autovector $v$ correspondiente a la segunda más pequeño autovalor de la Matriz laplaciana define como

$L^{norma}:=I-D^{-1/2}AD^{-1/2}$,

donde $D$ es la matriz diagonal

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

Un algoritmo matemáticamente equivalente​ toma el vector propio correspondiente a la mayor valor propio de la matriz laplaciana normalizada $P=D^{-1}A$.

Otra posibilidad es utilizar la matriz laplaciana definida como

$L:=D-A$

en lugar de la matriz laplaciana normalizada .

El particionamiento se puede hacer de varias maneras, tales como mediante el cálculo de la mediana $m$ de los componentes del vector propio segundo más pequeño $v$, y la colocación de todos los puntos cuyo componente en $v$ es mayor que $m$ en $B_{1}$, y el resto en $B_{2}$. 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 $k(x_{i},x_{j})=\phi ^{T}(x_{i})\phi (x_{j})$. El núcleo ponderada k - significa problema adicional se extiende este problema mediante la definición de un peso $w_{r}$ para cada grupo como el recíproco del número de elementos en el cluster,

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

Supongamos $F$ es una matriz de los coeficientes de la normalización para cada punto para cada grupo $F_{ij}=w_{r}$ si $i,j\ inc_{r}$ y cero en caso contrario. Supongamos $K$ 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,

$\max _{F}\operatorname {trace} \left(KF\right)$ de tal manera que,

$F=G_{n\times k}G_{n\times k}^{T}$

$G^{T}G=I$

tal que $\ text{rank}(G)=k$. Además, hay identidad limita en $F$ dada por,

$F\cdot \mathbb {I} =\mathbb {I}$

donde $\mathbb {I}$ representa un vector de unos.

$F^{T}\mathbb {I} =\mathbb {I}$

Este problema puede ser refundida como,

$\max _{G}{\text{ trace }}\left(G^{T}G\right).$

Este problema es equivalente al problema de agrupamiento espectral cuando las limitaciones de identidad en $F$ 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 $F$. 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

• Datos: Q2976589