如何使用k-means（Flann with python）对文档进行聚类？

Question

我希望基于相似性对文档进行聚类。

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

我非常非常新手 (k-means, 自然语言处理)。我需要的是速度和准确性。

我的问题是：

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

- Phyo Arkar Lwin

---

这个问题和http://stackoverflow.com/questions/8057442/document-clustering-basics基本相同。我建议您查看scikit-learn，它具有大部分您需要的功能并且可扩展：http://scikit-learn.org/stable/auto_examples/document_clustering.html. 另外，NLTK也有k-means: http://nltk.org/_modules/nltk/cluster/kmeans.html. - Fred Foo

非常感谢。Scikit和nltk的性能如何？你能对它们发表评论吗？ - Phyo Arkar Lwin

我从未尝试过NLTK的聚类，但可以肯定的是，对于较大的数据集，假设scikit-learn会快上几个数量级。不过，NLTK可能更容易使用。 - Fred Foo

如果您需要进行近似k-NN查询，则FLANN是最先进的选择（据我所知，scikit-learn和NLTK中都没有近似k-NN查询模块）。但是k-NN查询和K-Means聚类并不解决同一个问题。 - ogrisel

Answer 1

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

因此，这是您需要执行的操作：

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

如果我的特征词集是[狗, 猫, 街道, 披萨, 午餐]，那么我可以将每个文档转换为向量：

[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算法中使用这些向量，它希望能够将第一句和第三句分组在一起，因为它们是相似的，并且使第二句成为一个单独的聚类，因为它非常不同。

- dhg

---

非常有趣，我几天前在某个地方读到scikit.learn具有将任何文本文件或字符串向量化的功能。我想知道它所提供的数据结构是否适合Flann？ - Phyo Arkar Lwin

我只想补充一下，你可以使用某些词干算法来确保将同一个单词的小变化视为相同的关键字。这将减少变量的数量，并应使整个过程更准确。请参见此链接以获取更多信息[link]（http://packages.python.org/Whoosh/stemming.html） - jpsfer

是的，那将很好，我可以使用NLTK来生成/分词单词。 - Phyo Arkar Lwin

如果我没有任何特征词，我的词袋只是“任何不是停用词的单词”，那么每个向量的长度将是所有可能单词的长度，每个索引表示分配给该索引的单词的出现次数吗？ - Carpetfizz

@Carpetfizz。没错。 - CKM

Answer 2

这里有一个大问题：

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

关键问题在于均值函数。对于欧几里得距离，均值可以降低方差，但对于其他距离函数可能不起作用。因此，在最坏情况下，k-means将不再收敛，而是运行一个无限循环（尽管大多数实现支持在最大迭代次数时停止）。

此外，均值对于稀疏数据并不太敏感，文本向量往往非常稀疏。粗略地说，问题在于大量文档的均值看起来将不再像一个真实的文档，从而变得与任何真实文档不相似，并且更类似于其他均值向量。因此结果在某种程度上会退化。

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

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

有一种名为k-medoids的k-means变体。它可以使用任意距离函数工作，并通过使用对簇最为中心的真实文档（“medoid”）来避免整个“均值”问题。但是，已知的算法比k-means慢得多。

- Has QUIT--Anony-Mousse

---

非常感谢您指出这一点。您有推荐的K-medoids实现吗？ - Phyo Arkar Lwin