1. 劃分聚類(lèi)
其實(shí)從某種角度講，劃分聚類(lèi)是完全不用贅述的一種聚類(lèi)方法，可能也是最常見(jiàn)的聚類(lèi)算法了。著名的k-means算法就是個(gè)中典型。這次的內(nèi)容主要是通過(guò)k-means聚類(lèi)算法來(lái)總體介紹一下劃分聚類(lèi)。
簡(jiǎn)單來(lái)講，k均值聚類(lèi)究竟做了什么事，我們可以這樣來(lái)看，有N個(gè)數(shù)據(jù)點(diǎn)的集合D={x1,x2,…,xn}，每個(gè)xi代表一個(gè)特征向量，目標(biāo)是將這N個(gè)點(diǎn)根據(jù)某種相似準(zhǔn)則將其劃分到K個(gè)分類(lèi)中。而k均值所表達(dá)的重要在于相似準(zhǔn)則的選取，即不斷的使用類(lèi)簇的均值來(lái)完成這樣的劃分。當(dāng)然也有書(shū)把這種相似準(zhǔn)則稱之為評(píng)分函數(shù)。基于劃分的聚類(lèi)算法對(duì)于homogeneity的實(shí)現(xiàn)是通過(guò)選取適當(dāng)?shù)脑u(píng)分函數(shù)并使每一個(gè)數(shù)據(jù)點(diǎn)到它所屬的聚類(lèi)中心的距離最小化。而關(guān)鍵就是如何定義這種距離，和所謂的聚類(lèi)中心。舉個(gè)例子來(lái)講，如果定義聚類(lèi)間距離為歐式距離，那么可以使用協(xié)方差的概念來(lái)定義通用的評(píng)分函數(shù)。劃分聚類(lèi)的思想是最直觀和易懂的分類(lèi)思想，因此我也不在這里長(zhǎng)篇介紹，還是以算法的實(shí)現(xiàn)和代碼來(lái)直觀表現(xiàn)劃分聚類(lèi)的性能。
2. 算法實(shí)現(xiàn)
我們以k-means算法為例來(lái)實(shí)現(xiàn)劃分聚類(lèi)。該算法的復(fù)雜度為O(KnI)，其中I是迭代次數(shù)。這種算法的一個(gè)變體是依次分析每個(gè)數(shù)據(jù)點(diǎn)，而且一旦有數(shù)據(jù)點(diǎn)被重新分配就更新聚類(lèi)中心，反復(fù)的在數(shù)據(jù)點(diǎn)中循環(huán)直到解不再變化。k-means算法的搜索過(guò)程局限于全部可能的劃分空間的一個(gè)很小的部分。因此有可能因?yàn)樗惴ㄊ諗康皆u(píng)分函數(shù)的局部而非全局最小而錯(cuò)過(guò)更好的解。當(dāng)然緩解方法可以通過(guò)選取隨機(jī)起始點(diǎn)來(lái)改進(jìn)搜索（我們例子中的KMPP算法），或者利用模擬退火等策略來(lái)改善搜索性能。因此，從這個(gè)角度來(lái)理解，聚類(lèi)分析實(shí)質(zhì)上是一個(gè)在龐大的解空間中優(yōu)化特定評(píng)分函數(shù)的搜索問(wèn)題。
不多說(shuō)了，直接上代碼吧！！！
k-means算法：
for k = 1, … , K 令 r(k) 為從D中隨機(jī)選取的一個(gè)點(diǎn)；
while 在聚類(lèi)Ck中有變化發(fā)生 do
形成聚類(lèi)：
For k = 1, … , K do
Ck = { x ∈ D | d(rk,x) <= d(rj,x) 對(duì)所有j=1, … , K, j != k}；
End;
計(jì)算新聚類(lèi)中心：
For k = 1, … , K do
Rk = Ck 內(nèi)點(diǎn)的均值向量
End;
End;
具體實(shí)現(xiàn)部分因?yàn)橛?/span>Apache Commons Math的現(xiàn)成代碼，秉著Eric Raymond的TAOUP中的極大利用工具原則，我沒(méi)有寫(xiě)k-means的實(shí)現(xiàn)，而是直接利用Apache Commons Math中的k-means plus plus代碼來(lái)作為例子。
具體如何測(cè)試這一算法，給出了測(cè)試代碼如下：
1
private 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. 小結(jié)
劃分聚類(lèi)是聚類(lèi)分析中最常用的一種聚類(lèi)算法了，對(duì)于其研究的論文也是多如牛毛。感興趣的朋友們完全可以通過(guò)閱讀各種相關(guān)論文來(lái)感受這一算法的美妙。當(dāng)然還要再次感謝Apache Commons Math對(duì)于諸多常用數(shù)學(xué)計(jì)算的實(shí)現(xiàn)。對(duì)于聚類(lèi)分析的總結(jié)學(xué)習(xí)暫時(shí)到此告一段落，最近要忙著寫(xiě)論文，等過(guò)段時(shí)間有空可以考慮繼續(xù)聚類(lèi)算法的研究學(xué)習(xí)。
4. 參考文獻(xiàn)及推薦閱讀
[1]PatternRecognitionThird Edition, Sergios Theodoridis, Konstantinos Koutroumbas
[2]模式識(shí)別第三版, Sergios Theodoridis, Konstantinos Koutroumbas著, 李晶皎, 王愛(ài)俠, 張廣源等譯
[3]數(shù)據(jù)挖掘原理, David Hand and et al, 張銀奎等譯
[4]http://commons.apache.org/math/