Regroupement d'une longue liste de chaînes (mots) en groupes de similarité

31

J'ai le problème suivant à portée de main: j'ai une très longue liste de mots, éventuellement des noms, des noms de famille, etc. J'ai besoin de regrouper cette liste de mots, de sorte que des mots similaires, par exemple des mots avec une distance d'édition similaire (Levenshtein) apparaissent dans même cluster. Par exemple, "algorithme" et "alogrithme" devraient avoir de grandes chances d'apparaître dans le même cluster.

Je connais bien les méthodes de clustering non supervisées classiques comme le clustering k-means, le clustering EM dans la littérature sur la reconnaissance de formes. Le problème ici est que ces méthodes fonctionnent sur des points qui résident dans un espace vectoriel. J'ai des mots de cordes à ma main ici. Il semble que la question de savoir comment représenter les chaînes dans un espace vectoriel numérique et calculer les "moyennes" des groupes de chaînes ne soit pas suffisamment répondue, selon mes efforts d'enquête jusqu'à présent. Une approche naïve pour attaquer ce problème serait de combiner le clustering k-Means avec la distance de Levenshtein, mais la question demeure "Comment représenter" les moyens "des chaînes?". Il existe un poids appelé poids TF-IDF, mais il semble qu'il soit principalement lié au domaine du regroupement de "documents texte", et non au regroupement de mots uniques. http://pike.psu.edu/cleandb06/papers/CameraReady_120.pdf

Ma recherche dans ce domaine se poursuit, mais je voulais aussi avoir des idées d'ici. Que recommanderiez-vous dans ce cas, quelqu'un est-il au courant de méthodes pour ce genre de problème?

clustering k-means pattern-recognition Ufuk Can Bicici
la source
1
J'ai appris l'existence d'une variante de k-means nommée "K-medoids". en.wikipedia.org/wiki/K-medoids Il ne fonctionne pas avec la distance euclidienne L2 et n'a pas besoin du calcul des moyennes. Il utilise le point de données qui est le plus proche des autres d'un cluster en tant que «médoïde».
Ufuk Can Bicici
1
It seems that there are some special string clustering algorithms. Si vous venez d'un domaine spécifiquement text-mining, et non de statistiques / analyse de données, cette déclaration est garantie. Cependant, si vous apprenez la branche de clustering telle qu'elle est, vous constaterez qu'il n'existe aucun algorithme "spécial" pour les données de chaîne. Le «spécial» est la façon dont vous prétraitez ces données avant de les saisir dans une analyse de cluster.
ttnphns
en relation: stackoverflow.com/questions/21511801/…
Andre Holzner
Notez la différence entre la propagation d'affinité et le clustering K-Means et comment cela affectera le temps de calcul. quora.com/…
Gabriel Alon

Réponses:

37

Appuyant la recommandation de @ mican pour la propagation d'affinité .

Extrait de l'article: L Frey, Brendan J. et Delbert Dueck. "Clustering en passant des messages entre les points de données." science 315,5814 (2007): 972-976. .

Son super facile à utiliser via de nombreux packages. Cela fonctionne sur tout ce que vous pouvez définir celui de la similitude par paire. Ce que vous pouvez obtenir en multipliant la distance de Levenshtein par -1.

J'ai rassemblé un exemple rapide en utilisant le premier paragraphe de votre question comme entrée. En Python 3:

import numpy as np
import sklearn.cluster
import distance

words = "YOUR WORDS HERE".split(" ") #Replace this line
words = np.asarray(words) #So that indexing with a list will work
lev_similarity = -1*np.array([[distance.levenshtein(w1,w2) for w1 in words] for w2 in words])

affprop = sklearn.cluster.AffinityPropagation(affinity="precomputed", damping=0.5)
affprop.fit(lev_similarity)
for cluster_id in np.unique(affprop.labels_):
    exemplar = words[affprop.cluster_centers_indices_[cluster_id]]
    cluster = np.unique(words[np.nonzero(affprop.labels_==cluster_id)])
    cluster_str = ", ".join(cluster)
    print(" - *%s:* %s" % (exemplar, cluster_str))

La sortie était (les exemples en italique à gauche du cluster dont ils sont exemplaires):

  • avoir: chances, éditer, main, avoir, haut
  • suivant: suivant
  • problème: problème
  • I: I, a, at, etc, in, list, of
  • éventuellement: éventuellement
  • cluster: cluster
  • mot: Pour, et, depuis longtemps, besoin, devrait, très, mot, mots
  • similaire: similaire
  • Levenshtein: Levenshtein
  • distance: distance
  • le: que, le, ceci, à, avec
  • idem: exemple, liste, noms, idem, tel, noms
  • algorithme: algorithme, alogrithme
  • apparaître: apparaître, apparaît

L'exécuter sur une liste de 50 prénoms aléatoires :

  • Diane: Deana, Diane, Dionne, Gerald, Irina, Lisette, Minna, Nicki, Ricki
  • Jani: Clair, Jani, Jason, Jc, Kimi, Lang, Marcus, Maxima, Randi, Raul
  • Verline: Destiny, Kellye, Marylin, Mercedes, Sterling, Verline
  • Glenn: Elenor, Glenn, Gwenda
  • Armandina: Armandina, Augustina
  • Shiela: Ahmed, Estella, Milissa, Shiela, Thresa, Wynell
  • Laureen: automne, Haydee, Laureen, Lauren
  • Alberto: Albertha, Alberto, Robert
  • Lore: Ammie, Doreen, Eura, Josef, Lore, Lori, Porter

Ça a l'air très bien pour moi (c'était amusant).

Lyndon White
la source
est-il possible d'avoir le même algorithme en utilisant uniquement sklearn? ou utiliser scipy.spatial.distance avec du hamming? quel est l'avantage d'utiliser le levenshtein? Je suppose que je vais devoir essayer d'utiliser cette question: stackoverflow.com/questions/4588541/…
pierre
1
@pierre Levenshtein est ce que j'appellerais une «distance du correcteur orthographique», c'est un bon indicateur du risque d'erreur orthographique humaine. Damerau Levenshtein pourrait être encore mieux. Je ne sais pas que la distance de Hamming est définie pour des chaînes de longueurs inégales. Il autorise uniquement les échanges, pas les insertions. déterminer comment garnir / rogner la corde le plus raisonnablement est presque aussi difficile que de calculer la distance de Levenshtein. Devez-vous garnir / couper le départ? La fin? Certains du milieu?
Lyndon White
Si vous vouliez vraiment éviter la dépendance aux distances. vous pouvez utiliser l' implémentation du code Rossetta
Lyndon White
en lisant le en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance je peux voir comment la transposition peut faire la différence spécialement pour typo et python a un tout nouveau package pour cela. Je peux voir comment je peux l'utiliser contre une liste de mots et obtenir le "plus proche", mais ce n'est peut-être pas le plus important. Je dois obtenir ma liste et vérifier avec le tf-idf. Merci cool
Pierre
1
@dduhaime presque certainement. En général, la propagation d'affinité fonctionne pour les préférences non symétriques, mais comme c'est symétrique, allez-y. Je suis sûr que quelque chose dans SciPy a un type de matrice triangulaire qui ducktypes comme une matrice complète. Je suis depuis trop longtemps en terre julia-lang et je ne me souviens pas comment cela se fait en python. (En julie, vous utiliseriez Symmetric)
Lyndon White
5

Utilisez des algorithmes de clustering de graphiques, tels que le clustering de Louvain, le clustering de recherche de voisinage restreint (RNSC), le clustering de propagation d'affinité (APC) ou l'algorithme de Markov Cluster (MCL).

micans
la source
Qu'en est-il de la méthode K-medoids que j'ai trouvée? Je dois implémenter cette solution dès que possible, donc cela m'a semblé une bonne solution. Je suis conscient de l'existence de ces méthodes basées sur les graphiques, mais je crains de ne pas avoir le temps dont j'ai besoin pour les comprendre et les mettre en œuvre.
Ufuk Can Bicici
Pour tous, des logiciels sont disponibles avec des accords de licence assez non restrictifs, comme la GNU GPL. Je ne suis pas un grand fan du type d'algorithme k-mediods principalement à cause du paramètre k mais cela dépend de vous naturellement. Si vous avez besoin d'une implémentation interne, je pense qu'APC et MCL sont probablement les plus faciles à implémenter. Si vous deviez faire cela, essayez-les d'abord bien sûr.
micans
2

Vous pouvez essayer le modèle d'espace vectoriel avec les n-grammes des mots comme entrées d'espace vectoriel. Je pense que vous devriez utiliser une mesure comme la similitude cosinus dans ce cas au lieu de modifier la distance.

peace_within_reach
la source