Python: String кластеризация с dbscan scikit-learn с использованием расстояния Levenshtein в качестве показателя:

Question

Я пытаюсь объединить несколько наборов данных URL (около 1 миллиона каждый), чтобы найти оригинал и опечатки каждого URL-адреса. Я решил использовать расстояние levenshtein как метрику подобия, а также dbscan, поскольку алгоритм кластеризации, поскольку алгоритмы k-mean не будут работать, потому что я не знаю количество кластеров.

У меня возникли некоторые проблемы с использованием реализации dcscan Scikit-learn.

Этот сниппл ниже работает с небольшими наборами данных в используемом формате, но поскольку он предварительно вычисляет всю матрицу расстояний, которая занимает пространство и время O (n^2) и слишком много для моих больших наборов данных. Я запускаю это в течение многих часов, но он просто заканчивается тем, что занимает всю память моего компьютера.

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) 

Итак, я решил, что мне нужно каким-то образом вычислить сходство на лету и, следовательно, пробовал этот метод.

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

Но этот метод заканчивает тем, что дает мне ошибку:

ValueError: could not convert string to float: URL 

Что я понимаю, означает, что ее пытаются преобразовать входные функции сходства с поплавками. Но я не хочу, чтобы это делалось. Насколько я понимаю, ему просто нужна функция, которая может принимать два аргумента и возвращает значение float, которое затем может сравниться с eps, которое должно делать расстояние levenshtein.

Я застрял в этой точке, так как я не знаю детали реализации dbscan от sklearn, чтобы найти, почему он пытается преобразовать его в float, и я также не знаю, как избежать O (n^2) матричное вычисление.

Пожалуйста, дайте мне знать, если есть лучший или более быстрый способ сгруппировать эти много строк, которые я, возможно, упустил.

Answer 1

Попробуйте ELKI вместо sklearn.

Это единственный инструмент, который я знаю, который позволяет индексировать DBSCAN с любым метрикой.

Включает расстояние Левенштейн. Вам нужно добавить индекс в свою базу данных с помощью -db.index. Я всегда использую индекс обложки (вам нужно выбрать одинаковое расстояние для индекса и для алгоритма, конечно!)

Вы можете использовать расстояния «pyfunc» и шаровые деревья в sklearn, но производительность была действительно плохой, потому что переводчика. Кроме того, DBSCAN в sklearn намного интенсивнее.

Answer 2

Из scikit учиться ЧаВО вы можете сделать это с помощью 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)