如何进行聚类分析（特别是字符串聚类）？

Question

我听说过聚类可以将相似的数据分组。我想了解它在字符串特定案例中是如何工作的。

我有一个包含超过100,000个不同单词的表格。

我希望能够识别出具有差异的相同单词（例如：house, house!!, hooouse, HoUse, @house, "house"等）。

为了识别相似性并将每个单词分组到一个聚类中，需要什么？哪种算法更推荐用于此？

- Renato Dinhani

Answer 1

要理解聚类是什么，可以想象一张地理地图。你可以看到许多不同的对象（例如房屋）。有些靠近，有些则远离。基于此，您可以将所有对象分成组（例如城市）。聚类算法正是做这件事情的 - 它们允许您在没有先前指定组边界的情况下将数据分成组。

所有聚类算法都基于2个对象之间的距离（或相似度）。在地理地图上，它是两个房屋之间的普通距离，在多维空间中，它可能是欧几里得距离（实际上，地图上两个房屋之间的距离也是欧几里得距离）。对于字符串比较，您必须使用不同的东西。这里有两个不错的选择Hamming和Levenshtein distance。在您的特定情况下，Levenshtein距离更可取（Hamming距离仅适用于相同大小的字符串）。

现在您可以使用其中一个现有的聚类算法。有很多算法，但并不是所有算法都适合您的需求。例如，纯k-means已经在此处提到，但它很难帮助您，因为它需要找到初始组数，并且对于具有大量字符串词典的情况，它可能是100、200、500、10000 - 您只不知道数字。因此，其他算法可能更合适。

其中之一是期望最大化算法。它的优点在于可以自动找到聚类数量。然而，在实践中，它通常比其他算法给出更少精确的结果，因此通常使用k-means加上EM，即首先使用EM找到聚类数量和它们的中心，然后使用k-means来调整结果。

另一个可能适合您任务的算法分支是层次聚类。在这种情况下，聚类分析的结果不是一组独立的群体，而是一棵树（层次结构），其中几个较小的聚类被组合成一个更大的聚类，所有聚类最终都是一个大聚类的一部分。在您的情况下，这意味着所有单词在某种程度上相似。

- ffriend

---

k-means在EM之上？从未听说过。例如Bishop（“Pattern Recognition and Machine Learning”，Springer 2006）给出的建议恰恰相反：EM更好，但启动速度较慢，因此可以使用几轮k-means优化来引导它。 - Fred Foo

建议将EM或k-means与字符串编辑距离结合使用毫无意义。k-means不仅需要一个距离度量，还需要定义一组样本的明确定义平均值，对于编辑距离下的字符串来说是不可能定义的。 - Fred Foo

@larsmans：在k-means之上使用EM算法可以加快收敛速度并更好地防止局部最小值。在EM算法之上使用k-means可以自动发现类别数量并具有k-means的所有优点。我没有看到矛盾之处。EM算法比k-means更好吗？抱歉，但是如果没有具体的任务和数据集，这样的说法对我来说毫无意义。无论如何，我并不是说k-means一定会在字符串聚类方面表现更好，我想强调的是人们可以很容易地将两者结合起来，而Bishop的引用也证实了这一点。 - ffriend

EM更好的地方在于它产生概率分布而不是硬分类分配（尽管样本->最近中心距离可以被利用来在事后产生软分配）。 - Fred Foo

此外，k-means需要找到类中心的方法，即与所有其他元素平均距离最小的元素。对于空间数据来说，平均值是一种很好的方法，但不是唯一的方法。最终，您始终可以直接估计簇中每个元素到所有其他元素的平均距离。关于您的最后评论：我非常确定EM在许多方面都比k-means更具优势，同样，k-means也比EM更具优势。概率并不是唯一有价值的东西。例如，朴素贝叶斯会产生概率，但SVM现在仍然更受欢迎;) - ffriend

Answer 2

有一个名为 stringdist 的包，它允许使用多种不同的方法进行字符串比较。以下是从该页面复制的内容：

• 汉明距离：两个字符串中相同符号的位置数。仅适用于长度相等的字符串。
• Levenshtein 距离：将字符串 a 转换为字符串 b 所需的最小插入、删除和替换次数。
• (完整的) Damerau-Levenshtein 距离：与 Levenshtein 距离类似，但允许相邻符号的转置。
• 最优字符串对齐 / 受限 Damerau-Levenshtein 距离：类似于 (完整的) Damerau-Levenshtein 距离，但每个子字符串只能编辑一次。
• 最长公共子串距离：必须从两个字符串中移除的最少符号数量，直到生成的子字符串相同。
• q-gram 距离：两个字符串的 N-gram 向量之间绝对差值的总和。
• 余弦距离：1 减去两个 N-gram 向量的余弦相似度。
• Jaccard 距离：1 减去共享 N-gram 和所有观察到的 N-gram 的商。
• Jaro 距离：Jaro 距离是由 4 个值组成的公式，实际上是 Jaro-Winkler 距离的特殊情况，其中 p = 0。
• Jaro-Winkler 距离：该距离是由两个比较的字符串 (A,B,m,t,l) 确定的 5 个参数的公式，并且 p 可选择 [0, 0.25]。

那将给出距离。也许只按字符串距离排序就足够了，您可能不需要执行聚类分析。我已经创建了一个脚本来提供基本功能此处... 随时根据需要进行改进。

- Amit Kohli

Answer 3

你可以使用一种叫做“亲和传播”的聚类算法。该算法需要一个称为相似度矩阵的输入，你可以通过使用Python中的fuzzywuzzy库中的Levenstein距离的负数或partial_ratio和token_set_ratio的调和平均值来生成它。

- sourabh gupta

Answer 4

您可以使用像Levenshtein距离这样的算法进行距离计算，使用k-means进行聚类。

Levenshtein距离是一种用于测量两个序列之间差异量的字符串度量标准。

进行一些测试，并找到每个单词的相似性阈值，以决定您的分组。

- Oded

---

哪种算法更适合字符串聚类？ - Renato Dinhani

你说的“更推荐”是什么意思？ - Oded

有一些聚类算法，对吧？以问题中的房子为例，哪种算法可以更适合获得这种类型的结果？我想把所有这些词放在同一个簇中。 - Renato Dinhani

你可以使用k-means进行聚类，使用Levenshtein距离进行距离计算。 - Oded

你怎么计算均值？ - Arturo Hernandez