linkage_2">linkage

linkage是scipy中的一个层次聚类函数，可将距离最近的数聚在一起，形成聚类簇；多个聚类簇再次聚类，得到更高层级的聚类簇。重复这个过程，直到所有的聚类簇都聚成一个最终的类。

其调用方法为

python">scipy.cluster.hierarchy.linkage(y, method='single', metric='euclidean', optimal_ordering=False)

其中method表示聚类方法；metric表示聚类时采用的距离。在详细介绍这两者的可选参数之前，先对linkage做一个简单示例。

python">from scipy.cluster.hierarchy import dendrogram, linkage
from matplotlib import pyplot as plt
X = [[i] for i in [2, 8, 0, 4, 1, 9, 9, 0]]

Z = linkage(X, 'single')
print(Z)

$Z$的结果如下，是一个二维数组，记$X$的长度为$n$，则$Z$尺寸为$(n-1)\times 4$。其中$Z_{i0},Z_{i1}$属于第$n+i$聚类簇，且二者之间的距离为$Z_{i2}$，$Z_{i3}$表示对于一个新形成的聚类簇中的元素个数。

$i$	$Z_{i0}$	$Z_{i1}$	$Z_{i2}$	$Z_{i3}$	类别
0	2	7	0	2	8
1	5	6	0	2	9
2	0	4	1	2	10
3	8	10	1	4	11
4	1	9	1	3	12
5	3	11	2	5	13
6	12	13	4	8	14

$Z_{i0},Z_{i1}$中的这些数显然不是从$X$中抽取得到的，而是$X$中每个元素的所属类别，映射如下

2	8	0	4	1	9	9	0
0	1	2	3	4	5	6	7

$Z$的第一行表示，$2$和$7$组成一个簇，且$2,7$之间距离为0，根据上表，$2,7$对应的是两个$0$，所以二者之间的距离为0。且二者新形成的聚类簇为$n+i=8+0=8$，二者组成的簇共有两个元素。第二、三行与之类似。

第四行表明，$8$和$10$之间距离为1，其中$8$是由$2,7$两个位置的两个$0$组成；$10$由$0,4$两个位置组成的，以此类推。

上面的矩阵可通过dendrogram进行可视化，结果如下

python">dn = dendrogram(Z)
plt.show()

method

可选方法及其含义如下

• single 最小距离
• complete 最大距离
• average 平均距离
• weighted 加权距离
• centroid 中心距离
• median 和中心距离相似
• ward 基于Ward方差最小化算法

metric

可选距离包括下表

距离函数	备注	表达式
braycurtis	Bray-Curtis距离	$\frac{\sum |u_i-v_i|}{\sum |u_i+v_i|}$
canberra	Canberra距离	$\frac{\sum |u_i-v_i|}{\sum |u_i|+|v_i|}$
chebyshev	切比雪夫距离	$\max (\vec{u}-\vec{v})$
minkowski([,p])	闵氏距离	$\Vert u-v{\Vert }_p$
cityblock	曼哈顿距离	$\sum |u_i-v_i|$
euclidean	欧氏距离	$\Vert u-v{\Vert }_2$
sqeuclidean	平方欧式距离	$\sum w_i|u_i-v_i{|}^2$
cosine	余弦距离	$1-\frac{u\cdot v}{\Vert u{\Vert }_2\Vert v{\Vert }_2}$
correlation	相关距离	$1-\frac{(u-\bar{u})(v-\bar{v})}{\Vert u-\bar{u}{\Vert }_2\Vert v-\bar{v}{\Vert }_2}$
jensenshannon	JS距离
mahalanobis	马氏距离
seuclidean	归一化欧式距离

距离函数	备注	表达式
dice	Dice距离	$\frac{|10|+|01|}{2|11|+|01|+|10|}$
hamming	汉明距离	$\frac{[01]+[10]}{N}$
jaccard	杰卡德距离	$\frac{|10|+|01|}{|11|+|01|+|10|}$
kulczynski1	Kulczynski距离	$\frac{[11]}{[01]+[10]}$
rogerstanimoto	谷本距离	$\frac{R}{[11]+[00]+R}$
russellrao	Russell&Rao距离	$\frac{N-[11]}{N}$
sokalmichener	Sokal-Michener距离	$\frac{R}{R+[11]+[00]}$
sokalsneath	Sokal-Sneath距离	$\frac{R}{[11]+[00]+R}$
yule	Yule距离	$\frac{2[01]\cdot [10]}{[11]\cdot [00]+[10]\cdot [01]}$

可用方法method，主要是针对距离的聚类算法，下面记D为距离值，d为采用的方法

• signle $d(u,v)=\min (D(u_i,v_j))$
• complete $d(u,v)=\max (D(u_i,v_j))$
• average $d(u,v)={\sum }_{i,j}\frac{D(u_i,v_j)}{}$
• weighted $d(u,v)=\frac{d(s,v)+d(t,v)}{2}$
• centroid $d(s,t)=\Vert c_s-c_t{\Vert }_2$