Grupowanie długiej listy ciągów (słów) w grupy podobieństwa

Mam pod ręką następujący problem: Mam bardzo długą listę słów, ewentualnie imion, nazwisk itp. Muszę utworzyć listę słów w taki sposób, aby podobne słowa, na przykład słowa o podobnej odległości edycji (Levenshtein) pojawiły się w ten sam klaster. Na przykład „algorytm” i „alogrithm” powinny mieć duże szanse na pojawienie się w tym samym klastrze.

Doskonale zdaję sobie sprawę z klasycznych, nieobjętych nadzorem metod grupowania, takich jak grupowanie k-średnich, grupowanie EM w literaturze Rozpoznawanie wzorców. Problem polega na tym, że metody te działają na punktach znajdujących się w przestrzeni wektorowej. Mam tutaj pod ręką słowa strun. Wydaje się, że zgodnie z moimi dotychczasowymi badaniami na pytanie, jak reprezentować ciągi w cyfrowej przestrzeni wektorowej i obliczyć „środki” klastrów ciągów, nie uzyskano wystarczającej odpowiedzi. Naiwnym podejściem do ataku na ten problem byłoby połączenie grupowania k-średnich z odległością Levenshteina, ale nadal pozostaje pytanie „jak reprezentować” oznacza „łańcuchy znaków”? Istnieje waga nazywana wagą TF-IDF, ale wydaje się, że jest ona głównie związana z obszarem klastrowania „dokumentu tekstowego”, a nie zgrupowaniem pojedynczych słów. http://pike.psu.edu/cleandb06/papers/CameraReady_120.pdf

Moje poszukiwania w tej dziedzinie wciąż trwają, ale chciałem też stąd czerpać pomysły. Co byś polecił w tym przypadku, czy ktoś jest świadomy metod tego rodzaju problemów?

Rekomendacja Seconding @ mican dotycząca propagacji powinowactwa .

Z pracy: L Frey, Brendan J. i Delbert Dueck. „Grupowanie poprzez przekazywanie wiadomości między punktami danych”. science 315.5814 (2007): 972–976. .

Jest bardzo łatwy w użyciu za pośrednictwem wielu pakietów. Działa na wszystkim, co można zdefiniować podobieństwem par. Co możesz uzyskać, mnożąc odległość Levenshteina przez -1.

Rzuciłem razem szybki przykład, używając pierwszego akapitu twojego pytania jako danych wejściowych. W Pythonie 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))

Dane wyjściowe były (przykłady kursywą po lewej stronie klastra, których są przykładem):

• mieć: szanse, edytować, rozdawać, mieć, wysokie
• następujące: następujące
• problem: problem
• I: I, a, at, etc, in, list, of
• ewentualnie: ewentualnie
• klaster: klaster
• słowo: Bo i przez długi czas trzeba, bardzo, słowo, słowa
• podobne: podobne
• Levenshtein: Levenshtein
• odległość: odległość
• the: that, the, this, to with
• same: przykład, lista, nazwiska, takie same, nazwiska
• algorytm: algorytm, alogrithm
• pojawiają się: pojawiają się, pojawiają się

Uruchomienie go na liście 50 losowych imion :

• 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: Jesień, Haydee, Laureen, Lauren
• Alberto: Albertha, Alberto, Robert
• Wiedza: Ammie, Doreen, Eura, Josef, Lore, Lori, Porter

Wygląda mi całkiem nieźle (to była zabawa).

Użyj algorytmów klastrowania wykresów, takich jak klastrowanie Louvaina, klastrowanie wyszukiwania z ograniczonym sąsiedztwem (RNSC), klastrowanie propagacji powinowactwa (APC) lub algorytm klastra Markowa (MCL).

Możesz wypróbować model przestrzeni wektorowej z n-gramami słów jako pozycji przestrzeni wektorowej. Myślę, że w tym przypadku musiałbyś użyć miary podobnej do podobieństwa cosinus zamiast edytować odległość.