Clustering matrice de similarité cosinus
Quelques questions sur stackoverflow mentionner ce problème, mais je n'ai pas trouvé de solution concrète.
J'ai une matrice carrée qui se compose de cosinus des similitudes (les valeurs entre 0 et 1), par exemple:
| A | B | C | D
A | 1.0 | 0.1 | 0.6 | 0.4
B | 0.1 | 1.0 | 0.1 | 0.2
C | 0.6 | 0.1 | 1.0 | 0.7
D | 0.4 | 0.2 | 0.7 | 1.0
Le carré de la matrice peuvent être de toute taille. Je veux obtenir des clusters (je ne sais pas combien) pour maximiser les valeurs entre les éléments du cluster. I. e. pour l'exemple ci-dessus je devrais obtenir deux groupes:
- B
- A, C, D
La raison d'être parce que C & D ont la valeur la plus élevée entre eux, et Un & C ont également la valeur la plus élevée entre eux.
Un élément peut être en un seul cluster.
De rappel n'est pas si important que cela pour ce problème, mais la précision est très importante. Il est acceptable pour une sortie en trois groupes: 1) B, 2), 3) C, D . Mais il n'est pas acceptable pour la sortie toute solution où B est dans un cluster avec un autre élément.
Je pense que la diagonale (1.0) de me confondre. Mes données est la garantie d'avoir au moins un cluster de 2+ éléments, et je veux trouver autant de clusters que possible sans pour autant sacrifier la précision.
Je vais devoir mettre en Python.
- Avez-vous essayé de clustering hiérarchique? Cela sonne exactement ce que vous essayez, classification ascendante hiérarchique de clustering.
Vous devez vous connecter pour publier un commentaire.
Vous pouvez facilement le faire en utilisant spectral clustering. Vous pouvez utiliser le prêt implémentations comme dans la sklearn ou de mettre en œuvre vous-même. Il est plutôt facile de l'algorithme.
Voici un morceau de code de le faire en python à l'aide de sklearn:
Comme vous pouvez le voir, il renvoie à la mise en cluster que vous avez mentionnés.
L'algorithme prend le dessus k vecteurs propres de la matrice d'entrée correspondant aux plus grandes valeurs propres, puis exécute les k-moyennes de l'algorithme sur la nouvelle matrice. Voici un code simple qui fait cela pour votre matrice:
Noter que la mise en œuvre de l'algorithme dans le sklearn bibliothèque peuvent différer de la mienne. L'exemple que j'ai donné est la façon la plus simple de le faire. Il y a quelques bon tutoriel disponible en ligne décrivant l'algorithme de clustering spectral en profondeur.
Pour le cas, vous souhaitez que l'algorithme pour déterminer le nombre de clusters par lui-même, vous pouvez utiliser de la Densité en Fonction Algorithmes de Clustering comme DBSCAN: