Bündelung einer langen Liste von Zeichenfolgen (Wörtern) in Ähnlichkeitsgruppen

Ich habe das folgende Problem zur Hand: Ich habe eine sehr lange Liste von Wörtern, möglicherweise Namen, Nachnamen usw. Ich muss diese Wortliste so gruppieren, dass ähnliche Wörter, zum Beispiel Wörter mit ähnlichem Bearbeitungsabstand (Levenshtein), in der Liste angezeigt werden gleichen Cluster. Zum Beispiel sollten "Algorithmus" und "Alogrithmus" hohe Chancen haben, im selben Cluster zu erscheinen.

Mir sind die klassischen, nicht überwachten Clustering-Methoden wie k-means clustering und EM clustering in der Literatur zur Mustererkennung bekannt. Das Problem hierbei ist, dass diese Methoden auf Punkten arbeiten, die sich in einem Vektorraum befinden. Ich habe hier Saitenworte zur Hand. Es scheint, dass die Frage, wie man Strings in einem numerischen Vektorraum darstellt und das "Mittel" von String-Clustern berechnet, nach meinen bisherigen Umfrageanstrengungen nicht ausreichend beantwortet ist. Ein naiver Ansatz, um dieses Problem anzugehen, wäre die Kombination von k-Means-Clustering mit Levenshtein-Abstand, aber die Frage bleibt immer noch "Wie soll man" Mittel "von Zeichenketten darstellen?". Es gibt ein Gewicht, das als TF-IDF-Gewicht bezeichnet wird, aber es scheint, dass es hauptsächlich mit dem Bereich des "Textdokument" -Clusterings zusammenhängt, nicht mit dem Clustering einzelner Wörter. http://pike.psu.edu/cleandb06/papers/CameraReady_120.pdf

Meine Suche in diesem Bereich dauert noch an, aber ich wollte auch hier Anregungen bekommen. Was würden Sie in diesem Fall empfehlen, kennt jemand Methoden für diese Art von Problem?

Empfehlung von Seconding @ mican zur Affinitätsvermehrung .

Aus der Zeitung: L Frey, Brendan J. und Delbert Dueck. "Clustering durch Weiterleiten von Nachrichten zwischen Datenpunkten." science 315, 5814 (2007): 972–976. .

Es ist super einfach über viele Pakete zu bedienen. Es funktioniert auf alles, was Sie die paarweise Ähnlichkeit definieren können. Was Sie durch Multiplizieren der Levenshtein-Distanz mit -1 erhalten können.

Ich habe ein kurzes Beispiel zusammengestellt und dabei den ersten Absatz Ihrer Frage als Eingabe verwendet. In 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))

Ausgabe war (Beispiele in Kursivschrift links vom Cluster, für die sie beispielhaft sind):

• haben: Chancen, bearbeiten, Hand, haben, hoch
• folgend: folgend
• Problem: Problem
• I: Ich, eine, bei, etc, in, Liste, von
• möglicherweise: möglicherweise
• Cluster: Cluster
• wort: Für und für lange brauchen, sollten, sehr, wort, worte
• ähnlich: ähnlich
• Levenshtein: Levenshtein
• entfernung: entfernung
• das: das, das, das, mit
• Same: Beispiel, Liste, Namen, Same, solche, Nachnamen
• Algorithmus: Algorithmus, Algorithmus
• Erscheinen: Erscheinen, erscheint

Ausführen auf einer Liste von 50 zufälligen Vornamen :

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

Sieht für mich ziemlich gut aus (das hat Spaß gemacht).

Verwenden Sie Graph-Clustering-Algorithmen wie Louvain-Clustering, RNSC (Restricted Neighborhood Search Clustering), APC (Affinity Propgation Clustering) oder MCL (Markov-Cluster-Algorithmus).

Sie können das Vektorraummodell mit den n-Gramm der Wörter als Vektorraumeinträge ausprobieren. Ich denke, Sie müssten in diesem Fall ein Maß wie Cosinus-Ähnlichkeit verwenden, anstatt Abstand zu bearbeiten.