string - 聚类(尤其是字符串聚类)如何工作？

Question

我听说过聚类以对相似数据进行分组。我想知道它在 String 的特定情况下是如何工作的。

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

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

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

Answer 1

要了解什么是聚类，请想象一张 map 。您可以看到许多不同的对象(例如房屋)。它们中的一些彼此靠近，而另一些则很远。基于此，您可以将所有对象分成组(例如城市)。聚类算法正是这样做的——它们允许您将数据分成组，而无需事先指定组边界。

所有聚类算法均基于距离 (或可能性)在 2 个对象之间。在地理 map 上是正常的两栋房子之间的距离，在多维空间中可能是欧几里得距离(其实 map 上两栋房子之间的距离也是欧几里得距离)。对于字符串比较，您必须使用不同的东西。这里有 2 个不错的选择是 Hamming和 Levenshtein distance .在您的特定情况下 Levenshtein 距离 如果更可取(汉明距离仅适用于相同大小的字符串)。

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

其中之一是expectation maximization算法。它的优点是它可以自动找到簇的数量。然而，在实践中，它给出的结果通常不如其他算法精确，因此使用 是正常的。 EM 上的 k-means ，即先用 EM 求出簇的个数及其中心，然后用 k-means 调整结果。

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