K-moyennes sur les similitudes cosinus en fonction de la distance euclidienne (LSA)

J'utilise l'analyse sémantique latente pour représenter un corpus de documents dans un espace dimensionnel inférieur. Je veux regrouper ces documents en deux groupes en utilisant k-means.

Il y a plusieurs années, j'ai fait cela en utilisant le gensim de Python et en écrivant mon propre algorithme k-means. J'ai déterminé les centroïdes de cluster en utilisant la distance euclidienne, mais j'ai ensuite regroupé chaque document en fonction de la similitude du cosinus avec le centroïde. Cela semblait plutôt bien fonctionner.

Maintenant, j'essaie de le faire sur un corpus de documents beaucoup plus vaste. K-means ne converge pas, et je me demande si c'est un bug dans mon code. J'ai lu récemment que vous ne devriez pas regrouper en utilisant la similitude cosinus, car k-means ne fonctionne que sur la distance euclidienne. Même si, comme je l'ai mentionné, cela semblait bien fonctionner dans mon cas de test plus petit.

Maintenant, je rencontre cela sur la page Wikipedia de LSA :

Les documents et les représentations vectorielles de termes peuvent être regroupés en utilisant des algorithmes de regroupement traditionnels comme k-means en utilisant des mesures de similitude comme cosinus.

Alors c'est quoi? Puis-je utiliser la similitude cosinus ou non?

Oui, tu peux l'utiliser. Le problème est que la similitude cosinus n'est pas une distance, c'est pourquoi elle est appelée similitude. Néanmoins, il peut être converti en une distance comme expliqué ici .

En fait, vous pouvez utiliser n'importe quelle distance. Une étude très intéressante des propriétés des fonctions de distance dans les espaces de grande dimension (comme c'est généralement le cas dans la recherche d'informations) est On The Surprising Behavior of Distance Metrics in High Dimensional Space . Cependant, il ne compare pas Euclidean vs cosinus.

Je suis tombé sur cette étude où ils affirment que dans les espaces de grande dimension, les deux distances ont tendance à se comporter de manière similaire.

La distance euclidienne ne convient pas pour comparer des documents ou des groupes de documents. Lors de la comparaison de documents, un problème clé est la normalisation par la longueur du document. La similitude des cosinus permet ce type de normalisation, mais pas la distance euclidienne. De plus, les documents sont souvent modélisés sous forme de distributions de probabilités multinomiales (ce qu'on appelle un sac de mots). La similitude de cosinus est une approximation de la divergence JS qui est une méthode statistiquement justifiée pour la similitude. Un problème clé avec les documents et le cosinus est qu'il faut appliquer une normalisation appropriée de tf-idf aux comptes. Si vous utilisez Gensim pour dériver la représentation LSA, Gensim le fait déjà.

Une autre observation utile pour votre cas d'utilisation de 2 clusters est que vous pouvez obtenir une bonne initialisation non aléatoire car LSA est juste SVD. Vous le faites de la manière suivante:

• Prenez uniquement le premier composant de chaque document (en supposant que le premier composant est le vecteur singulier supérieur).
• Triez ces valeurs en gardant une trace des identifiants du document pour chaque valeur.
• cluster 1 = identifiants de document correspondant aux premières, par exemple 1000 (ou plus) valeurs
• cluster 2 = identifiants de document correspondant au bas, par exemple 1000 (ou plus) valeurs
• juste faire la moyenne des vecteurs pour chaque cluster et normaliser par la longueur du vecteur.
• Appliquez maintenant k-means à cette initialisation. Cela signifie qu'il suffit d'itérer (1) l'attribution de documents au centroïde le plus proche actuel et (2) la moyenne et la normalisation des nouveaux centroïdes après la réaffectation

Oui, la même mise à jour du centroïde par moyenne vectorielle fonctionne.

Voir cas m = 1 dans la section 2.2 de ce document . w sont les poids et les poids sont tous à 1 pour les algorithmes de moyenne k de base.

L'article utilise les propriétés de l'inégalité de Cauchy-Schwartz pour établir la condition qui minimise la fonction de coût pour k-mean.

Souvenez-vous également que la similitude de cosinus n'est pas une distance vectorielle. La dissimiliarité cosinus est. (Cela devrait être un bon terme de recherche.) Par conséquent, lorsque vous mettez à jour la partition, vous recherchez arg maxplutôt que arg min.