Mesure de la qualité du clustering

J'ai un algorithme de clustering (pas k-means) avec le paramètre d'entrée (nombre de clusters). Après avoir effectué le clustering, j'aimerais obtenir une mesure quantitative de la qualité de ce clustering. L'algorithme de clustering a une propriété importante. Pour si j'alimente points de données sans aucune distinction significative entre eux à cet algorithme, j'obtiendrai un cluster contenant points de données et un cluster avec point de données. Ce n'est évidemment pas ce que je veux. Je souhaite donc calculer cette mesure de qualité pour estimer le caractère raisonnable de ce regroupement. Idéalement, je pourrai comparer ces mesures pour différents . Je vais donc exécuter un clustering dans la plage de$k$$k=2$$N$$N-1$$1$$k$$k$et choisissez celui avec la meilleure qualité. Comment calculer une telle mesure de qualité?

MISE À JOUR:

Voici un exemple lorsque est un mauvais clustering. Disons qu'il y a 3 points sur un plan formant un triangle équilatéral. Diviser ces points en 2 grappes est évidemment pire que de les diviser en 1 ou 3 grappes.$(N-1, 1)$

Le choix de la métrique dépend plutôt de ce que vous considérez comme le but du clustering. Personnellement, je pense que le regroupement devrait viser à identifier différents groupes d'observations générés chacun par un processus de génération de données différent. Je testerais donc la qualité d'un clustering en générant des données à partir de processus de génération de données connus, puis je calculerais la fréquence à laquelle les modèles sont mal classés par le clustering. Bien sûr, cela impliquait de faire des hypothèses sur la distribution des modèles de chaque processus de génération, mais vous pouvez utiliser des ensembles de données conçus pour une classification supervisée.

D'autres considèrent le clustering comme tentant de regrouper des points avec des valeurs d'attribut similaires, auquel cas des mesures telles que SSE, etc. sont applicables. Cependant, je trouve cette définition de clustering plutôt insatisfaisante, car elle ne vous dit que quelque chose sur l'échantillon particulier de données, plutôt que quelque chose de généralisable sur les distributions sous-jacentes. La façon dont les méthodes traitent les clusters qui se chevauchent est un problème particulier avec cette vue (pour la vue "processus de génération de données", elle ne pose aucun problème réel, vous obtenez simplement des probabilités d'appartenance à un cluster).

Le clustering n'étant pas supervisé, il est difficile de savoir a priori quel est le meilleur clustering. C'est un sujet de recherche. Gary King, un spécialiste des sciences sociales quantitatif bien connu, a un prochain article sur ce sujet.

Ici, vous avez quelques mesures, mais il y en a beaucoup plus:

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

Distance inter cluster: somme de la distance carrée entre chaque centre de gravité du cluster.

Distance intra-cluster pour chaque cluster: somme de la distance carrée entre les éléments de chaque cluster et son centre de gravité.

Rayon maximum: la plus grande distance d'une instance à son centre de gravité de cluster.

Rayon moyen: somme de la plus grande distance d'une instance à son centre de gravité de cluster divisé par le nombre de clusters.

Vous êtes tombé sur la zone de validation de clustering. Mon élève a effectué la validation en utilisant les techniques décrites dans:

A. Banerjee et RN Dave. Validation des clusters à l'aide de la statistique hopkins. 2004 Conférence internationale de l'IEEE sur les systèmes flous IEEE Cat No04CH37542, 1: p. 149-153, 2004.

Il est basé sur le principe que si un cluster est valide, les points de données sont uniformément répartis au sein d'un cluster.

Mais avant cela, vous devez déterminer si vos données ont une prétendue tendance de clustering, c'est-à-dire si cela vaut la peine d'être clusterisé et le nombre optimal de clusters:

S. Saitta, B. Raphael et IFC Smith. Un indice de validité complet pour le clustering. Intell. Données Anal., 12 (6): p. 529–548, 2008.

Comme d'autres l'ont souligné, il existe de nombreuses mesures de regroupement de la «qualité»; la plupart des programmes minimisent l'ESS. Aucun chiffre ne peut en dire long sur le bruit dans les données, ou le bruit dans la méthode, ou les minima plats - points bas en Saskatchewan.

Essayez donc d'abord de visualiser, de vous faire une idée d'un clustering donné, avant de le réduire à "41". Faites ensuite 3 runs: obtenez-vous les SSE 41, 39, 43 ou 41, 28, 107? Quelles sont les tailles et les rayons des grappes?

(Ajouté :) Jetez un œil aux graphiques de silhouette et aux scores de silhouette, par exemple dans le livre d'Izenman, Modern Multivariate Statistical Techniques (2008, 731p, isbn 0387781889).

La silhouette peut être utilisée pour évaluer les résultats du clustering. Pour ce faire, il compare la distance moyenne au sein d'un cluster avec la distance moyenne aux points du cluster le plus proche.

Une méthode telle que celle utilisée dans la forêt aléatoire non supervisée pourrait être utilisée.

Les algorithmes de forêt aléatoire traitent la classification non supervisée comme un problème à deux classes, où un ensemble de données artificiel et aléatoire complètement différent est créé à partir du premier ensemble de données en supprimant la structure de dépendance dans les données (randomisation).

Vous pouvez ensuite créer un tel ensemble de données artificiel et aléatoire, appliquer votre modèle de clustering et comparer la métrique de votre choix (par exemple, SSE) dans vos vraies données et vos données aléatoires.

Mélanger dans la randomisation, la permutation, le bootstrap, l'ensachage et / ou le jacknifing pourrait vous donner une mesure similaire à une valeur P en mesurant le nombre de fois qu'un modèle de clustering donné vous donne une valeur plus petite pour vos vraies données que vos données aléatoires en utilisant une métrique de choix (par exemple, SSE, ou prédiction d'erreur hors du sac).

Votre métrique est donc la différence (probabilité, différence de taille, ...) dans toute métrique de choix entre des données vraies et aléatoires.

Itérer cela pour de nombreux modèles vous permettrait de distinguer les modèles.

Cela peut être implémenté dans R.

randomforest est disponible en R

Si l'algorithme de regroupement n'est pas déterministe, essayez de mesurer la «stabilité» des regroupements - découvrez à quelle fréquence chaque observation appartient au même regroupement. C'est une méthode généralement intéressante, utile pour choisir l'algorithme k dans kmeans.