Python: klastrowanie ciągów z dbscan scikit-learning, przy użyciu odległości Levenshtein jako metryki:

Question

Próbowałem zebrać wiele zestawów danych adresów URL (około 1 miliona każdy), aby znaleźć oryginał i literówki każdego adresu URL. Zdecydowałem się użyć odległości levenshtein jako metryki podobieństwa, wraz z dbscan jako algorytmem grupowania, ponieważ algorytmy k-średnich nie będą działać, ponieważ nie znam liczby klastrów.

Mam pewne problemy przy korzystaniu z dbscan w Scikit-learning.

Poniższy fragment kodu działa na małych zestawach danych w formacie I jest używany, ale ponieważ jest to prekomputacja całej macierzy odległości, która zajmuje O (n^2) przestrzeń i czas i jest o wiele za duża dla moich dużych zbiorów danych. Uruchomiłem to przez wiele godzin, ale kończy się to zabieraniem całej pamięci mojego komputera.

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) 

Więc pomyślałem, że potrzebuję jakiegoś sposobu, aby obliczyć podobieństwo w locie i stąd wypróbowałem tę metodę.

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

Ale ta metoda kończy się dając mi błąd:

ValueError: could not convert string to float: URL 

Które Zdaję sobie sprawę, że jego środki próbuje konwertować wejść do funkcji podobieństwa do pływaków. Ale nie chcę tego robić. O ile rozumiem, po prostu potrzebuje funkcji, która może przyjąć dwa argumenty i zwrócić wartość zmiennoprzecinkową, którą następnie można porównać do eps, co powinna zrobić odległość od levenshtein.

Utknąłem w tym punkcie, ponieważ nie znam szczegółów implementacji dbscanu sklearna, aby znaleźć powód, dla którego próbuję go przekonwertować, i nie mam lepszego pomysłu na uniknięcie O (n^2) obliczenia macierzy.

Proszę dać mi znać, jeśli istnieje lepszy lub szybszy sposób na zgrupowanie tych wielu ciągów, które mogłem przeoczyć.

Answer 1

Spróbuj ELKI zamiast sklearn.

Jest to jedyne znane mi narzędzie, które umożliwia indeksowane DBSCAN z wartością dowolną metryką.

Obejmuje odległość Levenshtein. Musisz dodać indeks do swojej bazy danych za pomocą -db.index. Zawsze używam indeksu drzewa okładek (musisz wybrać tę samą odległość dla indeksu i dla algorytmu, oczywiście!)

Można używać odległości "pyfunc" i drzewek piłek w sklearn, ale wydajność była naprawdę zła, ponieważ tłumacza. Ponadto, DBSCAN w sklearn ma o wiele więcej pamięci.

Answer 2

Z scikit-learn FAQ można to zrobić poprzez making a custom metric:

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)