k-Means聚類

k-Means聚類

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

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

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

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

① 適當(dāng)選擇c個類的初始中心;

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

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

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

該算法的較大優(yōu)勢在于簡潔和快速。算法的關(guān)鍵在于初始中心的選擇和距離公式。

2)k-Means聚類算法的實現(xiàn)

k-Means聚類算法的實現(xiàn)步驟如下。

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

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

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

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

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

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

3)k-Means聚類算法參數(shù)調(diào)整

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