User Tools

Site Tools


bellitto_thomas:thomas_bellito

Visual Analytics Course

Bordeaux roadmap 2013- 2014 / Thomas Bellitto's corner

Projet : Graph Clustering and Minimum Cut Trees

Introduction

Ce projet se base sur l'article “Graph Clustering and Minimum Cut Trees”, de Gary William Flake, Robert E. Tarjan et Kostas Tsioutsiouliklis, publié en 2003 dans “Internet Mathematics”. Cet article propose un algorithme, CutClustering, pour le problème de graph clustering, qui consiste en toute généralité à regrouper les sommets du graphe en groupe de sommets ayant une densité d'arêtes internes fortes, mais peu d'arêtes entre eux. Nous allons ici discuter de ce qu'on attend d'un algorithme de clustering et commenter les résultats de CutClustering, d'un point de vue théorique et pratique.

L'algorithme proposé par l'article a l'avantage de s'adapter sans problème aux graphes pondérés, si bien que ce sont ces graphes qui serviront de cadre à notre étude. Nous supposerons dans la suite nos graphes connexes (dans le cas contraire, il suffit de clusteriser indépendamment chaque composante connexe). Nous nous restreindrons également aux graphes non-orientés, il est en effet difficile de donner un sens à l'orientation des arêtes en terme de clustering. Nous noterons ainsi nos graphes avec et

Critère de qualité d'un clustering

La notion de coupe dans un graphe sera centrale dans la suite du rapport. Si et forment une partition de , la coupe vaut par définition . La coupe minimale entre deux sommets et est la partition de telle que , et est minimum. On appelle alors coupe de par rapport à .

Du point de vue des coupes dans le graphe, on attend d'un clustering que les coupes intercluster soient faibles et que toutes les coupes intracluster soient fortes.

Pour mesurer la qualité d'un clustering, on a souvent recours aux deux grandeurs usuelles suivantes :

L'expansion d'une coupe est définie par . On définit ainsi l'expansion d'un cluster C par . L'expansion d'un clustering, qu'il s'agit de maximiser est alors l'expansion la plus faible sur les clusters formés.

On définit de la même façon la conductance d'une coupe par . La conductance d'un cluster est le minimum des conductances sur les coupes du cluster et la conductance d'un clustering est la plus petite conductance des clusters.

Ces deux critères, assez proche, diffèrent essentiellement par le fait que l'expansion accorde la même importance à chaque sommet quand la conductance accorde au sommet une importance proportionnelle à leur poids (défini comme la somme des poids des arêtes adjacentes).

L'expérience montre que ces deux critères conduisent souvent à des clustering plus pertinents que les seules coupes intracluster. Le problème est justement que ces critères ne mesurent que la cohésion intra-cluster. De plus, le fait que ces grandeurs soient plus difficiles à calculer les rend aussi plus difficiles à optimiser que les seules coupes minimales.

L'algorithme CutClustering sur lequel porte le projet propose simultanément de minorer l'expansion de chaque cluster et de majorer le ratio (poids des arêtes intercluster)/(poids total des arêtes du graphe).

L'algorithme CutClustering

Principe

Gomory et Hu (1961) ont prouvé l'existence pour chaque graphe d'un arbre associé appelé MinCutTree ayant la propriété suivante : pour et , si on coupe l'arête de poids le plus faible sur le chemin entre et dans , les deux composantes connexes résultantes définissent une coupe minimales entre et .

L'algorithme CutClustering procède alors comme suit : on ajoute dans le graphe un sommet artificiel relié à tous les autres par une arête de poids . On détermine ensuite l'arbre de coupes minimales du graphe, puis on y supprime et toutes les arêtes adjacentes. Les composantes connexes ainsi obtenues définissent un clustering du graphe.

Résultats théoriques

Le principal résultat garantissant la qualité du clustering ainsi obtenu est le suivant : pour tout cluster S, pour toute partition P,Q de S :

La partie gauche de l'équation garantit une borne supérieure sur la cohésion intercluster, et la partie de droite, une borne inférieure sur la cohésion intracluster.

Choix du paramètre

Le paramètre déterminant pour le clustering est le poids des arêtes reliant les sommets du graphe au puits artificiel . Comme ce sert de bornes à la fois aux critères inter et intra clusters, sa valeur déterminera l'importance qu'on accorde à chacun d'entre eux.

Un faible permettra d'avoir peu d'arêtes entre les clusters, mais n'empêchera pas une forte densité au sein d'un cluster. Le cas extrême étant où les coupes minimales sépareront toutes de . Le sommet sera alors une feuille de l'arbre et sa suppression laissera un seul cluster trivial contenant tous les sommets.

Un fort au contraire garantira une forte densité dans les clusters, sans pouvoir forcer les clusters à n'être que peu reliés. Le cas extrême donnera un arbre de coupes minimales en étoile autour de et le clustering obtenu sera une union de singletons, sans plus d'intérêt que le cas .

Comme souvent, les clustering intéressants demanderont un compromis entre les différents critères.

Complexité et amélioration

La complexité temporelle de l'algorithme est due à la construction de l'arbre de coupes minimales. En utilisant l'algorithme de Gomory et Hu (1961), ce dernier peut se calculer en calculs de coupes minimales. À noter quand même que cet algorithme peut être largement amélioré. En effet, la seule chose qui nous intéresse est le placement des nœuds de cet arbre par rapport à .

On remarque alors la propriété suivante : si la coupe minimale de par rapport à contient un sommet , alors elle contient la coupe de par rapport à toute entière. Ainsi, tous les sommets de la coupe de peuvent être placés dans le cluster de sans autre calcul. Statistiquement, les sommets qui auront les plus grandes coupes (par l'inclusion) par rapport à sont les sommets de poids le plus fort (somme des poids des arêtes adjacentes). On en déduit alors l'algorithme suivant :

  • On commence par trier les sommets par poids décroissant
  • On calcule pour le premier sa coupe par rapport à , et on en fait un cluster.
  • on itère pour chaque sommet suivant :
    • s'il appartient à un cluster, on ne fait rien, sa coupe par rapport à sera incluse dans le cluster
    • sinon, on calcule sa coupe par rapport à et on en fait un cluster. Il n'est pas impossible que ce nouveau cluster contienne intégralement un ou plusieurs clusters déjà calculés, mais ce n'est pas un problème. En aucun cas le nouveau cluster ne peut contenir une partie stricte non vide d'un cluster déjà créé. On remplace donc simplement les anciens clusters par le nouveau qui les englobe.

Comme dit auparavant, il est rare que la coupe d'un sommet par rapport à soit intégralement contenue dans celle d'un sommet de poids plus faible. Bien qu'il n'y ait pas de garantie théorique, empiriquement, le nombre de calcul de coupes minimales à faire évolue asymptotiquement comme le nombre final de cluster renvoyé par l'algorithme.

Hiérarchie de clusters

Comme dit précédemment, un grand conduira à plus de clusters et un petit, à des clusters plus gros. Plus intéressant, on remarque que les clusters obtenus pour seront systématiquement inclus dans les clusters obtenus pour . On peut alors par exemple construire un arbre de clusters en calculant le clustering pour plusieurs valeurs de .

Plutôt que de refaire le calcul à chaque fois, une possibilité plus rapide est de commencer par une grande valeur de (donc des petits clusters), puis de fusionner les sommets d'un même cluster avant de recommencer pour plus petit. On crée en fait un méta-sommet comprenant tous les sommets d'un même cluster et on relie les clusters par des méta arêtes dont le poids est la somme des poids des arêtes entre les deux clusters. On obtient toujours le même clustering que si on avait fait tourner l'algorithme sur le graphe de départ, mais on a beaucoup moins de sommets et les calculs sont donc plus rapides.

CutClustering en pratique

Implémentation

L'algorithme CutClustering a été implémenté sous Tulip. Le code produit est contenu dans l'archive suivante : clustering.tar.gz. On peut le charger et le lancer directement sur le graphe à clusteriser. L'utilisateur peut changer à sa guise la valeur du paramètre alpha. Le programme affichera alors dans la console de Tulip quel sommet a été placé dans quel cluster et le nombre total de cluster résultant. Le code ne permet mallheureusement pas de manipuler les graphes pondérés, et toutes les arêtes du graphe en entrée ont un poids égal à un, mais l'utilisateur peut tout de même donner à une valeur non entière (les résultats sont triviaux pour 0 (un cluster) et 1 ou plus( clusters)). Les commentaires indiquent comment étendre le code aux graphes pondérés.

La recherche de coupes minimales utilise l'algorithme de Ford-Fulkerson, un algorithme conçu à la base pour résoudre le problème dual de flots maximaux. Une fois que l'algorithme de Ford-Fulkerson ne trouve plus de chemin améliorant entre la source et le puits , on sait qu'on a atteint le flot maximal et donc que la coupe minimale est saturée. Dans le graphe résiduel, la composante connexe de est alors sa coupe optimale par rapport à .

Des résultats décevants sur certaines classes de graphes

Un constat qui s'impose rapidement en testant l'algorithme sur diverses classes de graphes est à quel point il est difficile d'obtenir des clusterings non triviaux. Tulip permet par exemple de simuler des grilles approchées. Les points ont alors une position donnée et sont reliés avec les sommets les plus proches. Bien que le graphe soit relativement loin d'une union de cliques disjointes, ces graphes contiennent tout de même des zones de fortes densité et se prêtent largement mieux au clustering que des graphes complètement aléatoires, voire bipartis. On pourrait alors attendre d'un algorithme de clustering qu'il regroupe les sommets par proximité géographique. Malheureusement, dans les graphes “en grille”, la meilleure coupe entre un point et un point consiste bien souvent à isoler l'un des deux sommets dans un singleton.

Les bornes théoriques sont évidemment respectées, mais il en ressort que pour certaines applications, les critères énoncés en première partie traduisent assez mal les attentes réelles du clustering et le résultat est inintéressant et inexploitable. Par exemple, dans le cas d'un graphe où les nœuds sont placés géographiquement, il est normal que deux clusters adjacents soient reliés et ne minimiser que la coupe maximale entre deux clusters n'est pas forcément pertinent.

Les meilleurs résultats ont été obtenus en générant des graphes parfaitement clusterisés (union de cliques disjointes) et en faisant des modifications locales aléatoires (ajout/suppression d'arêtes). Les arêtes inter-clusters sont alors réparties plus uniformément entre les clusters et les clusters ne contiennent pas de sommets “frontières” reliés à beaucoup de sommets extérieurs, ce qui permet à l'algorithme de donner des résultats très satisfaisants (retrouver le clustering parfait initial). Ce ne sont toutefois pas ces cas qui ont le plus grand intérêt pratique.

Conclusion

L'algorithme étudié propose une solution rapide et élégante à un problème d'optimisation difficile. La complexité est essentiellement dictée par l'algorithme de Ford-Fulkerson, qui, malgré des bornes théoriques élevées, est très bon dans la pratique. De plus, l'optimisation proposée dans la section complexité permet de réduire significativement le temps de calcul. À noter tout de même que comme pour tous les algorithmes d'optimisation, les résultats obtenus ne seront satisfaisants que dans la mesure où les grandeurs sur lesquelles portent l'optimisation traduisent réellement les attentes de l'utilisateur.

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/bellitto_thomas/thomas_bellito.txt · Last modified: 2014/01/17 13:16 by tbellitto