Mahout kmeans聚類

Mahout? K-means聚類

一、Kmeans 聚類原理

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

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

（1）適當選擇c個類的初始中心；

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

（3）利用均值等方法更新該類的中心值；

（4）對于所有的c個聚類中心，如果利用（2）（3）的迭代法更新后，值保持不變，則迭代結束，否則繼續迭代。

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

二、Mahout kmeans實現

?Mahout kmeans MapReduce實現的原理和上述的一致，值得注意的是，Mahout將數據存儲在HDFS，用MapReduce做批量并行的計算。在做kmeans之前，需要將文本用Mahout向量化模塊工具做向量化。計算過程主要分為三個步驟：初始中心選取，尋找簇中心，劃分數據。

（一） 簇定義

簇Cluster是一個實體，保存該簇的關鍵信息。

?privateint id; 簇編號

核心參數：計算完數據后最終的簇屬性

?private long numPoints; 簇中點的個數

?private Vector center; 中心向量 center=

?private Vector radius; 半徑向量?radius =

調整參數：簇中加入一個點后調整的參數

?private double s0; s0=?權重和。對于Kmeans，w=1 ,所有s0=numPoints

?private Vector s1;? s1=? x 為point，w為權重。對kmeansw =1

?private Vector s2 ;? s2=?x 為point，w為權重。對kmeansw =1

（二） 初始中心點選擇

（1）RandomSeedGenerator 將輸入的向量隨機選擇K個輸出到HDFS作為Kmeans 聚類的初始中心點。

（2）另一種將Canopy計算出的簇中心作為kmeans聚類的初始中心點。

（三） 迭代更新中心

? 通過不斷的迭代，移動簇中心。該過程劃分為兩個部分，一個是簇劃分Job，一個是控制迭代循環。

1.簇劃分Job過程：

????? Map:

Collection<Cluster> clusters = newArrayList<Cluster>()

setUp(){

????? ?????? ?????? ?讀入上一次輸出的全部中心點，填充cluster。

}

Map(WritableComparable<?> key, VectorWritable point){

用KMeansClustererclusterer 將point 劃分到cluster中距離最近的一個cluster中。

輸出: key? clusterID ，value? ClusterObservations

}

}

? Combiner:

?? ?Reduce（key?clusterID ，value? Iterator<ClusterObservations> it ）{

?? ? ?????? ?計算同一個cluster的局部參數。

??? }

?? Reduce:

?? ? Reduce(key? clusterID ，value? ClusterObservations){

計算同一cluster的全局參數。

計算cluster的新中心。

對比之前的中心，計算是否收斂。

替換新的中心點作為cluster的中心。

輸出 keyclusterID，value Cluster

}

2.循環過程

?while(!收斂||沒有達到相應的迭代次數){

???? 1.執行迭代Job，輸入全部數據，輸出新的簇中心；

???? 2.判斷是否有簇沒有收斂。只要有一個簇沒有收斂，則斷定為全局不收斂。

?}

（四） 劃分數據

??劃分數據過程是對簡單的，只需要計算向量和所有簇的距離，將其劃分到距離最小的一個簇中。由一個map完成。

Map:

Collection<Cluster> clusters = new ArrayList<Cluster>()

setUp(){

讀取最終收斂的簇，填充clusters。

}

Map(WritableComparable<?> key, VectorWritable point){

?? Double min = 0 ;

?? String clusterID ;

?????? While(cluster :clusters){

????? 計算min;

????? 得到最小距離的clusterID;

????? }

?????? 輸出：clusterID ,point

???? }

三、API說明

API

KMeansDriver.main(args);
--input(-i)	輸入路徑
--outpu(-o)	輸出路徑
--distanceMeasure(-dm)	距離類權限命名，如“org.apache.mahout.common.distance.Cosine DistanceMeasure”
--clusters(-c)	中心點存儲路徑，如果該路徑下沒有中心點，則隨機生成并寫入該目錄
--numClusters(-k)	簇個數
--convergenceDelta(-cd)	收斂值
--maxIter(-x)	最大迭代次數
--overwrite(-ow)	是否覆蓋上次操作
--clustering(-cl)	是否執行聚類
--method(-xm)	默認”mapreduce”,或”sequential”

?

示例

String? [] arg=?????????? {"-x","10",

?????? ?????? ?????? ?????? ?????? ?????? "-c","kmeans_center",

?????? ?????? ?????? ?????? ?????? ?????? "-i","vector\tfidf-vectors",

?????? ?????? ?????? ?????? ?????? ?????? "-o","kmeans",

??????????????????????? "-dm","org.apache.mahout.common.distance.?? EuclideanDistanceMeasure",

?????? ?????? ?????? ?????? ?????? ?????? "-k","3",

?????? ?????? ?????? ?????? ?????? ?????? "-cd","0.01",

?????? ?????? ?????? ?????? ?????? ?????? "-ow",

?????? ?????? ?????? ?????? ?????? ?????? "-cl",

?????? ?????? ?????? ?????? ?????? ?????? "-xm","mapreduce"};

?????? ?????? KMeansDriver.main(arg);

?

輸出

結果文件	Key類型	Value類型	說明
clusters-*	類id (org.apache.hadoop.io.Text)	類中心 (org.apache.mahout. clustering.kmeans.Cluster)	每條記錄以類id和類中心表示一個類別
clusteredPoints	類id (org.apache.hadoop.io.IntWritable)	文檔向量 (org.apache. mahout.clustering.WeightedVectorWritable)	每條記錄中，文檔向量代表文檔，類id代表該文檔所屬類別

注:clusters-*中*代表數字，第i次迭代產生的類信息即為clusters-i

四、參考文獻

?1.《web數據挖掘》