Clustering : FDPC, k-means et HDBSCAN

Télécharger le fichier original (Mémoire de fin d’études)

Fast Density Peak Clustering (FDPC)

L’algorithme de clustering FDPC [48] est un algorithme basé sur la densité capable de mettre en évidence des clusters non-convexes en donnant une règle de décision pratique pour identifier les groupes de manière pertinente.
Tout comme pour l’algorithme Mean-Shift [9], les centres de clusters, que nous préférons appeler cœurs de clusters (car ils ne sont pas obligatoirement au centre de leur cluster) sont définis comme des maximums locaux de densité. Autrement dit, un cœur de cluster est défini comme un point de relativement haute densité dont tous les voisins ont une densité plus faible et qui est éloigné de tout autre maximum local.
Cette innovante méthode qui a suscité l’intérêt de nombreux chercheurs (en moyenne une citation tous les trois jours depuis sa parution) présente à la fois des résultats très intéressants mais aussi des limitations très sévères.
Son premier inconvénient est que sa complexité est telle qu’il est impensable de l’appliquer sur des jeux de données très volumineux. Aussi sa manière d’estimer la densité se fait à travers un paramètre dc très diﬃcile à choisir et qui a pourtant un impact très important sur les résultats. Enfin, la phase de sélection des cœurs né-cessite l’expertise humaine pour être pertinente et peut malgré tout provoquer des erreurs. De plus l’aﬃliation des points non-cœurs aux clusters n’est pas plus robuste.
Beaucoup de chercheurs se sont penchés sur cet algorithme en vue de l’amélio-rer ou le modifier légèrement afin de pouvoir l’appliquer à certains problèmes spéci-fiques. Il a été utilisé avec succès pour une étude de comportements de consommation d’électricité [60], pour du clustering de textes [34], pour partitionner des sons via décomposition en sous-mots [64], pour la modélisation et surveillance de processus de production industriels [44], sur des données médicales [30] et a été légèrement modifié pour travailler à la segmentation d’images [18, 52, 8], pour la détection d’outliers [13] et enfin pour la sélection de bandes hyper-spectrales [22]. Dans [40] on mène une étude comparative de k-means et FDPC et conclut que ce dernier est moins rapide mais fournit un clustering plus qualitatif.

Fonctionnement et limites

Phase 1 : estimation des densités

Considérons l’échantillon de points (xi)i=1…N ∈ Rp. Lors de la première phase de FDPC, les distances euclidiennes dij entre tous les couples {(xi, xj), i 6= j} doivent être calculées. Ensuite un paramètre dc qui reflète une distance est fixé afin de compter, pour chacun des xi, le nombre de points qui sont à une distance inférieure ou égale à dc. Ce compte, pouvant être représenté comme le nombre de points appartenant à la boule B(xi, dc) de centre xi et de rayon dc, sert de mesure de la densité locale.

Phase 2 : détection des cœurs et clustering

L’étape suivante consiste en la recherche, pour chaque point xi, du point le plus proche parmi ceux de plus haute densité. On l’appellera NPHD pour « Nearest Point of Higher Density ». La distance séparant xi de son NPHD, qui est notée δi et s’obtient grâce à la formule δi = min (dij), j:ρj>ρi est utilisée conjointement aux comptes de densité pour trouver les cœurs de clusters. En eﬀet, une fois ces deux variables obtenues pour chaque observation, on trace le nuage de points appelé graphe de décision, avec en abscisse les densités ρi et en ordonnée δi. Les cœurs de clusters sont alors définis comme les outliers dans ce graphe. Un exemple d’un tel graphe est donné dans l’image du milieu de la figure 1.3. En d’autres termes, les cœurs sont les points possédant à la fois une très haute densité, mais aussi une grande distance δi. Le point de plus haute densité xk ne possède pas de NPHD donc par convention est fixé à δk = maxj(dij).
Une fois les cœurs déterminés, les autres points non-cœurs sont attribués récursive-ment au même cluster que leur NPHD. L’algorithmique entière de FDPC est détaillée dans l’Algorithme 1 et un exemple des résultats qu’il peut obtenir est illustré dans la figure 1.3.
Comme nous l’avons déjà dit, cet algorithme montre des résultats intéressants mais souﬀre de nombreux problèmes très contraignants. Voici les problèmes que nous avons pu identifier concernant FDPC :
— Dès la première étape FDPC doit calculer et enregistrer autant de distances qu’il y a de couples de points dans l’échantillon ce qui mène à une complexité de l’ordre de O(N2). Ce premier point limite déjà cet algorithme à de relativement petit jeux de données.
— Le choix de dc est diﬃcile alors qu’il a un impact très important sur toutes les étapes de l’algorithme. De plus puisque dc est statique, cette méthode est incapable de gérer correctement à la fois les zones denses et les zones peu denses. En eﬀet, s’il est bien choisi pour représenter une zone dense donnée, il sera alors trop petit pour bien représenter les zones moins denses (et vice versa).
— Aucune règle de décision automatique satisfaisante n’est donnée pour détec-ter les cœurs dans le graphe de décision. Dans l’illustration de la figure 1.3 les cœurs ressortent très bien et sont bien séparés des non-cœurs mais dans de nombreux cas réels il y a toute une continuité entre cœurs et non-cœurs. Inévitablement le choix des cœurs est donc relativement approximatif dès que le jeu de données monte en complexité.
— De plus, certains points peuvent avoir une grande densité et un grand δ à la fois, donc détectés en tant que cœurs de cluster, alors qu’ils ne doivent clairement pas être considérés comme tels, mettant directement en cause leur définition de cœur de cluster. C’est le cas dans l’exemple illustré dans la figure 1.4 où FDPC détecte deux cœurs de clusters au lieu d’un seul (ce dernier suivant une distribution uniforme 1d). En eﬀet dans cet exemple où le point en rouge à gauche (fig A) ne se démarque des voisins qu’à cause de l’aléa, il se retrouve identifié à tort comme un cœur de cluster, à la condition que δ soit considéré comme grand.
— Enfin, la définition de NPHD utilisé dans FDPC qui lie deux points pour en déduire la distance qui les sépare δ ne prend pas en compte la densité qui sépare ces deux points. Ce problème peut mener à de sérieuses erreur d’aﬀectation comme on peut le voir illustré dans la figure 1.5. On suppose pour cet exemple que FDPC ne s’est pas trompé et a détecté correctement les deux cœurs de cluster, le rouge et le bleu. Avec leur définition de NPHD, le point vert trouve comme NPHD le point bleu car il est pus proche que le rouge, et donc hérite du label du cluster bleu et le propage récursivement de NPHD en NPHD jusqu’à la moitié du cluster de gauche.

Extensions récentes de FDPC

Afin de dépasser certaines des limitations soulignées plus haut, un nombre de tra-vaux non négligeable ont été eﬀectués dans le but d’améliorer l’algorithme originel. La plupart ne se concentrent que sur un seul des problèmes à la fois, suivant l’application qu’ils veulent en faire.

Gérer de gros volumes de données

La seule méthode ayant pour but d’améliorer FDPC sur ce point est une extension proposée par [33] dans le but de traiter de nombreuses trajectoires de taxis (données GPS bi-dimensionnelles). L’approche ici consiste en la projection du jeu de données pour former une image de la densité qui est utilisée pour dessiner le contour des clusters. Cette méthode a montré de bon résultats mais est limité à des jeux de données bi-dimensionnels uniquement.

Le choix de dc

Le choix de base pour dc faisant apparemment consensus est de le fixer à la valeur telle que le compte de densité moyen induit se trouve égal à 2% de N (ρ¯ = 2%N selon [13]). Un autre choix moins trivial et basé sur l’entropie a été proposé par [58], mais ce dernier coûte un nombre considérable d’opérations le rendant inapplicable dès que N devient grand. Il existe deux méthodes qui remplacent l’estimation de la densité (1.1) par une non-paramétrique Les deux s’accordent à considérer la densité comme haute si elle dépasse la moyenne, c’est à dire si ρi > mean(ρ). De plus ils ajoutent une étape d’agrégation des clusters : Deux clusters seront agrégés s’il existe un point x qui appartient au premier cluster et un point y qui appartient au second tels que la distance d(x, y) soit inférieure à dc.
Un autre algorithme basé sur dc est présenté par [32]. Afin de prendre en compte la densité avoisinante lors de la sélection des cœurs, les concepts de DBSCAN [15] sont couplés à la « divide and conquer strategy ». Les cœurs potentiels sont soumis à un test supplémentaire : si le point considéré est densité-atteignable depuis un cœur de cluster alors ce point est ignoré et ne deviendra pas cœur de cluster.

Autres améliorations

[62] utilise les k plus proches voisins pour améliorer la règle d’aﬃliation aux clus-ters des points restants, qui ne définissent pas un cœur de cluster. Donc après la phase de détection des cœurs, les outliers restants qui possèdent un grand δiK = maxj∈KNNi (dij) sont supprimés et considérés comme du bruit.
Ensuite les points restants sont assignés à travers une certaine stratégie : le label d’un cœur xc est propagé sur ses voisins non aﬃliés qui sont à une distance inférieure P à j∈KNNc dcj/K et ces points récemment aﬃliés propagent récursivement leur label selon la même logique.
Les points qui ont survécu à cette première passe sont soumis à une deuxième stratégie dont l’aspect principal réside en l’apprentissage de la probabilité pci qu’un point xi appartienne à au cluster c. Après avoir établi ces probabilités, chaque xi est naturellement assigné au cluster le plus probable.
Un dérivé de FDPC qui peut gérer des densités inégales a été proposé par [66]. Les densités ρi et distances δi sont remplacées par des variables au comportement similaires.

k-means

Avec ses 60 ans d’ancienneté, k-moyennes, mais plus souvent appelé k-means [36], est l’un des plus connus et des plus anciens algorithmes de classification automatique non-supervisée. Cette heuristique est vouée à résoudre le problème de partitionnement modélisé de la manière suivante. Soit (x1, …, xN ) l’échantillon constitué de N points que nous voulons partitionner. Pour un paramètre k fixé par l’utilisateur, l’algorithme k-means cherche à partitionner les observations xi en k ensembles C = {C1, …, Ck} de manière optimale.
L’initialisation des moyennes joue un rôle important sur les résultats en sortie. Si elles sont mal initialisées, on risque de faire converger l’algorithme sur un minimum local potentiellement éloigné du minimum global. La manière basique (méthode de Forgy) est d’initialiser les k moyennes initiales à k données d’entrée choisies aléa-toirement. Des variantes de l’algorithme de base ont donc été proposés comme k-means++ [3] dont la stratégie d’initialisation est également de choisir aléatoirement mais en abaissant les chances de choisir un point proche des centres déjà initialisés par exemple.
Les moyennes peuvent également être remplacées par des médianes [26] ou en-core par la somme de fonctions variées comme l’algorithme Fuzzy C-means [14] où l’appartenance n’est plus exclusive mais traduite par un degré d’appartenance.
Les distances aux moyennes aussi peuvent être remplacées par une probabilité d’appartenance au groupe qui est supposé gaussien, ce qui donne lieu aux algorithmes de type Espérance-Maximisation EM [11].
Cet algorithme et ses variantes sont très eﬃcaces lorsque les données sont réparties en amas gaussiens mais leur eﬃcacité s’eﬀondre dès que les clusters sont de forme arbitraires, particulièrement pour des clusters non-concentriques.
Aussi, le comportement de cet algorithme peut énormément varier selon le para-mètre k qui est bien souvent diﬃcile à déterminer compte tenu du cadre non-supervisé.
Cependant la complexité de cet algorithme est exemplaire lorsqu’elle utilise les arbres k-d (voir section 2.1.1) puisqu’elle se trouve ainsi égale à O(kT N) où T est le nombre d’itérations et N le nombre d’observations. Ainsi, bien implémentée, cette heuristique se trouve être une des plus rapides ce qui participe en partie à sa renommée et celle de ses variantes.

DBSCAN et HDBSCAN

DBSCAN

DBSCAN [15] est un algorithme de regroupement basé sur la densité qui a été pensé pour découvrir des partitions de forme arbitraire. Un point important dans la compréhension de cet algorithme est que pour appartenir à un cluster un objet doit être un objet cœur, c’est à dire que chaque élément doit contenir un certain nombre minimum de points dans son voisinage. Les points sont liés entre eux au sein d’un même cluster s’ils possèdent ces cœurs en tant que voisins.
Cette idée repose donc sur une notion de voisinage et sur un seuil qui détermine la densité minimum acceptable qui seront définis plus bas. Il ne possède oﬃciellement qu’un paramètre à choisir (bien qu’un second apparaisse finalement mais est fixé de manière hasardeuse par les auteurs) et une aide est fournie afin d’eﬀectuer ce choix.
Cet algorithme introduit entre autres les quatre définitions suivantes qu’il faut expli-citer avant d’aller plus loin dans les explications.

Table des matières

Introduction
1 Clustering : FDPC, k-means et HDBSCAN
1.1 Machine learning
1.1.1 Classification automatique
1.1.2 Partitionnement de données (Clustering)
1.2 Fast Density Peak Clustering (FDPC)
1.2.1 Fonctionnement et limites
Phase 1 : estimation des densités
Phase 2 : détection des coeurs et clustering
1.2.2 Extensions récentes de FDPC
Gérer de gros volumes de données
Le choix de dc
Sélection des coeurs
Autres améliorations
1.3 k-means
1.4 DBSCAN et HDBSCAN
1.4.1 DBSCAN
1.4.2 HDBSCAN
2 Outils auxiliaires
2.1 Arbres de recherche et hypersphères
2.1.1 Arbres de recherche
Les arbres binaires
Arbres binaires de recherche
Arbres k-d
2.1.2 Volume de superposition entre deux n-sphères
Volume d’une calotte d’hypersphère
Volume de superposition entre deux n-sphères quelconques
Volume de superposition entre deux n-sphères de même rayon
2.2 Pré-traitement de trajectoires d’avions
2.2.1 Données fonctionnelles et description de données de vol
2.2.2 Interpolation via B-splines cubiques
Base de fonctions et base de splines
Interpolation
2.2.3 Application et reconstruction des trajectoires
3 Procedure CM itérée à fenêtre décroissante (ICMDW)
3.1 Principe général de ICMDW
3.2 Procédure pre-Cover Map (pre-CM)
3.3 Procédure CM itérée à fenêtre décroissante (ICMDW)
3.3.1 Définitions, notations et présentation intuitive de ICMDW
3.3.2 ICMDW : le sous algorithme CM et son itération
4 Exploitation du réseau de boules : carte de densité et clustering
4.1 Cartes de densité
4.1.1 Densité de type surface-grille
4.1.2 Densité générationnelle
4.1.3 Limitations
Boules terminales non-représentatives
Boules tardives
Trous dans la densité
Limitations mineures
4.2 Du réseau de boules au Partitionnement
4.2.1 Adaptation naïve de FDPC à notre structure arborescente
Élection des champions (voir Algorithme 6)
Sélection des coeurs et affiliation
4.2.2 Partitionnement robuste de Ballstering
5 Paramétrage et Complexité théorique
5.1 Choix des paramètres
5.1.1 Coefficient de décroissance R
5.1.2 Le rayon initial d0c
5.2 Complexité de Ballstering
6 Résultats empiriques
6.1 Résultats expérimentaux sur données simulées
6.1.1 Évaluation de la qualité
Birch1
Birch3
Multishapes
Évaluation via critères externes
6.2 Évaluation de la complexité et scaling
6.3 Application aux relevés du trafic aérien français
Conclusion et perspectives
A Diverses représentations des trajectoires d’avions
B Compléments empiriques : choix du paramètre Nmin et qualité du clustering
C Algorithmique de DBSCAN