聚類(lèi)算法學(xué)習(xí)筆記(四)——層次聚類(lèi)
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)绾慰刂颇兀砍S玫淖龇ň褪菫樗惴ㄏ拗埔粋€(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ǔ)句如下:

2

3

4

MATLAB還有一個(gè)簡(jiǎn)化的層次聚類(lèi)版本,一句話搞定

Java實(shí)現(xiàn)的版本:

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

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)容的代碼地址:
posted on 2010-03-19 20:08 changedi 閱讀(13756) 評(píng)論(23) 編輯 收藏 所屬分類(lèi): 聚類(lèi)分析