谁能给我指出一个可以聚类约 100 万个对象的层次聚类工具(最好在 python 中)？我试过hcluster还有Orange .
hcluster 在处理 18k 个对象时遇到问题。 Orange 能够在几秒钟内聚集 18k 个对象，但以 100k 个对象失败(内存饱和并最终崩溃)。
我在 Ubuntu 11.10 上运行 64 位 Xeon CPU (2.53GHz) 和 8GB RAM + 3GB 交换。
最佳答案
问题可能是他们会尝试计算完整的 2D 距离矩阵(大约 8 GB 天真 double )，然后他们的算法将在 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 万。
关于python - 100万个对象的层次聚类，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9156961/