Regroupement avec similitude cosinus

8

J'ai un grand ensemble de données et une similitude cosinus entre eux. Je voudrais les regrouper en utilisant la similitude cosinus qui assemble des objets similaires sans avoir à spécifier au préalable le nombre de clusters que j'attends.

J'ai lu la documentation sklearn de DBSCAN et Affinity Propagation, où les deux nécessitent une matrice de distance (pas une matrice de similitude en cosinus).

Vraiment, je cherche juste un algorithme qui ne nécessite pas a) une métrique de distance et b) un nombre prédéfini de clusters .

Quelqu'un connaît-il un algorithme qui ferait cela?

Smith Volka
la source

Réponses:

8

Tout d'abord, chaque algorithme de clustering utilise une sorte de métrique de distance. Ce qui est en fait important, car chaque métrique a ses propres propriétés et convient à différents types de problèmes.

Vous avez dit que vous aviez une similitude cosinus entre vos enregistrements, il s'agit donc en fait d'une matrice de distance. Vous pouvez utiliser cette matrice comme entrée dans un algorithme de clustering.

Maintenant, je suggère de commencer par le clustering hiérarchique - il ne nécessite pas un nombre défini de clusters et vous pouvez soit saisir des données et sélectionner une distance, soit saisir une matrice de distance (où vous avez calculé la distance d'une manière ou d'une autre).

Notez que le clustering hiérarchique est coûteux à calculer, donc si vous avez beaucoup de données, vous pouvez commencer avec juste un échantillon.

HonzaB
la source
Merci pour la réponse utile. J'ai un problème similaire comme ce datascience.stackexchange.com/questions/20198 et je voudrais utiliser la réponse qui y est donnée. Cependant, pour trouver les points les plus proches du centroïde, il utilise la distance cosinus minimale. Si j'utilise la similitude cosinus, serait-ce la similitude cosinus la plus élevée?
Smith Volka
1
Vous pouvez simplement convertir la distance en similitude. Si la distance entre A et B est de 0,3, la similitude sera de 1 à 0,3 = 0,7.
HonzaB
3

DBSCAN peut être mis en œuvre de manière triviale avec une mesure de similitude au lieu d'une distance. Vous avez juste besoin de changer le <= epsilon en>> epsilon.

HAC fonctionne également très bien avec les similitudes (au moins lien unique, lien complet, UPGMA, WPGMA - n'utilisez pas Ward), si vous échangez "min" et "max" (vous voulez fusionner avec une similitude maximale plutôt que minimale) distance).

Si vous êtes paresseux, vous pouvez également transformer votre similitude en distance. Si vous avez un maximum fixe, dist = max-sim fera souvent l'affaire.

A QUIT - Anony-Mousse
la source
Merci pour la réponse. que voulait dire ypu par epsilon dans <= epsilon en a> = epsilon?
Smith Volka
Ok, la valeur par défaut de eps dans sklearn est 0,5. Est-ce correct si j'augmente cette valeur (par exemple, 0,8). Est-ce ce que vous vouliez dire dans votre réponse?
Smith Volka
DBSCAN utilise un seuil de distance epsilon maximum. Par GDBSCAN, vous pouvez également utiliser une similitude minimale à la place. vous devez changer le code, pas le paramètre . Sklearn ne prend pas en charge une similitude. ELKI prend directement en charge les fonctions de similitude dans GDBSCAN via SimilarityNeighborPredicate.
A QUIT - Anony-Mousse
Si vous ne pouvez pas coder, vous pouvez faire l'approche "paresseuse" que j'ai mentionnée. Il devrait donner les mêmes résultats.
A QUIT - Anony-Mousse
Qu'entendez-vous par Si vous avez un maximum fixe, dist = max-sim fera souvent l'affaire? Je suis intéressé à l'essayer.
Smith Volka
3

J'utiliserais le clustering hiérarchique de sklearn

from sklearn.feature_extraction.text import CountVectorizer, TfidfTransformer
from scipy.cluster import  hierarchy

#Vectorizing
X = CountVectorizer().fit_transform(docs)
X = TfidfTransformer().fit_transform(X)
#Clustering
X = X.todense()
threshold = 0.1
Z = hierarchy.linkage(X,"average", metric="cosine")
C = hierarchy.fcluster(Z, threshold, criterion="distance")

Cest votre regroupement des documents docs.

Vous pouvez utiliser d'autres mesures au lieu de cosine, et utiliser un seuil différent de0.1

Uri Goren
la source
"docs" est-il la matrice de données d'origine? Où mettre la matrice de données, ou où mettre la matrice de similitude cosinus? merci
Bill Ancalagon le
1
docssont les documents, Zest la matrice de similitude cosinus
Uri Goren
3

Je pense que le package clustMixType pourrait vous donner de meilleurs résultats / informations.

En utilisant ce package, vous pouvez utiliser directement une combinaison de données catégoriques et numériques, il n'a besoin d'aucun type d'encodage à chaud.

Il vous suffit d'alimenter les données et elles se séparent automatiquement en données catégoriques et numériques, si vous rencontrez des problèmes au moment de la ségrégation, vous pouvez utiliser des fonctions comme as.factor(to convert to a categorical)et as.numeric(to convert to a Numeric field).

Vous pouvez calculer à l' Lambda(mean Distance value)avance et alimenter en entrée de l'algorithme.

Si vous ne connaissez pas le nombre optimal de clusters, vous pouvez utiliser WSS(within Sum of Squares), plot(elbow chart)pour décider du nombre optimal de clusters.

Toros91
la source
2

Toutes les méthodes de clustering utilisent une métrique de distance quelconque. Et rappelez-vous que la distance est essentiellement une mesure de dissimilarité. Donc, si vous normalisez votre similitude entre 0 et 1, votre distance est simplement 1-similitude

Quant aux algorithmes qui ne nécessitent pas de spécifier un certain nombre de clusters, il existe bien sûr des techniques de clustering hiérarchiques, qui construisent essentiellement une structure arborescente que vous pouvez "couper" où vous le souhaitez (vous pouvez utiliser des métriques de performance pour le faire automatiquement )

X-means est une version de K-means qui essaie un certain nombre de K et choisit celle qui maximise une fonction d'évaluation.

Le décalage moyen «trouve» également un nombre naturel de grappes mais est sensible à d'autres paramètres tels que la bande passante par exemple.

Valentin Calomme
la source