24

谁能给我指出一个可以聚类约 100 万个对象的层次聚类工具（最好在 python 中）？我试过了hcluster，还有Orange。

hcluster18k 个对象有问题。Orange 能够在几秒钟内聚集 18k 个对象，但以 100k 个对象失败（内存饱和并最终崩溃）。

我在 Ubuntu 11.10 上运行 64 位 Xeon CPU (2.53GHz) 和 8GB RAM + 3GB 交换。

4

2 回答 2

15

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

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

如果你真的想继续层次聚类，我相信ELKIO(n^2) （虽然是Java）有一个SLINK. 100 万个对象的速度应该大约是 100 万倍。我不知道他们是否也有CLINK。而且我不确定O(n^3)除了单链接和完整链接之外，是否还有其他变体的子算法。

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

于 2012-02-06T08:59:00.993 回答
11

要击败 O(n^2)，您必须首先将 1M 点（文档）减少到例如 1000 堆每堆 1000 点，或每堆 100 堆 10k，或者......
两种可能的方法：

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

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

这两种方法的效果如何主要取决于目标树的大小和形状——有多少层，有多少叶子？
您正在使用什么软件，您需要多少小时/天进行集群？

对于平面集群方法， K-d_tree对于 2d、3d、20d 甚至 128d 中的点都可以正常工作——这不是你的情况。我对聚类文本几乎一无所知。 局部敏感散列？

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

添加：另请参见
google-all-pairs-similarity-search “在稀疏向量数据中查找所有相似向量对的算法”，Beyardo 等。2007
SO 层次聚类启发式

于 2012-02-27T14:22:32.073 回答