1 Agglomerative Clutsering

????????這是一種自底而上的層次聚類方法。大致可以分為三步：

1.將每一個(gè)元素單獨(dú)定為一類
2.每一輪都合并指定距離(對指定距離的理解很重要)最小的類
3.迭代第二步，直到所有的元素都?xì)w為同一類/類別數(shù)量已經(jīng)達(dá)到了我們需要的數(shù)量

2 Agglomerative Clutsering的分類

????????根據(jù)對元素之間相似度（距離）的不同定義，將Agglomerative Clustering的聚類方法分為三種：Single-linkage,Complete-linkage和Group average.

Single-linkage	要比較的距離為元素對之間的最小距離
Complete-linkage	要比較的距離為元素對之間的最大距離
Group average	要比較的距離為類之間的平均距離

其中平均距離的計(jì)算方式為，假設(shè)有A，B兩個(gè)類，A中有n個(gè)元素，B中有m個(gè)元素。在A與B中各取一個(gè)元素，可得到他們之間的距離。將nm個(gè)這樣的距離相加，得到距離和。最后距離和除以nm得到A，B兩個(gè)類的平均距離。

2.1 舉例

假如我們有5個(gè)元素，ABCDE，他們之間兩兩的距離如下：

2.1.1?single-linkage

• ?首先每個(gè)元素一個(gè)類：{A}{B}{C}{D}{E}
• ?然后判斷兩個(gè)類之間的最小距離

• 最小的 最小距離為1：{A}{B}合并

	AB	C	D	E
AB	0	A->C=3,B->C=2 ∴{AB}->C=2	A->D=4,B->D=3 ∴{AB}->D=3	A->E=5,B->E=4 ∴{AB}->E=4
C	A->C=3,B->C=2 ∴{AB}->C=2	0	1	2
D	A->D=4,B->D=3 ∴{AB}->D=3	1	0	1
E	A->E=5,B->E=4 ∴{AB}->E=4	2	1	0

• 最小的? 最小距離為1：{C}{D}合并????????

	AB	CD	E
AB	0	A->C=3,B->C=2 A->D=4,B->D=3 ∴{AB}->{CD}=2	A->E=5,B->E=4 ∴{AB}->E=4
CD	A->C=3,B->C=2 A->D=4,B->D=3 ∴{AB}->{CD}=2	0	C->E=2,D->E=1 ∴{CD}->E=1
E	A->E=5,B->E=4 ∴{AB}->E=4	C->E=2,D->E=1 ∴{CD}->E=1	0

• 最小的 最小距離為1：{CD}{E}合并?????????

	AB	CDE
AB	0	A->C=3,B->C=2 A->D=4,B->D=3 A->E=5,B->E=4 ∴{AB}->{CDE}=2
CDE	A->C=3,B->C=2 A->D=4,B->D=3 A->E=5,B->E=4 ∴{AB}->{CDE}=2	0

• 最小的 最小距離為2{AB}{CDE}合并? ???

2.1.2? ?Complete-linkage ? ?

• ?首先每個(gè)元素一個(gè)類：{A}{B}{C}{D}{E}
• ?然后判斷兩個(gè)類之間的最大距離

• 最小的? 最大距離為1：合并AB?

	AB	C	D	E
AB	0	A->C=3,B->C=2 ∴{AB}->C=3	A->D=4,B->D=3 ∴{AB}->D=4	A->E=5,B->E=4 ∴{AB}->E=5
C	A->C=3,B->C=2 ∴{AB}->C=3	0	1	2
D	A->D=4,B->D=3 ∴{AB}->D=4	1	0	1
E	A->E=5,B->E=4 ∴{AB}->E=5	2	1	0

• 最小的? 最大距離為1：{C}{D}合并????????

	AB	CD	E
AB	0	A->C=3,B->C=2 A->D=4,B->D=3 ∴{AB}->{CD}=4	A->E=5,B->E=4 ∴{AB}->E=5
CD	A->C=3,B->C=2 A->D=4,B->D=3 ∴{AB}->{CD}=4	0	C->E=2,D->E=1 ∴{CD}->E=2
E	A->E=5,B->E=4 ∴{AB}->E=5	C->E=2,D->E=1 ∴{CD}->E=2	0

• 最小的 最大距離為2：{CD}{E}合并? ??

	AB	CDE
AB	0	A->C=3,B->C=2 A->D=4,B->D=3 A->E=5,B->E=4 ∴{AB}->{CDE}=5
CDE	A->C=3,B->C=2 A->D=4,B->D=3 A->E=5,B->E=4 ∴{AB}->{CDE}=5	0

• 最小的 最大距離為5：{AB}{CDE}合并

2.1.3 group average?

• ?首先每個(gè)元素一個(gè)類：{A}{B}{C}{D}{E}
• ?然后判斷兩個(gè)類之間的平均距離

• 最小的? 平均距離為1：合并AB?

	AB	C	D	E
AB	0	A->C=3,B->C=2 ∴{AB}->C=(3+2)/2=2.5	A->D=4,B->D=3 ∴{AB}->D=(4+3)/2=3.5	A->E=5,B->E=4 ∴{AB}->E=(5+4)/2=4.5
C	A->C=3,B->C=2 ∴{AB}->C=(3+2)/2=2.5	0	1	2
D	A->D=4,B->D=3 ∴{AB}->D=(4+3)/2=3.5	1	0	1
E	A->E=5,B->E=4 ∴{AB}->E=(5+4)/2=4.5	2	1	0

• 最小的? 平均距離為1：{C}{D}合并????????

	AB	CD	E
AB	0	A->C=3,B->C=2 A->D=4,B->D=3 ∴{AB}->{CD}=(3+2+4+3)/4=3	A->E=5,B->E=4 ∴{AB}->E=(5+4)/2=4.5
CD	A->C=3,B->C=2 A->D=4,B->D=3 ∴{AB}->{CD}=(3+2+4+3)/4=3	0	C->E=2,D->E=1 ∴{CD}->E=(2+1)/1.5
E	A->E=5,B->E=4 ∴{AB}->E=(5+4)/2=4.5	C->E=2,D->E=1 ∴{CD}->E=(2+1)/1.5	0

• 最小的 平均距離為2：{CD}{E}合并? ??

	AB	CDE
AB	0	A->C=3,B->C=2 A->D=4,B->D=3 A->E=5,B->E=4 ∴{AB}->{CDE}=(2+3+3+4+4+5)/6
CDE	A->C=3,B->C=2 A->D=4,B->D=3 A->E=5,B->E=4 ∴{AB}->{CDE}=(2+3+3+4+4+5)/6	0

• ?{AB}{CDE}合并

以group average為例，比如我們需要分成三類，那么當(dāng)我們合并到{AB}{CD}{E}的時(shí)候，就結(jié)束迭代

參考文獻(xiàn)：聚類Agglomerative Clustering 及其三種方法Single-linkage、Complete-linkage，Group average_M1M1M16的博客-CSDN博客_complete linkage

總結(jié)

以上是生活随笔為你收集整理的机器学习笔记 （聚类） 层次聚类 Agglomerative Clutsering（Single-linkage、Complete-linkage，Group average）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。