Les problèmes de clustering visent à séparer un jeu de donner en plusieurs ensembles, appelés clusters, tel que les points ce trouvant à l'intérieur d'un cluster soit le plus proches possible les uns des autres et le plus éloigné possible de ceux des autres clusters. La proximité entre deux points est définie par l'utilisateur et dépand du type de donnée étudier.
L'algorithme des K-Moyennes est un algorithme de Clustering par optimisation. Le but est de trouver l'ensemble
avec
1. Inialiser les clusters avec des valeurs aléatoirement
choisie parmi les points. TWCV[0] = +∞, compte=0.
2. Assigner chaque point au cluster dont le centre lui est le
plus proche (ie trouver i* tel ||x-c_i*|| = min_i(||x-c_i||)).
3. Calculer TWCV[compte+1].
4. Si TWCV[compte+1] < TWCV[compte], incrémenter compte de 1
puis reprendre à l'étape 2.
Sinon, terminer le programme.
L'algorithme ne converge pas vers le minimum global mais vers un minimum local. Ce minimum est fortement impacté par le choix des points d'initialisation qui est aléatoire. Il est donc conseillé de relancer plusieur fois l'algorithme et de choisir le résultat ayant la plus petite TWCV.
Contrairement à l'algorithme des K-Moyennes, DBSCAN (density-based spatial clustering of applications with noise) est un algorithme de clustering à densité. On définie un cluster par un nombre de points minimum
L'
Pour tous points
$A$ et$B$ du cluster, il existe une suite de points du cluster$(x_i)$ avec$x_0= A$ et$x_{i+1} \in \varepsilon\text{-voisinage}(x_i)$ tel que$B$ appartient à l'ensemble $$\bigcup_i \text{$\varepsilon$ -voisinage}(x_i).$$
Voici la reproduction de l'algorithme DBSCAN, tel que proposé par Kriegel et Xu dans leur article de 1996.
DBSCAN (SetOfPoints, Eps, MinPts)
// SetOfPoints is UNCLASSIFIED
ClusterId := nextId(NOISE);
FOR i FROM 1 TO SetOfPoints.size DO
Point := SetOfPoints.get(i);
IF Point.CiId = UNCLASSIFIED THEN
IF ExpandCluster(SetOfPoints, Point,
ClusterId, Eps, MinPts) THEN
ClusterId := nextId(ClusterId)
END IF
END IF
END FOR
END;
ExpandCluster (SetOfPoints, Point, CiId, Eps,
MinPts) : Boolean;
seeds := SetOfPoints. regionQuery (Point, Eps )
IF seeds.size<MinPts THEN // no core point
SetOfPoint. changeCl Id (Point, NOISE)
RETURN False;
ELSE // all points in seeds are density-
// reachable from Point
SetOfpoints. changeCiIds ( seeds, C1 Id)
seeds.delete (Point)
WHILE seeds <> Empty DO
currentP := seeds.first()
result := setofPoints.regionQuery(currentP,Eps)
IF result.size >= MinPts THEN
FOR i FROM 1 TO result.size DO
resultP := result.get(i)
IF resultP. CiId
IN (UNCLASSIFIED, NOISE} THEN
IF resultP.CiId = UNCLASSIFIED THEN
seeds, append (resultP)
END IF;
SetOfPoints. changeCiId ( resultP, CiId)
END IF; // UNCLASSIFIED or NOISE
END FOR ;
END IF; // result.size >= MinPts
seeds, delete (currentP)
END WHILE; // seeds <> Empty
RETURN True ;
END IF
END;
Dans le premier exemple on est face a un exemple de clusters bien définie à la fois dense et séparé de l'autre cluster ainsi DBSCAN eT KMeans avec
Dans le second example, on s'attendrait à avoir deux clusters le premier étant le cercle central et le second le cercle exterieur mai aucun des deux algorithmes ne parvient à se résultat.
KMeans sépare les points en deux groupes selon une droite. Ce comportant est du à la nature de Kmean qui cherche à diviser les points en
Les algorithmes de clustering étant des algorithmes non supervisés, il est difficile de définir les résultats qui sont sensé être obtenu. La définition des clusters la plus approprié ainsi que celle de la norme utilisé et les paramètres de la méthodes influence grandement le résultat de la méthodes. Il s'agit donc d'utiliser ses algorithmes précautionneusement et de bien définir les objectifs fixés.
R. Xu and D. C. Wunsch, "Survey of Clustering Algorithms," IEEE Transactions on Neural Networks, Institute of Electrical and Electronics Engineers (IEEE), May 2005.
https://en.wikipedia.org/wiki/K-means_clustering, consulté le 5 mars 2021
https://en.wikipedia.org/wiki/DBSCAN, consulté le 8 mars 2021
Ester, Kriegel, Sander, Xu. (1996). “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databaseswith Noise” in Proceedings of the 2nd International Conference on Knowledge Discovery and Data mining.
# apt install gnuplot-qt
En mode RELEASE
cmake utilise la sortie graphique si GNUPLOT est disponible, en mode DBG
, il faut affecter TRUE
à la variable USE_SCIPLOT
$ cmake -D USE_SCIPLOT=TRUE ..
$ make
Dans le dossier .build/
, utiliser l'exécutable ./run
pour lancer le programme d'exemple ou ./test_clustering
pour effectuer les tests.
Le programme utilise une sortie graphique pour afficher les clusters ainsi que la sortie standard pour afficher le rapport d'exécution des algorithmes. Attention, ce rapport peut excéder la capacité d'affichage du terminal si le nombre de points est trop élévé.
Les tests utilisent la librairie Googletest, ./test_clustering
peut prendre en argument tous ceux définis par la librarie.
En particulier ./test_clustering -h
permet de lister les argumements possibles et ./test_clustering --filter=<regex>
permet de n'exécuter qu'une partie des tests.