对100万个对象进行分层聚类

Question

有没有人能给我推荐一个层次聚类工具(最好是在python中)，它可以聚类大约一百万个对象？我尝试过hcluster和Orange。

hcluster在处理18k对象时遇到了问题。Orange能够在几秒钟内集群18k个对象，但失败了100k个对象(内存饱和并最终崩溃)。

我在Ubuntu11.10上运行64位Xeon CPU (2.53 RAM )和8 8GB内存+3 8GB交换空间。

Answer 1

要击败O(n^2)，您必须首先将您的1M点(文档)减少到1000堆，每堆1000点，或者100堆10k，或者...

两种可能的方法：

例如，

• 从15k点构建一个层次树，然后逐个添加其余的: time ~ 1M * treedepth
• first构建100或1000个扁平集群，然后构建100或1000个集群中心的层次树。

这两种方法的效果取决于目标树的大小和形状--有多少层，有多少叶？

您使用的是什么软件，需要多少小时/几天才能完成群集？

对于平面集群方法，K-d_tree适用于2d、3d、20d甚至128d中的点--不是您的情况。我对文本聚类几乎一无所知；Locality-sensitive_hashing？

看看scikit-learn clustering --它有几种方法，包括DBSCAN。

添加:另请参阅

google-all-pairs-similarity-search“在稀疏矢量数据中寻找所有相似矢量对的算法”，Beyardo et el。2007年

SO hierarchical-clusterization-heuristics

Answer 2

问题可能是他们会尝试计算完整的2D距离矩阵(大约8 GB，双精度)，然后他们的算法无论如何都会在O(n^3)时间内运行。

您应该认真考虑使用不同的聚类算法。层次聚类速度很慢，而且结果通常不太令人信服。特别是对于数以百万计的物体，你不能只看树状图来选择适当的切割。

如果您真的想继续分层集群，我相信ELKI (尽管是Java语言)有一个SLINK的O(n^2)实现。在一百万个对象的情况下，速度大约是一百万倍。我不知道他们是否已经有CLINK了。而且我不确定除了单链和完整链之外，是否还有其他变体的子O(n^3)算法。

考虑使用其他算法。例如，K-意味着可以很好地缩放对象的数量(通常也不是很好，除非您的数据非常干净和规则)。在我看来，只要你对参数有所了解，DBSCAN和OPTICS就相当不错。如果您的数据集是低维的，则可以通过适当的索引结构很好地加速它们。如果您有一个包含O(log n)查询时间的索引，那么它们应该在O(n log n)中运行。这对于大型数据集来说会有很大的不同。我个人在110k的图像数据集上使用过OPTICS，没有出现任何问题，所以我可以想象它在您的系统上可以很好地扩展到100万。