¿Cuál es la diferencia entre los vectores propios de la matriz de afinidad y los vectores propios de la gráfica de Laplacia en el contexto de la agrupación espectral?

8

En el agrupamiento espectral, es una práctica estándar resolver el problema del vector propio

Lv=λv

donde es el gráfico laplaciano, es el vector propio relacionado con el valor propio .Lvλ

Mi pregunta: ¿por qué molestarse en tomar el gráfico laplaciano? ¿No podría resolver el problema del vector propio para el gráfico (matriz de afinidad) en sí, como lo hizo el tipo en este video ?

PD: Hice esta misma pregunta en CrossValidated, pero creo que este es un canal más apropiado. Perdóname si me equivoco.

felipeduque
fuente
El enlace de video está roto :(
wcochran

Respuestas:

4

El concepto es el mismo, pero el tipo de datos te confunde. Agrupación espectral como Ng et al. explicar se trata de agrupar datos estándar, mientras que la matriz laplaciana es una matriz derivada de gráficos utilizada en la teoría de gráficos algebraicos.

Entonces, el punto es que siempre que codifique la similitud de sus objetos en una matriz, esta matriz podría usarse para la agrupación espectral.

Si tiene datos estándar, es decir, una matriz de características de muestra, puede encontrar la proximidad o afinidad o lo que quiera llamarlo como matriz y aplicar la agrupación espectral.

Si tiene un gráfico, esta afinidad sería algo así como matriz de adyacencia, matriz de distancia o matriz de Laplacialn y resolver la función propia de dicha matriz le da el resultado correspondiente.

El punto sobre el uso de Laplacian en lugar de adyacencia es mantener la llamada matriz de afinidad positiva semi-definida (y la matriz Laplacian normalizada es una mejor opción ya que le da valores propios normalizados entre 0 y 2 y revela la estructura del gráfico mucho mejor).

En resumen, siempre que tenga una matriz que contenga la afinidad de sus datos, puede usar el agrupamiento espectral en general. La diferencia está en los detalles (por ejemplo, la propiedad del laplaciano normalizado que acabo de mencionar)

Kasra Manshaei
fuente
Sí, creo que estoy un poco confundido. Todavía no está claro para mí. Si tengo datos estándar (sin afinidad), puedo convertirlo en una matriz de afinidad A tomando la distancia por pares entre las muestras de datos. Ahora, si veo A como un gráfico, puedo tomar el Laplaciano y resolver los vectores propios y obtener una solución; Si no veo A como un gráfico, simplemente podría resolver los vectores propios de la matriz (PCA) y obtener una solución. ¿Cual es la diferencia?
felipeduque
Leí tu pregunta nuevamente. La respuesta son las propiedades (por ejemplo, la que mencioné en mi respuesta). La matriz laplaciana proporciona una mejor descomposición. Sin embargo, absolutamente puede utilizar la función propia para cualquier matriz relacionada con similitudes y obtener algunos resultados que son diferentes solo en detalles. Por ejemplo, sobre el PCA que mencionó: PCA toma la matriz de covarianza para capturar donde la varianza es alta, pero en general el concepto sigue la misma dirección que las otras técnicas de descomposición espectral. Revisaré mi respuesta pronto cuando vea algunas oraciones de "Saturday Night";)
Kasra Manshaei