Implémentation de k-means avec matrice de distance personnalisée en entrée

14

Quelqu'un peut-il me signaler une implémentation de k-means (ce serait mieux si dans matlab) qui peut prendre la matrice de distance en entrée? L'implémentation matlab standard nécessite la matrice d'observation en entrée et il n'est pas possible de modifier la mesure de similitude de façon personnalisée.

clustering matlab k-means Eugenio
la source
2
Vous pouvez essayer de générer des données brutes correspondant à votre matrice de distances euclidiennes et les saisir dans K-Means. Une autre approche facile pourrait consister à utiliser la méthode de Ward de regroupement hiérarchique de la matrice: K-Means et Ward partagent une idéologie similaire de ce qu'est un cluster.
ttnphns
en plus de ttnphns et Not Durrett, vous pourriez trouver Est-il correct d'utiliser la distance de Manhattan avec la liaison inter-cluster de Ward dans le clustering hiérarchique? intéressant
steffen
Pas Matlab, mais la page de python sous est-il-possible-de-spécifier-votre-fonction-de-distance-en utilisant-scikits-learn-k-means peut utiliser n'importe laquelle des 20 métriques impaires dans scipy.spatial. distance.
denis

Réponses:

13

Étant donné que k-means doit pouvoir trouver les moyennes de différents sous-ensembles des points que vous souhaitez regrouper, il n'est pas vraiment logique de demander une version de k-means qui prend une matrice de distance en entrée.

Vous pouvez essayer les k-medoids à la place. Certaines implémentations matlab sont disponibles.

NF
la source
1
Salut, merci pour la réponse; au lieu de donner directement la matrice de distance, serait-il possible de donner en entrée une métrique de distance personnalisée? Le fait est que je dois comparer deux méthodes de clustering et, puisque dans la seconde j'utilise une matrice de similarité personnalisée, je veux utiliser la même approche avec kmeans afin d'obtenir une comparaison équitable.
Eugenio
2
ELKI vous permet d'utiliser des fonctions de distance arbitraires avec k-means. Notez que l'algorithme peut ensuite échouer à converger. K-means est vraiment conçu pour la distance euclidienne au carré (somme des carrés). Avec d'autres distances, la moyenne peut ne plus s'optimiser, et boom, l'algorithme ne finira pas par converger. Sérieusement, envisagez d'utiliser des k-médoïdes. En fait, il a été écrit pour permettre d'utiliser l'idée des k-moyennes avec des distances arbitraires .
A QUIT - Anony-Mousse
Il existe également un pyclustering d'une bibliothèque python / C ++ qui vous permet de fournir une fonction métrique personnalisée: github.com/annoviko/pyclustering/issues/417
CpILL
7

Vous pouvez transformer votre matrice de distances en données brutes et les saisir dans le clustering K-Means. Les étapes seraient les suivantes:

1) Les distances entre vos N points doivent être des carrés euclidiens. Effectuer un " double centrage " de la matrice: moyenne de la ligne de soustraction de chaque élément; dans le résultat, soustraire la moyenne des colonnes de chaque élément; dans le résultat, ajoutez la moyenne de la matrice à chaque élément; divisez par moins 2. La matrice que vous avez maintenant est la matrice SSCP (somme des carrés et des produits croisés) entre vos points dans laquelle l'origine est placée au centre géométrique du nuage de N points. (Lire l'explication du double centrage ici .)

2) Effectuer PCA (analyse des composants principaux) sur cette matrice et obtenir la matrice de chargement des composants NxN . Certaines des dernières colonnes sont probablement toutes à 0, alors coupez-les. Ce que vous restez maintenant, ce sont en fait les scores des composants principaux, les coordonnées de vos N points sur les composants principaux qui passent, sous forme d'axes, à travers votre nuage. Ces données peuvent être traitées comme des données brutes adaptées à l'entrée K-Means.

PS Si vos distances ne sont pas géométriquement correctes au carré euclidien, vous pouvez rencontrer un problème: la matrice SSCP peut ne pas être positive (semi) définie. Ce problème peut être résolu de plusieurs manières mais avec une perte de précision.

ttnphns
la source
Merci pour votre réponse! En fait, je n'ai pas de matrice de distances réelles mais une matrice de similitude (0 ... 1) entre les objets, et les similitudes ne sont pas calculées exactement en utilisant les distances euclidiennes mais avec un algorithme personnalisé qui prend en considération les données brutes mais pas dans le manière standard. Je suppose que dans ce cas, je ne peux pas appliquer votre procédure, ai-je raison?
Eugenio
Vous pouvez toujours, après avoir converti les similitudes en distances. Ce dernier ne sera probablement pas un vrai euclidien (et donc le SSCP aura des valeurs propres négatives); essayez ensuite d'ajouter une petite constante aux distances jusqu'à ce que le SSCP perde neg. eig. Il existe également d'autres moyens de contourner le problème. Et n'oubliez pas que vous doublez la matrice centrale des distances au carré .
ttnphns
PS Et au fait. Si votre matrice présente des similitudes, eh bien, c'est encore mieux. Vous le traitez simplement comme la matrice SSCP dont je parlais et vous faites PCA avec. Pourtant, le problème d'éventuelles valeurs propres négatives demeure.
ttnphns
@ttnphns, désolé je manque votre explication à l' étape 1. La matrice de distance X(disons N * N) va être symétrique, donc , colMeans(X) =rowMeans(X) et une fois que vous soustrayez des moyens de ligne ou col: Y=X-rowMeans(X), mean(Y)est 0.
Zhubarb
1
@Zhubarb, quand je dis You could turn your matrix of distances into raw data(points 1 et 2), je me réfère essentiellement à la mise à l'échelle multidimensionnelle (MDS) de Torgerson , dans laquelle le double centrage est l'étape initiale. Veuillez effectuer une recherche sur ce site (et sur Google également) à propos de cette procédure. Le "double centrage" est la conversion des distances (au carré) en la matrice de produit scalaire correspondante définie sur l'origine placée dans le centre de gravité du nuage des points.
ttnphns
3

Veuillez consulter cet article, rédigé par l'une de mes connaissances;)

http://arxiv.org/abs/1304.6899

Il s'agit d'une implémentation généralisée de k-means, qui prend en entrée une matrice de distance arbitraire. Il peut s'agir de n'importe quelle matrice symétrique non négative avec une diagonale nulle. Notez qu'il peut ne pas donner de résultats sensibles pour des matrices de distances étranges. Le programme est écrit en C #.

Le code source peut être obtenu en visitant le lien ci-dessus, puis en cliquant sur Autres formats, puis sur Télécharger la source. Ensuite, vous obtiendrez un .tar.gz contenant Program.cs. Alternativement, le code source peut également être copié à partir du PDF.

szali
la source
3

Vous pouvez utiliser la bibliothèque Java Machine Learning. Ils ont une implémentation K-Means. L'un des constructeurs accepte trois arguments

  1. Valeur K.
  2. Un objet de cela est une instance de la classe DistanceMeasure .
  3. Nombre d'itérations.

On peut facilement étendre la classe DistanceMeasure pour obtenir le résultat souhaité. L'idée est de renvoyer les valeurs d'une matrice de distance personnalisée dans la méthode de mesure (Instance x, Instance y) de cette classe.

K-Means est incarné pour converger en supposant certaines propriétés de la métrique de distance. La distance euclidienne, la distance de Manhattan ou d'autres métriques standard satisfont à ces hypothèses. Puisqu'une mesure de distance personnalisée peut ne pas satisfaire ces hypothèses, le constructeur a un troisième paramètre spécifiant le nombre d'itérations à exécuter pour la construction du cluster.

Chaitanya Shivade
la source