Python: String clustern mit scikit-learns dbscan, Levenshtein Entfernung als Metrik verwenden:

Question

Ich habe versucht, mehrere Datensätze von URLs (etwa 1 Million) zu gruppieren, um das Original und die Tippfehler jeder URL zu finden. Ich entschied mich dafür, den Levenshtein-Abstand als Ähnlichkeitsmaßstab zu verwenden, zusammen mit dbscan als Clustering-Algorithmus, da k-Means-Algorithmen nicht funktionieren, weil ich die Anzahl der Cluster nicht kenne.

Ich habe einige Probleme mit Scikit-learns Implementierung von dbscan.

Dieser Ausschnitt unten arbeitet mit kleinen Datensätzen in dem Format, das ich benutze, aber da er die gesamte Abstandsmatrix vorberechnet, benötigt er O (n^2) Raum und Zeit und ist viel zu groß für meine großen Datensätze. Ich habe das viele Stunden lang gemacht, aber es endet damit, dass ich die gesamte Erinnerung an meinen PC nehme.

lev_similarity = -1*np.array([[distance.levenshtein(w1[0],w2[0]) for w1 in words] for w2 in words]) 
dbscan = sklearn.cluster.DBSCAN(eps = 7, min_samples = 1) 
dbscan.fit(lev_similarity) 

Also dachte ich, ich brauchte einen Weg, um die Ähnlichkeit im Flug zu berechnen und versuchte daher diese Methode.

dbscan = sklearn.cluster.DBSCAN(eps = 7, min_samples = 1, metric = distance.levenshtein) 
dbscan.fit(words) 

Aber diese Methode endet mir einen Fehler geben:

ValueError: could not convert string to float: URL 

Was ich erkennen, bedeutet, dass sein Versuch, die Eingaben in die Ähnlichkeitsfunktion zu Schwimmern zu konvertieren. Aber ich will nicht, dass es das tut. Soweit ich verstehe, braucht es nur eine Funktion, die zwei Argumente und einen Float-Wert zurückgeben kann, die dann mit eps verglichen werden kann, was die Levenshtein-Distanz tun sollte.

Ich bin an diesem Punkt fest, wie ich nicht weiß, die Implementierungsdetails von sklearn dbscan zu finden, warum es versucht, es in Float zu konvertieren, und auch habe ich keine bessere Idee, wie die O (n^2) Matrixberechnung.

Bitte lassen Sie mich wissen, ob es einen besseren oder schnelleren Weg gibt, diese vielen Strings, die ich vielleicht übersehen habe, zu clustern.

Answer 1

Versuchen ELKI statt sklearn.

Es ist das einzige Werkzeug, das ich kenne, das indexbeschleunigte DBSCAN mit jeder Metrik ermöglicht.

Es enthält Levenshtein Entfernung. Sie müssen Ihrer Datenbank einen Index mit -db.index hinzufügen. Ich benutze immer den Cover Tree Index (Sie müssen natürlich den gleichen Abstand für den Index und für den Algorithmus wählen!)

Sie könnten "pyfunc" Entfernungen und Ball Bäume in sklearn verwenden, aber die Leistung war wirklich schlecht, weil des Dolmetschers. Außerdem ist DBSCAN in sklearn viel speicherintensiver.

Answer 2

Von dem Scikit-Learn FAQ Sie dies durch making a custom metric tun können:

from leven import levenshtein  
import numpy as np 
from sklearn.cluster import dbscan 
data = ["ACCTCCTAGAAG", "ACCTACTAGAAGTT", "GAATATTAGGCCGA"] 
def lev_metric(x, y): 
    i, j = int(x[0]), int(y[0])  # extract indices 
    return levenshtein(data[i], data[j]) 

X = np.arange(len(data)).reshape(-1, 1) 
dbscan(X, metric=lev_metric, eps=5, min_samples=2)