k-Means聚類

1)k-Means聚類算法原理k-Means算法接受參數k，然后將事先輸入的n個數據對象劃分為k個聚類以便使所獲得的聚類滿足：同一聚類中的對象相似度較高;而不同聚類中的對象相似度較小。

聚類相似度是利用各聚類中對象的均值所獲得一個“中心對象”(引力中心)來進行計算的。

k-Means算法是最為經典的基于劃分的聚類方法，是十大經典數據挖掘算法之一。k-Means算法的基本思想是：以空間中k個點為中心進行聚類，對最靠近它們的對象歸類。通過迭代的方法，逐次更新各聚類中心的值，直至得到最好的聚類結果。

假設要把樣本集分為c個類別，算法描述如下：

① 適當選擇c個類的初始中心;

② 在第k次迭代中，對任意一個樣本，求其到c個中心的距離，將該樣本歸到距離最短的中心所在的類;

③ 利用均值等方法更新該類的中心值;

④ 對于所有的c個聚類中心，如果利用②及③的迭代法更新后其值保持不變，則迭代結束，否則繼續迭代。

該算法的較大優勢在于簡潔和快速。算法的關鍵在于初始中心的選擇和距離公式。

2)k-Means聚類算法的實現

k-Means聚類算法的實現步驟如下。

(1)參數input指定待聚類的所有數據點，clusters指定初始聚類中心。如果指定參數k，由org.apache.mahout.clustering.kmeans.RandomSeedGenerator.buildRandom通過org.apache. hadoop.fs直接從input指定文件中隨機讀取k個點放入clusters中。

(2)根據原數據點和上一次迭代(或初始聚類)的聚類中心計算本次迭代的聚類中心，輸出到clusters-N目錄下。該過程由org.apache.mahout.clustering.kmeans下的KMeansMapper\KMeansCombiner\KMeansReducer\KMeansDriver實現。

① KMeansMapper：在configure中初始化mapper時讀入上一次迭代產生或初始聚類中心(每個mapper都讀入所有的聚類中心)。map方法對輸入的每個點都計算其最近的距離類，并加入輸出的key為該點所屬聚類ID，value為KMeansInfo實例，包含點的個數和各分量的累加和。

② KMeansCombiner：本地累加KMeansMapper輸出的同一聚類ID下的點個數和各分量的和。

③ KMeansReducer：累加同一聚類ID下的點個數和各分量的和，求本次迭代的聚類中心，并根據輸入Delta判斷該聚類是否已收斂。上一次迭代聚類中心與本次迭代聚類中心距離小于Delta。輸出各聚類中心和其是否收斂標記。

④ KMeansDriver：控制迭代過程直至超過較大迭代次數或所有聚類都已收斂每輪迭代后，KMeansDriver讀取其clusters-N目錄下的所有聚類。若所有聚類已收斂，則整個k-Means聚類過程收斂了。

3)k-Means聚類算法參數調整

manhout kmeans聚類有兩個重要參數，即收斂Delta和較大迭代次數。通常情況下，Delta值越小，表示收斂條件越高，因此最終收斂的聚類數可能會降低，而較大迭代次數可通過觀察每次迭代后收斂聚類數決定，當收斂聚類數幾乎不再變化或振蕩時可停止迭代。