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

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

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

我被困在这一点上，因为我不知道 sklearn 的 dbscan 的实现细节，无法找到它试图将其转换为 float 的原因，而且我也不知道如何避免 O(n^ 2)矩阵计算。

如果有任何更好或更快的方法来聚类我可能忽略的这些字符串，请告诉我。

Answer 1

在 scikit-learn 常见问题解答中，您可以通过 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)