k-Means聚類(lèi)

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

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

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

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

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

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

③ 利用均值等方法更新該類(lèi)的中心值;

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

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

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

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

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

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

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

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

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

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

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

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