如何根据相似性度量对文档进行聚类？

Question

我阅读了有关如何根据相似性对文档进行聚类等主题的帖子 here。但我仍然不明白它是如何实现的。我的测试是我有 10 个文档的 cos 相似性度量。以下是一些：

D1  D2   sim(D1,D2)

d1  d10 0.6823 
d1  d2  0.6377 
d1  d8  0.0307 
d1  d9  0.0294 
d1  d7  0.0284 
d1  d3  0.0234 
d1  d4  0.0199 
d1  d6  0.0110 
d1  d5  0.0030 
d10 d2  0.7232 
d10 d3  0.3898 
d10 d4  0.3054 
d10 d9  0.0256 
d10 d7  0.0227 
d10 d8  0.0226 
d10 d6  0.0110 
d10 d5  0.0060 
d2  d3  0.7850 
...
...

我可以仅根据相似性度量对这些文档进行聚类吗？如果我指定簇数，该怎么做？如果我不指定聚类数，算法能不能自动聚类那些文档，怎么办？提前致谢。

Answer 1

聚类是机器学习的最大领域之一（按比例，您可以将其与数学中的 "integration" 或编程中的 "sorting" 进行比较），实际上有数百种不同的算法，侧重于不同的问题设置和要求。其中一些需要指定集群的数量，有些则不需要。有些可以只使用成对相似性，有些需要对被聚类的项目进行一些明确的表示，等等。

我建议你从两个经典的聚类算法开始：

http://en.wikipedia.org/wiki/K-means_clustering - 在这里，您预先指定聚类的数量 ("k")，但是被聚类的对象必须是矢量 space 中的点（有一些方法将文档聚类问题简化为向量 space 问题 - 搜索 "term vector representation"）。由于您正在处理余弦相似度，看起来您已经有了一个向量 space，因此您可以使用 K-means。
http://en.wikipedia.org/wiki/Hierarchical_clustering (in particular, "single-linkage agglomerative clustering" http://en.wikipedia.org/wiki/Single-linkage_clustering) - 在这里，您只需要成对的相似性：您通过反复查找两个最相似的文档并将它们加入同一个集群来构建一棵树，直到您拥有所需数量的集群。

Answer 2

各种聚类算法对成对距离进行操作；许多也可以适应成对相似性。

层次凝聚聚类 (HAC) 是这方面的原型。它适用于距离或相似性矩阵，并合并从单个文档开始的最相似的集群。其他算法包括 DBSCAn、OPTICS、...

k-means 正好相反。它计算均值，以及与均值的距离。由于使用 mean，它不适用于相似性或其他距离而不是平方欧几里德。平均值最小化最小二乘法，而不是距离。但是，有时您有出路。如果您的数据被归一化为非负单位球体，则平方欧几里德 d2(a,b)= 2 - 2*cos(a,b)。因此，球形 k-means 也适用。其他依赖坐标和均值的算法包括 Mean-Shift 和 BIRCH。

如何根据相似性度量对文档进行聚类？

How to cluster docs based on their similarity measures?

machine-learning

data-mining