Comment décider du nombre correct de clusters?

54

Nous trouvons les centres de cluster et attribuons des points à k différents groupes de cluster dans le clustering k-means, qui est un algorithme très bien connu et qui se retrouve presque dans tous les packages d'apprentissage automatique du réseau. Mais la partie manquante et la plus importante à mon avis est le choix d’un k correct. Quel est le meilleur rapport qualité-prix? Et qu'entend-on par meilleur ?

J'utilise MATLAB pour le calcul scientifique où regarder les tracés de silhouette est donné comme un moyen de décider de k discuté ici . Cependant, je serais plus intéressé par les approches bayésiennes. Toutes les suggestions sont appréciées.

petrichor
la source
2
Belle question ...
Sous visualisation-for-clustering, il y a (ahem) un moyen de visualiser les k-clusters et de voir l’effet de divers k en une seule fois, à l’aide de MST.
denis
J'ai répondu à cette question avec une demi - douzaine de méthodes Rplus ici
Ben
1
Pour choisir le "meilleur" nombre k de grappes, il faut comparer des solutions de grappes avec différents k - quelle solution est "meilleure". À cet égard, la tâche semble similaire à la comparaison des méthodes de classification - ce qui est "meilleur" pour vos données. Les directives générales sont ici .
ttnphns

Réponses:

28

Cela a été demandé à quelques reprises sur stackoverflow: ici , ici et ici . Vous pouvez regarder ce que la foule là-bas pense de cette question (ou d'une petite variante de celle-ci).

Permettez-moi également de copier ma propre réponse à cette question sur stackoverflow.com:

Malheureusement, il n’existe aucun moyen de définir automatiquement le "droit" K et il n’existe pas non plus de définition de ce que "droit" est. Il n’existe pas de méthode statistique fondée sur des principes, simple ou complexe, permettant de définir le "bon K". Il existe des heuristiques, des règles empiriques qui fonctionnent parfois, parfois non.

La situation est plus générale, car de nombreuses méthodes de regroupement utilisent ce type de paramètres, ce qui constitue un gros problème en suspens dans la communauté des chercheurs en apprentissage par regroupement / non supervisé.

Carlos
la source
+1 Après avoir lu ceci - cela me semble tellement intuitif ... mais je dois dire que je n'y avais jamais pensé auparavant. que le problème du choix du nombre de PC dans PCA équivaut au problème du choix du nombre de clusters dans K-mean ...
Dov
2
@Dov, ces deux choses ne sont pas tout à fait équivalentes. Certaines mesures spécifiques peuvent être utilisées pour examiner la qualité d'une solution PCA (notamment l'erreur de reconstruction, mais aussi le% de variance capturé, etc.), et elles ont tendance à être (généralement) cohérentes. Cependant, dans le clustering, il n’ya souvent pas de "bonne réponse" - un cluster peut être meilleur qu’un autre par une métrique, et l’inverse peut être vrai en utilisant une autre métrique. Et dans certaines situations, deux regroupements différents pourraient être également probables sous la même métrique.
TDC
@tdc mais cela n'est-il pas fr.wikipedia.org/wiki/… est-il plus ou moins amélioré ? outcomes.com/docs/WebSiteDocs/PCA/… ?
Dov
2
@Dov Oui, ils se ressemblent "plus ou moins", mais je disais simplement que le problème du choix du nombre de grappes est beaucoup plus complexe que celui du nombre de PC, c'est-à-dire qu'ils ne sont pas "équivalents".
TDC
1
+1 tu as raison. Nous introduisons en quelque sorte un autre modèle ou une autre hypothèse pour choisir le meilleur k, mais la question qui se pose est de savoir pourquoi ce modèle ou cette hypothèse est le meilleur ...
petrichor
19

Tout d'abord une mise en garde. Dans le clustering, il n’existe souvent aucune "bonne réponse": un cluster peut être meilleur qu’un autre par une métrique, et l’inverse peut être vrai en utilisant une autre métrique. Et dans certaines situations, deux regroupements différents pourraient être également probables sous la même métrique.

Cela dit, vous voudrez peut-être jeter un coup d’œil sur les processus de Dirichlet . Voir aussi ce tutoriel .

Si vous commencez avec un modèle de mélange gaussien, vous rencontrez le même problème qu'avec k-means - vous devez choisir le nombre de clusters. Vous pouvez utiliser des preuves de modèle, mais elles ne seront pas robustes dans ce cas. L’astuce consiste donc à utiliser un processus de Dirichlet avant les composants de mélange, ce qui vous permet d’avoir un nombre potentiellement infini de composants de mélange, mais le modèle trouvera (généralement) automatiquement le nombre "correct" de composants (sous les hypothèses de le modèle).

Notez que vous devez toujours spécifier le paramètre de concentration du processus de Dirichlet avant. Pour les petites valeurs de , les échantillons d'un PD sont probablement composés d'un petit nombre de mesures atomiques de poids élevé. Pour les grandes valeurs, la plupart des échantillons seront probablement distincts (concentrés). Vous pouvez utiliser un hyper-prior sur le paramètre de concentration, puis déduire sa valeur à partir des données. Cet hyper-prior peut être suffisamment vague pour autoriser de nombreuses valeurs possibles. Cependant, avec suffisamment de données, le paramètre de concentration cessera d'être si important et cet hyper-préalable pourrait être abandonné.ααα

tdc
la source
1
Un processus de Dirichlet sous quel paramètre de concentration? C'est un peu l'équivalent de la même question initiale, k-signifie sous quelle k? Bien que je convienne que nous comprenons mieux la distribution de Direchlet que le comportement d’un algorithme complexe sur des données réelles.
carlosdc
@carlosdc bon point, j'ai mis à jour la réponse pour inclure un peu de discussion sur le paramètre de concentration
tdc
1
D'après mon expérience, il est beaucoup plus facile d'apprendre un paramètre de concentration à valeur continue comme alpha que de déterminer le nombre de grappes dans un modèle de mélange fini. Si vous voulez vous en tenir à un modèle de mélange fini et adopter une tactique bayésienne, il existe un MCMC à saut réversible ( onlinelibrary.wiley.com/doi/10.1111/1467-9868.00095/abstract )
1
Très bonne réponse. J'ajouterais l'article Revisiting K-Means: New Algorithms via Bayesian Nonparametrics . Ce qui donne une approche simple et continue de K-Means. Ensuite, il est facile, en utilisant l'optimisation, de trouver la valeur optimale.
Royi
9

J'utilise la méthode du coude :

  • Commencez avec K = 2, puis augmentez-le à chaque étape de 1, calculez vos grappes et le coût de la formation. A un certain niveau de valeur pour K, le coût diminue considérablement et ensuite, il atteint un plateau lorsque vous l'augmentez davantage. C'est la valeur K que vous voulez.

La raison en est que, après cela, vous augmentez le nombre de clusters mais le nouveau cluster est très proche de certains des existants.

von Petrushev
la source
Cela ressemble au principe que la méthode L (voir ma réponse) évalue.
winwaed
6

La taille des clusters dépend fortement de vos données et de l'utilisation des résultats. Si vous utilisez vos données pour diviser des éléments en catégories, essayez d’imaginer le nombre de catégories que vous souhaitez d’abord. Si c'est pour la visualisation de données, rendez-le configurable, afin que les gens puissent voir à la fois les grands groupes et les plus petits.

Si vous avez besoin de l’automatiser, vous pouvez ajouter une pénalité pour augmenter k et calculer ainsi le cluster optimal. Ensuite, vous pondérez simplement k selon que vous voulez une tonne de grappes ou très peu.

neurone
la source
5

J'ai réussi à utiliser la "méthode L" pour déterminer le nombre de grappes dans une application géographique (c'est-à-dire un problème essentiel, même si techniquement non euclidien).

La méthode L est décrite ici: Détermination du nombre de clusters / segments dans les algorithmes de clustering / segmentation hiérarchique Stan Salvador et Philip Chan

Essentiellement, cela évalue l'ajustement pour différentes valeurs de k. Un graphe en forme de "L" apparaît avec la valeur k optimale représentée par le coude dans le graphe. Un simple calcul de la droite des moindres carrés à deux lignes est utilisé pour trouver le point du genou.

J'ai trouvé la méthode très lente car les k-moyennes itératives doivent être calculées pour chaque valeur de k. Aussi, j’ai trouvé que k-means fonctionnait mieux avec plusieurs exécutions et choisissait le meilleur à la fin. Bien que chaque point de données n'ait que deux dimensions, une simple distance de Pythagore ne peut pas être utilisée. Donc, cela fait beaucoup de calculs.

Une solution consiste à ignorer toutes les autres valeurs de k (disons) à la moitié des calculs et / ou à réduire le nombre d'itérations k-moyennes, puis à lisser légèrement la courbe obtenue pour obtenir un ajustement plus précis. J'ai posé la question à ce sujet chez StackOverflow - IMHO, la question du lissage reste une question de recherche ouverte.

Winwaed
la source
4

Vous devez reconsidérer ce que fait k-mean. Il essaie de trouver le partitionnement optimal de Voronoï de l'ensemble de données en cellules. Les cellules de Voronoï sont des cellules de forme étrange, structure orthogonale d'une triangulation de Delaunay.k

Mais que se passe-t-il si votre ensemble de données ne correspond pas vraiment au schéma de Voronoï?

Très probablement, les clusters réels ne seront pas très significatifs. Cependant, ils peuvent toujours fonctionner pour tout ce que vous faites. Même en séparant un "vrai" cluster en deux parties, car votre est trop élevé, le résultat peut très bien fonctionner, par exemple, pour la classification. Je dirais donc: le meilleur est celui qui convient le mieux à votre tâche.kkk

En fait, lorsque vous avez grappes dont la taille et l’espace ne sont pas égaux (et ne rentrent donc pas dans le schéma de partitionnement de Voronoï), il peut être nécessaire d’augmenter k pour obtenir k-moyennes afin d’obtenir de meilleurs résultats.k

Anony-Mousse
la source
3
Bien que la description de K-moyennes dans le premier paragraphe ne soit pas erronée, certaines personnes pourraient être induites en erreur en assimilant cette méthode au partitionnement de Voronoï basé sur les données d'origine. Ce n'est pas le cas: la partition est basée sur les emplacements des moyens du cluster, ce qui pourrait ne pas (et ne sera généralement pas) coïncider avec les données d'origine.
whuber
3

Globalement, vous pouvez choisir le nombre de clusters dans deux chemins différents.

  1. axée sur les connaissances: vous devriez avoir quelques idées du nombre de clusters dont vous avez besoin du point de vue commercial. Par exemple, vous regroupez des clients, vous devriez vous demander, après avoir obtenu ces clients, que dois-je faire ensuite? Peut-être aurez-vous un traitement différent pour différentes grappes? (par exemple, publicité par courriel ou par téléphone). Alors combien de traitements possibles envisagez-vous? Dans cet exemple, vous sélectionnez 100 grappes n’auront pas beaucoup de sens.

  2. Basé sur les données: plus de grappes sont sur-ajustées et moins de grappes sont sous-ajustées. Vous pouvez toujours diviser les données en deux et exécuter une validation croisée pour voir combien de clusters sont bons. Notez que dans le clustering, vous avez toujours la fonction de perte, similaire au réglage supervisé.

Enfin, vous devez toujours combiner les connaissances et les données dans le monde réel.

Haitao Du
la source
2

Comme personne ne l’a encore souligné, je pensais partager cela. Il existe une méthode appelée X-moyennes ( voir ce lien ) qui estime le nombre approprié de grappes en utilisant le critère d’information bayésien (BIC). Essentiellement, cela reviendrait à essayer K signifie avec différents K, calculer le BIC pour chaque K et choisir le meilleur K. Cet algorithme le fait efficacement.

Il existe également une implémentation de weka , dont les détails peuvent être trouvés ici .

rivu
la source
0

Une autre approche consiste à utiliser un algorithme évolutif dont les individus ont des chromosomes de différentes longueurs. Chaque individu est une solution candidate: chacun porte les coordonnées des centroïdes. Le nombre de centroïdes et leurs coordonnées sont évolués afin de parvenir à une solution donnant le meilleur score d'évaluation en clustering.

Ce document explique l'algorithme.

felipeduque
la source