Quelle est la différence entre les vecteurs propres à matrice d'affinité et les vecteurs propres à graphes laplaciens dans le contexte du regroupement spectral?

8

Dans le clustering spectral, il est courant de résoudre le problème des vecteurs propres

Lv=λv

où est le graphe laplacien, est le vecteur propre lié à la valeur propre .Lvλ

Ma question: pourquoi s'embêter à prendre le graphe laplacien? Ne pourrais-je pas simplement résoudre le problème du vecteur propre pour le graphique (matrice d'affinité) lui-même, comme le gars l'a fait dans cette vidéo ?

PS: J'ai posé cette même question dans CrossValidated mais je pense que c'est une chaîne plus appropriée. Pardonnez-moi si je me trompe.

machine-learning clustering graphs Felipeduque
la source
Le lien vidéo est rompu :(
wcochran

Réponses:

4

Le concept est le même, mais vous êtes confus par le type de données. Regroupement spectral comme Ng et al. expliquer concerne le regroupement de données standard tandis que la matrice laplacienne est une matrice dérivée de graphe utilisée dans la théorie des graphes algébriques.

Donc, le fait est que chaque fois que vous encodez la similitude de vos objets dans une matrice, cette matrice pourrait être utilisée pour le regroupement spectral.

Si vous avez des données standard, c'est-à-dire une matrice de caractéristiques d'échantillon, vous pouvez trouver la proximité ou l'affinité ou tout ce que vous voulez appeler comme matrice et appliquer un regroupement spectral.

Si vous avez un graphique, cette affinité serait quelque chose comme une matrice d'adjacence, une matrice de distance ou une matrice de Laplacialn et la résolution de la fonction propre pour une telle matrice vous donne le résultat correspondant.

Le point sur l'utilisation du laplacien plutôt que de la contiguïté est de garder la soi-disant matrice d'affinité positive semi-définie (et la matrice laplacienne normalisée est un meilleur choix car elle vous donne des valeurs propres normalisées entre 0 et 2 et révèle la structure du graphique beaucoup mieux).

Donc, pour faire court, tant que vous disposez d'une matrice contenant l'affinité de vos données, vous pouvez utiliser le clustering spectral en général. La différence est dans les détails (ig la propriété du laplacien normalisé que je viens de mentionner)

Kasra Manshaei
la source
Oui, je pense que je suis un peu confus. Ce n'est toujours pas clair pour moi. Si j'ai des données standard (sans affinité), je peux en faire une matrice d'affinité A en prenant la distance par paire entre les échantillons de données. Maintenant, si je vois A comme un graphique, je peux prendre le laplacien et résoudre les vecteurs propres et obtenir une solution; si je ne vois pas A comme un graphique, je pourrais simplement résoudre les vecteurs propres matriciels (PCA) et obtenir une solution. Quelle est la différence?
felipeduque
J'ai relu votre question. La réponse est les propriétés (par exemple celle que j'ai mentionnée dans ma réponse) La matrice laplacienne permet une meilleure décomposition. Cependant, vous pouvez absolument utiliser la fonction propre pour toutes les matrices liées à la similitude et obtenir des résultats qui sont différents juste dans les détails. Par exemple, à propos de l'ACP que vous avez mentionnée: l'ACP prend la matrice de covariance pour capturer là où la variance est élevée, mais en général le concept suit la même direction que les autres techniques de décomposition spectrale. Je relirai ma réponse dès que je verrai des phrases "samedi soir";)
Kasra Manshaei