Choisir une méthode de clustering

Lorsque vous utilisez l'analyse par grappes sur un ensemble de données pour regrouper des cas similaires, vous devez choisir parmi un grand nombre de méthodes de regroupement et de mesures de distance. Parfois, un choix peut influencer l’autre, mais il existe de nombreuses combinaisons de méthodes possibles.

Quelqu'un at-il des recommandations sur la manière de choisir parmi les divers algorithmes / méthodes de classification et mesures de distance ? Comment cela est-il lié à la nature des variables (catégorielles ou numériques, par exemple) et au problème de classification? Y a-t-il une technique optimale?

Il n’ya pas de réponse définitive à votre question, car même au sein de la même méthode, le choix de la distance pour représenter les (dis) similitudes peut donner des résultats différents, par exemple lorsqu’on utilise euclidien ou euclidien au carré dans un regroupement hiérarchique. Autre exemple, pour les données binaires, vous pouvez choisir l’indice Jaccard comme mesure de similarité et procéder à la classification hiérarchique classique; mais il existe des approches alternatives, comme le Mona ( Monothetic Analysis) un algorithme qui ne considère qu’une variable à la fois, alors que d’autres approches hiérarchiques (par exemple HC classique, Agnes, Diana) utilisent toutes les variables à chaque étape. L'approche k-means a été étendue de différentes manières, y compris la partition autour de médoïdes (PAM) ou d'objets représentatifs plutôt que de centroïdes (Kaufman et Rousseuw, 1990), ou de regroupements flous (Chung et Lee, 1992). Par exemple, la principale différence entre les k-moyennes et PAM est que PAM minimise une somme de dissimilarités plutôt qu'une somme de distances euclidiennes au carré; La classification floue permet de considérer une "appartenance partielle" (nous associons à chaque observation un poids reflétant l'appartenance à une classe). Et pour les méthodes reposant sur un cadre probabiliste, ou le clustering basé sur un modèle (ou analyse de profil latentpour les psychométriciens), il existe un excellent package: Mclust . Vous devez donc déterminer comment définir la ressemblance des individus ainsi que la méthode de mise en relation des individus (regroupement récursif ou itératif, appartenance à une classe stricte ou floue, approche non supervisée ou semi-supervisée, etc.).

Habituellement, pour évaluer la stabilité d'un cluster, il est intéressant de comparer plusieurs algorithmes qui "partagent" en gros une similitude (par exemple, k-moyennes et classification hiérarchique, car la distance euclidienne fonctionne pour les deux). Pour évaluer la concordance entre deux solutions de cluster, certains indicateurs ont été suggérés en réponse à cette question, Où couper un dendrogramme? (voir aussi les références croisées pour un autre lien sur ce site). Si vous utilisez R, vous constaterez que plusieurs packages sont déjà disponibles dans la vue des tâches de l'analyse des clusters. Plusieurs packages incluent des vignettes décrivant des méthodes spécifiques ou fournissant des études de cas.

Analyse de cluster: concepts de base et algorithmes fournit une bonne vue d'ensemble de plusieurs techniques utilisées dans l'analyse de cluster. En ce qui concerne un bon livre récent avec des illustrations R, je recommanderais le chapitre 12 de Izenman, Techniques statistiques multivariées modernes (Springer, 2008). Quelques autres références standard sont données ci-dessous:

• Cormack, R., 1971. Revue de la classification. Journal de la Société royale de statistique, A 134, 321–367.
• Everitt, B., 1974. Analyse en grappes . Londres: Heinemann Educ. Livres.
• Gordon, A., 1987. Revue de la classification hiérarchique. Journal de la Société royale de statistique, A 150, 119-137.
• Gordon, A., 1999. Classification , 2e édition. Chapman et Hall.
• Kaufman, L., Rousseuw, P., 1990. Recherche de groupes dans les données: introduction à l'analyse par grappes . New York, Wiley.

Une citation de Hastie, Tibshirani et Friedman, Éléments d'apprentissage statistique , p. 506:

"Une mesure de dissimilarité appropriée est beaucoup plus importante pour réussir le clustering que le choix de l'algorithme de clustering. Cet aspect du problème ... dépend de la connaissance d'un domaine spécifique et est moins sujet à la recherche en général."

(Cela dit, ne serait-il pas intéressant que (wibni) existe un site où les étudiants pourraient essayer quelques algorithmes et métriques sur quelques petits jeux de données standard?)

Vous ne pouvez pas savoir à l'avance quel algorithme de clustering serait le mieux, mais il existe quelques indices. Par exemple, si vous souhaitez regrouper des images, vous devez d'abord essayer certains algorithmes comme Fuzzy Art, ou si vous souhaitez regrouper des faces, vous devez commencer. avec regroupement géométrique global (GGCI) pour l’image.

Quoi qu'il en soit, cela ne garantit pas le meilleur résultat. Par conséquent, je voudrais utiliser un programme qui vous permette d'exécuter méthodiquement différents algorithmes de cluster, tels que weka, RapidMiner ou même R (ce qui n'est pas visuel). Là, je vais régler le programme sur lance tous les différents algorithmes de regroupement que je peux, avec toutes les distances possibles, et s'ils ont besoin de paramètres, expérimentez chacun avec une variété de valeurs de paramètre différentes (sauf si je ne connais pas le nombre de clusters, exécutez-les avec une variété des nombres de celui-ci). Une fois l’expérience validée, laissez-la en marche, mais rappelez-vous de stocker quelque part les résultats de chaque exécution de la mise en cluster.

Comparez ensuite les résultats afin d’obtenir le meilleur résultat possible. Ceci est délicat car il existe plusieurs métriques que vous pouvez comparer et tous ne sont pas fournis par chaque algorithme. Par exemple, les algorithmes de clustering flous ont des métriques différentes des méthodes non floues, mais ils peuvent toujours être comparés en considérant les groupes résultants comme étant non flous. Je vais m'en tenir à la comparaison avec les métriques classiques telles que:

• SSE: somme de l'erreur de carré des éléments de chaque cluster.

• Distance inter-grappe: somme de la distance carrée entre chaque centre de grappe.

• Distance intra-groupe pour chaque groupe: somme de la distance au carré entre les éléments de chaque groupe et son centroïde.

• Rayon maximum: distance maximale entre une instance et son centre de gravité.

• Rayon moyen: somme de la distance la plus grande entre une instance et son centroïde de cluster divisé par le nombre de clusters.

Choisir la bonne distance n'est pas une tâche élémentaire. Lorsque nous voulons effectuer une analyse par grappes sur un ensemble de données, différents résultats peuvent apparaître avec différentes distances. Il est donc très important de choisir la distance qui convient, car nous pouvons créer un faux bon artefact qui capture bien la variabilité, mais en réalité sans sens dans notre problème.

La distance euclidienne est appropriée lorsque j'ai des variables numériques continues et que je veux refléter les distances absolues. Cette distance prend en compte toutes les variables et ne supprime pas les redondances. Par conséquent, si j'avais trois variables qui expliquent la même chose (elles sont corrélées), je pondérerais cet effet par trois. De plus, cette distance n’est pas invariante en termes d’échelle, c’est pourquoi j’ai l'habitude de mettre à l'échelle auparavant pour utiliser la distance.
Exemple d'écologie: Nous avons différentes observations dans de nombreuses localités, parmi lesquelles les experts ont prélevé des échantillons de certains facteurs microbiologiques, physiques et chimiques. Nous voulons trouver des modèles dans les écosystèmes. Ces facteurs ont une forte corrélation, mais nous savons que tout le monde est pertinent, nous ne voulons donc pas supprimer ces redondances. Nous utilisons la distance euclidienne avec des données mises à l'échelle pour éviter l'effet des unités.

La distance de Mahalanobis est appropriée lorsque j'ai des variables numériques continues et que je veux refléter les distances absolues, mais nous voulons supprimer les redondances. Si nous avons répété des variables, leur effet répétitif disparaîtra.

La famille Hellinger , le profil d’espèce et la distance d’accord sont appropriés pour souligner les différences entre les variables et pour différencier les profils. Ces distances pondèrent par les quantités totales de chaque observation, de telle sorte que les distances sont petites lorsque variable par variable, les individus sont plus similaires, bien que les grandeurs absolues soient très différentes. Fais attention! Ces distances reflètent très bien la différence entre les profils, mais ont perdu l'effet de magnitude. Ils pourraient être très utiles lorsque nous avons différentes tailles d'échantillons. Exemple d'écologie: Nous souhaitons étudier la faune de nombreuses terres et nous disposons d'une matrice de données d'un inventaire du gastéropode (emplacements d'échantillonnage en rangées et noms d'espèces en colonnes). La matrice se caractérise par le nombre de zéros et de grandeurs différentes, car certaines localités ont certaines espèces et d'autres, d'autres. Nous pourrions utiliser la distance de Hellinger.

Bray-Curtis est assez similaire, mais il est plus approprié de différencier les profils et de prendre en compte les grandeurs relatives.

En ce qui me concerne, si vous voulez un choix sûr, les méthodes de regroupement spectral ont obtenu les taux de précision les plus élevés de ces dernières années - du moins pour le regroupement d'images.

En ce qui concerne la métrique de distance, cela dépend beaucoup de la manière dont vos données sont organisées. Le choix sûr est la distance euclidienne simple, mais si vous savez que vos données contiennent de multiples variétés, vous devez mapper les points via les méthodes du noyau.

PS: ils sont tous liés à des valeurs numériques, non catégoriques. Je ne sais pas comment on pourrait s'y prendre pour regrouper des données catégoriques.

Voici un résumé de plusieurs algorithmes de clustering qui peuvent aider à répondre à la question.

"quelle technique de regroupement dois-je utiliser?"

Il n'y a pas d'algorithme de classification objectivement "correct" Ref

Les algorithmes de clustering peuvent être classés en fonction de leur "modèle de cluster". Un algorithme conçu pour un type de modèle particulier échouera généralement sur un type de modèle différent. Par exemple, k-means ne peut pas trouver de groupes non convexes, il ne peut trouver que des groupes de forme circulaire.

Par conséquent, la compréhension de ces "modèles de grappes" devient la clé pour comprendre comment choisir parmi les divers algorithmes / méthodes de classification. Les modèles de cluster typiques incluent:

[1] Modèles de connectivité: construit des modèles basés sur la connectivité à distance. Par exemple, clustering hiérarchique. Utilisé lorsque nous avons besoin d'un partitionnement différent basé sur la hauteur de coupe de l'arbre. Fonction R: hclust dans le package de statistiques.

[2] Modèles centroïdes: construit des modèles en représentant chaque cluster par un seul vecteur moyen. Utilisé lorsque nous avons besoin d'un partitionnement net (par opposition à la mise en cluster floue décrite plus tard). Fonction R: kmeans dans les statistiques.

[3] Modèles de distribution: construit des modèles basés sur des distributions statistiques telles que les distributions normales multivariées utilisées par l'algorithme d'optimisation des attentes. Utilisé lorsque les formes de grappe peuvent être arbitraires contrairement à k-means qui suppose des grappes circulaires. Fonction R: emcluster dans le package emcluster.

[4] Modèles de densité: construit des modèles basés sur des grappes en tant que régions denses connectées dans l'espace de données. Par exemple, DBSCAN et OPTICS. Utilisé lorsque les formes de cluster peuvent être arbitraires, contrairement à k-means qui suppose des clusters circulaires. R function dbscan dans le package dbscan.

[5] Modèles de sous-espace: construit des modèles basés à la fois sur les membres du cluster et sur les attributs pertinents. Par exemple, biclustering (également appelé co-clustering ou clustering à deux modes). Utilisé lorsqu'un regroupement simultané de lignes et de colonnes est nécessaire. Fonction biclust dans un emballage biclust.

[6] Modèles de groupe: crée des modèles basés sur les informations de regroupement. Par exemple, filtrage collaboratif (algorithme de recommandation). Fonction R Recommender dans le package recommenderlab.

[7] Modèles basés sur des graphes: construit des modèles basés sur des cliques. Les algorithmes de détection de structure de communauté tentent de trouver des sous-graphes denses dans des graphes dirigés ou non dirigés. Par exemple, R fonction cluster_walktrap dans le package igraph.

[8] Carte de fonctions auto-organisée de Kohonen: construit des modèles basés sur un réseau de neurones. R fonction som dans le package kohonen.

[9] Clustering spectral: construit des modèles basés sur une structure de cluster non convexe ou lorsqu'une mesure du centre ne constitue pas une description appropriée du cluster complet. Fonction R spécc dans le package kernlab.

[10] Regroupement de sous-espaces: pour les données de grande dimension, les fonctions de distance pourraient être problématiques. Les modèles de cluster incluent les attributs pertinents pour le cluster. Par exemple, la fonction hddc dans le package R HDclassif.

[11] Regroupement de séquences: regrouper des séquences liées. Package rBlast.

[12] Propagation par affinité: construit des modèles basés sur le message passant entre des points de données. Avant d'exécuter l'algorithme, il n'est pas nécessaire de déterminer le nombre de clusters. C'est mieux pour certaines tâches de vision par ordinateur et de biologie informatique, par exemple le regroupement d'images de visages humains et l'identification de transcriptions réglementées, que k-means, Ref Rpackage APCluster.

[13] Regroupement de flux: construit des modèles basés sur des données arrivant en continu telles que des enregistrements téléphoniques, des transactions financières, etc. Par exemple, le package R BIRCH [ https://cran.r-project.org/src/contrib/Archive/birch/].

[14] Regroupement de documents (ou regroupement de textes): construit des modèles basés sur la SVD. Il a utilisé dans l'extraction de sujet. Par exemple, Carrot [ http://search.carrot2.org] est un moteur de regroupement de résultats de recherche open source pouvant regrouper des documents en catégories thématiques.

[15] Modèle de classe latente: il relie un ensemble de variables multivariées observées à un ensemble de variables latentes. La LCA peut être utilisée dans le filtrage collaboratif. La fonction R recommandée dans le paquet recommenderlab dispose d'une fonctionnalité de filtrage collaboratif.

[16] Biclustering: utilisé pour regrouper simultanément des lignes et des colonnes de données bimodales. Par exemple, R fonctionne biclust dans le paquet biclust.

[17] Clustering léger (clustering flou): chaque objet appartient à chaque cluster à un certain degré. Par exemple, R Fclust fonctionne dans le package fclust.