[Notas del curso CS224W] Agrupación espectral
Dado un gráfico no dirigido, los nodos del gráfico se dividen en dos grupos disjuntos. La siguiente pregunta a considerar es:
En primer lugar, es necesario aclarar las características de una buena partición:
A continuación, el objetivo de la partición estará relacionado con el "corte de borde". " de la partición Expresado por la ecuación, donde el corte es el conjunto de aristas con dos puntos extremos ubicados en particiones diferentes, es decir, w_{ij}. Si no hay representación del peso en la imagen, entonces.
De esta forma, el criterio de corte del gráfico se puede definir como el valor que minimiza el corte, es decir, considerando la situación que se muestra en la siguiente figura, el corte marcado por la línea roja satisface la situación de minimización, pero este no es el método de segmentación esperado, por lo que es necesario considerar tantas conexiones dentro del clúster como sea posible.
Para producir particiones más equilibradas, [Shi-Malik, '97] propuso un nuevo criterio de evaluación de particiones, la conductancia, que define la conectividad en relación con la densidad de la partición, a saber:
Donde representa el volumen , que representa la suma de los grados ponderados de todos los nodos en la partición A, es decir. Se puede observar que el valor de esta fórmula tiende a ser máximo cuando los volúmenes de las dos particiones en el denominador son lo más iguales posible. Pero el problema que lo acompaña en este momento es que calcular el conjunto de corte de conductancia óptimo es un problema NP-difícil. La partición espectral que se estudiará a continuación permite garantías aproximadas de optimización de los criterios anteriores.
[Fiedler '73] propuso un esquema para encontrar el punto de corte óptimo, que representa la división como un vector, si es un nodo, corresponderá, y viceversa. Se espera que la partición se logre de manera que el vector actual también sea ortogonal. A continuación, encontraremos el esquema de partición que minimiza el corte de partición mediante la siguiente fórmula:
Si el valor de se extiende al rango real, entonces tenemos:
En este momento , la matriz laplaciana El segundo valor propio más pequeño de se obtiene mediante la siguiente fórmula; el vector propio correspondiente se obtiene mediante, aquí también llamado vector de Fiedler. En este momento, puede utilizar positivo y negativo para determinar a qué partición pertenece el nodo. El proceso anterior se llama agrupación espectral.
Este proceso corresponde a las tres etapas básicas del algoritmo de agrupamiento espectral: