Mientras hacemos agrupaciones espectrales, ¿por qué encontramos el vector propio del gráfico laplaciano? ¿Por qué no usar la matriz de adyacencia directamente?

Answer 1

Ajá, me gustaría responder a esto, ya que me confundió mucho hace unos meses.

¡Absolutamente la respuesta es “SÍ”! Pero usar la matriz de adyacencia directamente prefiere lidiar con diferentes escenarios en comparación con el uso del Gráfico
Laplaciano

Un viejo documento “Cortes normalizados y segmentación de imágenes” en la página en princeton.edu incluyó algunas discusiones y basado en las conclusiones y cifras que proporciono mi respuesta. Pero, en primer lugar, deberíamos estar de acuerdo en que en lugar de encontrar los vectores propios más pequeños como lo hacemos para Graph Laplacian, debemos extraer los vectores propios más grandes.

Simplemente puede desplazarse hacia abajo a la página 39 en la sección 6.1 y verá la tabla de esta manera: (observe que la definición de asso (A, B) y corte (A, B) es inherentemente la misma, es decir [matemáticas] \ Sigma_ {u \ en A, v \ en B} {} w_ {u, v} [/ math])

La tabla resume la información principal sobre 3 métodos diferentes. La fila superior muestra su función objetivo (discreta) y la fila siguiente muestra el sistema de valor propio para calcular las soluciones correspondientes.
¿Ver? La ecuación de izquierda a abajo le dijo que podría usar la matriz de adyacencia (ponderada) (digamos W) exactamente y este es otro tipo de agrupación espectral. Una cosa que debe notar es la comparación entre asociación promedio y corte promedio:

• asociación promedio : [matemáticas] \ frac {asso (A, A)} {| A |} + \ frac {asso (B, B)} {| B |} [/ matemáticas] (1)
• corte promedio : [matemática] \ frac {corte (A, A)} {| A |} + \ frac {corte (B, B)} {| B |} [/ matemática] (2)

Obviamente, las únicas diferencias entre las funciones objetivas de estas 2 medidas son las moleculares. Tenga en cuenta que no hay garantías de que [matemática] V = A \ cup B, A \ cap B = \ emptyset [/ math] Intuitivamente,

tanto el algoritmo de corte normalizado como el de corte promedio intentan encontrar una “partición equilibrada” de un gráfico ponderado, mientras que, por otro lado, la asociación normalizada y la asociación promedio intentan encontrar grupos “ajustados” en el gráfico.

El documento estimula algunos escenarios para verificar los tres tipos de métodos dos y no hay necesidad de copiar los detalles aquí. Una cosa que no mencioné es que la forma en que agrupamos es usar algoritmos de agrupamiento clásicos (generalmente k-means) para agrupar los vectores propios calculados a partir de las ecuaciones de valores propios y estos son solo una aproximación. Y personalmente, creo que hay 2 razones principales por las que los algoritmos de agrupación espectral basados ​​en asociados no se usan ampliamente como los basados ​​en cortes:

1. La aproximación no es ajustada;
2. Las matrices de adyacencia no siempre son positivas, semitfinidas, lo que puede hacer que los valores propios no sean números reales.

Finalmente, el agrupamiento espectral no es solo una parte que incluye un corte mínimo o corte normalizado. De hecho, todos los métodos que utilizan espectros (valores propios, vectores propios) están dentro del alcance de este tipo de algoritmos, pero recuerde que su rendimiento depende en gran medida de los escenarios.