Comment comprendre les inconvénients de K-means

K-means est une méthode largement utilisée dans l'analyse par grappes. À mon sens, cette méthode ne nécessite AUCUNE hypothèse, c’est-à-dire qu’elle me donne un ensemble de données et un nombre de grappes prédéterminé, k, et que je m’applique simplement à cet algorithme qui minimise la somme des erreurs au carré (SSE), au sein de la grappe au carré. Erreur.

Donc, k-means est essentiellement un problème d'optimisation.

J'ai lu des informations sur les inconvénients de k-means. La plupart d'entre eux disent que:

• k-means suppose que la variance de la distribution de chaque attribut (variable) est sphérique;
• toutes les variables ont la même variance;
• la probabilité a priori pour toutes les k grappes est la même, c'est-à-dire que chaque grappe a à peu près le même nombre d'observations;

Si l'une de ces 3 hypothèses est violée, alors k-means échouera.

Je ne pouvais pas comprendre la logique derrière cette affirmation. Je pense que la méthode des k-moyennes ne fait essentiellement aucune hypothèse, elle minimise simplement l'ESS, de sorte que je ne vois pas le lien entre minimiser l'ESS et ces 3 "hypothèses".

Bien que la réponse de David Robinson me plaise beaucoup ici, voici une autre critique de k-means.

Mise en cluster de données non mises en cluster

Exécutez k-means sur des données uniformes et vous obtiendrez toujours des grappes! Il ne vous dit pas quand les données ne se regroupent pas et peut mener votre recherche dans une impasse de cette façon.

Sensible à l'échelle

Le redimensionnement de vos jeux de données changera complètement les résultats. Bien que cela ne soit pas mauvais en soi, il est mauvais de ne pas se rendre compte que vous devez accorder une attention particulière à la mise à l'échelle de vos données . Les facteurs d' échelle sont supplémentaires paramètres cachés dans k signifie que « par défaut » à 1 et sont donc facilement négligé, mais ont un impact majeur (mais bien sûr , cela vaut pour beaucoup d' autres algorithmes, aussi).$d$

C'est probablement ce que vous avez appelé "toutes les variables ont la même variance". Sauf qu'idéalement, vous devriez également envisager une mise à l'échelle non linéaire, le cas échéant.

Sachez également qu'il ne s'agit que d'une heuristique qui consiste à mettre à l'échelle chaque axe pour obtenir une variance unitaire . Cela ne garantit pas que k-means fonctionne. La mise à l'échelle dépend de la signification de votre ensemble de données. Et si vous avez plus d'un cluster, vous voudriez que chaque cluster (indépendamment) ait la même variance dans chaque variable.

Voici un contre-exemple classique d'ensembles de données que k-means ne peut pas regrouper. Les deux axes sont iid dans chaque groupe, il serait donc suffisant de le faire dans une dimension. Mais les grappes ont des variances variables, et k-means les divise donc de manière incorrecte.

Je ne pense pas que ce contre-exemple pour k-means soit couvert par vos points:

• Toutes les grappes sont sphériques (ida gaussiennes).
• Tous les axes ont la même distribution et donc la variance.
• Les deux groupes ont 500 éléments chacun.

Cependant, k-means échoue toujours mal (et cela empire si j'augmente la variance au-delà de 0,5 pour le plus grand cluster). Mais: ce n'est pas l'algorithme qui a échoué. Ce sont les hypothèses, qui ne tiennent pas . K-means fonctionne parfaitement, il ne fait qu'optimiser le mauvais critère.

Même sur des ensembles de données parfaits, il peut rester bloqué dans un minimum local

Vous trouverez ci-dessous le meilleur des 10 exécutions de k-moyennes sur le jeu de données A3 classique. Ceci est un ensemble de données synthétiques, conçu pour k-means . 50 grappes, chacune de forme gaussienne, assez bien séparées. Pourtant, c’est seulement avec k-means ++ et 100 itérations que j’ai obtenu le résultat attendu ... (ci-dessous 10 itérations de k-means classiques, à titre d’illustration).

Vous trouverez rapidement de nombreux clusters dans cet ensemble de données, où k-means n'a pas réussi à trouver la structure correcte. Par exemple, en bas à droite, un cluster était divisé en trois parties. Mais il n'y a aucun moyen, k-means va déplacer l'un de ces centroïdes vers un endroit totalement différent de l'ensemble de données - il est pris au piège dans un minimum local (et c'était déjà le meilleur des 10 essais!)

Et il existe de nombreux minima locaux dans cet ensemble de données. Très souvent, lorsque vous obtenez deux échantillons du même cluster, il se bloque au minimum là où ce cluster reste divisé, et deux autres clusters sont fusionnés. Pas toujours, mais très souvent. Il faut donc beaucoup d'itérations pour avoir un choix chanceux. Avec 100 itérations de k-moyennes, j'ai quand même compté 6 erreurs, et avec 1000 itérations, je l'ai réduite à 4 erreurs. K-means ++, de par la manière dont il pondère les échantillons aléatoires, fonctionne beaucoup mieux avec cet ensemble de données.

Les moyens sont continus

Bien que vous puissiez exécuter k-means sur des données binaires (ou des données catégoriques codées à une seule étape), les résultats ne seront plus binaires. Vous obtenez donc un résultat, mais vous pouvez être incapable de l'interpréter à la fin, car le type de données est différent de celui de vos données d'origine.

Hypothèse cachée: l'ESS mérite d'être minimisé

Ceci est essentiellement déjà présent dans la réponse ci-dessus, bien démontrée avec une régression linéaire. Il y a des cas d'utilisation où k-means est parfaitement logique. Lorsque Lloyd devait décoder les signaux PCM, il connaissait le nombre de tonalités différentes et l'erreur du moins carré minimisait le risque d'erreur de décodage. Et en quantifiant la couleur de l'image, vous réduisez également les erreurs de couleur lorsque vous réduisez la palette. Mais sur vos données, la somme des écarts carrés est-elle un critère important à minimiser?

Dans le contre-exemple ci-dessus, la variance ne vaut pas la peine d'être minimisée, car elle dépend du cluster. Au lieu de cela, un modèle de mélange gaussien doit être ajusté aux données, comme indiqué dans la figure ci-dessous:

(Mais ce n'est pas non plus la méthode ultime. Il est tout aussi facile de construire des données qui ne satisfont pas à la "combinaison de k distributions gaussiennes", par exemple en ajoutant beaucoup de bruit de fond)

Trop facile à utiliser mal

Dans l’ensemble, il est trop facile de jeter des k-means sur vos données et d’obtenir néanmoins un résultat (assez aléatoire, mais vous ne le remarquerez pas). Je pense qu'il serait préférable d'avoir une méthode qui peut échouer si vous n'avez pas compris vos données ...

K-moyennes comme quantification

Si vous voulez un modèle théorique de ce que fait k-means, considérez-le comme une approche de quantification et non comme un algorithme de classification.

L'objectif de k-means - minimiser l'erreur au carré - est un choix raisonnable si vous remplacez chaque objet par son centroïde le plus proche. (Cela a beaucoup moins de sens si vous inspectez les données d'origine du groupe à mon humble avis.)

Il y a de très bons cas d'utilisation pour cela. On pense au cas d'utilisation original de Lloyd par PCM, ou par exemple la modification de la couleur (Wikipedia) . Si vous voulez réduire une image à k couleurs, vous ne voulez remplacer chaque pixel avec le plus proche barycentre. Minimiser la déviation de couleur au carré permet alors de mesurer l'optimalité L2 en approximation d'image en utilisant seulement couleurs.$k$

Cette quantification est probablement assez similaire à celle de la régression linéaire. La régression linéaire trouve le meilleur modèle linéaire . Et k-means trouve (parfois) la meilleure réduction en k valeurs d’un ensemble de données multidimensionnel. Où "meilleur" est l'erreur la moins carrée.

IMHO, k-means est un bon algorithme de quantification (voir la première image de cet article - si vous voulez approximer l'ensemble de données à deux points, c'est un choix raisonnable!). Si vous souhaitez effectuer une analyse par grappes comme dans la structure de découverte, alors k-means n'est pas le meilleur choix. Il a tendance à se regrouper lorsqu'il n'y a pas de groupes et qu'il ne peut pas reconnaître les différentes structures que vous voyez souvent dans les données.

Impression fine: toutes les images ont été générées avec ELKI . Les données ont été générées à l'aide du .xmlformat de génération de données, mais elles sont tellement fondamentales qu'il ne vaut pas la peine de les partager.

Quelle bonne question, c'est une occasion de montrer comment on inspecterait les inconvénients et les hypothèses de toute méthode statistique. À savoir: créer des données et essayer l'algorithme!

Nous examinerons deux de vos hypothèses et verrons ce qu'il advient de l'algorithme k-means lorsque ces hypothèses sont brisées. Nous nous en tiendrons aux données bidimensionnelles, car elles sont faciles à visualiser. (Grâce à la malédiction de la dimensionnalité , l’ajout de dimensions supplémentaires est susceptible de rendre ces problèmes plus graves, pas moins). Nous allons travailler avec le langage de programmation statistique R: vous pouvez trouver le code complet ici (et le message sous forme de blog ici ).

Détournement: Quatuor d'Anscombe

Tout d'abord, une analogie. Imaginez que quelqu'un soutienne ce qui suit:

J'ai lu des informations sur les inconvénients de la régression linéaire, à savoir qu'elle s'attend à une tendance linéaire, que les résidus sont normalement distribués et qu'il n'y a pas de valeurs aberrantes. Mais tout ce que la régression linéaire fait est de minimiser la somme des erreurs au carré (SSE) de la ligne prédite. C'est un problème d'optimisation qui peut être résolu quelles que soient la forme de la courbe ou la distribution des résidus. Ainsi, la régression linéaire ne nécessite aucune hypothèse pour fonctionner.

Eh bien, oui, la régression linéaire fonctionne en minimisant la somme des résidus au carré. Mais ce n’est pas en soi l’objectif d’une régression: nous essayons de tracer une ligne servant de prédicteur fiable et non biaisé de y et basé sur x . Le théorème de Gauss-Markov nous dit que réduire au minimum l'ESS permet d'atteindre cet objectif, mais ce théorème repose sur des hypothèses très spécifiques. Si ces hypothèses sont brisées, vous pouvez toujours minimiser l'ESS, mais cela pourrait ne pas être le cas.n'importe quoi. Imaginez: "Vous conduisez une voiture en appuyant sur la pédale: la conduite est essentiellement un processus consistant à" pousser la pédale ". La pédale peut être actionnée peu importe la quantité d'essence dans le réservoir. Par conséquent, même si le réservoir est vide, vous pouvez toujours appuyer sur la pédale et conduire la voiture. "

Mais parler n’est pas cher. Regardons les données froides et difficiles. Ou en fait, des données inventées.

Ce sont en fait mes données inventées préférées : le Quatuor d'Anscombe . Créée en 1973 par le statisticien Francis Anscombe, cette délicieuse concoction illustre la folie de la confiance aveugle en méthodes statistiques. Chacun des jeux de données a la même pente de régression linéaire, l'interception, la valeur p et - et pourtant, nous pouvons voir qu'un seul d'entre eux, I , convient à la régression linéaire. Dans II, cela suggère une mauvaise forme, dans III, il est faussé par une seule valeur aberrante - et dans IV, il n'y a clairement aucune tendance!$R^2$

On pourrait dire "La régression linéaire fonctionne toujours dans ces cas, car elle minimise la somme des carrés des résidus." Mais quelle victoire à la Pyrrhus ! La régression linéaire va toujours tracer une ligne, mais si c'est une ligne sans signification, qui s'en soucie?

Nous voyons donc maintenant que le fait d’optimiser ne signifie pas que nous atteignons notre objectif. Et nous voyons que la constitution de données et leur visualisation constituent un bon moyen de contrôler les hypothèses d'un modèle. Accrochez-vous à cette intuition, nous en aurons besoin dans une minute.

Hypothèse cassée: données non sphériques

Vous soutenez que l'algorithme k-means fonctionnera bien sur des grappes non sphériques. Des groupes non sphériques comme ... ceux-ci?

Ce n’est peut-être pas ce à quoi vous vous attendiez, mais c’est un moyen parfaitement raisonnable de construire des grappes. En regardant cette image, nous, les humains, reconnaissons immédiatement deux groupes de points naturels - il n’ya pas de doute. Voyons maintenant comment k-means fonctionne: les affectations sont affichées en couleur, les centres imputés en X.

Eh bien, ce n'est pas correct. K-means essayait de placer une cheville carrée dans un trou rond - en essayant de trouver de beaux centres entourés de sphères soignées - et cela a échoué. Oui, cela minimise toujours la somme des carrés au sein de la grappe, mais comme dans le Quatuor d'Anscombe ci-dessus, c'est une victoire à la Pyrrhus!

Vous pourriez dire "Ce n'est pas un exemple juste ... aucune méthode de clustering ne peut correctement trouver des clusters aussi bizarres." Pas vrai! Essayez la mise en cluster hiérarchique à liaison simple :

J'y suis arrivé! En effet, la mise en grappe hiérarchique à liaison unique établit les bonnes hypothèses pour cet ensemble de données. (Il y a toute une autre classe de situations où cela échoue).

Vous pourriez dire "C'est un cas unique, extrême, pathologique." Mais ce n'est pas! Par exemple, vous pouvez faire du groupe externe un demi-cercle au lieu d'un cercle, et vous verrez que k-means continue à faire terriblement (et que le regroupement hiérarchique fonctionne toujours bien). Je pourrais facilement évoquer d'autres situations problématiques, et ce en deux dimensions seulement. Lorsque vous regroupez des données 16 dimensions, toutes sortes de pathologies peuvent survenir.

Enfin, je dois noter que k-means est toujours récupérable! Si vous commencez par transformer vos données en coordonnées polaires , le regroupement fonctionne désormais:

C'est pourquoi la compréhension des hypothèses sous-jacentes à une méthode est essentielle: elle ne vous dit pas seulement quand une méthode présente des inconvénients, elle vous indique également comment les corriger.

Hypothèse cassée: grappes de taille inégale

Que se passe-t-il si les grappes ont un nombre impair de points - est-ce que cela empêche également la formation de grappes k-signifie? Eh bien, considérons cet ensemble de grappes, de tailles 20, 100, 500. J'ai généré chacune à partir d'une gaussienne multivariée:

Cela ressemble à k-means pourrait probablement trouver ces clusters, non? Tout semble être généré dans des groupes bien rangés. Essayons donc k-means:

Aie. Ce qui s'est passé ici est un peu plus subtil. Dans sa quête pour minimiser la somme des carrés à l'intérieur des grappes, l'algorithme k-means donne plus de "poids" aux grappes plus grandes. En pratique, cela signifie que nous sommes heureux de laisser ce petit groupe atterrir loin de tout centre, tout en utilisant ces centres pour "scinder" un groupe beaucoup plus grand.

Si vous jouez un peu avec ces exemples ( code R ici! ), Vous verrez que vous pouvez construire beaucoup plus de scénarios où k-means obtient une fausse embarrassante.

Conclusion: pas de repas gratuit

Il existe une construction charmante dans le folklore mathématique, formalisée par Wolpert et Macready , appelée "Théorème sans repas gratuit". Il est probablement mon théorème favori dans la philosophie de l' apprentissage machine, et je savoure la moindre chance de l' amener (ai - je mentionné que j'aime cette question?) L'idée de base est déclaré (non rigoureusement) comme ceci: « en moyenne dans toutes les situations possibles, chaque algorithme fonctionne aussi bien. "

Son contre-intuitif? Considérez que pour chaque cas où un algorithme fonctionne, je pourrais construire une situation où il échoue terriblement. La régression linéaire suppose que vos données se situent sur une ligne - mais que se passe-t-il si elle suit une onde sinusoïdale? Un test t suppose que chaque échantillon provient d'une distribution normale: et si vous ajoutiez une valeur aberrante? Tout algorithme d’ascension de gradient peut être piégé dans des maxima locaux, et toute classification supervisée peut être trompée en surapprentissage.

Qu'est-ce que ça veut dire? Cela signifie que ces hypothèses sont la source de votre pouvoir! Lorsque Netflix vous recommande des films, vous supposez que si vous aimez un film, vous aimerez ceux qui sont similaires (et vice-versa). Imaginez un monde où ce n'était pas vrai et où vos goûts sont parfaitement aléatoires: dispersés au hasard parmi les genres, les acteurs et les réalisateurs. Leur algorithme de recommandation échouerait terriblement. Serait-il logique de dire "Eh bien, cela minimise toujours une erreur au carré attendue, donc l'algorithme fonctionne toujours"? Vous ne pouvez pas créer d'algorithme de recommandation sans émettre certaines hypothèses sur les goûts des utilisateurs, tout comme vous ne pouvez pas créer d'algorithme de clustering sans émettre des hypothèses sur la nature de ces clusters.

Alors n'acceptez pas ces inconvénients. Connaissez-les afin qu'ils puissent éclairer votre choix d'algorithmes. Comprenez-les, vous pourrez ainsi peaufiner votre algorithme et transformer vos données pour les résoudre. Et aimez-les, parce que si votre modèle ne peut jamais se tromper, cela signifie qu'il ne sera jamais juste.

Je voudrais juste ajouter à la réponse de @ DavidRobinson que le groupement à une variance totale de cluster minimale est en réalité un problème d' optimisation combinatoire , dont k-Means n'est qu'une technique - et étant donné la nature «unique» de ce dernier, la «descente la plus raide» locale, un très mauvais aussi. Aussi, essayer d'améliorer substantiellement les "os nus" k-Means en cherchant quelque part (mais rapidement!) À savoir où les semences devraient être placées, est voué à l'échec dès le départ: puisque les semences ont un impact (drastique!) Sur les grappes finales, cela revient à: "savoir" quel est l'optimum ... avant de le calculer.

Cependant, comme la plupart des problèmes d'optimisation, il peut néanmoins être sujet à une technique d' optimisation sérieuse . L’un d’eux correspond très étroitement à la structure du problème (comme le demande la NFL!), Et cela se voit certainement dans ses résultats. Je ne veux pas faire de publicité ici (ce serait - et à juste titre - contre l'étiquette), alors si cela vous intéresse, lisez-la ici et faites votre propre jugement.

Ceci étant dit, je conviens avec @ttnphns que k-Means n’identifie certainement pas un mélange gaussien - les fonctions de coût des deux problèmes sont complètement différentes. Il s'avère que trouver le meilleur ajustement (en termes de probabilité du modèle à partir des données) Gaussian Mixture est également un problème d' optimisation combinatoire - et pour lequel une technique d' optimisation sérieuse existe également. Encore une fois, pas de publicité: vous pouvez tirer ici votre propre conclusion - je dirai simplement que l'algorithme qui y est discuté peut en effet identifier correctement les clusters comme la dernière image du message de @ DavidRobinson . Même correctement (c'est-à-dire d'une manière mathématiquement bien définie), le problème persistant des valeurs aberrantes est résolu.C'est-à-dire que les points de données n'appartenant à aucune des grappes, car ils sont simplement aléatoires (notoirement, ils font complètement dérailler k-Means, par exemple). Pour ce faire, une distribution uniforme supplémentaire est en concurrence avec les Gaussiens ... et le résultat est splendide: sur des données uniformément distribuées, il est en effet indiqué qu'il n'y a rien là-dedans (je ne l'ai jamais vu nulle part ailleurs).

Maintenant, évidemment, selon la NFL, et comme vous l'avez dit à juste titre , même les mélanges gaussiens globalement optimaux avec identification des valeurs aberrantes reposent sur une hypothèse préalable, à savoir que les données sont effectivement distribuées normalement. Heureusement cependant, grâce à la loi des grands nombres, de nombreux phénomènes naturels ne sont conformes à cette hypothèse.

AVERTISSEMENT: avec toutes mes excuses, j'ai écrit les deux articles ci-dessus et les algorithmes dont ils discutent.

PS J'ai déjà rencontré Macready lors d'une conférence - un gars extrêmement brillant et gentil!

Logiquement, les inconvénients de K-means sont les suivants:

• nécessite une séparabilité linéaire des grappes
• besoin de spécifier le nombre de clusters
• Algorithmique: la procédure de Loyds ne converge pas vers le vrai maximum global même avec une bonne initialisation lorsqu'il y a beaucoup de points ou de dimensions

Mais K-means est meilleur que ce que nous pensons habituellement. Je suis devenu assez enthousiaste après l'avoir testé par rapport à d'autres méthodes de regroupement (spectrale, densité ...) et à la LDA dans la classification de textes réels d'un million de textes: K-means avait une précision bien supérieure à celle de LDA par exemple (88% vs 59%). Certaines méthodes de regroupement étaient bonnes, mais K-means était proche du sommet… et plus abordable en termes de complexité.

Je n'ai jamais entendu parler d'une méthode de regroupement universellement meilleure pour un large éventail de problèmes. Ne pas dire que K-means est universellement meilleur non plus, mais simplement qu'il n'y a pas de super-héros de clustering universel à ma connaissance. Beaucoup d'articles, beaucoup de méthodes, pas une vraie révolution (dans mon expérience personnelle limitée de tester certains d'entre eux).

La principale raison pour laquelle les inconvénients logiques de K-moyennes ne sont souvent qu'apparents est que la mise en cluster de points dans un plan 2D est une chose que vous faites rarement en apprentissage automatique. Beaucoup de choses de l'intuition géométrique qui sont vraies en 2D, 3D ... ne sont pas pertinentes dans des dimensions plutôt élevées ou des espaces vectoriels abstraits (comme un sac de mots, un vecteur de variables ...)

Séparabilité linéaire: vous devez rarement traiter avec des clusters circulaires dans des données réelles. Il est même préférable de supposer qu'ils n'existent pas dans ces cas. Permettre à votre algorithme de les rechercher lui permettrait de trouver des groupes circulaires impairs dans le bruit. L'hypothèse linéaire dans K-moyennes le rend souvent plus robuste.

Nombre de groupes: Il n'y a souvent pas de nombre idéal idéal de groupes que vous souhaitez voir. Pour la classification de texte par exemple, il peut y avoir 100 catégories, 105, 110 ... tout cela est plutôt subjectif. Spécifier le nombre de clusters devient équivalent à spécifier une granularité globale. De toute façon, toutes les méthodes de clustering nécessitent une spécification de granularité.

Maximum global: Je pense que c'est un vrai problème. Le véritable K-moyen abstrait qui consisterait à trouver le minimum global pour le SOD est fondamentalement NP-Hard. Seul Lloyd est abordable et c'est ... très imparfait. Nous avons vraiment constaté que le fait de se rapprocher du minimum réel (grâce aux répétitions) améliorait nettement la qualité des résultats. La réplication du K-means est une amélioration mais pas une solution parfaite. Pour un grand ensemble de données, vous aurez besoin de réplications de pour avoir une petite chance de trouver le minimum minimal. D'autres méthodes telles que "terminer avec la recherche gourmande" (proposée dans Matlab) sont astronomiquement coûteuses dans de grands ensembles de données.$10^{\text{a lot}}$

Mais tous les algorithmes de clustering ont de telles limitations. Par exemple, dans la classification spectrale: vous ne pouvez pas trouver les vrais vecteurs propres, mais seulement des approximations.

Pour le même temps de calcul, une bibliothèque LDA assez optimisée faisait moins de bien que notre K-means fait maison (pas parfaitement optimisé). Depuis lors, je pense un peu différemment.

Pour comprendre les inconvénients de K-means, j'aime réfléchir au modèle qui le sous-tend.

$K$$K$

$K$$\sigma^2 \mathbf{I}$$\sigma^2$$K$$\sigma^2 \rightarrow 0$

Alors, qu'est-ce que cela nous dit sur les inconvénients de K-means?

1. K-means conduit à des grappes qui ont une apparence gaussienne multivariée.
2. Comme la variance entre les variables est la même, K-moyennes conduit à des grappes qui semblent sphériques.
3. $K$
4. K-means tend vers des groupes de taille égale.

K-means est en fait un algorithme assez restrictif. L'avantage étant qu'avec les hypothèses ci-dessus, vous pouvez exécuter l'algorithme assez rapidement. Mais si la performance du clustering est votre principale préoccupation, K-means est généralement trop restrictif dans des situations réelles.