一种近均匀分布数据的高效聚类算法

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. 迭代您的data
4. 如果当前群集的当前值与第一个值之间的差值小于阈值，请将它们放入同一群集中，否则将启动一个新群集。

由于排序的原因，这应该是O(n log n)。