Algorithmes de clustering : du début à l'état de l'art

Ce n'est pas un mauvais moment pour être Data Scientist. Les personnes sérieuses pourraient s'intéresser à vous si vous orientez la conversation vers « Big Data », et le reste de la foule sera intrigué lorsque vous mentionnerez « Intelligence artificielle » et « Apprentissage automatique ». Même Google pense que vous n'êtes pas mauvais et que vous vous améliorez encore. Il existe de nombreux algorithmes "intelligents" qui aident les scientifiques des données à faire leur magie. 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 commenceront 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, c'est là que l'utilisateur ne nous a pas donné beaucoup d'informations sur la sortie attendue. L'algorithme n'a que les données et il devrait faire du mieux qu'il peut. Dans notre cas, il doit effectuer un regroupement - séparer les données en groupes (clusters) contenant des points de données similaires, tandis que la dissemblance entre les groupes est aussi élevée que possible. Les points de données peuvent représenter n'importe quoi, comme nos clients. Le clustering peut être utile si nous voulons, par exemple, regrouper des utilisateurs similaires, puis lancer différentes campagnes marketing sur chaque cluster.

Clustering K-Means

Après l'introduction nécessaire, les cours de Data Mining continuent toujours avec K-Means ; un algorithme de clustering efficace et largement utilisé. Avant de l'exécuter, nous devons définir une fonction de distance entre les points de données (par exemple, la distance euclidienne si nous voulons regrouper des 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 jeu 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 centre de gravité et choisissons simplement le moins éloigné.

2. Étape de mise à jour : pour chaque cluster, un nouveau centroïde est calculé comme la moyenne de tous les points du cluster. De l'étape précédente, nous avons un ensemble de points qui sont affectés à un cluster. Maintenant, pour chacun de ces ensembles, nous calculons une moyenne que nous déclarons un nouveau centroïde du cluster.

Après chaque itération, les centroïdes se déplacent lentement et la distance totale entre chaque point et 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, conduisant ainsi à nouveau aux mêmes centroïdes. K-Means est garanti de converger vers un optimum local. Cependant, cela ne doit pas nécessairement être la meilleure solution globale (optimum global).

Le résultat final du regroupement peut dépendre de la sélection des centroïdes initiaux, donc beaucoup de réflexion a été consacrée à ce problème. Une solution simple consiste simplement à exécuter K-Means plusieurs fois avec des affectations initiales aléatoires. Nous pouvons ensuite 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 de sélection des points initiaux peuvent reposer 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 seuls qui sont juste "off" qui peuvent être juste quelques erreurs. Puisqu'ils sont loin de tout cluster significatif, chacun de ces points peut finir par être son propre « cluster ». Un bon équilibre est la variante K-Means++ [Arthur et Vassilvitskii, 2007], dont l'initialisation choisira toujours des points aléatoires, mais avec une probabilité proportionnelle à la distance carrée des centroïdes précédemment attribués. Les points 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 à mesure que leurs probabilités s'additionnent, résolvant le problème des valeurs aberrantes que nous avons mentionné.

K-Means++ est également l'initialisation par défaut pour l'implémentation Scikit-learn K-Means 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 data Instances data = DataSource.read("data.arff"); // Create the model SimpleKMeans kMeans = new SimpleKMeans(); // We want three clusters kMeans.setNumClusters(3); // Run K-Means kMeans.buildClusterer(data); // Print the centroids Instances centroids = kMeans.getClusterCentroids(); for (Instance centroid: centroids) { System.out.println(centroid); } // Print cluster membership for each instance for (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[::10]) [1 1 1 1 1 0 0 0 0 0 2 2 2 2 2] > >> print(yiris[::10]) [0 0 0 0 0 1 1 1 1 1 2 2 2 2 2]

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

Dans ce cas, nous savions qu'il y avait trois groupes (espèces) différents, et K-Means a reconnu correctement ceux qui vont ensemble. Mais, comment choisit-on un bon nombre de clusters k en général ? Ce genre de questions est assez courant en Machine Learning. Si nous demandons plus de clusters, ils seront plus petits, et donc l'erreur totale (total des distances entre les points et leurs clusters assignés) sera plus petite. Alors, est-ce une bonne idée de simplement définir un k plus grand ? Nous pouvons 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, ni assez générale pour couvrir certains nouveaux points qui peuvent apparaître. C'est ce qu'on appelle le surajustement, et nous ne voulons pas cela.

Une façon de traiter ce problème est d'inclure une pénalité pour un plus grand nombre de clusters. Donc, nous essayons maintenant de minimiser non seulement l'erreur, mais erreur + pénalité . L'erreur convergera simplement vers zéro à mesure que nous augmenterons le nombre de clusters, mais la pénalité augmentera. À certains moments, le gain 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 [Pelleg et Moore, 2000].

Une autre chose que nous devons définir correctement est la fonction de distance. Parfois, c'est une tâche simple, logique compte tenu de la nature des données. Pour les points dans l'espace, la distance euclidienne est une solution évidente, mais elle peut être délicate pour les caractéristiques de différentes "unités", pour les variables discrètes, etc. Cela peut nécessiter une grande connaissance du domaine. Ou, nous pouvons appeler Machine Learning pour obtenir de l'aide. Nous pouvons en fait essayer d'apprendre la fonction de distance. Si nous avons un ensemble de points d'apprentissage 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 regroupé. .

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, il peut être considéré 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 n'est décrit que par son centroïde. Ce n'est pas trop 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 plus loin et décrire chaque cluster par son centre de gravité (moyenne), sa covariance (afin que nous puissions 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 courants (qui, là encore, 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 clusters ou plus peuvent être des candidats acceptables, de sorte que le point a une distribution de probabilités sur les clusters. Cette propriété de l'algorithme, des points n'appartenant pas à un seul cluster est appelée "soft clustering".

L'étape M recalcule maintenant les paramètres de chaque cluster, en utilisant les attributions de points à l'ensemble de clusters précédent. 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'appartenir 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, nous pouvons donc 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 similaires aux données que nous avons observées.

Propagation par affinité

Affinity Propagation (AP) a été publié par Frey et Dueck en 2007 et devient de plus en plus populaire en raison de sa simplicité, de son applicabilité générale et de ses performances. Il change son statut de l'état de l'art à la norme de facto.

Les principaux inconvénients des K-Means et des algorithmes similaires sont de devoir sélectionner le nombre de clusters et de choisir l'ensemble initial de points. Au lieu de cela, la propagation d'affinité 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 exemples 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. Similitudes entre les points de données, représentant à quel point un point est bien adapté pour être l'exemple d'un autre. S'il n'y a pas de similitude entre deux points, car ils ne peuvent pas appartenir au même cluster, cette similitude peut être omise ou définie sur -Infinity 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 nous pouvons donc les représenter à travers les 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 convient aux 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 nxn en mémoire, mais plutôt de conserver une liste des similitudes avec les points connectés. Dans les coulisses, « échanger des messages entre des points » revient à manipuler des matrices, et ce n'est qu'une question de perspective et de mise en œuvre.

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

1. Calcul des responsabilités : la responsabilité r(i, k) reflète les preuves accumulées de la manière dont le point k est bien adapté pour servir d'exemple pour le point i, en tenant compte d'autres exemples potentiels pour le point i. La responsabilité est envoyée du point de données i au point d'exemplaire candidat k.

2. Calcul des disponibilités : la disponibilité a(i, k) reflète les preuves accumulées de la pertinence pour le point i de choisir le point k comme exemplaire, en tenant compte du soutien d'autres points selon lesquels le point k devrait être un exemplaire. La disponibilité est envoyée du point d'exemplaire candidat k au point i.

Afin de calculer les responsabilités, l'algorithme utilise les similitudes et les disponibilités d'origine calculées à l'itération précédente (initialement, toutes les disponibilités sont mises à zéro). Les responsabilités sont définies sur la similarité d'entrée entre le point i et le point k comme exemplaire, moins la somme la plus élevée de la similarité et de la disponibilité entre le point i et d'autres exemplaires candidats. La logique derrière le calcul de la pertinence d'un point pour un exemplaire est qu'il est davantage favorisé si la préférence a priori initiale était plus élevée, mais la responsabilité diminue lorsqu'il y a un point similaire qui se considère comme un bon candidat, il y a donc un ' concurrence' entre les deux jusqu'à ce que l'un soit décidé dans une itération.

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

Enfin, nous pouvons avoir différents critères d'arrêt pour terminer la procédure, par exemple lorsque les changements de valeurs tombent en dessous d'un certain seuil ou que le nombre maximum d'itérations est atteint. À tout moment de la procédure de propagation d'affinité, la somme des matrices de responsabilité (r) et de disponibilité (a) nous donne les informations de regroupement dont nous avons besoin : pour le point i, le k avec le maximum r(i, k) + a(i, k) représente le point je suis exemplaire. Ou, si nous avons juste besoin de l'ensemble d'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 encore nécessiter quelques ajustements si nous obtenons plus ou moins de clusters que ce que nous pouvons trouver optimal. Heureusement, en ajustant simplement les préférences, nous pouvons réduire ou augmenter le nombre de clusters. Définir les préférences sur une valeur plus élevée conduira à plus de clusters, car chaque point est "plus certain" de son aptitude à être un exemple et est donc plus difficile à "battre" et à l'inclure sous la "domination" d'un autre point. Inversement, définir des préférences plus basses entraînera moins de clusters ; comme s'ils disaient « non, non, s'il vous plaît, vous êtes un meilleur exemple, je rejoins votre cluster ». En règle générale, nous pouvons définir toutes les préférences sur la similarité médiane pour un nombre moyen à élevé de clusters, ou sur la similarité la plus faible pour un nombre modéré de clusters. Cependant, quelques exécutions avec des préférences d'ajustement peuvent être nécessaires pour obtenir le résultat qui correspond exactement à nos besoins.

La propagation d'affinité hiérarchique mérite également d'être mentionnée, en tant que variante de l'algorithme qui traite la complexité quadratique en divisant l'ensemble de données en quelques sous-ensembles, en les regroupant séparément, puis en effectuant le deuxième niveau de regroupement.

À la fin…

Il existe toute une gamme d'algorithmes de clustering, chacun avec ses avantages et ses inconvénients en ce qui concerne le type de données dont ils disposent, la complexité temporelle, les faiblesses, etc. Pour mentionner plus d'algorithmes, par exemple, il y a Hierarchical Agglomerative Clustering (ou Linkage Clustering), utile lorsque nous n'avons pas nécessairement de clusters circulaires (ou hyper-sphériques) et que nous ne connaissons pas le nombre de clusters à l'avance. Cela commence par chaque point étant un cluster séparé et fonctionne en joignant les deux clusters les plus proches à chaque étape jusqu'à ce que tout soit dans un grand cluster.

Avec Hierarchical Agglomerative Clustering, nous pouvons facilement décider du nombre de clusters par la suite en coupant le dendrogramme (diagramme en arbre) horizontalement là où nous le jugeons approprié. Il est également répétable (donne toujours la même réponse pour le même jeu de données), mais est également d'une plus grande complexité (quadratique).

Ensuite, DBSCAN (Density-Based Spatial Clustering of Applications with Noise) est également un algorithme qui mérite d'être mentionné. Il regroupe des points qui sont étroitement regroupés, élargissant 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 à eux seuls, et nous pourrons les explorer dans un article 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.