Classification Automatique / Clustering
Travaux Pratiques
Objectifs
Programmer quelques méthodes simples de clustering, évaluer la qualité d'une partition, leur performance, comparer les méthodes, ...
Evaluation
Rapport présentant l'implémentation algorithmique des méthodes, les résultats obtenus ainsi qu'une petite discussion autour des résultats...
Données de travail
On dispose de 3 jeux de données de 1000 échantillons dans RxR (data1.txt, data2.txt, data3.txt) sur lesquels on va tester les différentes méthodes de clustering.
Visualiser ces données et évaluer qualitativement la répartition des points.
Clustering séquentiel
Dans le clustering séquentiel (algorithme de classification à seuil ou classification en ligne), on ne fixe pas le nombre de clusters mais un seuil de proximité permettant d'affecter un point à un prototype (le centre du cluster).
Programmer un tel algorithme (le seuil de proximité sera le seul paramètre). Le tester sur les 3 jeux de données avec différentes valeurs de seuil. Evaluer de façon quantitative la qualité des partitions obtenues. Conclusion.
Montrer que la partition finale dépend du seuil de proximité fixé mais aussi et surtout de l'ordre dans lequel les points à classer sont présentés. Proposer des solutions pour résoudre ce problème. Eventuellement les programmer. Conclusion.
K-means
Dans les k-means, le nombre k de clusters est fixé au départ. A partir d'une partition initiale (k moyennes choisies au hasard), on cherche à améliorer itérativement la partition en minimisant un certain critère.
Choisir un critère. Programmer l'algorithme des k-means avec k comme paramètre. Le tester sur les 3 jeux de données avec différentes valeurs de k. Evaluer de façon quantitative la qualité des partitions obtenues. Conclusion.
Montrer que la partition finale obtenue est indépendante du choix inital des k moyennes mais que la vitesse de convergence dépend de ces moyennes initiales. Proposer des solutions pour résoudre ce problème. Eventuellement les programmer. Conclusion.
Nuées dynamiques
Les nuées dynamiques sont une généralisation des k-means. Le principe de l'algorithme est exactement le même mais cette fois-ci le cluster n'est pas représenté par son centre mais par un noyau (ensemble de points représentatifs du cluster).
Choisir un noyau. Programmer cet algorithme avec comme paramètres le nombre de clusters et le nombre maximal d'itérations. Le tester sur les 3 jeux de données avec différentes valeurs des 2 paramètres. Evaluer de façon quantitative la qualité des partitions obtenues. Conclusion.
Montrer que la partition finale obtenue dépend du tirage des noyaux initiaux. Proposer des solutions pour résoudre ce problème. Eventuellement les programmer. Conclusion.
Classification Ascendante Hiérarchique
La classification ascendante hiérarchique (ou CAH) procède par fusions successives d'ensembles de points (clusters): en considérant initialement tous les points comme des clusters singletons, on fusionne à chaque étape les 2 clusters les plus proches au sens d'une distance, jusqu'à obtenir un seul cluster contenant tous les points.
Le code matlab (cah.zip) permet de construire une hiérarchie et d'afficher le dendogramme associé. Tester le code sur les 3 jeux de données avec les deux distances proposées (lien minimum et lien maximum). Programmer la construction d'une hiérarchie avec le critère d'inertie de Ward. Comparer les hiérarchies obtenues. Conclusion.
Montrer que l'on peut faire varier la granularité de la typologie finale en programmant le choix du ou des points de coupure dans la hiérarchie. Conclusion.
Synthèse
Comparer les performances obtenues (temps de calcul, qualité des partitions, forme des clusters,...) par chacune des méthodes sur les 3 jeux de données. Conclusion.
Return to my Home Page
Last updated: May 2008