Graph-Based Clustering - Version imprimable

+- Forum AFC (https://forum.afcytometrie.fr)
+-- Forum : Forums (https://forum.afcytometrie.fr/forumdisplay.php?fid=3)
+--- Forum : Analyse de données (https://forum.afcytometrie.fr/forumdisplay.php?fid=6)
+--- Sujet : Graph-Based Clustering (/showthread.php?tid=4)

---

Graph-Based Clustering - Quentin - 2020-07-01

Bonjour,

Je propose une discussion / listing autour des différents algorithmes de clustering basé sur les graphes. J'invite toute personne a compléter / corriger le contenue de ce poste.

Le plus connu dans notre domaine est sans doute Phenograph (et son implémentation en R: Rphenograph) mais depuis peu il existe des variantes se basant sur les mêmes 3 étapes de cet algorithme pour optimiser le temps de calcul et la qualité des résultats.

Les trois étapes de ces algorithmes sont les mêmes dans le principe  :

• Recherche des proches voisins par une métrique de distance
  

• Transformation en graphique avec une métrique (la plus utilisée étant l'index de Jaccard : https://fr.wikipedia.org/wiki/Indice_et_distance_de_Jaccard)
  

• Regroupement des nœuds du graphe en "communauté" (en cluster donc au final)
  

A l'heure actuelle j'ai noté 5 variantes de cette approche dont deux sans publications mais avec des liens github.

1. Phenograph  (utilisé dans cytofkit : https://pubmed.ncbi.nlm.nih.gov/26095251/ )
   
2. PARC (https://www.biorxiv.org/content/10.1101/765628v1)
   
3. FastPG (https://www.biorxiv.org/content/10.1101/2020.06.19.159749v1.full)
   
4. Rphenoannoy (https://github.com/stuchly/Rphenoannoy)
   
5. i-cyto/RPhenograph (https://github.com/i-cyto/Rphenograph)
   

PS : j'éditerai ce poste pour ajouter des informations sur chaques algorithmes

---