【python-scipy】scipy.cluster.hierarchy 学习 & 总结 (fcluster, linkage等)
博主最近在依据scipy的手册学习，按每个模块进行记录，对scipy其他部分有疑惑的可以看一下博主的相关合集。p.s. 更新中
层级聚类原理
当我们需要对一个集合S中的元素进行聚类的时候，我们肯定预先有一个评价标准
d
d
d，用于计算任意两个节点a和b之间的距离
d
(
a
,
b
)
d(a,b)
d(a,b)，再依据计算的结果进行聚类。说得更清楚一些，有两个方式来实现聚类，一个是从单个到总体：我们首先将每个向量都当作一个类，利用
d
d
d计算出两两之间的距离，合并距离最小的两个，循环进行；另一个是从整体到单一：先把所有的看作同一类，利用
d
d
d计算出两两之间的距离，跳出距离最大的a,b，其他向量计算到a,b的距离进而分为2类，后续以此类推。
其实看到后面会发现，这个hierarchy cluster（层级聚类）在算法上是定死的，给我们留下的空间只在于选择何种评价标准
d
d
d。我们首先看看这个
d
d
d应该有哪些性质。
度量
数学上来讲，度量是一个二元函数 D × D → R ≥ 0 \mathbf{D} \times \mathbf{D} \rightarrow \mathbb{R}_{\geq 0} D×D→R≥0，并且满足以下三条性质：
- 非负性（分离性）
d ( a , b ) ≥ 0 ( ∀ a , b ∈ D ) d(a,b) \geq 0 \quad (\forall a,b \in \mathbf{D})\quad d(a,b)≥0(∀a,b∈D) 并且 d ( a , b ) = 0 ⇔ a = b \quad d(a,b) = 0 \, \Leftrightarrow \, a = b d(a,b)=0⇔a=b - 对称性
d ( a , b ) = d ( b , a ) ( ∀ a , b ∈ D ) d(a,b) \, = d(b,a) \quad (\forall a,b \in \mathbf{D}) d(a,b)=d(b,a)(∀a,b∈D) - 三角不等式
d ( a , c ) ≤ d ( a , b ) + d ( b , c ) ( ∀ a , b , c ∈ D ) d(a,c) \, \leq \, d(a,b) + d(b,c) \quad (\forall a,b,c \in \mathbf{D}) d(a,c)≤d(a,b)+d(b,c)(∀a,b,c∈D)
需要注意的是，在scipy中，通过linkage的接口我们能从以下度量中进行选择：
‘braycurtis’, ‘canberra’, ‘chebyshev’, ‘cityblock’, ‘correlation’, ‘cosine’, ‘dice’, ‘euclidean’, ‘hamming’, ‘jaccard’, ‘jensenshannon’, ‘kulsinski’, ‘mahalanobis’, ‘matching’, ‘minkowski’, ‘rogerstanimoto’, ‘russellrao’, ‘seuclidean’, ‘sokalmichener’, ‘sokalsneath’, ‘sqeuclidean’, ‘yule
我们列举几个比较常用的度量：
- 欧式度量(euclidean) 就是我们最熟悉的度量
d i s t ( x 1 , x 2 ) = ∑ k = 1 n ( x k 1 − x k 2 ) 2 ∀ x i = ( x 1 i , . . . , x n i ) ∈ R n i = 1 , 2 dist(x_1,x_2)=\sqrt{\sum_{k=1}^n(x_k^1-x_k^2)^2} \quad \forall x_i=(x_1^i,...,x_n^i) \in \mathbb{R}^n \quad i=1,2 dist(x1,x2)=k=1∑n(xk1−xk2)2∀xi=(x1i,...,xni)∈Rni=1,2 - p范数诱导的度量(minkowski)
d i s t ( x 1 , x 2 ) = ∣ ∣ x 1 − x 2 ∣ ∣ p dist(x_1,x_2)=||x_1-x_2||_p dist(x1,x2)=∣∣x1−x2∣∣p - 曼哈顿度量(cityblock)
d i s t ( x 1 , x 2 ) = ∑ k = 1 n ∣ x k 1 − x k 2 ∣ dist(x_1,x_2)=\sum_{k=1}^n|x_k^1-x_k^2| dist(x1,x2)=k=1∑n∣xk1−xk2∣ - 欧式度量的平方(sqeuclidean)
- 余弦(cosine)
d i s t ( x 1 , x 2 ) = < x 1 , x 2 > ∣ ∣ x 1 ∣ ∣ ∣ ∣ x 2 ∣ ∣ dist(x_1,x_2)=\frac{<x_1,x_2>}{||x_1||||x_2||} dist(x1,x2)=∣∣x1∣∣∣∣x2∣∣<x1,x2>
-协方差(correlation)
scipy使用方法
linkage中如何调用这些度量
linkage(y, method='single', metric='euclidean', optimal_ordering=False)
在metric参数上，我们可以通过输入上一节中提及的度量名称对使用的度量进行修改。
但是特别地，我们需要注意一下method参数
linkage – method参数
读者到这里可以回顾一下之前提到的聚类的两种方法：从单一到整体和从整体到单一，我们在此用前举例。我们在脑子里想象一下整个过程，第一步是明确的，计算两两元素之间的距离，最近的两个进行分类。那么假设我们总共有n个向量
{
x
i
}
i
=
1
n
\{ x_i \} _{i=1}^n
{xi}i=1n等待分类，经过这一步我们剩余n-2个向量
{
x
i
}
i
=
3
n
\{ x_i \} _{i=3}^n
{xi}i=3n和一个由2个向量组成的cluster
[
x
1
,
x
2
]
[x_1,x_2]
[x1,x2]；按照之前的说法，在进行第二步的时候需要计算这剩下的n-1个东西相互之间两两的距离，这时候有一个问题，前面剩余的n-2个向量之间计算距离是简单的，只需利用选好的metric去计算
d
i
s
t
(
x
i
,
x
j
)
dist(x_i,x_j)
dist(xi,xj)，但是如何计算其与cluster之间的距离呢？
这就是我们为什么需要method。我们linkage的method中可以选择以下几种方法：
single, complete, average, weighted, centroid, ward
其具体含义基本望文生义，其余可参考scipy的文档。往下拉一点就是了
linkage – 返回值
函数返回给我们一个矩阵Z，其包含了聚类中每一步的操作以及一些信息。
X = [[i] for i in [2, 8, 0, 4, 1, 9, 9, 0]]
Z = linkage(X)
###
Z =
[[ 2. 7. 0. 2.]
[ 5. 6. 0. 2.]
[ 0. 4. 1. 2.]
[ 8. 10. 1. 4.]
[ 1. 9. 1. 3.]
[ 3. 11. 2. 5.]
[12. 13. 4. 8.]]
###
一共有8个元素，需要进行7次聚类，所以Z有7行。每一行有四个元素，前两个是进行cluster操作的向量的索引值，第三个是
d
i
s
t
dist
dist，第四个是该类目前有几个元素。在生成新的cluster后，其会被赋予索引值8,9,10等，一点一点往上加，这也是为什么只有8个元素但是最后几行的索引值有10+。
fcluster的用法
首先fcluster处理的是linkage的返回值Z，其通过这样一个矩阵进行进一步的细分。其实也可以理解这种功能的拆分，因为在聚类的过程中涉及的变量太多，全怼在一个函数里看不到中间过程，也不利于调参。
fcluster(Z, t, criterion='inconsistent', depth=2, R=None, monocrit=None)
其中t是一个阈值，用于后续分类，criterion是依据
d
i
s
t
dist
dist判断是否需要将其归为一类的判别法，depth和R当且仅当criterion='inconsistent‘时有用, R是一个矩阵，monocrit是当判别法为monocrit或maxcluster_monocrit时需要指定的变量。
criterion只介绍几种，一些原因是一部分用的很少，另一些原因是我也没看懂doc里面说的什么意思（所以还请大佬在评论区不吝赐教，感谢！！）
- ’distance‘ with threshold t
类内距离和初始的元素 < t <t <t时放进来，否则单独分为两类 - ‘maxclust’ with threshold t
所聚类数量不多于t个