1. 層次聚類(lèi)
層次聚類(lèi)算法與之前所講的順序聚類(lèi)有很大不同，它不再產(chǎn)生單一聚類(lèi)，而是產(chǎn)生一個(gè)聚類(lèi)層次。說(shuō)白了就是一棵層次樹(shù)。介紹層次聚類(lèi)之前，要先介紹一個(gè)概念——嵌套聚類(lèi)。講的簡(jiǎn)單點(diǎn)，聚類(lèi)的嵌套與程序的嵌套一樣，一個(gè)聚類(lèi)中R1包含了另一個(gè)R2，那這就是R2嵌套在R1中，或者說(shuō)是R1嵌套了R2。具體說(shuō)怎么算嵌套呢？聚類(lèi)R1={{x1,x2},{x3},{x4,x5}嵌套在聚類(lèi)R2={{x1,x2,x3},{x4,x5}}中，但并不嵌套在聚類(lèi)R3={{x1,x4},{x3},{x2,x5}}中。
層次聚類(lèi)算法產(chǎn)生一個(gè)嵌套聚類(lèi)的層次，算法最多包含N步，在第t步，執(zhí)行的操作就是在前t-1步的聚類(lèi)基礎(chǔ)上生成新聚類(lèi)。主要有合并和分裂兩種實(shí)現(xiàn)。我這里只講合并，因?yàn)榍耙浑A段正好課題用到，另外就是合并更容易理解和實(shí)現(xiàn)。當(dāng)然分裂其實(shí)就是合并的相反過(guò)程。
令g(Ci,Cj)為所有可能的X聚類(lèi)對(duì)的函數(shù)，此函數(shù)用于測(cè)量?jī)蓚€(gè)聚類(lèi)之間的近鄰性，用t表示當(dāng)前聚類(lèi)的層次級(jí)別。通用合并算法的偽碼描述如下：
1. 初始化：
a) 選擇Â0={{x1},…,{xN}}
b) 令t=0
2. 重復(fù)執(zhí)行以下步驟：
a) t=t+1
b) 在Ât-1中選擇一組(Ci,Cj)，滿(mǎn)足
c) 定義Cq=CiÈCj，并且產(chǎn)生新聚類(lèi)Ât=(Ât-1-{Ci,Cj})È{Cq}
直到所有向量全被加入到單一聚類(lèi)中。
這一方法在t層時(shí)將兩個(gè)向量合并，那么這兩個(gè)向量在以后的聚類(lèi)過(guò)程中的后繼聚類(lèi)都是相同的，也就是說(shuō)一旦它們走到一起，那么以后就不會(huì)再分離……（很專(zhuān)一哦O(∩_∩)O~）。這也就引出了這個(gè)算法的缺點(diǎn)，當(dāng)在算法開(kāi)始階段，若出現(xiàn)聚類(lèi)錯(cuò)誤，那么這種錯(cuò)誤將一直會(huì)被延續(xù)，無(wú)法修改。在層次t上，有N-t個(gè)聚類(lèi)，為了確定t+1層上要合并的聚類(lèi)對(duì)，必須考慮(N-t)(N-t-1)/2個(gè)聚類(lèi)對(duì)。這樣，聚類(lèi)過(guò)程總共要考慮的聚類(lèi)對(duì)數(shù)量就是(N-1)N(N+1)/6，也就是說(shuō)整個(gè)算法的時(shí)間復(fù)雜度是O(N3)。
舉例來(lái)說(shuō)，如果令X={x1, x2, x3, x4, x5}，其中x1=[1, 1]T, x2=[2, 1]T, x3=[5, 4]T, x4=[6, 5]T, x5=[6.5, 6]T。那么合并算法執(zhí)行的過(guò)程可以用下面的圖來(lái)表示。
P(X)是不相似矩陣
該算法從核心過(guò)程上來(lái)講，就是先計(jì)算出數(shù)據(jù)集中向量之間的距離，記為距離矩陣（也叫不相似矩陣）。接著通過(guò)不斷的對(duì)矩陣更新，完成聚類(lèi)。矩陣更新算法的偽碼描述如下：
1. 初始化：
a) Â0={{x1},…,{xN}}
b) P0=P(X) (距離矩陣)
c) t=0
2. 重復(fù)執(zhí)行以下步驟：
a) t=t+1
b) 合并Ci和Cj為Cq，這兩個(gè)聚類(lèi)滿(mǎn)足d(Ci,Cj)=minr,s=1,…,N,r≠sd(Cr,Cs)
c) 刪除第i和j行，第i和j列，同時(shí)插入新的行和列，新的行列為新合并的類(lèi)Cq與所有其他聚類(lèi)之間的距離值
直到將所有向量合并到一個(gè)聚類(lèi)中
大家可以看到，層次聚類(lèi)算法的輸出結(jié)果總是一個(gè)聚類(lèi)，這往往不是我們想要的，我們總希望算法在得到我們期望的結(jié)果后就停止。那么我們?nèi)绾慰刂颇兀砍Ｓ玫淖龇ň褪菫樗惴ㄏ拗埔粋€(gè)閾值，矩陣更新過(guò)程中，總是將兩個(gè)距離最近的聚類(lèi)合并，那么我們只要加入一個(gè)閾值判斷，當(dāng)這個(gè)距離大于閾值時(shí)，就說(shuō)明不需要再合并了，此時(shí)算法結(jié)束。這樣的閾值引入可以很好的控制算法結(jié)束時(shí)間，將層次截?cái)嘣谀骋粚由稀?/span>
2. 算法實(shí)現(xiàn)
MATLAB實(shí)現(xiàn)了層次聚類(lèi)算法，基本語(yǔ)句如下：
1
X = [1 2;2.5 4.5;2 2;4 1.5;4 2.5] ;
2Y = pdist(X,'euclid');
3Z = linkage(Y,'single');
4T = cluster(Z,'cutoff',cutoff);
MATLAB還有一個(gè)簡(jiǎn)化的層次聚類(lèi)版本，一句話搞定
1T = clusterdata(X,cutoff)
Java實(shí)現(xiàn)的版本：
1package util;
2
3import java.util.*;
4
5
public class Clusterer 
{
6
private List[] clusterList;
7 DisjointSets ds;
8 private static final int MAX = Integer.MAX_VALUE;
9 private int n;
10 private int cc;
11
12 // private double ori[] = {1,2,5,7,9,10};
13
14
public Clusterer(int num) {
15 ds = new DisjointSets(num);
16 n = num;
17 cc = n;
18 clusterList = new ArrayList[num];
19 for (int i = 0; i < n; i++)
20 clusterList[i] = new ArrayList();
21
}
22
23 public List[] getClusterList() {
24 return clusterList;
25 }
26
27 public void setClusterList(List[] clusterList) {
28 this.clusterList = clusterList;
29 }
30
31 public void output() {
32 int ind = 1;
33 for (int i = 0; i < n; i++) {
34 clusterList[ds.find(i)].add(i);
35 }
36 for (int i = 0; i < n; i++) {
37 if (clusterList[i].size() != 0) {
38 System.out.print("cluster " + ind + " :");
39 for (int j = 0; j < clusterList[i].size(); j++) {
40 System.out.print(clusterList[i].get(j) + " ");
41 }
42 System.out.println();
43 ind++;
44 }
45 }
46 }
47
48 /** *//**
49 * this method provides a hierachical way for clustering data.
50 *
51 * @param r
52 * denote the distance matrix
53 * @param n
54 * denote the sample num(distance matrix's row number)
55 * @param dis
56 * denote the threshold to stop clustering
57 */
58 public void cluster(double[][] r, int n, double dis) {
59 int mx = 0, my = 0;
60 double vmin = MAX;
61 for (int i = 0; i < n; i++) { // 尋找最小距離所在的行列
62 for (int j = 0; j < n; j++) {
63 if (j > i) {
64 if (vmin > r[i][j]) {
65 vmin = r[i][j];
66 mx = i;
67 my = j;
68 }
69 }
70 }
71 }
72 if (vmin > dis) {
73 return;
74 }
75 ds.union(ds.find(mx), ds.find(my)); // 將最小距離所在的行列實(shí)例聚類(lèi)合并
76 double o1[] = r[mx];
77 double o2[] = r[my];
78 double v[] = new double[n];
79 double vv[] = new double[n];
80 for (int i = 0; i < n; i++) {
81 double tm = Math.min(o1[i], o2[i]);
82 if (tm != 0)
83 v[i] = tm;
84 else
85 v[i] = MAX;
86 vv[i] = MAX;
87 }
88 r[mx] = v;
89 r[my] = vv;
90 for (int i = 0; i < n; i++) { // 更新距離矩陣
91 r[i][mx] = v[i];
92 r[i][my] = vv[i];
93 }
94 cluster(r, n, dis); // 繼續(xù)聚類(lèi)，遞歸直至所有簇之間距離小于dis值
95 }
96
97 /** *//**
98 *
99 * @param r
100 * @param cnum
101 * denote the number of final clusters
102 */
103 public void cluster(double[][] r, int cnum) {
104 /**//*if(cc< cnum)
105 System.err.println("聚類(lèi)數(shù)大于實(shí)例數(shù)");*/
106 while (cc > cnum) {// 繼續(xù)聚類(lèi)，循環(huán)直至聚類(lèi)個(gè)數(shù)等于cnum
107 int mx = 0, my = 0;
108 double vmin = MAX;
109 for (int i = 0; i < n; i++) { // 尋找最小距離所在的行列
110 for (int j = 0; j < n; j++) {
111 if (j > i) {
112 if (vmin > r[i][j]) {
113 vmin = r[i][j];
114 mx = i;
115 my = j;
116 }
117 }
118 }
119 }
120 ds.union(ds.find(mx), ds.find(my)); // 將最小距離所在的行列實(shí)例聚類(lèi)合并
121 double o1[] = r[mx];
122 double o2[] = r[my];
123 double v[] = new double[n];
124 double vv[] = new double[n];
125 for (int i = 0; i < n; i++) {
126 double tm = Math.min(o1[i], o2[i]);
127 if (tm != 0)
128 v[i] = tm;
129 else
130 v[i] = MAX;
131 vv[i] = MAX;
132 }
133 r[mx] = v;
134 r[my] = vv;
135 for (int i = 0; i < n; i++) { // 更新距離矩陣
136 r[i][mx] = v[i];
137 r[i][my] = vv[i];
138 }
139 cc--;
140 }
141 }
142
143 public static void main(String args[]) {
144 double[][] r = { { 0, 1, 4, 6, 8, 9 }, { 1, 0, 3, 5, 7, 8 },
145 { 4, 3, 0, 2, 4, 5 }, { 6, 5, 2, 0, 2, 3 },
146 { 8, 7, 4, 2, 0, 1 }, { 9, 8, 5, 3, 1, 0 } };
147 Clusterer cl = new Clusterer(6);
148 //cl.cluster(r, 6, 1);
149 cl.cluster(r, 3);
150 cl.output();
151 }
152
153
}
154
3. 小結(jié)
層次聚類(lèi)算法是非常常用的聚類(lèi)算法，同時(shí)也是被廣泛研究的聚類(lèi)算法。層次聚類(lèi)本身分為合并和分裂兩種實(shí)現(xiàn)，在合并算法中，又分基于矩陣?yán)碚摰暮喜⒑突趫D論的合并。本文只是初學(xué)聚類(lèi)的一點(diǎn)體會(huì)，因此只實(shí)現(xiàn)了基于矩陣?yán)碚摰乃惴ǎ瑫r(shí)，用于大數(shù)據(jù)集合的層次算法如CURE，ROCK和Chameleon算法都沒(méi)有涉及，這些算法如果以后有時(shí)間，會(huì)整理發(fā)布。還有截?cái)帱c(diǎn)的選擇，最佳聚類(lèi)數(shù)的確定都是可以研究的問(wèn)題。
4. 參考文獻(xiàn)及推薦閱讀
[1]Pattern Recognition Third Edition, Sergios Theodoridis, Konstantinos Koutroumbas
[2]模式識(shí)別第三版, Sergios Theodoridis, Konstantinos Koutroumbas著, 李晶皎, 王愛(ài)俠, 張廣源等譯
PS，第四第五節(jié)的內(nèi)容的代碼地址：