聚類算法學習筆記（五）——劃分聚類

1.     劃分聚類

其實從某種角度講，劃分聚類是完全不用贅述的一種聚類方法，可能也是最常見的聚類算法了。著名的k-means算法就是個中典型。這次的內容主要是通過k-means聚類算法來總體介紹一下劃分聚類。

簡單來講，k均值聚類究竟做了什么事，我們可以這樣來看，有N個數據點的集合D={x1,x2,…,xn}，每個xi代表一個特征向量，目標是將這N個點根據某種相似準則將其劃分到K個分類中。而k均值所表達的重要在于相似準則的選取，即不斷的使用類簇的均值來完成這樣的劃分。當然也有書把這種相似準則稱之為評分函數。基于劃分的聚類算法對于homogeneity的實現是通過選取適當的評分函數并使每一個數據點到它所屬的聚類中心的距離最小化。而關鍵就是如何定義這種距離，和所謂的聚類中心。舉個例子來講，如果定義聚類間距離為歐式距離，那么可以使用協方差的概念來定義通用的評分函數。劃分聚類的思想是最直觀和易懂的分類思想，因此我也不在這里長篇介紹，還是以算法的實現和代碼來直觀表現劃分聚類的性能。

2. 算法實現

       我們以k-means算法為例來實現劃分聚類。該算法的復雜度為O(KnI)，其中I是迭代次數。這種算法的一個變體是依次分析每個數據點，而且一旦有數據點被重新分配就更新聚類中心，反復的在數據點中循環直到解不再變化。k-means算法的搜索過程局限于全部可能的劃分空間的一個很小的部分。因此有可能因為算法收斂到評分函數的局部而非全局最小而錯過更好的解。當然緩解方法可以通過選取隨機起始點來改進搜索（我們例子中的KMPP算法），或者利用模擬退火等策略來改善搜索性能。因此，從這個角度來理解，聚類分析實質上是一個在龐大的解空間中優化特定評分函數的搜索問題。

不多說了，直接上代碼吧！！！

k-means算法：

for k = 1, … , K 令 r(k) 為從D中隨機選取的一個點；

while 在聚類Ck中有變化發生 do

       形成聚類：

       For k = 1, … , K do

              Ck = { x ∈ D | d(rk,x) <= d(rj,x) 對所有j=1, … , K, j != k}；

       End;

       計算新聚類中心：

       For k = 1, … , K do

              Rk = Ck 內點的均值向量

       End;

End;

具體實現部分因為有Apache Commons Math的現成代碼，秉著Eric Raymond的TAOUP中的極大利用工具原則，我沒有寫k-means的實現，而是直接利用Apache Commons Math中的k-means plus plus代碼來作為例子。

具體如何測試這一算法，給出了測試代碼如下：

 1private static void testKMeansPP(){
 2
 3        //ori is sample as n instances with m features, here n=8,m=2
 4
 5       int ori[][] = {{2,5},{6,4},{5,3},{2,2},{1,4},{5,2},{3,3},{2,3}};
 6
 7       int n = 8;
 8
 9       Collection<EuclideanIntegerPoint> col = new ArrayList<EuclideanIntegerPoint>();
10
11       for(int i=0;i<n;i++){
12
13           EuclideanIntegerPoint ec = new EuclideanIntegerPoint(ori[i]);
14
15           col.add(ec);
16
17       }
18
19       KMeansPlusPlusClusterer<EuclideanIntegerPoint> km = new KMeansPlusPlusClusterer<EuclideanIntegerPoint>(new Random(n));
20
21       List<Cluster<EuclideanIntegerPoint>> list = new ArrayList<Cluster<EuclideanIntegerPoint>>();
22
23       list = km.cluster(col, 3, 100);
24
25       output(list);
26
27    }
28
29private static void output(List<Cluster<EuclideanIntegerPoint>> list){
30
31       int ind = 1;
32
33       Iterator<Cluster<EuclideanIntegerPoint>> it = list.iterator();
34
35       while(it.hasNext()){
36
37           Cluster<EuclideanIntegerPoint> cl = it.next();
38
39           System.out.print("Cluster"+(ind++)+" :");
40
41           List<EuclideanIntegerPoint> li = cl.getPoints();
42
43           Iterator<EuclideanIntegerPoint> ii = li.iterator();
44
45           while(ii.hasNext()){
46
47              EuclideanIntegerPoint eip = ii.next();
48
49              System.out.print(eip+" ");
50
51           }
52
53           System.out.println();
54
55       }
56
57    }
58
59    /** *//**
60
61    *@param args
62
63    */
64
65    public static void main(String[] args) {
66
67       //testHierachicalCluster();
68
69       testKMeansPP();
70
71       //testBSAS();
72
73       //testMBSAS();
74
75    }
76
77

3. 小結

       劃分聚類是聚類分析中最常用的一種聚類算法了，對于其研究的論文也是多如牛毛。感興趣的朋友們完全可以通過閱讀各種相關論文來感受這一算法的美妙。當然還要再次感謝Apache Commons Math對于諸多常用數學計算的實現。對于聚類分析的總結學習暫時到此告一段落，最近要忙著寫論文，等過段時間有空可以考慮繼續聚類算法的研究學習。

4. 參考文獻及推薦閱讀

[1]PatternRecognitionThird Edition, Sergios Theodoridis, Konstantinos Koutroumbas

[2]模式識別第三版, Sergios Theodoridis, Konstantinos Koutroumbas著, 李晶皎, 王愛俠, 張廣源等譯

[3]數據挖掘原理, David Hand and et al, 張銀奎等譯

[4]http://commons.apache.org/math/

posted on 2010-05-11 21:07 changedi 閱讀(7797) 評論(5)  編輯  收藏 所屬分類: 聚類分析