Mahout 之kmeans算法學習筆記
1. 什麼是 k-means 聚類算法?
從網上找到了很多定義,這裡選取比較典型的幾個;
K-Mean 分群法是一種分割式分群方法,其主要目标是要在大量高緯的資料點中找出
具有代表性的資料點;這些資料點可以稱為群中心,代表點;然後再根據這些
群中心,進行後續的處理,這些處理可以包含
1 )資料壓縮:以少數的資料點來代表大量的資料,達到資料壓縮的功能;
2 )資料分類:以少數代表點來代表特點類别的資料,可以降低資料量及計算量;
分割式分群法的目的是希望盡量減小每個群聚中,每一點與群中心的距離平方差(square error)。
假設我們現在有一組包含c個群聚的資料,其中第 k 個群聚可以用集合 Gk來表示,假設 Gk包含nk筆
資料 {x1, x2, …, xnk),此群聚中心為yk,則該群聚的平方差 ek可以定義為:
ek = S i |xi-yk|2 ,其中 xi是屬於第 k 群的資料點。
而這c個群聚的總和平方差E便是每個群聚的平方差總和:
E = S k=1~c ek
我們分群的方法,就變成是一個最佳化的問題,換句話說,我們要如何選取 c 個群聚以及相關的群中心,
使得 E 的值為最小。
2 .處理流程
( 1 ) 從 c 個資料對象任意選擇 k 個對象作為初始聚類中心;
( 2 ) 循環( 3 )到( 4 )直到每個聚類不再發生變化為止;
( 3 ) 根據每個聚類對象的均值(中心對象),計算每個對象與這些中心對象的距離;并根據最小距離重新對相應對象進行劃分;
( 4 ) 重新計算每個(有變化)聚類的均值(中心對象)
3. java 算法的實作說明
1) 假設給點一組 c 點資料 X = {x1, ..., xc} ,每一點都有 d 維;給定一個群聚的數目 k, 求其
最好的聚類結果。
2 ) BasicKMeans.java 主類
int coordCount = 250;// 原始的資料個樹
int dimensions = 100;// 每個資料的緯度數目
double[][] coordinates = new double[coordCount][dimensions];
這裡假設 c 點資料為 coordinates 對象,其中 c 為 coordCount,d 為 dimensions 相應值。
int mk = 30; // 想要群聚的數目
根據群聚數目定義 mk 個群聚類對象
mProtoClusters = new ProtoCluster[mK];// 見 ProtoCluster 類說明
// 首先随機選取 mk 個原始資料點作為群聚類
mProtoClusters[i]= new ProtoCluster (coordinates[j] );//i 依此為 0 到 mk 的值; j 為 0 到 coordCount的值
定義一個變量用于記錄和跟蹤每個資料點屬于哪個群聚類
mClusterAssignments = new int[coordCount];
mClusterAssignments[j]=i;// 表示第 j 個資料點對象屬于第 i 個群聚類
// 開始循環
- // 依次調用計算每個群聚類的均值
mProtoClusters[i].updateCenter(mCoordinates);// 計算第 i 個聚類對象的均值
- // 依次計算每個資料點到中心點的距離,然後根據最小值劃分到相應的群集類中;
采用距離平方差來表示資料點到中心點的距離;
//定義一個變量,來表示資料點到中心點的距離
mDistanceCache = new double[coordCount ][mk];
//其中mDistanceCache[i][j]表示第i個資料點到第j個群聚對象中心點的距離;
//距離算法描述():
a)依次取出每個資料點對象double[] coord = coordinates[i];
b)再依次取出每個群聚類中的中心點對象double[] center = mProtoClusters[j].mCenter;
c)計算coord對象與center對象之間的距離
double distance(double[] coord, double[] center) {
int len = coord.length;
double sumSquared = 0.0;
for (int i=0; i<len; i++) {
double v = coord[i] - center[i];
sumSquared += v*v; //平方差
}
return Math.sqrt(sumSquared);
}
d)循環執行上面的流程,把結果記錄在mDistanceCache[i][j]中;
- //比較出最小距離,然後根據最小距離重新對相應對象進行劃分
依次比較每個資料點的 最短中心距離,
int nearestCluster(int ndx) {
int nearest = -1;
double min = Double.MAX_VALUE;
for (int c = 0; c < mK; c++) {
double d = mDistanceCache[ndx][c];
if (d < min) {
min = d;
nearest = c;
}
}
return nearest;
}
該方法傳回該資料點對應的最短中心距離的群聚類的索引值;
比較每個 nearestCluster[coordCount] 的值和mClusterAssignments[coordCount]
的值是否相等,如果全相等表示所有的點已經是最佳距離了,直接傳回;
否則需要重新調整資料點和群聚類的關系,調整完畢後再重新開始循環;
調整時需要更新下列資料:
a)更新mProtoClusters[i]中的mCurrentMembership集合;
b)更新mClusterAssignments[i]中對應的值;
然後重行開始循環
3 ) ProtoCluster.java 是一個包含代表點的群聚類,該類有兩個最主要的屬性"代表點"和"群中心";
int[] mCurrentMembership;// 用于表示每個群聚包含的資料資料點集合
double[] mCenter;// 用于表示每個聚類對象的均值,也就是中心對象
void updateCenter(double[][] coordinates) {
// 該方法計算 聚類對象的均值 ;
// 根據 mCurrentMembership 取得原始資料點對象 coord ,該對象是 coordinates 的一個子集;然後取出該子集的均值;
取均值的算法很簡單,可以把 coordinates 想象成一個 m*n 的距陣 , 每個均值就是每個縱向列的取和平均值 , 該值保
存在 mCenter 中
for (int i=0; i< mCurrentMembership.length; i++) {
double[] coord = coordinates[mCurrentMembership[i]];
for (int j=0; j<coord.length; j++) {
mCenter[j] += coord[j];// 得到每個縱向列的和;
}
f or (int i=0; i<mCenter.length; i++) {
mCenter[i] /= mCurrentSize; // 對每個縱向列取平均值
}
}
K-Means這個詞第一次使用是在1967,但是它的思想可以追溯到1957年,它是一種非常簡單地基于距離的聚類算法,認為每個Cluster由相似的點組成而這種相似性由距離來衡量,不同Cluster間的點應該盡量不相似,每個Cluster都會有一個“重心”;另外它也是一種排他的算法,即任意點必然屬于某一Cluster且隻屬于該Cluster。當然它的缺點也比較明顯,例如:對于孤立點敏感、産生最終聚類之間規模的差距不大。
一、基本思想
1、數學描述
給定d維實數向量(),後面就将這個實數向量稱作點吧,短!K-Means算法會根據事先制定的參數k,将這些點劃分出k個Cluster(k ≤ n),而劃分的标準是最小化點與Cluster重心(均值)的距離平方和,假設這些Cluster為:,則數學描述如下:
,其中為第i個Cluster的“重心”(Cluster中所有點的平均值)。
聚類的效果類似下圖:
具體可見:http://en.wikipedia.org/wiki/K-means_clustering
2、算法步驟
典型的算法如下,它是一種疊代的算法:
(1)、根據事先給定的k值建立初始劃分,得到k個Cluster,比如,可以随機選擇k個點作為k個Cluster的重心,又或者用Canopy Clustering得到的Cluster作為初始重心(當然這個時候k的值由Canopy Clustering得結果決定);
(2)、計算每個點到各個Cluster重心的距離,将它加入到最近的那個Cluster;
(3)、重新計算每個Cluster的重心;
(4)、重複過程2~3,直到各個Cluster重心在某個精度範圍内不變化或者達到最大疊代次數。
别看算法簡單,很多複雜算法的實際效果或許都不如它,而且它的局部性較好,容易并行化,對大規模資料集很有意義;算法時間複雜度是:O(nkt),其中:n 是聚類點個數,k 是Cluster個數,t 是疊代次數。
三、并行化政策
K-Means較好地局部性使它能很好的被并行化。第一階段,生成Cluster的過程可以并行化,各個Slaves讀取存在本地的資料集,用上述算法生成Cluster集合,最後用若幹Cluster集合生成第一次疊代的全局Cluster集合,然後重複這個過程直到滿足結束條件,第二階段,用之前得到的Cluster進行聚類操作。
用map-reduce描述是:datanode在map階段讀出位于本地的資料集,輸出每個點及其對應的Cluster;combiner操作對位于本地包含在相同Cluster中的點進行reduce操作并輸出,reduce操作得到全局Cluster集合并寫入HDFS。
四、Mahout K-Means Clustering說明
mahout實作了标準K-Means Clustering,思想與前面相同,一共使用了2個map操作、1個combine操作和1個reduce操作,每次疊代都用1個map、1個combine和一個reduce操作得到并儲存全局Cluster集合,疊代結束後,用一個map進行聚類操作。可以在mahout-core下的src/main/java中的package:org.apache.mahout.clustering.kmeans中找到相關代碼:
1、資料模型
可以參見上一篇相同标題。
2、目錄結構
從目錄結構上說,需要兩個輸入目錄:一個用于儲存資料點集——input,一個用來儲存點的初始劃分——clusters;在形成Cluster的階段,每次疊代會生成一個目錄,上一次疊代的輸出目錄會作為下一次疊代的輸入目錄,這種目錄的命名為:Clusters-“疊代次數”;最終聚類點的結果會放在clusteredPoints檔案夾中而Cluster資訊放在Clusters-“最後一次疊代次數”檔案夾中。
3、如何抽象Cluster
可以從Cluster.java及其父類,對于Cluster,mahout實作了一個抽象類AbstractCluster封裝Cluster,具體說明可以參考上一篇文章,這裡做個簡單說明:
(1)、private int id; #每個K-Means算法産生的Cluster的id
(2)、private long numPoints; #Cluster中包含點的個數,這裡的點都是Vector
(3)、private Vector center; #Cluster的重心,這裡就是平均值,由s0和s1計算而來。
(4)、private Vector Radius; #Cluster的半徑,這個半徑是各個點的标準差,反映組内個體間的離散程度,由s0、s1和s2計算而來。
(5)、private double s0; #表示Cluster包含點的權重之和,
(6)、private Vector s1; #表示Cluster包含點的權重和,
(7)、private Vector s2; #表示Cluster包含點平方的權重和,
(8)、public void computeParameters(); #根據s0、s1、s2計算numPoints、center和Radius:
這幾個操作很重要,最後三步很必要,在後面會做說明。
(9)、public void observe(VectorWritable x, double weight); #每當有一個新的點加入目前Cluster時都需要更新s0、s1、s2的值
(10)、public ClusterObservation getObservations(); #這個操作在combine操作時會經常被用到,它會傳回由s0、s1、s2初始化的ClusterObservation對象,表示目前Cluster中包含的所有被觀察過的點
五、K-Means Clustering的Map-Reduce實作
K-Means Clustering的實作同樣包含單機版和MR兩個版本,單機版就不說了,MR版用了兩個map操作、一個combine操作和一個reduce操作,是通過兩個不同的job觸發,用Dirver來組織的,map和reduce階段執行順序是:
圖1
1、初始劃分的形成
K-Means算法需要一個對資料點的初始劃分,mahout裡用了兩種方法(以Iris dataset前3個feature為例):
(1)、使用RandomSeedGenerator類
在指定clusters目錄生成k個初始劃分并以Sequence File形式存儲,其選擇方法希望能盡可能不讓孤立點作為Cluster重心,大概流程如下:
圖2
(2)、使用Canopy Clustering
Canopy Clustering常常用來對初始資料做一個粗略的劃分,它的結果可以為之後代價較高聚類提供幫助,個人覺得Canopy Clustering用在資料預處理上要比單純拿來聚類更有用,比如對K-Means來說提供k值,另外還能很好的處理孤立點,當然,需要人工指定的參數由k變成了T1、T2,T1和T2所起的作用是缺一不可的,T1決定了每個Cluster包含點的數目,這直接影響了Cluster的“重心”和“半徑”,而T2則決定了Cluster的數目,T2太大會導緻隻有一個Cluster,而太小則會出現過多的Cluster。通過實驗,T1和T2取值會嚴重影響到算法的效果,如何确定T1和T2,似乎可以用AIC、BIC或者交叉驗證去做,但是我沒有找到具體做法,希望各位高人給指條明路:)。
以Iris為例,canopy方法選擇T1=3、T2=1.5、cd=0.5、x=10,兩種方法結果的前三個次元比較如下:
圖3
從圖中不同Cluster的交界情況可以看出這兩種方法的不同效果。
2、配置Cluster資訊
K-Means算法的MR實作,第一次疊代需要将随機方法或者Canopy Clustering方法結果目錄作為kmeans第一次疊代的輸入目錄,接下來的每次疊代都需要将上次疊代的輸出目錄作為本次疊代的輸入目錄,這就需要能在每次kmeans map和kmeans reduce操作前從該目錄得到Cluster的資訊,這個功能由KMeansUtil.configureWithClusterInfo實作,它依據指定的HDFS目錄将Canopy Cluster或者上次疊代Cluster的資訊存儲到一個Collection中,這個方法在之後的每個map和reduce操作中都需要。
3、KMeansMapper
對照上一篇第三節關于MR的那幅圖,map操作之前的InputFormat、Split、RR與上一篇完全相同。
1: public class KMeansMapper extends Mapper<WritableComparable<?>, VectorWritable, Text, ClusterObservations> {
2:
3: private KMeansClusterer clusterer;
4:
5: private final Collection<Cluster> clusters = new ArrayList<Cluster>();
6:
7: @Override
8: protected void map(WritableComparable<?> key, VectorWritable point, Context context)
9: throws IOException, InterruptedException {
10: this.clusterer.emitPointToNearestCluster(point.get(), this.clusters, context);
11: }
12:
13: @Override
14: protected void setup(Context context) throws IOException, InterruptedException {
15: super.setup(context);
16: Configuration conf = context.getConfiguration();
17: try {
18: ClassLoader ccl = Thread.currentThread().getContextClassLoader();
19: DistanceMeasure measure = ccl.loadClass(conf.get(KMeansConfigKeys.DISTANCE_MEASURE_KEY))
20: .asSubclass(DistanceMeasure.class).newInstance();
21: measure.configure(conf);
22:
23: this.clusterer = new KMeansClusterer(measure);
24:
25: String clusterPath = conf.get(KMeansConfigKeys.CLUSTER_PATH_KEY);
26: if (clusterPath != null && clusterPath.length()> 0) {
27: KMeansUtil.configureWithClusterInfo(conf, new Path(clusterPath), clusters);
28: if (clusters.isEmpty()) {
29: throw new IllegalStateException("No clusters found. Check your -c path.");
30: }
31: }
32: } catch (ClassNotFoundException e) {
33: throw new IllegalStateException(e);
34: } catch (IllegalAccessException e) {
35: throw new IllegalStateException(e);
36: } catch (InstantiationException e) {
37: throw new IllegalStateException(e);
38: }
39: }
40: }
(1)、KMeansMapper接收的是(WritableComparable<?>, VectorWritable) Pair,setup方法利用KMeansUtil.configureWithClusterInfo得到上一次疊代的Clustering結果,map操作需要依據這個結果聚類。
(2)、每個slave機器會分布式的處理存在硬碟上的資料,依據之前得到得Cluster資訊,用emitPointToNearestCluster方法将每個點加入到與其距離最近的Cluster,輸出結果為(與目前點距離最近Cluster的ID, 由目前點包裝而成的ClusterObservations) Pair。
4、KMeansCombiner
combiner操作是一個本地的reduce操作,發生在map之後,reduce之前:
1: public class KMeansCombiner extends Reducer<Text, ClusterObservations, Text, ClusterObservations> {
2:
3: @Override
4: protected void reduce(Text key, Iterable<ClusterObservations> values, Context context)
5: throws IOException, InterruptedException {
6: Cluster cluster = new Cluster();
7: for (ClusterObservations value : values) {
8: cluster.observe(value);
9: }
10: context.write(key, cluster.getObservations());
11: }
12:
13: }
5、KMeansReducer
很直白的的操作,隻是在setup的時候稍複雜。
1: public class KMeansReducer extends Reducer<Text, ClusterObservations, Text, Cluster> {
2:
3: private Map<String, Cluster> clusterMap;
4: private double convergenceDelta;
5: private KMeansClusterer clusterer;
6:
7: @Override
8: protected void reduce(Text key, Iterable<ClusterObservations> values, Context context)
9: throws IOException, InterruptedException {
10: Cluster cluster = clusterMap.get(key.toString());
11: for (ClusterObservations delta : values) {
12: cluster.observe(delta);
13: }
14: // force convergence calculation
15: boolean converged = clusterer.computeConvergence(cluster, convergenceDelta);
16: if (converged) {
17: context.getCounter("Clustering", "Converged Clusters").increment(1);
18: }
19: cluster.computeParameters();
20: context.write(new Text(cluster.getIdentifier()), cluster);
21: }
22:
23: @Override
24: protected void setup(Context context) throws IOException, InterruptedException {
25: super.setup(context);
26: Configuration conf = context.getConfiguration();
27: try {
28: ClassLoader ccl = Thread.currentThread().getContextClassLoader();
29: DistanceMeasure measure = ccl.loadClass(conf.get(KMeansConfigKeys.DISTANCE_MEASURE_KEY))
30: .asSubclass(DistanceMeasure.class).newInstance();
31: measure.configure(conf);
32:
33: this.convergenceDelta = Double.parseDouble(conf.get(KMeansConfigKeys.CLUSTER_CONVERGENCE_KEY));
34: this.clusterer = new KMeansClusterer(measure);
35: this.clusterMap = new HashMap<String, Cluster>();
36:
37: String path = conf.get(KMeansConfigKeys.CLUSTER_PATH_KEY);
38: if (path.length() > 0) {
39: Collection<Cluster> clusters = new ArrayList<Cluster>();
40: KMeansUtil.configureWithClusterInfo(conf, new Path(path), clusters);
41: setClusterMap(clusters);
42: if (clusterMap.isEmpty()) {
43: throw new IllegalStateException("Cluster is empty!");
44: }
45: }
46: } catch (ClassNotFoundException e) {
47: throw new IllegalStateException(e);
48: } catch (IllegalAccessException e) {
49: throw new IllegalStateException(e);
50: } catch (InstantiationException e) {
51: throw new IllegalStateException(e);
52: }
53: }
54: }
(1)、setup操作的目的是讀取初始劃分或者上次疊代的結果,建構Cluster資訊,同時做了Map<Cluster的ID,Cluster>映射,友善從ID找Cluster。
(2)、reduce操作非常直白,将從combiner傳來的<Cluster ID,ClusterObservations>進行彙總;
computeConvergence用來判斷目前Cluster是否收斂,即新的“重心”與老的“重心”距離是否滿足之前傳入的精度要求;
Last but not least,注意到有個cluster.computeParameters()操作,這個操作非常重要,它保證了本次疊代的結果不會影響到下次疊代,也就是保證了能夠“重新計算每個Cluster的重心”這一步驟。
前三個操作得到新的Cluster資訊;
後三個步驟清空S0、S1、S2資訊,保證下次疊代所需的Cluster資訊是“幹淨”的。
之後,reduce将(Cluster ID, Cluster) Pair寫入到HDFS中以”clusters-疊代次數“命名的檔案夾中。
6、KMeansClusterMapper
之前的MR操作用于建構Cluster資訊,KMeansClusterMapper則用構造好的Cluster資訊來聚類。
1: public class KMeansClusterMapper
2: extends Mapper<WritableComparable<?>,VectorWritable,IntWritable,WeightedVectorWritable> {
3:
4: private final Collection<Cluster> clusters = new ArrayList<Cluster>();
5: private KMeansClusterer clusterer;
6:
7: @Override
8: protected void map(WritableComparable<?> key, VectorWritable point, Context context)
9: throws IOException, InterruptedException {
10: clusterer.outputPointWithClusterInfo(point.get(), clusters, context);
11: }
12:
13: @Override
14: protected void setup(Context context) throws IOException, InterruptedException {
15: super.setup(context);
16: Configuration conf = context.getConfiguration();
17: try {
18: ClassLoader ccl = Thread.currentThread().getContextClassLoader();
19: DistanceMeasure measure = ccl.loadClass(conf.get(KMeansConfigKeys.DISTANCE_MEASURE_KEY))
20: .asSubclass(DistanceMeasure.class).newInstance();
21: measure.configure(conf);
22:
23: String clusterPath = conf.get(KMeansConfigKeys.CLUSTER_PATH_KEY);
24: if (clusterPath != null && clusterPath.length()> 0) {
25: KMeansUtil.configureWithClusterInfo(conf, new Path(clusterPath), clusters);
26: if (clusters.isEmpty()) {
27: throw new IllegalStateException("No clusters found. Check your -c path.");
28: }
29: }
30: this.clusterer = new KMeansClusterer(measure);
31: } catch (ClassNotFoundException e) {
32: throw new IllegalStateException(e);
33: } catch (IllegalAccessException e) {
34: throw new IllegalStateException(e);
35: } catch (InstantiationException e) {
36: throw new IllegalStateException(e);
37: }
38: }
39: }
(1)、setup依然是從指定目錄讀取并建構Cluster資訊;
(2)、map操作通過計算每個點到各Cluster“重心”的距離完成聚類操作,可以看到map操作結束,所有點就都被放在唯一一個與之距離最近的Cluster中了,是以之後并不需要reduce操作。
7、KMeansDriver
如果把前面的KMeansMapper、KMeansCombiner、KMeansReducer、KMeansClusterMapper看做是磚的話,KMeansDriver就是蓋房子的人,它用來組織整個kmeans算法流程(包括單機版和MR版)。示意圖如下:
圖4
8、Example
在源碼的/mahout-examples目錄下的package org.apache.mahout.clustering.syntheticcontrol.kmeans中有個Job.java檔案提供了對K-Means Clustering的一個版本。核心内容是兩個run函數:第一個是用随機選擇的方法确定初始劃分;第二個是用Canopy 方法确定初始劃分,需要注意的是,我們不需要Canopy 方法來做聚類操作,是以CanopyDriver.run的倒數第二個參數(runClustering)要設定為false。
example的使用方法如下:
● 啟動master和slave機器;
● 終端輸入:hadoop namenode –format
● 終端輸入:start-all.sh
● 檢視hadoop相關程序是否啟動,終端輸入:jps
● 在HDFS建立testdata目錄,終端輸入:hadoop dfs -mkdir testdata
● 将http://archive.ics.uci.edu/ml/中Iris資料集下載下傳,更改一下資料格式,将資料集中“,”替換為“ ”(空格),并上傳到HDFS的testdata檔案夾中,進入Iris目錄,終端輸入:hadoop dfs -put iris.txt testdata/
● 用Canopy 方法确定初始劃分,參數取值為:t1=3,t2=1.5,convergenceDelta=0.5,maxIter=10,進入mahout目錄,确認終端執行ls後可以看到mahout-examples-0.5-job.jar這個檔案,終端執行:hadoop jar mahout-examples-0.5-job.jar org.apache.mahout.clustering.syntheticcontrol.kmeans.Job -i testdata -o output-t1 3 -t2 1.5 -cd 0.5 -x 10
● 在http://localhost:50030/jobtracker.jsp 檢視作業執行情況:
圖5
從HDFS上可以看到以下幾個目錄:
圖6
job_201110082236_0001是由InputDriver對原始資料集的一個預處理,輸入目錄是:testdata,輸出目錄是:output/data
job_201110082236_0002是由CanopyDriver發起的對data的初始劃分,輸入目錄是:output/data,輸出目錄是:output/clusters-0
job_201110082236_0003是由KmeansDriver發起的建構Cluster的第一次疊代,輸入目錄是:output/clusters-0,輸出目錄是:output/clusters-1
job_201110082236_0004是由KmeansDriver發起的建構Cluster的第二次疊代,輸入目錄是:output/clusters-1,輸出目錄是:output/clusters-2
job_201110082236_0005是由KmeansDriver發起的Clustering,輸入目錄是:output/data,輸出目錄是:output/clusteredPoints
可見,要檢視最終結果需要兩個資訊:Cluster資訊和Clustering data後點的資訊,它們分别存儲在HDFS的最後一次疊代目錄output/clusters-2和聚類點目錄output/clusteredPoints。
● 檢視結果,将結果擷取到本地,終端輸入:bin/mahout clusterdump --seqFileDir /user/leozhang/output/clusters-2 --pointsDir /user/leozhang/output/clusteredPoints --output result.txt,終端輸入:ls可以看到result.txt這個檔案,檔案内容類似:
1: VL-1{n=68 c=[5.974, 2.771, 4.501, 1.472] r=[0.471, 0.291, 0.523, 0.303]}
2: Weight: Point:
3: 1.0: [7.000, 3.200, 4.700, 1.400]
4: 1.0: [6.400, 3.200, 4.500, 1.500]
5: 1.0: [6.900, 3.100, 4.900, 1.500]
6: 1.0: [5.500, 2.300, 4.000, 1.300]
7: 1.0: [6.500, 2.800, 4.600, 1.500]
8: 1.0: [5.700, 2.800, 4.500, 1.300]
9: 1.0: [6.300, 3.300, 4.700, 1.600]
10: 1.0: [4.900, 2.400, 3.300, 1.000]
11: 1.0: [6.600, 2.900, 4.600, 1.300]
12: 1.0: [5.200, 2.700, 3.900, 1.400]
13: 1.0: [5.000, 2.000, 3.500, 1.000]
14: 1.0: [5.900, 3.000, 4.200, 1.500]
15: 1.0: [6.000, 2.200, 4.000, 1.000]
16: 1.0: [6.100, 2.900, 4.700, 1.400]
17: 1.0: [5.600, 2.900, 3.600, 1.300]
18: 1.0: [6.700, 3.100, 4.400, 1.400]
19: 1.0: [5.600, 3.000, 4.500, 1.500]
20: 1.0: [5.800, 2.700, 4.100, 1.000]
21: 1.0: [6.200, 2.200, 4.500, 1.500]
22: 1.0: [5.600, 2.500, 3.900, 1.100]
23: 1.0: [5.900, 3.200, 4.800, 1.800]
24: 1.0: [6.100, 2.800, 4.000, 1.300]
25: 1.0: [6.300, 2.500, 4.900, 1.500]
26: 1.0: [6.100, 2.800, 4.700, 1.200]
27: 1.0: [6.400, 2.900, 4.300, 1.300]
28: 1.0: [6.600, 3.000, 4.400, 1.400]
29: 1.0: [6.800, 2.800, 4.800, 1.400]
30: 1.0: [6.700, 3.000, 5.000, 1.700]
31: 1.0: [6.000, 2.900, 4.500, 1.500]
32: 1.0: [5.700, 2.600, 3.500, 1.000]
33: 1.0: [5.500, 2.400, 3.800, 1.100]
34: 1.0: [5.500, 2.400, 3.700, 1.000]
35: 1.0: [5.800, 2.700, 3.900, 1.200]
36: 1.0: [6.000, 2.700, 5.100, 1.600]
37: 1.0: [5.400, 3.000, 4.500, 1.500]
38: 1.0: [6.000, 3.400, 4.500, 1.600]
39: 1.0: [6.700, 3.100, 4.700, 1.500]
40: 1.0: [6.300, 2.300, 4.400, 1.300]
41: 1.0: [5.600, 3.000, 4.100, 1.300]
42: 1.0: [5.500, 2.500, 4.000, 1.300]
43: 1.0: [5.500, 2.600, 4.400, 1.200]
44: 1.0: [6.100, 3.000, 4.600, 1.400]
45: 1.0: [5.800, 2.600, 4.000, 1.200]
46: 1.0: [5.000, 2.300, 3.300, 1.000]
47: 1.0: [5.600, 2.700, 4.200, 1.300]
48: 1.0: [5.700, 3.000, 4.200, 1.200]
49: 1.0: [5.700, 2.900, 4.200, 1.300]
50: 1.0: [6.200, 2.900, 4.300, 1.300]
51: 1.0: [5.100, 2.500, 3.000, 1.100]
52: 1.0: [5.700, 2.800, 4.100, 1.300]
53: 1.0: [5.800, 2.700, 5.100, 1.900]
54: 1.0: [4.900, 2.500, 4.500, 1.700]
55: 1.0: [5.700, 2.500, 5.000, 2.000]
56: 1.0: [5.800, 2.800, 5.100, 2.400]
57: 1.0: [6.000, 2.200, 5.000, 1.500]
58: 1.0: [5.600, 2.800, 4.900, 2.000]
59: 1.0: [6.300, 2.700, 4.900, 1.800]
60: 1.0: [6.200, 2.800, 4.800, 1.800]
61: 1.0: [6.100, 3.000, 4.900, 1.800]
62: 1.0: [6.300, 2.800, 5.100, 1.500]
63: 1.0: [6.100, 2.600, 5.600, 1.400]
64: 1.0: [6.000, 3.000, 4.800, 1.800]
65: 1.0: [5.800, 2.700, 5.100, 1.900]
66: 1.0: [6.300, 2.500, 5.000, 1.900]
67: 1.0: [5.900, 3.000, 5.100, 1.800]
68: VL-0{n=51 c=[5.008, 3.400, 1.494, 0.261] r=[0.346, 0.395, 0.273, 0.159]}
69: Weight: Point:
70: 1.0: [5.100, 3.500, 1.400, 0.200]
71: 1.0: [4.900, 3.000, 1.400, 0.200]
72: 1.0: [4.700, 3.200, 1.300, 0.200]
73: 1.0: [4.600, 3.100, 1.500, 0.200]
74: 1.0: [5.000, 3.600, 1.400, 0.200]
75: 1.0: [5.400, 3.900, 1.700, 0.400]
76: 1.0: [4.600, 3.400, 1.400, 0.300]
77: 1.0: [5.000, 3.400, 1.500, 0.200]
78: 1.0: [4.400, 2.900, 1.400, 0.200]
79: 1.0: [4.900, 3.100, 1.500, 0.100]
80: 1.0: [5.400, 3.700, 1.500, 0.200]
81: 1.0: [4.800, 3.400, 1.600, 0.200]
82: 1.0: [4.800, 3.000, 1.400, 0.100]
83: 1.0: [4.300, 3.000, 1.100, 0.100]
84: 1.0: [5.800, 4.000, 1.200, 0.200]
85: 1.0: [5.700, 4.400, 1.500, 0.400]
86: 1.0: [5.400, 3.900, 1.300, 0.400]
87: 1.0: [5.100, 3.500, 1.400, 0.300]
88: 1.0: [5.700, 3.800, 1.700, 0.300]
89: 1.0: [5.100, 3.800, 1.500, 0.300]
90: 1.0: [5.400, 3.400, 1.700, 0.200]
91: 1.0: [5.100, 3.700, 1.500, 0.400]
92: 1.0: [4.600, 3.600, 1.000, 0.200]
93: 1.0: [5.100, 3.300, 1.700, 0.500]
94: 1.0: [4.800, 3.400, 1.900, 0.200]
95: 1.0: [5.000, 3.000, 1.600, 0.200]
96: 1.0: [5.000, 3.400, 1.600, 0.400]
97: 1.0: [5.200, 3.500, 1.500, 0.200]
98: 1.0: [5.200, 3.400, 1.400, 0.200]
99: 1.0: [4.700, 3.200, 1.600, 0.200]
100: 1.0: [4.800, 3.100, 1.600, 0.200]
101: 1.0: [5.400, 3.400, 1.500, 0.400]
102: 1.0: [5.200, 4.100, 1.500, 0.100]
103: 1.0: [5.500, 4.200, 1.400, 0.200]
104: 1.0: [4.900, 3.100, 1.500, 0.100]
105: 1.0: [5.000, 3.200, 1.200, 0.200]
106: 1.0: [5.500, 3.500, 1.300, 0.200]
107: 1.0: [4.900, 3.100, 1.500, 0.100]
108: 1.0: [4.400, 3.000, 1.300, 0.200]
109: 1.0: [5.100, 3.400, 1.500, 0.200]
110: 1.0: [5.000, 3.500, 1.300, 0.300]
111: 1.0: [4.500, 2.300, 1.300, 0.300]
112: 1.0: [4.400, 3.200, 1.300, 0.200]
113: 1.0: [5.000, 3.500, 1.600, 0.600]
114: 1.0: [5.100, 3.800, 1.900, 0.400]
115: 1.0: [4.800, 3.000, 1.400, 0.300]
116: 1.0: [5.100, 3.800, 1.600, 0.200]
117: 1.0: [4.600, 3.200, 1.400, 0.200]
118: 1.0: [5.300, 3.700, 1.500, 0.200]
119: 1.0: [5.000, 3.300, 1.400, 0.200]
120: VL-2{n=31 c=[6.932, 3.106, 5.855, 2.142] r=[0.491, 0.293, 0.449, 0.235]}
121: Weight: Point:
122: 1.0: [6.300, 3.300, 6.000, 2.500]
123: 1.0: [7.100, 3.000, 5.900, 2.100]
124: 1.0: [6.300, 2.900, 5.600, 1.800]
125: 1.0: [6.500, 3.000, 5.800, 2.200]
126: 1.0: [7.600, 3.000, 6.600, 2.100]
127: 1.0: [7.300, 2.900, 6.300, 1.800]
128: 1.0: [6.700, 2.500, 5.800, 1.800]
129: 1.0: [7.200, 3.600, 6.100, 2.500]
130: 1.0: [6.500, 3.200, 5.100, 2.000]
131: 1.0: [6.400, 2.700, 5.300, 1.900]
132: 1.0: [6.800, 3.000, 5.500, 2.100]
133: 1.0: [6.400, 3.200, 5.300, 2.300]
134: 1.0: [6.500, 3.000, 5.500, 1.800]
135: 1.0: [7.700, 3.800, 6.700, 2.200]
136: 1.0: [7.700, 2.600, 6.900, 2.300]
137: 1.0: [6.900, 3.200, 5.700, 2.300]
138: 1.0: [7.700, 2.800, 6.700, 2.000]
139: 1.0: [6.700, 3.300, 5.700, 2.100]
140: 1.0: [7.200, 3.200, 6.000, 1.800]
141: 1.0: [6.400, 2.800, 5.600, 2.100]
142: 1.0: [7.200, 3.000, 5.800, 1.600]
143: 1.0: [7.400, 2.800, 6.100, 1.900]
144: 1.0: [7.900, 3.800, 6.400, 2.000]
145: 1.0: [6.400, 2.800, 5.600, 2.200]
146: 1.0: [7.700, 3.000, 6.100, 2.300]
147: 1.0: [6.300, 3.400, 5.600, 2.400]
148: 1.0: [6.400, 3.100, 5.500, 1.800]
149: 1.0: [6.900, 3.100, 5.400, 2.100]
150: 1.0: [6.700, 3.100, 5.600, 2.400]
151: 1.0: [6.900, 3.100, 5.100, 2.300]
152: 1.0: [6.800, 3.200, 5.900, 2.300]
153: 1.0: [6.700, 3.300, 5.700, 2.500]
154: 1.0: [6.700, 3.000, 5.200, 2.300]
155: 1.0: [6.500, 3.000, 5.200, 2.000]
156: 1.0: [6.200, 3.400, 5.400, 2.300]
● 為了能比較直覺的檢視資料,可以利用R(可以使用強大的RStudio,需要安裝rgl),我将資料整理到以下連結:http://files.cnblogs.com/vivounicorn/data%26result.rar ,分組顯示資料前三維,不同Cluster用不同顔色表示。效果類似于圖3,代碼類似于:
1: library(rgl)
2: ttt = textConnection("
3: x y z t group
4: 5.100 3.500 1.400 0.200 Iris-setosa
5: .........
6: 6.300 3.300 6.000 2.500 Iris-virginica
7: .........
8: 7.000 3.200 4.700 1.400 Iris-versicolor
9: .........
10: ")
11:
12: colors =c("red","green","blue")
13: pca <- read.table(ttt,header=TRUE)
14: p3d <- plot3d(pca$x, pca$y, pca$z, xlab="feature 1", ylab="feature 2",
15: zlab="feature 3",
16: col=as.integer(pca$group) ,
17: box=FALSE, size=5)
執行pca <- read.table(ttt,header=TRUE)可能會報錯:Error in read.table(ttt, header = TRUE) : more columns than column names,沒關系,再重新執行一下這句就行了。
六、總結
K-Means Clustering是基于距離的排他的劃分方法,初始劃分對它很重要,mahout裡實作了兩種方法:随機方法和Canopy方法,前者比較簡單,但孤立點會對其Clustering效果造成較大影響,後者對孤立點的處理能力很強但是需要确定的參數多了一個且如何合理取值需要探讨。