我一直在尝试聚集多个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)矩阵也没有更好的想法计算.
如果有更好或更快的方法来聚集这些我可能忽略的字符串,请告诉我.
python cluster-analysis machine-learning levenshtein-distance scikit-learn