Comment savoir si les données sont suffisamment «regroupées» pour que les algorithmes de regroupement produisent des résultats significatifs?

Comment sauriez-vous si vos données (de haute dimension) présentent suffisamment de clustering pour que les résultats de kmeans ou d'un autre algorithme de clustering soient réellement significatifs?

Pour l'algorithme k-means en particulier, quelle réduction de la variance au sein d'une grappe devrait-il y avoir pour que les résultats de la grappe soient significatifs (et non parasites)?

Le regroupement devrait-il être apparent lorsqu'une forme de données de dimensions réduites est tracée, et les résultats de kmeans (ou d'autres méthodes) n'ont-ils pas de sens si le regroupement ne peut pas être visualisé?

À propos de k-means en particulier, vous pouvez utiliser les statistiques Gap. Fondamentalement, l’idée est de calculer la qualité d’une mesure de classification basée sur la dispersion moyenne comparée à une distribution de référence pour un nombre croissant de grappes. Plus d'informations peuvent être trouvées dans l'article original:

Tibshirani, R., Walther, G. et Hastie, T. (2001). Estimation du nombre de grappes dans un ensemble de données via la statistique des écarts . JR Statist. Soc. B, 63 (2): 411-423.

La réponse que j'ai fournie à une question connexe met en évidence d'autres indices de validité généraux pouvant être utilisés pour vérifier si un ensemble de données donné présente une sorte de structure.

Lorsque vous ne savez pas ce que vous attendez s'il n'y a que du bruit, une bonne approche consiste à utiliser le rééchantillonnage et à étudier la stabilité des grappes. En d'autres termes, rééchantillonnez vos données (via bootstrap ou en y ajoutant un petit bruit) et calculez la "proximité" des partitions résultantes, mesurée par les similitudes de Jaccard . En bref, cela permet d’estimer la fréquence avec laquelle des grappes similaires ont été récupérées dans les données. Cette méthode est facilement disponible dans le package fpc R en tant que clusterboot(). Il prend en entrée des données brutes ou une matrice de distance et permet d'appliquer un large éventail de méthodes de classification (méthodes hiérarchiques, k-moyennes, floues). La méthode est discutée dans les références liées:

Hennig, C. (2007) Evaluation par grappes de la stabilité des grappes . Statistiques de calcul et d'analyse de données , 52, 258-271.

Hennig, C. (2008) Point de dissolution et robustesse d'isolement: critères de robustesse pour les méthodes générales d'analyse par grappes . Journal of Multivariate Analysis , 99, 1154-1176.

Vous trouverez ci-dessous une petite démonstration avec l'algorithme k-means.

sim.xy <- function(n, mean, sd) cbind(rnorm(n, mean[1], sd[1]),
rnorm(n, mean[2],sd[2]))
xy <- rbind(sim.xy(100, c(0,0), c(.2,.2)),
            sim.xy(100, c(2.5,0), c(.4,.2)),
            sim.xy(100, c(1.25,.5), c(.3,.2)))
library(fpc)
km.boot <- clusterboot(xy, B=20, bootmethod="boot",
                       clustermethod=kmeansCBI,
                       krange=3, seed=15555)

Les résultats sont assez positifs dans cet ensemble de données artificiel (et bien structuré) puisqu’aucune des trois grappes ( krange) n’a été dissoute entre les échantillons et que la similarité moyenne par Jaccard par grappe est> 0,95 pour toutes les grappes.

Vous trouverez ci-dessous les résultats sur les 20 échantillons bootstrap. Comme on peut le constater, les unités statistiques ont tendance à rester groupées dans le même groupe, à quelques exceptions près pour les observations intermédiaires.

Vous pouvez bien sûr étendre cette idée à n’importe quel indice de validité: choisissez une nouvelle série d’observations par bootstrap (avec remplacement), calculez votre statistique (par exemple, largeur de la silhouette, corrélation cophénétique, gamma de Hubert, dans la somme des carrés) les numéros de grappes (par exemple, 2 à 10), répétez 100 ou 500 fois et examinez le diagramme en boîte de vos statistiques en fonction du nombre de grappes.

Voici ce que j’obtiens avec le même jeu de données simulé, mais en utilisant la classification hiérarchique de Ward et en prenant en compte la corrélation cophénétique (qui évalue la qualité de la reproduction des informations de distance dans les partitions résultantes) et la largeur de la silhouette (mesure combinant l’homogénéité intra-grappe et séparation des grappes).

La corrélation cophénétique varie de 0,6267 à 0,7511 avec une valeur médiane de 0,7031 (500 échantillons bootstrap). La largeur de la silhouette semble être maximale quand on considère 3 groupes (médiane 0,8408, plage 0,7371-0,8769).

Un moyen de visualiser rapidement si les données de grande dimension présentent suffisamment de regroupement consiste à utiliser l'incorporation stochastique du voisin t-distribuée ( t-SNE ). Il projette les données dans un espace de faible dimension (par exemple 2D, 3D) et fait un très bon travail pour conserver la structure de cluster, le cas échéant.

Par exemple , ensemble de données MNIST :

Olivetti fait face à l'ensemble de données:

Certes, la capacité de discerner visuellement les grappes dans un nombre de dimensions pouvant être tracé est un critère douteux pour l’utilité d’un algorithme de classification, en particulier si cette réduction de dimension est effectuée indépendamment de la classification elle-même (c’est-à-dire: le regroupement fonctionnera).

En fait, les méthodes de regroupement ont la plus grande valeur dans la recherche des groupes où l’œil / l’esprit humain est incapable de voir les groupes.

La réponse simple est: faites un clustering, puis vérifiez si cela a fonctionné (avec l’un des critères qui vous intéressent, voir aussi la réponse de @ Jeff).

Quand les résultats ont-ils un sens ? En particulier, k-mean résultats?

Le fait est que k-means optimise une statistique mathématique donnée. Il n'y a pas de "sens" associé à cela.

En particulier pour les données de grande dimension, la première question devrait être: la distance euclidienne est-elle toujours significative ? Sinon, n'utilisez pas de k-moyennes. La distance euclidienne a un sens dans le monde physique, mais perd rapidement son sens lorsque vous avez d'autres données. En particulier, lorsque vous transformez artificiellement des données en un espace vectoriel, y a-t-il une raison pour laquelle elles devraient être euclidiennes?

Si vous prenez le jeu de données «vieux fidèle» classique et que vous y exécutez k-means sans normalisation, mais avec une distance euclidienne pure, cela n'a déjà plus de sens. La MÉ, qui utilise en fait une certaine forme de "distance locale" de Mahalanobis, fonctionnera beaucoup mieux. En particulier, il s’adapte aux axes ayant des échelles très différentes.

Par ailleurs, l'un des points forts de k-means est qu'il ne partitionnera en fait que les données, peu importe à quoi elles ressemblent. Vous pouvez utiliser k-means pour partitionner le bruit uniforme en k grappes . On peut affirmer que, de toute évidence, les grappes k-moyennes ne sont pas significatives. On peut aussi accepter ceci: l'utilisateur voulait partitionner les données afin de minimiser les distances euclidiennes au carré, sans exiger que les clusters soient "significatifs".

Je viens tout juste de commencer à utiliser des algorithmes de clustering récemment, alors j'espère qu'une personne plus informée pourra fournir une réponse plus complète, mais voici quelques réflexions:

Comme vous le savez sans doute, «significatif» est très subjectif. Donc, si le regroupement est suffisamment bon dépend entièrement de la raison pour laquelle vous devez regrouper en premier lieu. Si vous essayez de prédire l'appartenance à un groupe, il est probable que tout regroupement fera mieux que le hasard (et non le pire), de sorte que les résultats devraient être significatifs dans une certaine mesure.

Si vous voulez savoir à quel point ce cluster est fiable , vous avez besoin d'un indicateur pour le comparer. Si vous avez un ensemble d'entités avec des appartenances connues, vous pouvez utiliser une analyse discriminante pour voir la qualité des prédictions. Si vous n'avez pas un ensemble d'entités avec des appartenances connues, vous devrez savoir quelle variance est typique des clusters dans votre domaine. Les attributs physiques des entités avec des catégories rigides sont susceptibles d'avoir une variance au sein du groupe beaucoup plus faible que les données psychométriques sur les humains, mais cela ne rend pas nécessairement la classification plus «mauvaise».

Votre deuxième question fait référence à «Quelle valeur de k devrais-je choisir? Encore une fois, il n'y a pas de réponse difficile ici. En l'absence d'un ensemble de catégories a priori, vous souhaiterez probablement minimiser le nombre de clusters tout en minimisant la variance moyenne des clusters. Une approche simple pourrait consister à tracer le «nombre de grappes» par rapport à la «variance de grappe moyenne» et à rechercher le «coude» - pour lequel l'ajout de plusieurs grappes n'a pas d'impact significatif sur la variance de votre grappe.

Je ne dirais pas que les résultats de k-means n'ont pas de sens s'ils ne peuvent pas être visualisés, mais ils sont certainement attrayants lorsque les grappes sont visuellement apparentes. Cela nous ramène à la question: pourquoi avez-vous besoin de faire du clustering et quelle est votre fiabilité? En fin de compte, vous devez répondre à cette question en fonction de votre utilisation des données.

Pour savoir si un cluster est significatif, vous pouvez exécuter un algorithme pour compter le nombre de clusters et voir s'il génère quelque chose de plus grand que 1.

$k$$k$

$k$$k$