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

editar

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,[1]​ 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[2]​ 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[3]

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.[4]​ Un código de fuente abierta está disponible en[5]

Relación con k - means

editar

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.[6]​ Transformar el problema de agrupamiento espectral en un kernel ponderada k - significa problema se reduce en gran medida la carga computacional[7]

Medidas para comparar clusterings

editar

Ravi Kannan, Santosh Vempala y Adrian Vetta en el siguiente documento[8]​ 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

editar
  1. Jianbo Shi y Jitendra Malik, "cortes normalizados y segmentación de imágenes", IEEE Transactions on PAMI, vol. 22, No. 8, agosto 2000
  2. Marina Meila y Jianbo Shi, "Aprender Segmentación por Random Walks Archivado el 10 de diciembre de 2015 en Wayback Machine.", Sistemas de Procesamiento de Información Neuronales 13 (PIN 2000), .. 2001, pp 873-879
  3. Zare, Habil; P. Shooshtari; A. Gupta; R. Brinkman (2010). «reducción de datos para el agrupamiento espectral para analizar un alto rendimiento de citometría de flujo de datos». BMC Bioinformatics 11: 403. doi:10.1186/1471-2105-11-403. 
  4. Arias-Castro, E. y Chen, G. y Lerman, G. (2011), «agrupamiento espectral basado en aproximaciones lineales locales.», Revista Electrónica de Estadística 5: 1537-1587, doi:10.1214/11-ejs651 .
  5. software estadístico Gratis:.. https://github.com/ezahedi/Network-Clustering/tree/master/Spectral-clustering
  6. Dhillon, I.S. y Guan, Y. y Kulis, B. (2.004). «núcleo k - medios: agrupamiento espectral y cortes normalizados». Actas de la décima Conferencia Internacional ACM SIGKDD sobre descubrimiento de conocimientos y minería de datos. 
  7. Dhillon, Inderjit; Yuqiang Guan; Brian Kulis (11 2007). «tabuladas Cortes gráfico sin vectores propios: un enfoque multinivel». IEEE Transactions on Análisis de patrones y la máquina de Inteligencia 29 (11): 14.01. doi:10.1109/tpami.2007.1115. 
  8. Kannan, Ravi; Vempala, Santosh; Vetta, Adrian. «El agrupamientos: Good . Malo y espectral». Diario del ACM 51.