將一長串字符串（單詞）聚類成相似組
我手頭有以下問題：我有一個很長的單詞列表，可能是名字、姓氏等。我需要對這個單詞列表進行聚類，以便相似的單詞，例如具有相似編輯（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))輸出是（以斜體表示的示例，位於它們作為示例的集群的左側）：
- *有：*機會，編輯，手，有，高
- *以下：*以下
- *問題：*問題
- I: I, a, at, etc, in, list, of
- *可能：*可能
- *集群：*集群
- word: for, and, for, long, need, should, very, word, words
- *類似的：*類似的
- *文史丹：*文史丹
- *距離：*距離
- *的：*那個，那個，這，到，與
- *相同：*示例，列表，名稱，相同，例如，姓氏
- *算法：*算法，算法
- *出現：*出現，出現
在50 個隨機名字的列表上運行它：
- *黛安：*迪安娜、黛安、迪翁、杰拉德、伊琳娜、莉塞特、明娜、妮基、瑞奇
- *賈尼：*克萊爾、賈尼、傑森、Jc、基米、朗、馬庫斯、馬克西瑪、蘭迪、勞爾
- *Verline：*命運、凱莉、瑪麗蓮、梅賽德斯、斯特林、Verline
- *格倫：*埃莉諾、格倫、格溫達
- *阿曼迪納：*阿曼迪納，奧古斯丁
- *希拉：*艾哈邁德、埃斯特拉、米麗莎、希拉、特蕾莎、溫內爾
- *勞倫：*秋，海蒂，勞倫，勞倫
- *阿爾貝托：*阿爾貝塔、阿爾貝托、羅伯特
- *絕殺：*艾米、多琳、歐拉、約瑟夫、洛瑞、洛瑞、波特
對我來說看起來很棒（這很有趣）。