4.3 TP - Implémentation du spectral clustering

Le but de ce TP est d’implementer deux différents algorithmes de spectral clustering et d’analyser leur comportement sur quelques graphes simples.

Debugging dans RStudio

RStudio a plein de fonctionnalités utiles pour le développement de code. Quand on écrit une fonction plus ou moins complexes, on aimerait exécuter le code ligne par ligne sur un petit exemple pour s’assurer que tout se passe comme prévu. Comment faire ?

• Il faut que la fonction se trouve dans un script R (un fichier avec la terminaison .R, pas dans un notebook), et il faut sauvegarder le fichier.
• Ensuite vous placez un (ou plusieurs) breakpoint à l’endroit dans la fontion où vous voulez que le calcul s’arrête lorsque vous exéctuez la fonction. On place un breakpoint en cliquant à gauche du numéro de la ligne concernée.
  
• Il faut sourcer le code. Il faut que les breakpoints soient de ronds pleins rouges.
• Enfin vous appelez votre fonction sur un exemple, le calcul commence et va s’arrêter au premier breakpoint. Maintenant vous pouvez vérifier la valeur de tous les objets.
• Pour continuer, cliquer sur une des flèches vertes dans la console, ou sur Stop pour sortir du mode debug.
• Pour enlever un breakpoint il suffit de cliquer sur le point rouge.

Exercice 1

1. Ecrire une fonction R qui effectue le spectral clustering normalisé. Cette fonction prend en argument une matrice d’adjacence et le nombre de cluster souhaité. Elle peut afficher les valeurs propres de la matrice laplacienne \(L_N\) et renvoie le clustering obtenu. (La fonction eigen() donne le spectre d’une matrice.)
2. Simuler un petit graphe dont vous connaissez le résultat (par exemple une clique) et tester votre fonction.
3. Faites de même pour le spectral clustering basé sur \(L_\text{abs}\).

Exercice 2

Simuler des graphes diverses et analyser le spectre des lapalciens \(L_N\) et \(L_{\text{abs}}\) associés. Est-ce que la méthode du eigengap permet de choisir un nombre de clusters raisonnable ? Vérifier quelle méthode retrouve le bon clustering. D’ailleurs, comment compare-t-on les clusters obtenus par deux algorithmes de classification différente ? (Il faut faire attention au problème du ``label switching’’).

Quelques idées pour des graphes à simuler:

• un graphe \(G(n,p)\) (avec une seule composante connexe) (utiliser la fonction sample_gnp())
• un graphe avec deux, trois ou quatre communautés
• un graphe en étoile
• un graphe bi-parti (complet entre les deux parties)
• deux étoiles connectées par une arête.

Exercice 3

Reprenez un des graphes réels vus aux TP précédents (graphe friends ou karate par exemple) et appliquez les algorithmes de clustering sur ces données. Interprétez vos résultats.