Agorithmes de clustering : Du début à l’état de l’art

Ce n’est pas un mauvais moment pour être un scientifique des données. Les personnes sérieuses peuvent trouver de l’intérêt pour vous si vous orientez la conversation vers le « Big Data », et le reste de la foule des fêtards sera intrigué lorsque vous mentionnerez « l’intelligence artificielle » et « l’apprentissage automatique ». Même Google pense que vous n’êtes pas mauvais, et que vous vous améliorez encore. Il y a beaucoup d’algorithmes « intelligents » qui aident les spécialistes des données à faire leur travail de magicien. Tout cela peut sembler compliqué, mais si nous comprenons et organisons un peu les algorithmes, il n’est même pas si difficile de trouver et d’appliquer celui dont nous avons besoin.

Les cours sur l’exploration de données ou l’apprentissage automatique commencent généralement par le clustering, car il est à la fois simple et utile. C’est une partie importante d’un domaine un peu plus large de l’apprentissage non supervisé, où les données que nous voulons décrire ne sont pas étiquetées. Dans la plupart des cas, l’utilisateur ne nous a pas donné beaucoup d’informations sur le résultat attendu. L’algorithme ne dispose que des données et doit faire du mieux qu’il peut. Dans notre cas, il doit effectuer un regroupement, c’est-à-dire séparer les données en groupes (clusters) qui contiennent des points de données similaires, tandis que la dissimilarité entre les groupes est aussi élevée que possible. Les points de données peuvent représenter n’importe quoi, par exemple nos clients. Le clustering peut être utile si nous voulons, par exemple, regrouper des utilisateurs similaires et ensuite lancer différentes campagnes de marketing sur chaque cluster.

K-Means Clustering

Après l’introduction nécessaire, les cours de Data Mining se poursuivent toujours avec K-Means ; un algorithme de clustering efficace, largement utilisé et polyvalent. Avant de l’exécuter réellement, nous devons définir une fonction de distance entre les points de données (par exemple, la distance euclidienne si nous voulons regrouper les points dans l’espace), et nous devons définir le nombre de clusters que nous voulons (k).

L’algorithme commence par sélectionner k points comme centroïdes de départ (« centres » des clusters). Nous pouvons simplement sélectionner n’importe quels k points aléatoires, ou nous pouvons utiliser une autre approche, mais choisir des points aléatoires est un bon début. Ensuite, nous répétons itérativement deux étapes :

1. Étape d’affectation : chacun des m points de notre ensemble de données est affecté à un cluster qui est représenté par le plus proche des k centroïdes. Pour chaque point, nous calculons les distances à chaque centroïde, et choisissons simplement le moins distant.

2. Étape de mise à jour : pour chaque cluster, un nouveau centroïde est calculé comme la moyenne de tous les points du cluster. A partir de l’étape précédente, nous avons un ensemble de points qui sont affectés à un cluster. Maintenant, pour chacun de ces ensembles, on calcule une moyenne que l’on déclare être un nouveau centroïde du cluster.

Après chaque itération, les centroïdes se déplacent lentement, et la distance totale de chaque point à son centroïde assigné devient de plus en plus faible. Les deux étapes sont alternées jusqu’à convergence, c’est-à-dire jusqu’à ce qu’il n’y ait plus de changement dans l’affectation des clusters. Après un certain nombre d’itérations, le même ensemble de points sera attribué à chaque centroïde, ce qui conduira à nouveau aux mêmes centroïdes. K-Means est garanti pour converger vers un optimum local. Cependant, cela ne doit pas nécessairement être la meilleure solution globale (optimum global).

Le résultat final du clustering peut dépendre de la sélection des centroïdes initiaux, c’est pourquoi beaucoup de réflexions ont été menées sur ce problème. Une solution simple consiste simplement à exécuter K-Means plusieurs fois avec des affectations initiales aléatoires. Nous pouvons alors sélectionner le meilleur résultat en prenant celui avec la somme minimale des distances de chaque point à son cluster – la valeur d’erreur que nous essayons de minimiser en premier lieu.

D’autres approches pour sélectionner les points initiaux peuvent s’appuyer sur la sélection de points distants. Cela peut conduire à de meilleurs résultats, mais nous pouvons avoir un problème avec les valeurs aberrantes, ces rares points isolés qui sont juste « off » qui peuvent juste être quelques erreurs. Comme ils sont éloignés de tout groupe significatif, chacun de ces points peut finir par constituer son propre « groupe ». Un bon équilibre est la variante K-Means++ , dont l’initialisation choisira toujours des points aléatoires, mais avec une probabilité proportionnelle à la distance au carré des centroïdes précédemment assignés. Les points qui sont plus éloignés auront une probabilité plus élevée d’être sélectionnés comme centroïdes de départ. Par conséquent, s’il y a un groupe de points, la probabilité qu’un point du groupe soit sélectionné augmente également au fur et à mesure que leurs probabilités s’additionnent, ce qui résout le problème des points aberrants que nous avons mentionné.

K-Means++ est également l’initialisation par défaut de l’implémentation K-Means de Scikit-learn de Python. Si vous utilisez Python, cela peut être votre bibliothèque de choix. Pour Java, la bibliothèque Weka peut être un bon début :

Java (Weka)

// Load some dataInstances data = DataSource.read("data.arff");// Create the modelSimpleKMeans kMeans = new SimpleKMeans();// We want three clusterskMeans.setNumClusters(3);// Run K-MeanskMeans.buildClusterer(data);// Print the centroidsInstances centroids = kMeans.getClusterCentroids();for (Instance centroid: centroids) { System.out.println(centroid);}// Print cluster membership for each instancefor (Instance point: data) { System.out.println(point + " is in cluster " + kMeans.clusterInstance(point));}

Python (Scikit-learn)

> >> from sklearn import cluster, datasets> >> iris = datasets.loadiris()> >> Xiris = iris.data> >> yiris = iris.target> >> kmeans = cluster.KMeans(nclusters=3)> >> kmeans.fit(Xiris)KMeans(copy_x=True, init='k-means++', ...> >> print(kmeans.labels)> >> print(yiris)

Dans l’exemple Python ci-dessus, nous avons utilisé un jeu de données d’exemple standard ‘Iris’, qui contient les dimensions des pétales et des sépales de fleurs pour trois espèces différentes d’iris. Nous les avons regroupés en trois clusters, et avons comparé les clusters obtenus aux espèces réelles (cible), pour voir qu’ils correspondent parfaitement.

Dans ce cas, nous savions qu’il y avait trois clusters (espèces) différents, et K-Means a reconnu correctement ceux qui vont ensemble. Mais, comment choisir un bon nombre de clusters k en général ? Ce genre de questions est assez courant en apprentissage automatique. Si nous demandons plus de clusters, ils seront plus petits, et donc l’erreur totale (total des distances entre les points et les clusters qui leur sont attribués) sera plus petite. Alors, est-ce une bonne idée de définir un k plus grand ? Nous pourrions finir par avoir k = m, c’est-à-dire que chaque point est son propre centroïde, chaque cluster n’ayant qu’un seul point. Oui, l’erreur totale est de 0, mais nous n’avons pas obtenu une description plus simple de nos données, et elle n’est pas assez générale pour couvrir les nouveaux points qui peuvent apparaître. C’est ce qu’on appelle l’overfitting, et nous ne voulons pas cela.

Une façon de traiter ce problème est d’inclure une certaine pénalité pour un plus grand nombre de clusters. Ainsi, nous essayons maintenant de minimiser non seulement l’erreur, mais l’erreur + la pénalité. L’erreur convergera simplement vers zéro lorsque nous augmenterons le nombre de clusters, mais la pénalité augmentera. À certains moments, le gain résultant de l’ajout d’un autre cluster sera inférieur à la pénalité introduite, et nous aurons le résultat optimal. Une solution qui utilise le critère d’information bayésien (BIC) à cette fin est appelée X-Means .

Une autre chose que nous devons définir correctement est la fonction de distance. Parfois, c’est une tâche simple, une tâche logique étant donné la nature des données. Pour les points dans l’espace, la distance euclidienne est une solution évidente, mais cela peut être délicat pour les caractéristiques de différentes  » unités « , pour les variables discrètes, etc. Cela peut nécessiter une grande connaissance du domaine. Nous pouvons également faire appel à l’apprentissage automatique. Nous pouvons en fait essayer d’apprendre la fonction de distance. Si nous disposons d’un ensemble d’entraînement de points dont nous savons comment ils doivent être regroupés (c’est-à-dire des points étiquetés avec leurs clusters), nous pouvons utiliser des techniques d’apprentissage supervisé pour trouver une bonne fonction, puis l’appliquer à notre ensemble cible qui n’est pas encore clusterisé.

La méthode utilisée dans K-Means, avec ses deux étapes alternées, ressemble à une méthode d’espérance-maximisation (EM). En fait, elle peut être considérée comme une version très simple de EM. Cependant, il ne doit pas être confondu avec l’algorithme de clustering EM plus élaboré, même s’il partage certains des mêmes principes.

Clustering EM

Ainsi, avec le clustering K-Means, chaque point est affecté à un seul cluster, et un cluster est décrit uniquement par son centroïde. Ce n’est pas très flexible, car nous pouvons avoir des problèmes avec les clusters qui se chevauchent, ou ceux qui ne sont pas de forme circulaire. Avec le clustering EM, nous pouvons maintenant aller un peu plus loin et décrire chaque cluster par son centroïde (moyenne), sa covariance (de sorte que nous pouvons avoir des clusters elliptiques) et son poids (la taille du cluster). La probabilité qu’un point appartienne à un cluster est maintenant donnée par une distribution de probabilité gaussienne multivariée (multivariée – dépendant de plusieurs variables). Cela signifie également que nous pouvons calculer la probabilité qu’un point soit sous une « cloche » gaussienne, c’est-à-dire la probabilité qu’un point appartienne à un cluster.

Nous commençons maintenant la procédure EM en calculant, pour chaque point, les probabilités qu’il appartienne à chacun des clusters actuels (qui, encore une fois, peuvent être créés aléatoirement au début). C’est l’étape E. Si un cluster est un très bon candidat pour un point, il aura une probabilité proche de un. Cependant, deux ou plusieurs grappes peuvent être des candidats acceptables, de sorte que le point a une distribution de probabilités sur les grappes. Cette propriété de l’algorithme, des points n’appartenant pas de manière restreinte à un cluster est appelée « soft clustering ».

L’étape M recalcule maintenant les paramètres de chaque cluster, en utilisant les affectations des points à l’ensemble précédent de clusters. Pour calculer la nouvelle moyenne, la covariance et le poids d’un cluster, chaque donnée ponctuelle est pondérée par sa probabilité d’appartenance au cluster, telle que calculée à l’étape précédente.

L’alternance de ces deux étapes augmentera la log-vraisemblance totale jusqu’à ce qu’elle converge. Encore une fois, le maximum peut être local, donc nous pouvons exécuter l’algorithme plusieurs fois pour obtenir de meilleurs clusters.

Si nous voulons maintenant déterminer un seul cluster pour chaque point, nous pouvons simplement choisir le plus probable. Ayant un modèle de probabilité, nous pouvons également l’utiliser pour générer des données similaires, c’est-à-dire pour échantillonner plus de points qui sont similaires aux données que nous avons observées.

Propagation par affinité

La Propagation par affinité (PA) a été publiée par Frey et Dueck en 2007, et ne fait que gagner en popularité en raison de sa simplicité, de son applicabilité générale et de ses performances. Elle est en train de changer de statut, passant de l’état de l’art à la norme de facto.

Les principaux inconvénients de K-Means et des algorithmes similaires sont de devoir sélectionner le nombre de clusters, et de choisir l’ensemble initial de points. La propagation par affinité, au contraire, prend en entrée des mesures de similarité entre des paires de points de données, et considère simultanément tous les points de données comme des exemplaires potentiels. Des messages à valeur réelle sont échangés entre les points de données jusqu’à ce qu’un ensemble d’exemplaires de haute qualité et les clusters correspondants émergent progressivement.

En entrée, l’algorithme nous demande de fournir deux ensembles de données :

1. Similarités entre les points de données, représentant à quel point un point est bien adapté pour être l’exemplaire d’un autre. S’il n’y a pas de similarité entre deux points, comme dans le cas où ils ne peuvent pas appartenir au même cluster, cette similarité peut être omise ou fixée à -Infini selon l’implémentation.

2. Préférences, représentant l’aptitude de chaque point de données à être un exemplaire. Nous pouvons avoir des informations a priori sur les points qui pourraient être favorisés pour ce rôle, et donc nous pouvons le représenter par des préférences.

Les similitudes et les préférences sont souvent représentées par une seule matrice, où les valeurs sur la diagonale principale représentent les préférences. La représentation matricielle est bonne pour les ensembles de données denses. Lorsque les connexions entre les points sont clairsemées, il est plus pratique de ne pas stocker toute la matrice n x n en mémoire, mais plutôt de conserver une liste de similarités avec les points connectés. Derrière la scène, « échanger des messages entre les points » est la même chose que manipuler des matrices, et ce n’est qu’une question de perspective et d’implémentation.

L’algorithme passe ensuite par un certain nombre d’itérations, jusqu’à ce qu’il converge. Chaque itération comporte deux étapes de passage de messages :

1. Calcul des responsabilités : La responsabilité r(i, k) reflète les preuves accumulées pour savoir si le point k est bien adapté pour servir d’exemplaire pour le point i, en tenant compte des autres exemplaires potentiels pour le point i. La responsabilité est envoyée du point de données i au point exemplaire candidat k.

2. Calcul des disponibilités : La disponibilité a(i, k) reflète les preuves accumulées de l’opportunité pour le point i de choisir le point k comme exemplaire, en tenant compte du soutien des autres points pour que le point k soit un exemplaire. La disponibilité est envoyée du point k comme exemplaire candidat au point i.

Pour calculer les responsabilités, l’algorithme utilise les similarités originales et les disponibilités calculées dans l’itération précédente (initialement, toutes les disponibilités sont fixées à zéro). Les responsabilités sont fixées à la similarité d’entrée entre le point i et le point k comme son exemplaire, moins la plus grande somme de la similarité et de la disponibilité entre le point i et les autres exemplaires candidats. La logique derrière le calcul de la pertinence d’un point pour un exemplaire est qu’il est favorisé davantage si la préférence initiale a priori était plus élevée, mais la responsabilité devient plus faible lorsqu’il y a un point similaire qui se considère comme un bon candidat, il y a donc une « compétition » entre les deux jusqu’à ce que l’un soit décidé dans une certaine itération.

Le calcul des disponibilités, alors, utilise les responsabilités calculées comme preuve si chaque candidat ferait un bon exemplaire. La disponibilité a(i, k) est fixée à l’auto-responsabilité r(k, k) plus la somme des responsabilités positives que le candidat exemplaire k reçoit des autres points.

Enfin, nous pouvons avoir différents critères d’arrêt pour terminer la procédure, comme lorsque les changements de valeurs tombent sous un certain seuil, ou que le nombre maximum d’itérations est atteint. A n’importe quel moment de la procédure de Propagation par Affinité, la somme des matrices de Responsabilité (r) et de Disponibilité (a) nous donne l’information de clustering dont nous avons besoin : pour le point i, le k avec le maximum de r(i, k) + a(i, k) représente l’exemplar du point i. Ou, si nous avons seulement besoin de l’ensemble des exemplaires, nous pouvons balayer la diagonale principale. Si r(i, i) + a(i, i) > 0, le point i est un exemplaire.

Nous avons vu qu’avec K-Means et des algorithmes similaires, décider du nombre de clusters peut être délicat. Avec AP, nous n’avons pas à le spécifier explicitement, mais il peut quand même avoir besoin d’un certain réglage si nous obtenons soit plus ou moins de clusters que nous pouvons trouver optimal. Heureusement, en ajustant simplement les préférences, nous pouvons diminuer ou augmenter le nombre de clusters. Si l’on fixe les préférences à une valeur plus élevée, on obtiendra plus de clusters, car chaque point est « plus certain » de son aptitude à être un exemple et il est donc plus difficile de le « battre » et de l’inclure sous la « domination » d’un autre point. À l’inverse, si l’on fixe des préférences plus basses, on aura moins de clusters, comme s’ils disaient « non, non, s’il vous plaît, vous êtes un meilleur exemplaire, je vais rejoindre votre cluster ». En règle générale, nous pouvons fixer toutes les préférences à la similarité médiane pour un nombre moyen à important de clusters, ou à la similarité la plus faible pour un nombre modéré de clusters. Cependant, un couple d’exécutions avec l’ajustement des préférences peut être nécessaire pour obtenir le résultat qui correspond exactement à nos besoins.

La Propagation d’Affinité Hiérarchique mérite également d’être mentionnée, comme une variante de l’algorithme qui traite la complexité quadratique en divisant l’ensemble de données en un couple de sous-ensembles, en les regroupant séparément, puis en effectuant le deuxième niveau de regroupement.

En fin de compte…

Il y a toute une gamme d’algorithmes de clustering, chacun avec ses avantages et ses inconvénients concernant le type de données avec lesquelles ils, la complexité en temps, les faiblesses, et ainsi de suite. Pour mentionner plus d’algorithmes, il y a par exemple le clustering agglomératif hiérarchique (ou clustering par liaison), bon pour quand on n’a pas forcément des clusters circulaires (ou hyper-sphériques), et qu’on ne connaît pas le nombre de clusters à l’avance. Il commence avec chaque point étant un cluster séparé, et fonctionne en joignant deux clusters les plus proches à chaque étape jusqu’à ce que tout soit dans un grand cluster.

Avec le clustering agglomératif hiérarchique, nous pouvons facilement décider du nombre de clusters après coup en coupant le dendrogramme (diagramme d’arbre) horizontalement où nous le trouvons approprié. Il est également répétable (donne toujours la même réponse pour le même ensemble de données), mais il est également d’une complexité plus élevée (quadratique).

Alors, DBSCAN (Density-Based Spatial Clustering of Applications with Noise) est également un algorithme qui mérite d’être mentionné. Il regroupe les points qui sont très proches les uns des autres, en étendant les clusters dans n’importe quelle direction où il y a des points proches, traitant ainsi différentes formes de clusters.

Ces algorithmes méritent un article à part entière, et nous pouvons les explorer dans un post séparé plus tard.

Il faut de l’expérience avec quelques essais et erreurs pour savoir quand utiliser un algorithme ou l’autre. Heureusement, nous avons une gamme d’implémentations dans différents langages de programmation, donc les essayer ne nécessite qu’un peu de volonté de jouer.