100万个对象的层次聚类

Question

有没有人能推荐一个分层聚类的工具（最好是用Python写的），可以处理大约100万个对象？我试过了hcluster和Orange。

hcluster在处理18000个对象时遇到了问题。而Orange可以在几秒钟内处理18000个对象，但在处理10万个对象时就不行了（内存满了，最后崩溃了）。

我使用的是一台64位的Xeon CPU（2.53GHz），有8GB内存和3GB的交换空间，运行的是Ubuntu 11.10。

Answer 1

问题可能出在他们会尝试计算完整的二维距离矩阵（大约8GB，使用双精度计算），然后他们的算法无论如何都会在O(n^3)的时间复杂度下运行。

你应该认真考虑使用不同的聚类算法。层次聚类速度很慢，通常结果也不太令人信服。特别是当对象数量达到百万时，你不能仅仅通过查看树状图来选择合适的切割点。

如果你真的想继续使用层次聚类，我相信ELKI（不过是Java写的）有一个O(n^2)的SLINK实现。对于100万个对象来说，这个算法的速度应该大约快100万倍。我不知道他们是否已经有CLINK。而且我不确定除了单链接和完全链接之外，是否还有其他变体的算法能做到O(n^3)以下。

考虑使用其他算法。例如，k-means算法在对象数量增加时表现得很好（不过通常效果也不太好，除非你的数据非常干净和规律）。我认为DBSCAN和OPTICS也相当不错，一旦你对参数有了感觉。如果你的数据集维度较低，使用合适的索引结构可以大大加速它们的运行。这样的话，它们的运行时间应该在O(n log n)，前提是你有一个查询时间为O(log n)的索引。这对于大数据集来说差别会很大。我个人在处理一个11万张图片的数据集时使用过OPTICS，没有遇到问题，所以我可以想象它在你的系统上扩展到100万也会很好。

Answer 2

要想打败O(n^2)的复杂度，首先你得把100万的点（文档）减少到比如说1000堆，每堆1000个点，或者100堆，每堆1万个点，等等。
这里有两种可能的方法：

• 从大约15000个点开始构建一个层次树，然后一个一个地添加剩下的点： 时间复杂度大约是1M * 树的深度

• 先构建100个或1000个平坦的聚类， 然后再根据这100个或1000个聚类中心构建你的层次树。

这两种方法的效果取决于你目标树的大小和形状—— 有多少层，有多少个叶子节点？
你在使用什么软件， 你有多少小时/天来进行聚类？

对于平坦聚类的方法， K-d树在2维、3维、20维甚至128维的点上都能很好地工作——但这不适合你的情况。 我对文本聚类几乎一无所知； 局部敏感哈希呢？

可以看看scikit-learn的聚类—— 它有几种方法，包括DBSCAN。

补充：还可以看看
google-all-pairs-similarity-search “在稀疏向量数据中查找所有相似向量对的算法”，Beyardo等，2007年
SO层次聚类启发式方法