11

我想根据相似性对文档进行聚类。

我已经尝试过 ssdeep （相似性哈希），速度非常快，但我被告知 k-means 更快，而 flann 是所有实现中最快的，而且更准确，所以我正在尝试使用 python 绑定的 flann，但我找不到任何示例如何在文本上执行（它只支持数字数组）。

我对这个领域非常陌生（k-means，自然语言处理）。我需要的是速度和准确性。

我的问题是：

  1. 我们可以使用 KMeans 进行文档相似性分组/聚类吗（Flann 似乎不允许任何文本输入）
  2. 弗兰是正确的选择吗？如果不是，请建议我支持文本/文档集群的高性能库，它具有 python 包装器/API。
  3. k-means是正确的算法吗？
4

2 回答 2

20

您需要将文档表示为数字数组（又名向量）。有很多方法可以做到这一点，具体取决于您想要的复杂程度，但最简单的方法就是将其表示为字数的向量。

所以这就是你要做的：

  1. 计算每个单词在文档中出现的次数。

  2. 选择一组将包含在向量中的“特征”词。这应该排除非常常见的词（又名“停用词”），如“the”、“a”等。

  3. 根据特征词的数量为每个文档制作一个向量。

这是一个例子。

如果您的“文档”是单个句子，并且它们看起来像（每行一个文档）：

there is a dog who chased a cat
someone ate pizza for lunch
the dog and a cat walk down the street toward another dog

如果我的一组特征词是[dog, cat, street, pizza, lunch]，那么我可以将每个文档转换为一个向量：

[1, 1, 0, 0, 0]  // dog 1 time, cat 1 time
[0, 0, 0, 1, 1]  // pizza 1 time, lunch 1 time
[2, 1, 1, 0, 0]  // dog 2 times, cat 1 time, street 1 time

你可以在你的 k-means 算法中使用这些向量，它希望将第一句和第三句组合在一起，因为它们很相似，并且使第二句成为一个单独的集群，因为它非常不同。

于 2012-09-19T14:55:13.593 回答
14

这里有一个大问题：

K-means 是为欧几里得距离设计的。

关键问题是均值函数。均值将减少欧几里得距离的方差，但对于不同的距离函数可能不会这样做。所以在最坏的情况下，k-means 将不再收敛，而是在无限循环中运行（尽管大多数实现支持在最大迭代次数处停止）。

此外，对于稀疏数据，均值不是很敏感，文本向量往往非常稀疏。粗略地说，问题在于大量文档的均值将不再看起来像真实文档，并且这种方式变得与任何真实文档不同，而与其他均值向量更相似。所以结果在某种程度上退化了。

对于文本向量，您可能需要使用不同的距离函数，例如余弦相似度。

当然，您首先需要计算数字向量。例如，通过使用相对词频，通过TF-IDF对其进行归一化。

k-means 有一个变体，称为k-medoids。它可以使用任意距离函数，并且通过使用对集群最核心的真实文档（“medoid”）来避免整个“平均”事情。但是已知的算法比 k-means 慢得多。

于 2012-09-19T18:04:19.690 回答