集群(尤其是字符串集群)如何工作？

Question

我听说过聚类来分组类似的数据.我想知道它在String的特定情况下是如何工作的.

我有一张超过10万字的表.

我想识别具有一些差异的相同单词(例如:)house, house!!, hooouse, HoUse, @house, "house", etc....

需要什么来识别群集中的相似性并对每个单词进行分组？为此更推荐什么算法？

Answer 1

要了解什么聚类是想象一个地理地图.您可以看到许多不同的对象(例如房屋).其中一些彼此接近,而另一些则相距甚远.基于此,您可以将所有对象拆分为组(例如城市).集群算法正是这样做的 - 它们允许您将数据拆分成组,而无需事先指定组边界.

所有聚类算法都基于2个对象之间的距离(或可能性).在地理地图上,它是两个房屋之间的正常距离,在多维空间中它可能是欧几里德距离(实际上,地图上两个房屋之间的距离也是欧几里德距离).对于字符串比较,您必须使用不同的东西.这里有2个不错的选择,那就是Hamming和Levenshtein的距离.在你的特殊情况下,如果更优选Levenshtein距离(汉明距离仅适用于相同大小的弦).

现在您可以使用现有的一种聚类算法.有很多,但并非所有都能满足您的需求.例如,这里已经提到的纯k-means几乎没有帮助你,因为它需要初始数量的组来查找,并且使用大型字符串字符串可能是100,200,500,10000 - 你只是不知道这个数字.所以其他算法可能更合适.

其中之一是期望最大化算法.它的优点是它可以自动找到多个簇.然而,在实践中,它通常会提供比其他算法更不精确的结果,因此在EM之上使用k-means是正常的,即首先使用EM找到簇的数量及其中心,然后使用k-means来调整结果.

可能适合您的任务的另一种可能的算法分支是分层聚类.在这种情况下,聚类分析的结果不是一组独立的组,而是树(层次结构),其中几个较小的聚类被分组为一个较大的聚类,并且所有聚类最终都是一个大聚类的一部分.在您的情况下,这意味着所有单词在某种程度上彼此相似.

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 个值的公式，实际上是 p = 0 的 Jaro-Winkler 距离的特例。
• Jaro-Winkler 距离：这个距离是由从 [0, 0.25] 中选择的两个比较字符串 (A,B,m,t,l) 和 p 确定的 5 个参数的公式。

那会给你距离。您可能不需要执行聚类分析，也许按字符串距离本身排序就足够了。我已经创建了一个脚本来提供这里的基本功能......随时根据需要对其进行改进。