java - 如何在 String 对象上运行 K-means 算法？

Question

我正在做一个项目，我需要根据句子的相似程度对句子进行分组。

例如，这些句子需要分组到一个集群中:

1. Apple 的第一季度业绩在华尔街仍不及预期
2. Apple 公布了 2013 年第一季度的 yield :创纪录的 545 亿美元收入。
3. Apple 公布了创纪录的收入和利润； iPhone 销量猛增近 30%。

标题不断出现，所以我可能需要即时安排和修改集群。目前我正在使用 Monge-Elkan 算法来确定两个字符串的相似程度，但我不知道如何对它们进行聚类。

在互联网上搜索让我相信我需要使用 K-Means 算法对内容进行分组，但我不确定如何继续使用我已有的东西。

让事情稍微复杂一点的是，我已经将它托管在 Google App Engine 上，所以我无法使用文件系统。

Answer 1

编辑距离指标不太可能有效地模拟句子含义的相似性，我假设您正在寻找。文本作为字符串的低级表示也是如此。

更好的方法是使用更高级别的表示，例如 vector-space model .在这里，您收集句子集合(语料库)中的所有独特单词，并将它们中的每一个映射到一个数字。然后将每个文档(句子)表示为一个 vector :

[w1_count, w2_count, ..., wN_count]

其中第 N 个元素是给定句子中第 N 个单词(映射到数字 N 的单词)的计数。

现在您可以在此数据集上运行 k-means，但更好:

1. 处理数据，使“Apple”等重要词的权重高于“on”或“in”等常用词。一种这样的技术是 TF-IDF .然后使用欧几里德距离对此运行标准 k-means。

2. 更好的是，使用更高级别的工具，例如 Latent Semantic Analysis或 Latent Dirichlet Allocation .

如果您想使用现有的方法，Simon G. 的回答为您指明了正确的方向，并且与距离覆盖的相似性在 this question 中得到了回答。 .