Python:使用Levenshtein距离作为度量标准,使用scikit-learn的dbscan进行字符串聚类:

Question

我一直在尝试聚集多个URL数据集(每个约100万个),以查找每个URL的原始和拼写错误.我决定使用levenshtein距离作为相似性度量,并将dbscan作为聚类算法,因为k-means算法不起作用,因为我不知道聚类的数量.

我使用Scikit-learn实现dbscan时遇到了一些问题.

下面的代码片段适用于我使用的格式的小数据集,但由于它预先计算整个距离矩阵,因此占用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

我意识到这意味着它试图将输入转换为相似函数浮动.但我不希望它这样做.据我所知,它只需要一个可以接受两个参数并返回一个浮点值的函数,然后它可以与mp进行比较,这是levenshtein距离应该做的.

我被困在这一点上,因为我不知道sklearn的dbscan的实现细节,以找出它为什么试图将它转换为float,而且我对如何避免O(n ^ 2)矩阵也没有更好的想法计算.

如果有更好或更快的方法来聚集这些我可能忽略的字符串,请告诉我.

Answer 1

从scikit-learn faq中,您可以通过制定自定义指标来完成此操作:

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)

Answer 2

尝试使用 ELKI 而不是 sklearn。

这是我所知道的唯一允许使用任何指标进行索引加速 DBSCAN 的工具。

它包括编辑距离。您需要使用 向数据库添加索引-db.index。我总是使用覆盖树索引（当然，您需要为索引和算法选择相同的距离！）

您可以在 sklearn 中使用“pyfunc”距离和球树，但由于解释器的原因，性能非常糟糕。此外，sklearn 中的 DBSCAN 更消耗内存。