100万个对象的层次聚类

Question

有谁能给我指一个层次化的集群工具（在python中更可取）来集群大约100万个对象吗？我试过^{}，也试过Orange。

hcluster有18k个对象的问题。Orange能够在几秒钟内对18k个对象进行集群，但在100k个对象上失败（内存饱和，最终崩溃）。

我在Ubuntu11.10上运行64位XeonCPU（2.53GHz）和8GB RAM+3GB交换。

Answer 1

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

您应该认真考虑使用不同的聚类算法。层次聚类是缓慢的，其结果通常不令人信服。尤其是对于上百万个物体，你不能只看树状图就选择合适的切割。

如果您真的想继续分层集群，我相信ELKI（尽管是Java）有一个O(n^2)实现SLINK。100万个物体的速度大约是100万倍。我不知道他们是否也有CLINK。我不确定除了单链接和完整链接之外，是否还有其他变体的子O(n^3)算法。

考虑使用其他算法。例如，k-means可以很好地适应对象的数量（通常也不是很好，除非您的数据非常干净和规则）。DBSCAN和OPTICS在我看来是非常好的，一旦你对参数有了感觉。如果您的数据集是低维的，那么使用适当的索引结构可以很好地加速它们。如果您有一个查询时间为O(log n)的索引，那么它们应该在O(n log n)中运行。这对于大型数据集来说会有很大的不同。我个人在110k个图像数据集上使用了OPTICS，没有问题，因此我可以想象它在您的系统上可以扩展到100万个。

Answer 2

要打败O（n^2），你必须先降低你的1米点数（文档） 例如，1000桩，每桩1000点，或100桩，每桩10k，或……
两种可能的方法：

• 从15k点构建一个层次树，然后逐个添加其余的： 时间~1M*treedepth

• 首先建造100或1000个平面集群， 然后构建100或1000个集群中心的层次树。

这两种方法的效果如何关键取决于 目标树的大小和形状-- 多少层，多少片叶子？
你在用什么软件， 你需要做多少小时/天的聚类？

对于扁平集群方法， K-d_tree秒 对二维、三维、20d甚至128d的点都可以很好地工作——这不是你的情况。 我对文本聚类几乎一无所知； Locality-sensitive_hashing？

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

添加：另请参见
google-all-pairs-similarity-search “在稀疏向量数据中寻找所有相似向量对的算法”，Beyardo et el。2007年
SO hierarchical-clusterization-heuristics