几乎均匀分布的数据的高效聚类算法

Question

我在玩自然语言处理，并试图对新闻文章标题进行聚类。我将标题转换为矢量，但它们几乎均匀分布。有2-3个新闻文章的小集群，但大多数新闻文章应该在他们自己的集群。

我试过使用k-means，但文章很少改变集群，因为数据是相当统一的。最初的随机簇最终成为最后的簇。

我尝试了凝聚式集群，它对于一个小数据集（几百篇文章）非常适用。然而，它需要很长时间，因为它至少是O（n^2）。

是否有任何有效的算法来聚类几乎均匀分布的数据？

例如，如果我的数据是一个实数集，它可能是这样的：

1 2 3 4 4.1 5 6

在这种情况下，该簇应该是：（1） ，（2），（3），（4，4.1），（5），（6）。 有没有更好的方法来做到这一点比凝聚聚类？

Answer 1

1. 对数据进行排序。
2. 选择一个阈值（见步骤4）
3. 迭代通过数据
4. 如果当前值和当前簇的第一值之间的差小于所述阈值时，把它们在同一个群集中，否则启动一个新的集群。

由于排序，这应该是O（n log n）。