一百万个对象的层次聚类
cluster-analysis
data-mining
machine-learning
python
5
0

谁能指出我可以聚类约一百万个对象的分层聚类工具(在python中更可取)?我尝试过hclusterOrange

hcluster无法处理18k个对象。 Orange能够在几秒钟内将18k个对象聚类,但是失败了10万个对象(饱和内存并最终崩溃)。

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

参考资料:
Stack Overflow
收藏
评论
共 2 个回答
高赞 时间 活跃

要击败O(n ^ 2),您必须首先将1M点(文档)减少为1000堆,每堆1000个点,或100堆,每10k,或...
两种可能的方法:

  • 从15k个点构建一个分层树,然后将其余部分一一添加:时间〜1M *树深度

  • 首先建立100或1000个扁平集群,然后建立100或1000个集群中心的层次树。

这两种方法的工作效果如何主要取决于目标树的大小和形状-多少个级别,多少个叶子?
您正在使用什么软件,以及群集需要多少小时/天?

对于平面集群方法, K-d_tree在2d,3d,20d甚至128d的点上都可以正常工作-这不是您的情况。我对群集文本几乎一无所知。 局域性敏感哈希

看一下scikit-learn集群 -它有几种方法,包括DBSCAN。

补充:另请参见
google-all-pairs- likeness -search “在稀疏矢量数据中查找所有相似矢量对的算法”,Beyardo等。 2007年
SO分层集群启发式

收藏
评论

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

您应该认真考虑使用其他聚类算法。层次聚类速度很慢,通常通常无法令人信服。特别是对于数百万个对象,您不能仅查看树状图来选择适当的切割。

如果您真的想继续层次化集群,我相信ELKI (尽管是Java)具有SLINKO(n^2)实现。在100万个对象中,其速度应约为100万倍。我也不知道他们是否已经拥有CLINK 。而且我不确定除单链接和完整链接之外,其他变体是否真的有sub- O(n^3)算法。

考虑使用其他算法。例如,k均值随对象数量的伸缩性很好(通常也不是很好,除非您的数据非常干净且规则)。一旦您对参数感到OPTICS ,我认为DBSCANOPTICS相当不错。如果您的数据集是低维的,那么使用适当的索引结构可以很好地加速它们。然后,他们应该在运行O(n log n) ,如果你有一个索引O(log n)查询时间。这对于大型数据集可能会产生巨大的影响。我个人已经在没有问题的110k图像数据集上使用了OPTICS ,因此我可以想象它可以在您的系统上扩展到100万。

收藏
评论
新手导航
  • 社区规范
  • 提出问题
  • 进行投票
  • 个人资料
  • 优化问题
  • 回答问题

关于我们

常见问题

内容许可

联系我们

@2020 AskGo
京ICP备20001863号