k-Means聚類

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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