我手头有以下问题：我有一个很长的单词列表，可能是名字、姓氏等。我需要对这个单词列表进行聚类，以便相似的单词，例如具有相似编辑（Levenshtein）距离的单词出现在同一个集群。例如“算法”和“算法”应该有很高的机会出现在同一个集群中。
我非常了解模式识别文献中的经典无监督聚类方法，如 k-means 聚类、EM 聚类。这里的问题是这些方法适用于位于向量空间中的点。我手头有字符串的话。根据我迄今为止的调查工作，似乎没有充分回答如何在数值向量空间中表示字符串以及计算字符串簇的“均值”的问题。解决这个问题的一种天真的方法是将 k-Means 聚类与 Levenshtein 距离相结合，但问题仍然是“如何表示字符串的“均值”？”。有一个权重叫做 TF-IDF 权重，但似乎它主要与“文本文档”聚类的领域有关，而不是针对单个单词的聚类。 http://pike.psu.edu/cleandb06/papers/CameraReady_120.pdf
我在这方面的搜索仍在继续，但我也想从这里获得想法。在这种情况下你会推荐什么，有人知道解决这种问题的任何方法吗？
支持@micans 对Affinity Propagation的推荐。
来自论文：L Frey、Brendan J. 和 Delbert Dueck。“通过在数据点之间传递消息进行聚类。” 科学315.5814 (2007): 972-976。.
通过许多软件包非常容易使用。它适用于任何可以定义成对相似性的东西。您可以通过将 Levenshtein 距离乘以 -1 得到。
我使用您问题的第一段作为输入，整理了一个简单的示例。在 Python 3 中：
import numpy as np
from sklearn.cluster import AffinityPropagation
import distance
words = "YOUR WORDS HERE".split(" ") #Replace this line
words = np.asarray(words) #So that indexing with a list will work
lev_similarity = -1*np.array([[distance.levenshtein(w1,w2) for w1 in words] for w2 in words])
affprop = AffinityPropagation(affinity="precomputed", damping=0.5)
affprop.fit(lev_similarity)
for cluster_id in np.unique(affprop.labels_):
exemplar = words[affprop.cluster_centers_indices_[cluster_id]]
cluster = np.unique(words[np.nonzero(affprop.labels_==cluster_id)])
cluster_str = ", ".join(cluster)
print(" - *%s:* %s" % (exemplar, cluster_str))
输出是（以斜体表示的示例，位于它们作为示例的集群的左侧）：
在50 个随机名字的列表上运行它：
对我来说看起来很棒（这很有趣）。
使用图聚类算法，例如 Louvain 聚类、受限邻域搜索聚类 (RNSC)、亲和传播聚类 (APC) 或马尔可夫聚类算法 (MCL)。
您可以尝试将单词的 n-gram 作为向量空间条目的向量空间模型。我认为在这种情况下，您必须使用余弦相似度之类的度量，而不是编辑距离。