Comment testez-vous une implémentation de k-means?

Avertissement: j'ai posté cette question sur Stackoverflow, mais je pensais que c'était peut-être mieux adapté à cette plate-forme.

Comment testez-vous votre propre implémentation de k-means pour des ensembles de données multidimensionnels?

Je pensais exécuter une implémentation déjà existante (c'est-à-dire Matlab) sur les données et comparer les résultats avec mon algorithme. Mais cela nécessiterait que les deux algorithmes fonctionnent plus ou moins de la même manière, et la correspondance entre les deux résultats n'est probablement pas un jeu d'enfant.

As-tu une meilleure idée?

Le k-means inclut un composant stochastique, il est donc très peu probable que vous obteniez le même résultat à moins que vous n'ayez exactement la même implémentation et que vous n'utilisiez la même configuration de départ. Cependant, vous pouvez voir si vos résultats sont en accord avec des implémentations bien connues (je ne sais pas pour Matlab, mais l'implémentation de l'algorithme k-means dans R est bien expliquée, voir Hartigan et Wong, 1979 ).

En ce qui concerne la comparaison de deux séries de résultats, il y a toujours un problème avec le changement d'étiquette s'il doit être exécuté plusieurs fois. Encore une fois, dans le package e1071 R, il existe une fonction très pratique (; matchClasses()) qui pourrait être utilisée pour trouver la «meilleure» correspondance entre deux catégories dans une table de classification bidirectionnelle. Fondamentalement, l'idée est de réorganiser les lignes afin de maximiser leur accord avec les colonnes, ou d'utiliser une approche gourmande et de permuter les lignes et les colonnes jusqu'à ce que la somme de la diagonale (accord brut) soit maximale. Un coefficient d'accord comme la statistique de Kappa est également fourni.

Enfin, sur la façon de comparer votre implémentation, il existe de nombreuses données disponibles gratuitement, ou vous pouvez simuler un ensemble de données dédié (par exemple, via un modèle de mélange fini, voir le package MixSim ).

Le mappage entre deux ensembles de résultats est facile à calculer, car les informations que vous obtenez dans un test peuvent être représentées comme un ensemble de trois tuples: le premier composant est un point (multidimensionnel), le second est une étiquette de cluster (arbitraire) fourni par votre algorithme, et le troisième est une étiquette de cluster (arbitraire) fournie par un algorithme de référence. Construire le par $k$$k$tableau de classification des paires d'étiquettes: si les résultats concordent, ce sera un multiple d'une matrice de permutation. Autrement dit, chaque ligne et chaque colonne doivent avoir exactement une cellule non nulle. C'est une simple vérification à programmer. Il est également simple de suivre de petites déviations de cet idéal vers des points de données individuels afin que vous puissiez voir précisément comment les deux réponses diffèrent si elles diffèrent. Je ne prendrais pas la peine de calculer des mesures statistiques de l'accord: soit il y a accord parfait (jusqu'à la permutation), soit il n'y en a pas, et dans ce dernier cas, vous devez rechercher tous les points de désaccord pour comprendre comment ils se produisent. Les résultats sont d'accord ou non; tout désaccord, même en un seul point, doit être vérifié.

Vous pouvez utiliser plusieurs types d'ensembles de données pour les tests: (1) ensembles de données publiés avec résultats k-means publiés; (2) des ensembles de données synthétiques avec des clusters forts évidents; (3) ensembles de données synthétiques sans regroupement évident. (1) est une bonne discipline à utiliser lorsque vous écrivez un programme de mathématiques ou de statistiques. (2) est facile à faire à bien des égards, par exemple en générant des points aléatoires pour servir de centres de grappes, puis en générant des nuages ​​de points en déplaçant aléatoirement les centres de grappes en quantités relativement faibles. (3) fournit des vérifications aléatoires qui peuvent révéler des comportements inattendus; encore une fois, c'est une bonne discipline générale de test.

En outre, envisagez de créer des ensembles de données qui mettent l'accent sur l'algorithme en se situant juste aux limites entre les solutions extrêmes. Cela nécessitera de la créativité et une compréhension approfondie de votre algorithme (ce que vous avez probablement!). Un exemple que je voudrais vérifier dans tous les cas serait des ensembles de vecteurs de la forme où v est un vecteur sans composante nulle et i prend des valeurs intégrales séquentielles 0 , 1 , 2 , … , n - 1 . Je voudrais également vérifier l'algorithme sur des ensembles de vecteurs qui forment des polygones équilatéraux. Dans les deux cas, les cas où n n'est pas$i \mathbb{v}$$\mathbb{v}$$i$$0, 1, 2, \ldots, n-1$$n$un multiple de est particulièrement intéressant, y compris lorsque n est inférieur à k . Ce qui est commun à ces situations, c'est que (a) elles utilisent toutes les dimensions du problème, mais (b) les solutions correctes sont géométriquement évidentes, et (c) il existe plusieurs solutions correctes.$k$$n$$k$

$d \ge 2$$\mathbb{u}$$\mathbb{v}$$2d$$\mathbb{x}$$\mathbb{z}$$\mathbb{x}$$\mathbb{z}$

$\mathbb{y}$$\mathbb{w}$$\mathbb{x}$$\mathbb{y}$$\mathbb{x}$$\mathbb{y}$$d$$n$$\cos(2 \pi k / n) \mathbb{x} + \sin(2 \pi k / n) \mathbb{y}$$k$$0$$n-1$

Une approche «naïve» très simple serait d'utiliser des données synthétiques simples, car chaque implémentation devrait aboutir aux mêmes clusters.

Exemple en Python avec import numpy as np:

test_data = np.zeros((40000, 4))
test_data[0:10000, :] = 30.0
test_data[10000:20000, :] = 60.0
test_data[20000:30000, :] = 90.0
test_data[30000:, :] = 120.0

Car n_clusters = 4cela devrait vous donner une permutation de[30, 60, 90, 120]

Étant donné que k-means contient des décisions qui sont choisies au hasard (la partie d'initialisation uniquement), je pense que la meilleure façon d'essayer votre algorithme est de sélectionner les points initiaux et de les laisser fixés dans votre algorithme d'abord, puis de choisir un autre code source de l'algorithme et fixer les points de la même manière. Ensuite, vous pouvez comparer les résultats réels.