Y a-t-il des cas où il n'y a pas de k optimal dans k-moyennes?

Cela me vient à l'esprit depuis au moins quelques heures. J'essayais de trouver un k optimal pour la sortie de l'algorithme k-means (avec une métrique de similitude cosinus ), donc j'ai fini par tracer la distorsion en fonction du nombre de grappes. Mon ensemble de données est une collection de 800 documents dans un espace à 600 dimensions.

D'après ce que je comprends, trouver le point du genou ou du coude sur cette courbe devrait me dire au moins approximativement le nombre de clusters dans lesquels je dois mettre mes données. Je mets le graphique ci-dessous. Le point auquel la ligne verticale rouge a été tracée a été obtenu en utilisant le test de dérivée seconde maximale . Après avoir fait tout cela, j'étais coincé à quelque chose de beaucoup plus simple: qu'est-ce que ce graphique me dit sur l'ensemble de données?

Est-ce que cela me dit que cela ne vaut pas la peine d'être regroupé et que mes documents manquent de structure ou que je dois définir un k très élevé? Une chose étrange cependant, c'est que même avec un faible k, je vois des documents similaires regroupés, donc je ne sais pas pourquoi je reçois cette courbe. Des pensées?

Dans la plupart des situations, j'aurais pensé qu'un tel tracé signifie essentiellement qu'il n'y a pas de structure de cluster dans les données. Cependant, le regroupement dans des dimensions très élevées telles que celle-ci est délicat car pour la métrique de distance euclidienne, toutes les distances ont tendance à être les mêmes lorsque le nombre de dimensions augmente. Voir cette page Wikipedia pour les références à certains articles sur ce sujet. En bref, c'est peut-être simplement la haute dimensionnalité de l'ensemble de données qui pose problème.

C'est essentiellement "la malédiction de la dimensionnalité", voir aussi cette page Wikipedia.

Un article qui peut être intéressant est Sanguinetti, G., "Dimensionality reduction of clustered datsets", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30 non. 3, pp. 535-540, mars 2008 ( www ). Ce qui est un peu comme une version non supervisée de LDA qui recherche un espace de faible dimension qui met l'accent sur la structure du cluster. Peut-être pourriez-vous l'utiliser comme méthode d'extraction de fonctionnalités avant d'effectuer k-means?

Comment utilisez-vous exactement la similitude cosinus? Est-ce ce que l'on appelle des K-means sphériques? Votre ensemble de données est assez petit, donc j'essaierais de le visualiser comme un réseau. Pour cela, il est naturel d'utiliser une similitude (en effet, par exemple, la similitude en cosinus ou la corrélation de Pearson), d'appliquer une coupure (ne considérer que les relations au-dessus d'une certaine similitude) et d'afficher le résultat sous forme de réseau dans par exemple Cytoscape ou BioLayout . Cela peut être très utile pour avoir une idée des données. Deuxièmement, je calculerais les valeurs singulières de votre matrice de données, ou les valeurs propres d'une matrice correctement transformée et normalisée (une matrice document-document obtenue sous une certaine forme). La structure de cluster doit (à nouveau) apparaître comme un saut dans la liste ordonnée des valeurs propres ou des valeurs singulières.

Généralement oui, k-means peut converger vers des solutions très distinctes qui peuvent être jugées inappropriées. Cela se produit en particulier pour les clusters aux formes irrégulières.

Pour obtenir plus d'intuition, vous pouvez également essayer une autre approche de visualisation: pour k-means, vous pouvez visualiser plusieurs exécutions avec k-means en utilisant Graphgrams (voir le package de graphogrammes WEKA - mieux obtenu par le gestionnaire de packages ou ici . Une introduction et des exemples peuvent également être trouvé ici .

Si je comprends bien le graphique, c'est un tracé du nombre de grappes, K sur l'axe des x et la distance à l'intérieur des grappes sur l'axe des y?

Parce que votre fonction objective K-means est de minimiser le WCSS, ce tracé doit toujours être monotone décroissant. Lorsque vous ajoutez des clusters, la distance entre les points du cluster diminue toujours. C'est le problème fondamental de la sélection des modèles, vous devez donc utiliser un peu plus de sophistication.

Essayez peut-être la statistique Gap: www-stat.stanford.edu/~tibs/ftp/gap.ps ou d'autres similaires.

En outre, vous pouvez constater que K-means n'est pas le bon outil pour le travail. Combien de grappes espérez-vous trouver? L'utilisation de la règle de variance pour la réduction de dimensionnalité pour le clustering n'est pas appropriée. Consultez cet article pour savoir quand la projection sur les premiers PC K-1 est une mesure de prétraitement appropriée: http://people.csail.mit.edu/gjw/papers/jcss.ps

Vous pouvez rapidement voir si c'est la bonne chose à faire en traçant la projection sur les deux premiers composants principaux. S'il y a une séparation claire, alors K-means devrait être correct, sinon vous devez chercher autre chose. Peut-être des sous-espaces K ou d'autres méthodes de regroupement de sous-espaces. Gardez à l'esprit que ces méthodes s'appliquent à la distance euclidienne. Je ne sais pas comment cela change pour le cosinus.