Effectuer un regroupement K-means (ou ses proches parents) avec uniquement une matrice de distance, pas des données de points par entités

Je veux effectuer un regroupement K-means sur les objets que j'ai, mais les objets ne sont pas décrits comme des points dans l'espace, c'est-à-dire par objects x featuresensemble de données. Cependant, je suis capable de calculer la distance entre deux objets quelconques (il est basé sur une fonction de similitude). Donc, je dispose de la matrice de distance objects x objects.

J'ai déjà implémenté K-means, mais c'était avec une entrée de jeu de données de points; et avec une entrée de matrice de distance, il n'est pas clair pour moi comment mettre à jour les grappes pour être les «centres» de grappe sans représentation ponctuelle. Comment cela se ferait-il normalement? Existe-t-il des versions de K-means ou des méthodes proches de cela?

De toute évidence, k-means doit être capable de calculer des moyennes .

Cependant, il en existe une variante bien connue connue sous le nom de k-medoids ou PAM (Partitioning Around Medoids), où le médoïde est l' objet existant le plus central du cluster. K-medoids n'a besoin que des distances par paires.

Vous décrivez exactement le problème posé par les -moyens du noyau ; lorsque vous ne pouvez pas représenter un point de données comme un vecteur euclidien, mais si vous pouvez toujours calculer (ou définir) le produit interne entre deux points de données, vous pouvez noyaliser l'algorithme. La page Web suivante fournit une brève description de l'algorithme:$k$

Page moyens du noyau$k$

Cette astuce du noyau est une idée très populaire et fondamentale en statistiques et en apprentissage automatique.

Page wiki sur l'astuce du noyau

Si vous êtes intéressé, le livre Learning with Kernels de Bernhard Schölkopf et Alexander J. Smola sera une très belle introduction.

Cette note de Max Welling semble très agréable; En outre, si vous utilisez R , vous pouvez jeter un oeil à ce paquet R .

MDS peut être un moyen unique de résoudre votre problème, mais il n'attaque pas directement le problème que vous souhaitez résoudre; contrairement au noyau k-means.

@gung a absolument raison de vous suggérer une mise à l'échelle multidimensionnelle (MDS) comme outil préliminaire pour créer des points X dimensions données à partir d'une matrice de distance. Je ne dois ajouter que quelques traits. Le regroupement K-means implique des distances euclidiennes . MDS vous donnera des coordonnées de points en dimensions vous garantissant ainsi des distances euclidiennes. Vous devez utiliser une MDS métrique et demander un nombre de dimensions aussi grand que possible, car votre objectif est de minimiser les erreurs de reconstruction des données, et non de les cartographier en 2D ou 3D.

Que faire si vous n'avez pas de logiciel MDS à portée de main mais avez des fonctions matricielles telles que la décomposition de valeurs propres ou la décomposition de valeurs singulières? Ensuite, vous pouvez faire vous - même un MDS métrique simple - Torgerson MDS, également connu sous le nom d'analyse de coordonnées principales (PCoA). Cela revient à une analyse des composants principaux un peu "tordue". Je ne vais pas le décrire ici, bien que ce soit assez simple. Vous pouvez le lire à de nombreux endroits, par exemple ici .

Enfin, il est possible de programmer directement «K-means for distance matrix input» - sans appeler ni écrire de fonctions faisant PCoA ou autre MDS métrique. Nous savons que (a) la somme des écarts au carré du centroïde est égale à la somme des distances euclidiennes au carré divisées par le nombre de points; et (b) savoir calculer les distances entre les centroïdes de grappe à partir de la matrice de distance ; (c) et nous savons en outre comment les sommes des carrés sont interdépendantes dans les K-moyennes. Tout cela fait de l'écriture de l'algorithme que vous voulez une entreprise simple et non complexe. Il faut cependant se rappeler que K-means est uniquement pour les distances euclidiennes / l'espace euclidien. Utilisez des K-medoids ou d'autres méthodes pour les distances non euclidiennes.

Une question similaire .

Je ne sais certainement pas comment cela se fait "normalement", et pour mémoire, je ne connais pas grand-chose à l'analyse de grappes. Cependant, connaissez-vous la mise à l'échelle multidimensionnelle ? ( Voici une autre référence, le wiki , et vous pouvez rechercher CV sous la balise de mise à l'échelle multidimensionnelle .) La mise à l'échelle multidimensionnelle prend une matrice de distances par paires, ce qui ressemble à votre situation. À partir du MDS, vous pouvez obtenir les emplacements des objets dans l'espace de dimension la plus basse nécessaire pour les représenter correctement. Je suppose que vous pourriez utiliser ces emplacements pour effectuer une analyse de cluster ultérieure comme k-means; alternativement, une fois que vous avez eu la sortie, vous n'aurez peut-être plus besoin de l'autorité de certification.

Je ne sais pas si vous utilisez R, mais voici la vue des tâches pour Psychometrics, qui comprend une section sur MDS dans R. Hope qui aide.

Un cluster optimal préservant l'incorporation de données de proximité non métriques devrait convenir à votre cas. Le papier montre comment vous pouvez obtenir une représentation vectorielle métrique de vos objets étant donné seulement une matrice de fonction de dissimilarité par paire de sorte que les affectations de cluster seront préservées pour une gamme d'algorithmes de clustering, y compris -means.$k$

Dans votre cas, ce que vous devez essentiellement faire est:

1. Ayez votre matrice de dissimilarité avec zéro auto-dissimilarité.$D$
2. Dans le cas où il n'est pas déjà symétrique, symétrisez en faisant la moyenne de et . D j $D_{ij}$$D_{ji}$
3. le centrer (c'est-à-dire soustraire la ligne et la colonne moyenne) pour obtenir$D^c$
4. Calculer$S^c = -\frac{1}{2}D^c$
5. Effectuer un décalage spectral: Soustraire le « plus petite valeur propre de de » spectre de faire en sorte qu'il devient positive semi - définie. Faites ceci pour obtenir .S c ˜ S$S^c$$S^c$$\tilde S^c$
6. Calculez la décomposition du vecteur propre de .$\tilde S^c = V \Lambda V^\top$
7. Restaurez une représentation vectorielle dans un espace métrique à dimensions de vos données: .X = V Λ 1 /$n-1$$X = V\Lambda^{1/2}$

Cela suppose que n'est pas trop grand. Si tel est le cas, faire en plus PCA vous donnera une représentation plus significative des données. (Le document décrit également comment procéder).$n$

Vos données peuvent également être visualisées en tant que réseau et vous pouvez utiliser l'un des nombreux algorithmes de clustering de réseau disponibles. Pour cela, vous devrez probablement appliquer un seuil sur les poids des bords et transformer les distances en similitudes. Ce n'est pas la façon de faire les «statistiques», mais l'analyse de cluster est un problème sous-spécifié pour commencer, et comme les outils d'exploration, les algorithmes de clustering de réseau fonctionnent très bien.

Je ne sais pas pourquoi c'est si rare dans la littérature, mais la solution suggérée par @gung et @ttnphns (projetant d'abord vos distances par paires dans un espace euclidien en utilisant l'analyse des coordonnées principales, par exemple via ce package si vous utilisez R, puis faire K-signifie de façon habituelle) est simple et ne nécessite pas d'algorithmes spécialisés. Personnellement, je l'ai utilisé ici intégré dans un cadre d'optimisation et cela a plutôt bien fonctionné.

En ce qui concerne le clustering et MDS, je suggère les ressources suivantes:

• Écologie numérique (Pierre Legendre et Louis Legendre): http://www.sciencedirect.com/science/bookseries/01678892/20 ou http://tinyurl.com/cgrdfqk (google books) - chapitre sur la «ressemblance écologique»
• Analyse des clusters (Brian S. Everitt, Sabine Landau, Morven Leese, Daniel Stahl): http://tinyurl.com/bld7k8h (google books) - chapitre sur 'Mesure de la proximité'
• Cours «Biostatistique-II, méthodes multivariées» par le professeur Brian C. McCarthy à l'Université de l'Ohio: http://www.ohio.edu/plantbio/staff/mccarthy/multivariate/multivariate.htm

Ces références couvrent également bien les sujets des fonctions de similitude et de distance (mesures de proximité) pour les données binaires et continues.