每篇一句：
You must strive to find your own voice. Because the longer you wait to begin, the less likely you are to find it at all.
--你必須努力去尋找自己的聲音妹蔽，因?yàn)槟阍竭t開(kāi)始尋找怎顾，找到的可能性越小齿税。
層次聚類算法：
層次聚類算法 （Hierarchical Clustering Method）又稱為系統(tǒng)聚類法、分級(jí)聚類法铲咨。
層次聚類算法又分為兩種形式：
-
凝聚層次聚類：
首先將每個(gè)對(duì)象作為一個(gè)簇嘲更，然后合并這些原子簇為越來(lái)越大的簇闸溃，直到某個(gè)終結(jié)條件被滿足勋陪。
-
分裂層次聚類：
首先將所有對(duì)象置于一個(gè)簇中贪磺，然后逐漸細(xì)分為越來(lái)越小的簇，直到達(dá)到了某個(gè)終結(jié)條件诅愚。
凝聚層次聚類：
本文介紹的為第一種形式寒锚，即凝聚層次聚類：
思路：每個(gè)樣本先自成一類，然后按距離準(zhǔn)則逐步合并违孝，減少類數(shù)刹前。
-
算法描述：
1）N個(gè)初始模式樣本自成一類，即建立N類：
G1(0)雌桑，G2(0)喇喉，...，Gn(0) (G_Group)
計(jì)算 各類之間（即各樣本間）的距離（相似性校坑、相關(guān)性）拣技，得一NN維距離矩陣∪鲎伲“0*”表示初始狀態(tài)过咬。
2）假設(shè)已求得距離矩陣D(n)（n為逐次聚類合并的次數(shù)），找出D(n)中的最小元素制妄，將其對(duì)應(yīng)的兩類合并為一類掸绞。由此建立新的分類：
G1(n+1)，G2(n+1)耕捞，...
3）計(jì)算合并后新類別之間的距離衔掸，得D(n+1)。
4）跳至第二步俺抽，重復(fù)計(jì)算及合并敞映。
- 結(jié)束條件：
取距離閾值T，當(dāng)D(n)的最小分量超過(guò)給定值T時(shí)磷斧，算法停止振愿。所得即為聚類結(jié)果。
或不設(shè)閾值T弛饭，一直將全部樣本聚成一類為止冕末，輸出聚類的分級(jí)樹(shù)。
分類結(jié)果 - 結(jié)束條件：
問(wèn)題討論：——類間距離計(jì)算準(zhǔn)則
在算法描述第一步中提到要計(jì)算每個(gè)聚類之間的距離侣颂，在層次聚類算法中档桃，計(jì)算聚類距離間距的計(jì)算方法主要有以下五種：
-
1）最短距離法： （常用）
如H、K是兩個(gè)聚類憔晒，則兩類間的最短距離定義為：
Dhk = min{D(Xh藻肄，Xk)} Xh∈H蔑舞，Xk∈K
Dhk: H類中所有樣本與K類中所有樣本之間的最小距離。
D(Xh嘹屯，Xk)： H類中的某個(gè)樣本Xh和K類中的某個(gè)樣本Xk之間的歐式距離攻询。
類間距離如果K類由I和J兩類合并而成，則：
Dhi = min{D(Xh, Xi)} Xh∈H,Xi∈I
Dhj = min{D(Xh, Xj)} Xh∈H,Xj∈J得到遞推公式：
Dhk = min{Dhi, Dhj}
類間距離遞推
-
2) 最長(zhǎng)距離法：
最長(zhǎng)距離法
-
3）中間距離法：
介于最長(zhǎng)與最短的距離之間抚垄。如果 K 類由 I 類和 J 類合并而成蜕窿，則 H 和 K 類之間的距離為：
中間距離法
-
4）重心法：
將每類中包含的樣本數(shù)考慮進(jìn)去。若 I 類中有 n I 個(gè)樣本呆馁， J 類中有 n J 個(gè)樣本桐经，則類與類之間的距離遞推式為：
重心法
-
5）類平均距離法：
類平均距離法
定義類間距離的方法不同，分類結(jié)果會(huì)不太一致浙滤。實(shí)際問(wèn)題中常用幾種不同的方法阴挣，比較分類結(jié)果，從而選擇一個(gè)比較切合實(shí)際的分類纺腊。
Python 實(shí)現(xiàn)：
- 解釋說(shuō)明見(jiàn)代碼中注釋
# coding=utf-8
from max_min_cluster import get_distance
def hierarchical_cluster(data, t):
# N個(gè)模式樣本自成一類
result = [[aData] for aData in data]
step2(result, t)
return result
def step2(result, t):
# 記錄類間最小距離
min_dis = min_distance(result[0], result[1]) # 初始為1,2類之間的距離
# 即將合并的類
index1 = 0
index2 = 1
# 遍歷畔咧，尋找最小類間距離
for i in range(len(result)):
for j in range(i+1, len(result)):
dis_temp = min_distance(result[i], result[j])
if dis_temp < min_dis:
min_dis = dis_temp
# 記錄即將合并的聚類位置下標(biāo)
index1 = i
index2 = j
# 閾值判斷
if min_dis <= t:
# 合并聚類index1, index2
result[index1].extend(result[index2])
result.pop(index2)
# 迭代計(jì)算，直至min_dis>t為止
step2(result, t)
def min_distance(list1, list2):
# 計(jì)算兩個(gè)聚類之間的最小距離：
# 遍歷兩個(gè)聚類的所有元素揖膜，計(jì)算距離（方法較為笨拙誓沸，有待改進(jìn)）
min_dis = get_distance(list1[0], list2[0])
for i in range(len(list1)):
for j in range(len(list2)):
dis_temp = get_distance(list1[i], list2[j]) # get_distance()函數(shù)見(jiàn)另一篇博文《聚類算法——最大最小距離算法》
if dis_temp < min_dis:
min_dis = dis_temp
return min_dis
# 測(cè)試hierarchical_cluster
# data = [[0, 3, 1, 2, 0], [1, 3, 0, 1, 0], [3, 3, 0, 0, 1], [1, 1, 0, 2, 0],[3, 2, 1, 2, 1], [4, 1, 1, 1, 0]]
# t = math.sqrt(5.5)
# result = hierarchical_cluster(data, t)
# for i in range(len(result)):
# print "----------第" + str(i+1) + "個(gè)聚類----------"
# print result[i]
# 結(jié)果為：
# ----------第1個(gè)聚類----------
# [[0, 3, 1, 2, 0], [1, 3, 0, 1, 0], [1, 1, 0, 2, 0]]
# ----------第2個(gè)聚類----------
# [[3, 3, 0, 0, 1]]
# ----------第3個(gè)聚類----------
# [[3, 2, 1, 2, 1], [4, 1, 1, 1, 0]]
**注： **
- 本次代碼實(shí)現(xiàn)中采取的類間距離計(jì)算準(zhǔn)則為最短距離法，但并未采取文中介紹的遞推公式壹粟，而是采取的較為簡(jiǎn)單的遍歷方式拜隧，數(shù)據(jù)量較大時(shí)，算法效率較低趁仙，讀者有時(shí)間的話可以思考嘗試所介紹的遞推方式洪添。
最后：
本文簡(jiǎn)單的介紹了 聚類算法——層次聚類算法 中 凝聚層次聚類 的相關(guān)內(nèi)容，以及相應(yīng)的代碼實(shí)現(xiàn)雀费，如果有錯(cuò)誤的或者可以改進(jìn)的地方干奢，歡迎大家指出。
代碼地址：聚類算法——層次聚類算法（碼云）
原文地址：聚類算法——層次聚類算法盏袄，也是本人的CSDN賬號(hào)忿峻，歡迎關(guān)注，博客會(huì)第一時(shí)間在CSDN更新辕羽。
