集羣計算

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時間裏沒有看到好的基準。