数据聚类算法

Question

什么是应对大维度和海量数据集并且速度快的最流行的文本聚类算法？ 在阅读了这么多论文和方法后，我感到很困惑..现在只想知道哪个算法被最广泛地使用，以便为编写文档聚类应用程序打下良好的基础。

- user352951

Answer 1

为了处理维度诅咒，您可以尝试确定生成数据集的“盲源”（即主题）。您可以使用主成分分析或因子分析来减少特征集的维度并计算有用的指数。

PCA是潜在语义索引中使用的方法，因为SVD可以被证明是PCA :)

请记住，在获取数据集的主要成分或其因子时，您可能会失去解释性，因此您可能需要采用非负矩阵分解路线。（这里的关键是！K-Means是一种特殊的NNMF！） 在NNMF中，数据集可以仅通过其加性、非负组件来解释。

- rano

Answer 2

没有一种适合所有情况的方法。分层聚类始终是一种选择。如果您想从数据中形成不同的组，可以选择K均值聚类（据说计算上也较少耗费资源）。

- crnlx

---

但是如何应对维度灾难呢？ - user352951

Answer 3

两种最流行的文档聚类方法是层次聚类和k-means。k-means更快，因为它在文档数量上是线性的，而不是层次聚类的二次方，但通常认为它能够给出更好的结果。数据集中的每个文档通常表示为一个n维向量（n是单词数），其中每个单词对应的维度大小等于其词频-逆文档频率分数。tf-idf分数减少了高频词在相似性计算中的重要性。余弦相似度通常用作相似性度量。

一篇比较层次聚类和双分k-means实验结果的论文可以在这里找到。

文档聚类中最简单的降维方法是：a）丢弃所有罕见和高频词（例如在不到1％和超过60％的文档中出现：这有点武断，您需要尝试不同的范围以查看对结果的影响），b）停用词：丢弃常见英语单词的停用词列表可以在线找到，c）词干提取或删除后缀以仅保留词根。最常见的词干提取器是由Martin Porter设计的词干提取器。许多语言的实现可以在此处找到。通常，这将将数据集中独特单词的数量减少到几百个或几千个，进一步的降维可能不需要。否则，可以使用PCA等技术。

- Suratna

Answer 4

如果您不需要语义文本聚类（从您的原始问题中我无法确定这是否是一个要求），可以尝试使用Levenshtein距离并构建相似度矩阵。从中，您可以使用k-medoids进行聚类，并通过使用轮廓系数来验证您的聚类结果。不幸的是，Levensthein可能会非常慢，但是可以通过使用阈值和其他方法来加速它。

另一种处理维度诅咒的方法是找到“对比集”，即在一个组中比其他组更突出的属性-值对的连接。然后，您可以将这些对比集作为维度之一，而不是使用原始属性或仅使用有限数量的属性。

- don

Answer 5

我会坚持使用kmedoids算法，因为你可以在算法开始时计算任意两点之间的距离，只需要做一次，这样可以节省时间，特别是在有许多维度的情况下。该算法通过选择距离其最近的点作为聚类中心来工作，而不是基于属于该聚类的点的平均值计算出的质心。因此，在这个算法中，所有可能的距离计算都已经为你完成了。

- mariana soffer