310
《Hadoop與大數據挖掘》一2.5 K-Means算法原理及Hadoop MapReduce實現
本節書摘來華章計算機《Hadoop與大數據挖掘》一書中的第2章 ，第2.5節，張良均 樊 哲 位文超 劉名軍 許國傑 周 龍 焦正升 著 更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看。
2.5 K-Means算法原理及Hadoop MapReduce實現
2.5.1 K-Means算法原理
K-Means算法是硬聚類算法，是典型的基於原型的目標函數聚類方法的代表。它是將數據點到原型的某種距離作為優化的目標函數，利用函數求極值的方法得到迭代運算的調整規則（如圖2-45所示）。K-Means算法以歐氏距離作為相似度測度，求對應某一初始聚類中心向量V最優分類，使得評價指標最小。算法采用誤差平方和準則函數作為聚類準則函數。
具體的算法步驟如下：
1）隨機在圖中取K（這裏K＝2）個種子點。
2）然後對圖中的所有點求到這K個種子點的距離，假如點Pi離種子點Si最近，那麼Pi屬於Si點群。圖2-45中，我們可以看到A、B屬於上麵的種子點，C、D、E屬於下麵中部的種子點。
3）接下來，我們要移動種子點到屬於它的“點群”的中心。見圖2-45中的第3步。
4）然後重複第2）和第3）步，直到種子點沒有移動。我們可以看到圖2-45中的第4步上麵的種子點聚合了A、B、C，下麵的種子點聚合了D、E。
圖2-46所示為K-Means算法的流程圖。
該流程圖描述其實和算法步驟類似，不過，這裏需要考慮下麵幾個問題：
1）選擇k個聚類中心用什麼方法？
提示：可以隨機選擇或直接取前k條記錄。
2）計算距離的方法有哪些？
提示：歐氏距離、餘弦距離等。
3）滿足終止條件是什麼？
提示：使用前後兩次的聚類中心誤差（需考慮閾值小於多少即可）；使用全局誤差小於閾值（閾值選擇多少？）。
請讀者考慮上麵的幾個問題，並完成下麵的動手實踐（K-Means算法實現）。
最後更新：2017-06-26 10:32:34