如何根据相似度矩阵对大量字符串进行聚类？

Question

我需要根据相似度对 500K+ 个字符串进行聚类。

我已经计算了它们的成对编辑距离并制作了一个稀疏相似度矩阵。该矩阵包含二进制相似性：小距离的值设置为 1.0，其他为 0.0。

我不知道什么样的聚类对我有好处。我事先不知道集群的数量，但它可能相当大，因为相似矩阵非常稀疏（大约 0.1% 的值是非零的）。

Answer 1

您是否考虑过 https://en.wikipedia.org/wiki/Soundex 之类的事情？这种算法的优点是相似的词具有相同的规范形式。例如，“Robert”和“Rupert”return 都是相同的字符串“R163”。然后你的聚类归结为一个像这样的地图：

clusters = { canonical_form: [list of similar words] }

当然，您可以根据您的域调整 Soundex 规则。