海量數據的聚類通常如何做？

01-21

場景：
1、每天100萬天新的商品數據入庫
2、使用Fuzzy K-Means對商品進行聚類

需求：
1、如何設計存儲方案呢？
2、聚類操作怎麼設計，如何計算比較合理呢？
重點在於，能否詳細的解釋這種場景下的海量數據處理如何做

（比如不必說用Map Reduce這種大方向性的解釋，最好能進一步說明如何用Map Reduce，如如何設計Map、如何設計Reduce）

簡單更新一下答案……前段時間上 Mahout 官網看了看，貌似項目已經併入 Spark 的 MLLib （https://spark.apache.org/mllib/），並且停止了更新，沒想到前幾天又放出了0.10.0的新版本，不過還是基於 Spark 的。

___________________________________________

首先不知道你要在哪些數據上做聚類，是所有數據還是每天的100萬？假如只在每天的100萬上聚類的話，就比較簡單了，因為100萬真的不算很大的數據量…

另外如果舊數據已經聚好了類，那就更簡單了，只需要比較每個新數據點和質心的距離，大於一定閾值的可以新開一個類。可以參考這個：Automatic online news issue construction in web environment。

現在假定你的舊數據沒有被處理，且你需要在所有數據上進行聚類，那麼這才是真正的大數據問題。

首先，有人推薦Apache Mahout: Scalable machine learning and data mining，這是一個開源的大數據機器學習庫，源代碼在apache/mahout · GitHub。這裡面包含了很多常用的聚類演算法，有k-Means，Canopy，Fuzzy k-Means，Streaming k-Means，Spectral Clustering，相信足夠滿足你的要求了。不過………………

不過Mahout現在的version才是0.9，而且代碼寫得比較亂，說實話既不穩定又不好用…根據我自己的測試，對於k-Means，Mahout的initialization效率極低。對於每個質心，Mahout都會在HDFS上建立一個新的文件，這個過程不知為什麼出奇的慢。所以如果你需要的聚的類數量不多，那麼還可以接受，如果需要k=幾千或幾萬，那麼必然會悲劇。我曾在一個有50多台機器的cluster上實驗Mahout的k-Means，結果還不如在我自己筆記本上跑得快。如果你一定要試試的話可以參考這個：Mahout分步式程序開發聚類Kmeans。

但Mahout並不是完全無價值的，重點是你可以參考Mahout實現你自己的演算法。比如根據Canopy：

Looking at the sample Hadoop implementation in http://code.google.com/p/canopy-clustering/ the processing is done in 3 M/R steps: 1. The data is massaged into suitable input format 1. Each mapper performs canopy clustering on the points in its input set and outputs its canopies" centers 1. The reducer clusters the canopy centers to produce the final canopy centers 1. The points are then clustered into these final canopies

這個描述已經很清楚了，完全可以寫出更適合數據的版本。

另外Google也有一些很好的大數據聚類的教程：https://www.youtube.com/watch?v=yjPBkvYh-sslist=PLEFAB97242917704A

----------------------------------------------------------------------------------

最後說點其他的，大數據聚類是一個很難的問題，就我已有的知識，很多不錯的聚類演算法在大數據上都不好用，比如Mean-Shift clustering，hierarchical clustering，這些方法大都需要計算距離矩陣，顯然實際上不可行。

如果我的理解有誤或是有什麼遺漏希望各位不吝指教…

GraphLab - Large-Scale Machine Learning on Graphs 這個可以做

做反欺詐時我們做過每天kw量級的帖子准實時聚類，用的是dbscan+simhash演算法，DBSCAN演算法的顯著優點是聚類速度快且能夠有效處理雜訊點和發現任意形狀的空間聚類。simhash演算法能夠把帖子用一個hash來表示，減少對比複雜度，為了減少對比數據量，我們把64位的simhash每16位分成4段，只對比四段中至少一段完全一樣的。我們把dbscan聚類得到的核心點放在一個單獨的核心點表中，把每分鐘發布的帖子和核心點做simhash對比，如果發現該帖子和某核心點密度可達，則把該帖子加入該核心點的聚類，上線後效果不錯，每分鐘准實時聚類無延時。

海量數據可以抽樣分析，先用抽樣數據進行聚類，把用戶分成幾類，然後用決策樹對每類提取規則，一個商品進來後就可以用規則對他進行歸類了。

題主問的是海量數據，那我就假設這是個工程問題而非演算法問題，因為演算法是一樣的。

100萬是增量吧，全量有多少？如果全量超過5000w，使用分散式會比單機進行優化更合適。

MapReduce結構在需要多次迭代的演算法中優勢不明顯，不如使用MPI架構的集群來進行分散式聚類計算。

1. 抽樣；

2. MapReduce: 每個map處理一塊數據，得到聚類結果把質心給reduce，reduce算一個平均質心，再迭代回map，直到滿足結束條件。

mahout的k-means演算法