In [ ]:

    

这节我们要看的是层次聚类,它的目的就是形成一个层级的聚类情况,从下到上反映了从单点相粘合形成小聚类,小聚类形成大聚类的过程.不像K-means或者高斯混合模型这种划分聚类方法需要事先给一个聚类的数量K,一般它会形成一个树状图,允许我们在各个层次（对应不同数量的聚类）看聚类情况,从而克服了划分聚类方法由固定的K带来的缺点.

层次聚类方法按照构建层级的方法分为两种:聚合型和分裂型.

顾名思义,聚合型就是从下到上,从每个单点构成的聚类出发,一步步将相近的聚类粘合;分裂型是从上到下,所有的点都属于一个聚类,慢慢将远的子集分裂出去形成新的聚类.

这个时候,我们就要好好定义下距离的"远""近"了.我们从点和点之间的度量(metric,数学上测量集合里元素之间距离的函数,满足一些性质就可以,参考维基百科)开始,到聚类和聚类之间的距离(linkage criterion).

对于数字型的数据,最常用的度量包括:
1.欧几里得距离,物理世界的直线距离,也就是2-范数诱导出的度量,所以有角标2,$\vert \vec a- \vec b \vert_2 =\sqrt{ \sum \limits_{i =1}^d \vert a_i-b_i \vert^2 }$,其中d为各个数据点的维度.

2.欧几里得平方距离,是欧几里得距离的平方,$\vert \vec a- \vec b \vert_2^2 = \sum \limits_{i =1}^d \vert a_i-b_i \vert^2 $

3.曼哈顿距离,我们可以想象田字形道路两点的距离,$\vert \vec a- \vec b \vert_1 = \sum \limits_{i =1}^d \vert a_i-b_i \vert $

4.最大距离,也就是无限范数诱导出的度量,$\vert \vec a- \vec b \vert_\infty = \max \limits_{i =1}^d \vert a_i-b_i \vert $

5.马氏距离，考虑到向量分量之间的关系，数学上用协方差矩阵表示,$\vert \vec a- \vec b \vert = \sqrt{ \{ \vec a - \vec b \}^T \times \Sigma^{-1}  \times \{ \vec a - \vec b \} } \vert $,其中 $\Sigma$为数据点所在的向量空间的分量之间的协方差矩阵.

对于文本或者非数字型的数据,我们使用编辑距离，最常用的包括：
6.汉明距离（Hamming distance）,也就是同样长度的两段字符串之间同一位置上不同字符的数量.

7.莱温斯顿距离（Levenshtein distance）,就是两个字符串之间从一个变到另一个需要的最少的单字改变数.

基于点和点之间的度量$d$,我们就可以规定聚类A,B之间的距离.常用的有以下几种：
1.最大距离（Complete-linkage clustering）,$\max\{ d(a,b) : a \in A, b\in B \}$

2.最小距离(Single-linkage clustering),$\min\{ d(a,b) : a \in A, b\in B \}$

3.平均距离(UPGMA),$ \frac {1} {n\times m} \sum \limits_ {a \in A, b\in B} d(a,b) \}$,其中$n,m$分别是A,B聚类的基数，也就是包含的点的数量.

4.中点距离(UPGMC),$\vert d(C_A,C_B)  \vert$,其中$C_A, C_B$分别是A，B的中点，也就是离中心最近的点

5.能量距离（Energy distance）,$ \frac {2} {n\times m} \sum \limits_ {a \in A, b\in B} \vert a-b\vert_2 - \frac{1}{n^2} \sum \limits_{a_i,a_j \in A} \vert a_i -a_j \vert_2 -\frac{1}{m^2} \sum \limits_{b_i,b_j \in B} \vert b_i -_j \vert_2 \}$

至于聚合型聚类的复杂度,最快的是R.Sibson在1972年提出的SLINK算法（https://grid.cs.gsu.edu/~wkim/index_files/papers/sibson.pdf）,时间复杂度是$O(n^2)$，空间复杂度是$O(n)$.
我们把n个数据点从0到$n-1$编号，SLINK算法求出的是两个数组A和B，A(i)代表把i数据点和起码一个比i序号大的数据点并入一个聚类的层级（表现在树状图上是高度，本质上是聚类之间的距离），而B（i）表示这个层级包含i的聚类中序号最大的点.
得到这两个数组后，
1)我们可以从A中最小的数$a_0$（可能有多个）开始，对应的点集{i}（因为可能多个，所以用集合表示）中的每个点，将它和它的B(i)划分为同一聚类并一直处于一个聚类,没有涉及的点单独成一个聚类;
2)将$a_0$从A中去除，找A中剩下的最小的数,对应的点集{i}中的每个点，将它和它的B(i)划入同一聚类并一直处于一个聚类,没有涉及的聚类（可能是单点聚类）保持不变.
3)重复2步骤,直到把所有点划入一个聚类.
因为SLINK算法归根到底是对$n*n$个度量的排序,所以每次运行的结果都是一样.
同一项目目录下，我会用Python实现.


相比于K-means方法，层次聚类每次运行都会得到相同结果，也可以在任何层次停止，处理的数据类型也更加丰富，比如可以通过设定合适的度量来处理字符串类型，但算法复杂度也会提高.


    

In [ ]: