使用Levenshtein距离在Python中实现层次聚类

Question

继上我的上一个问题后，我已经使用Python & Levenshtein距离实现了大量字符串的聚类算法。但是要花费很长时间才能完成聚类。有什么建议吗？再次

<> 迭代救援人员到场名单在for循环 在列表 运行在列表中的每个项目，找到相似百分比 如果相似度>阈值时，转移到集群 结束for循环

Answer 1

第一，使用分析器查看大部分时间都花在哪里。我怀疑这是在实际的Levenshtein计算中，但很确定。 Iff它是：

1. 用Cython实现Levenshtein函数。这会给你一个巨大的加速。
2. 计算多个线程中的线对。例如。如果你有1000个字符串，你有1000000对，所以你可以让8个线程中的每个线程执行125000个对。