集群计算

Question

我正在测试一些文本文档数据集上的聚类算法（词频作为特征）。依次运行Scikit Learn Clustering的一些方法，下面是它们花费多长时间~5万个文件，每个文件有26个特征。每次融合所花费的时间有很大的差异，我输入的数据越多，越极端，其中一些（例如MeanShift）在数据集增长到一定大小后才停止工作。

（下面给出的时刻是从剧本开始的总数，即KMEANS了0.004分，均值漂移（2.56 - 0.004）分钟等）

shape of input: (4957, 26) 

KMeans: 0.00491824944814 
MeanShift:  2.56759268443 
AffinityPropagation:  4.04678163528 
SpectralClustering:  4.1573699673 
DBSCAN:  4.16347868443 
Gaussian:  4.16394021908 
AgglomerativeClustering:  5.52318491936 
Birch:  5.52657626867 

我知道有些聚类算法在本质上更计算密集型（例如，章节here概述了Kmeans的需求与数据点的数量呈线性关系，而层次模型为O（m logm））。 所以我想知道

• 我怎么能确定有多少个数据点每一种算法可以 手柄;并且是等于输入文件/输入特征的数量 与此等式相关吗？
• 计算强度取决于集群 设置的数量 - 例如， Kmeans中的距离度量或DBSCAN中的距离度量？
• 聚类成功是否影响计算时间？一些诸如DBSCAN等算法很快完成 - mabe，因为他们没有在数据中发现任何聚类; Meanshift找不到集群 ，并且仍然需要永远。 （我在这里使用默认设置）。可能 一旦他们发现数据中的结构会发生剧烈变化？
• 原始计算能力是多少这些算法的限制因素？我能在每台普通桌面计算机上使用〜30个 功能集群〜300,000个文件吗？或者是否有意义 使用计算机群集来处理这些事情？

任何帮助，非常感谢！测试是在一台Mac mini上运行的，2.6 Ghz，8 GB。数据输入是numpy array。

Answer 1

这是一个太宽泛的问题。

事实上，这些问题中的大部分都没有答案。例如k-means是而不是只是线性的O（n），但是因为直到收敛所需的迭代次数趋向于随数据集大小增长，所以它比这更昂贵（如果运行直到收敛）。

多层次聚类可以从O（n log n）到O（n^3）中的任何位置，主要取决于实施方式和链接。如果我没有记错，sklearn的实现是O（n^3）算法。

一些算法有参数提前停止。在他们真正完成之前！对于k-means，如果你想真的完成算法，你应该使用tol=0。否则，如果相对改善小于这个因素，就会提前结束 - 这可能为时过早。 MiniBatchKMeans永远不会收敛。因为它每次只查看数据的随机部分，所以它会一直持续下去，除非您选择固定数量的迭代。

不要试图从小型数据集得出结论。你需要去你的限制。即什么是最大的数据集，你仍然可以在每个算法的说明，1和2以及4和12小时内处理？ 为了得到有意义的结果，你的运行时间应该是小时，除非这个算法只是耗尽内存之前 - 那么你可能会感兴趣的预测，你可以走多远扩大，直到你耗尽内存 - 假设你有1个TB的RAM，你仍然可以处理多大的数据？

的问题是，你不能简单地使用相同的参数数据集不同的尺寸。如果你没有选择好参数（例如DBSCAN把所有的东西都放入噪音中，或者把所有的东西都放入一个簇中），那么你也不能从中得出结论。

然后，有可能只是一个执行错误。最近，sklearn的DBSCAN变得快了很多。它仍然是相同的算法。所以2年前完成的大部分结果都是错误的，因为在sklearn中实施DBSCAN是不好的......现在它好多了，但它是最优的吗？可能不会。任何这些算法都可能出现类似的问题！

因此，做集群的一个很好的基准是真的困难。事实上，我在Looong时间里没有看到好的基准。