一、层次聚类
  层次聚类(Hierarchical Clustering)通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中，不同类别的原始数据点是树的最低层，树的顶层是一个聚类的根节点。创建聚类树有自下而上合并和自上而下分裂两种方法
二、合并算法
2.1、算法流程

(1) 将每个对象看作一类，计算两两之间的距离；

MIN度量
MAX度量
Group Average（平均距离度量）


Distance Between Centroids（质心度量）
Other methods driven by an objective function

Ward’s Method uses squared error




(2) 将距离最相近的两个类合并成一个新类；
(3) 重新计算新类与所有类之间的距离；
(4) 重复(2)、(3)，直到所有类最后合并成一类。

不同的度量方式，层次的划分也不一样

2.2、优缺点
2.2.1、优点：

1，距离和规则的相似度容易定义，限制少
2，不需要预先制定聚类数
3，可以发现类的层次关系
4，可以聚类成其它形状

2.2.2、缺点：

1，计算复杂度太高
2，奇异值也能产生很大影响
3，算法很可能聚类成链状
3，合并策略是最终的，一旦合并不可撤销

Reference

09 聚类算法 - 层次聚类 - CF-Tree、BIRCH、CURE
http://bluewhale.cc/2016-04-19/hierarchical-clustering.html
scipy实现树状图

文章目录
基于层次的聚类方法 简介
基于层次的聚类方法 概念
聚合层次聚类 图示
划分层次聚类 图示
基于层次的聚类方法 切割点选取
族间距离 概念
族间距离 使用到的变量
族间距离 最小距离
族间距离 最大距离
族间距离 中心点距离
族间距离 平均距离
基于层次聚类 ( 聚合层次聚类 ) 步骤
基于层次聚类 ( 聚合层次聚类 ) 算法终止条件
族半径 计算公式
基于层次聚类总结





基于层次的聚类方法 简介



1 . 基于层次的聚类方法 : 将 数据集样本对象 排列成 聚类树 , 在 指定 的层次 ( 切割点 ) 进行切割 , 切割点 时刻 的聚类分组 ,  就是 最终需要的聚类分组 ; 也就是这个切割点的切割的时刻 , 互相关联的样本 , 划分到一个聚类分组中 ;


2 . 基于层次聚类方法 的两种方式 :


① 聚合层次聚类 : 开始时 , 每个对象都是一个聚类分组 ( 原子聚类 ) , 根据 聚类之间的相似性 , 对原子聚类逐渐合并 , 最终会合并成一个聚类 ; 其 本质是 由 多个聚类分组 切割成 成少数 聚类分组 ;


② 划分层次聚类 : 开始时 , 所有的样本都在一个聚类中 , 根据聚类间相似性 , 对聚类进行划分 , 最终 每个样本 都会被划分成一个聚类分组 ( 原子聚类 ) ;  本质是 由 少数 聚类分组 划分成多个 聚类分组 ;




基于层次的聚类方法 概念



1 . 基于层次的聚类方法 概念 : 将数 据集样本对象 排列成 树结构 , 称为 聚类树 , 在指定的层次 ( 步骤 ) 上切割数据集样本 , 切割后时刻的 聚类分组 就是 聚类算法的 聚类结果 ;


2 . 基于层次的聚类方法 : 一棵树可以从叶子节点到根节点 , 也可以从根节点到叶子节点 , 基于这两种顺序 , 衍生出两种方法分支 , 分别是 : 聚合层次聚类 ,  划分层次聚类 ;


3 . 聚合层次聚类 ( 叶子节点到根节点 ) : 开始时 , 每个样本对象自己就是一个聚类 , 称为 原子聚类 , 然后根据这些样本之间的 相似性 , 将这些样本对象 ( 原子聚类 ) 进行 合并 ;
常用的聚类算法 : 大多数的基于层次聚类的方法 , 都是 聚合层次聚类 类型的 ; 这些方法从叶子节点到根节点 , 逐步合并的原理相同 ; 区别只是聚类间的相似性计算方式不同 ;


4 . 划分层次聚类 ( 根节点到叶子节点 ) :  开始时 , 整个数据集的样本在一个总的聚类中 , 然后根据样本之间的相似性 , 不停的切割 , 直到完成要求的聚类操作 ;


5 . 算法性能 : 基于层次的聚类方法的时间复杂度为 $O(N^2)$ , 如果处理的样本数量较大 , 性能存在瓶颈 ;




聚合层次聚类 图示



1 . 聚合层次聚类 图示 :

① 初始状态 : 最左侧 五个 数据对象 , 每个都是一个聚类 ;
② 第一步 : 分析相似度 , 发现 $a , b$ 相似度很高 , 将 $\{a ,b\}$ 分到一个聚类中 ;
③ 第二步 : 分析相似度 , 发现 $d, e$ 相似度很高 , 将 $\{d, e\}$ 分到一个聚类中 ;
④ 第三步 : 分析相似度 , 发现 $c$ 与 $d,e$ 相似度很高 , 将 $c$ 数据放入 $\{d, e\}$ 聚类中 , 组成 $\{c,d, e\}$ 聚类 ;
⑤ 第四步 : 分析相似度 , 此时要求的相似度很低就可以将不同的样本进行聚类 , 将前几步生成的两个聚类 , 合并成一个聚类 $\{a, b, c, d, e\}$ ;


2 . 切割点说明 : 实际进行聚类分析时 , 不会将所有的步骤走完 , 这里提供四个切割点 , 聚类算法进行聚类时 , 可以在任何一个切割点停止 , 使用当前的聚类分组当做聚类结果 ;


① 切割点 $1$ : 在切割点 $1$ 停止 , 会得到 $5$ 个聚类分组 , $\{a\}$ , $\{b\}$, $\{c\}$, $\{d\}$ , $\{e\}$ ;
② 切割点 $2$ : 在切割点 $2$ 停止 , 会得到 $4$ 个聚类分组 , $\{a, b\}$ , $\{c\}$, $\{d\}$ , $\{e\}$ ;
③ 切割点 $3$ : 在切割点 $3$ 停止 , 会得到 $3$ 个聚类分组 , $\{a, b\}$ , $\{c\}$, $\{d, e\}$ ;
④ 切割点 $4$ : 在切割点 $4$ 停止 , 会得到 $2$ 个聚类分组 ; $\{a, b\}$ , $\{c, d, e\}$ ;
⑤ 走完整个流程 : 会得到 $1$ 个聚类分组 ,  $\{a, b ,c, d, e\}$ ;




划分层次聚类 图示



1 . 划分层次聚类 图示 :



① 初始状态 : 最左侧 五个 数据对象 , 属于一个聚类 ;
② 第一步 : 分析相似度 , 切割聚类 , 将 $\{c,d, e\}$ 与 $\{a ,b\}$ 划分成两个聚类 ;
③ 第二步 : 分析相似度 , 将 $\{c,d, e\}$ 中的 $\{c\}$ 与 $\{d, e\}$ 划分成两个聚类 ;
④ 第三步 : 分析相似度 , 将 $\{d, e\}$ 拆分成 $\{d\}$ 和 $\{e\}$ 两个聚类 ;
⑤ 第四步 : 分析相似度 , 将 $\{a ,b\}$ 拆分成 $\{a\}$ 和 $\{b\}$ 两个聚类 , 至此所有的数据对象都划分成了单独的聚类 ;


2 . 切割点说明 : 实际进行聚类分析时 , 不会将所有的步骤走完 , 这里提供四个切割点 , 聚类算法进行聚类时 , 可以在任何一个切割点停止 , 使用当前的聚类分组当做聚类结果 ;


① 切割点 $1$ : 在切割点 $1$ 停止 , 会得到 $1$ 个聚类分组 ,  $\{a, b ,c, d, e\}$ ;
② 切割点 $2$ : 在切割点 $2$ 停止 , 会得到 $2$ 个聚类分组 ; $\{a, b\}$ , $\{c, d, e\}$ ;
③ 切割点 $3$ : 在切割点 $3$ 停止 , 会得到 $3$ 个聚类分组 , $\{a, b\}$ , $\{c\}$, $\{d, e\}$$ ;
④ 切割点 $4$ : 在切割点 $4$ 停止 , 会得到 $4$ 个聚类分组 , $\{a, b\}$ , $\{c\}$, $\{d\}$ , $\{e\}$ ;
⑤ 走完整个流程 : 会得到 $5$ 个聚类分组 , $\{a\}$ , $\{b\}$, $\{c\}$, $\{d\}$ , $\{e\}$ ;




基于层次的聚类方法 切割点选取



1 . 算法终止条件 ( 切割点 ) : 用户可以指定聚类操作的算法终止条件 , 即上面图示中的切割点 , 如 :


① 聚类的最低个数 :  聚合层次聚类中 , $n$ 个样本 , 开始有 $n$ 个聚类 , 逐步合并 , 聚类个数逐渐减少 , 当聚类个数达到最低值 $min$ , 停止聚类算法 ;
② 聚类最高个数 : 划分层次聚类中 , $n$ 个样本 , 开始有 $1$ 个聚类 , 逐步划分 , 聚类个数逐渐增加 , 当聚类个数达到最大值 $max$ , 停止聚类算法 ;
③ 聚类样本的最低半径 : 聚类的数据样本范围不能无限扩大 , 指定一个阈值 , 只有将该阈值内的样本放入一组 ; 半径指的是所有对象距离其平均点的距离 ;


2 . 切割点回退问题 : 切割点一旦确定 , 便无法回退 ; 这里以聚合层次聚类为例 :


① 处于切割点 $4$ : 如已经执行到了步骤三 , 此时处于切割点 $4$ ,  聚类分组为 $\{a, b\}$ , $\{c, d, e\}$ ;
② 试图回退到 切割点 $3$ : 想要会回退到切割点 $3$ 的状态 , 视图将聚类分组恢复成 $\{a, b\}$ , $\{c\}$, $\{d, e\}$ ;
③ 无法回退 : 该操作是无法实现的 , 聚类分组一旦 合并 或 分裂 , 此时就无法回退 ;




族间距离 概念



族间距离 :


① 作用: 族间距离 , 就是聚类分组之间的距离 , 之前的距离计算都是 样本 之间的距离 , 这里的基于层次聚类时 , 不管是聚合层次聚类 , 还是划分层次聚类 , 其都要进行 聚类分组 间的相似度比较 ,
② 聚合层次聚类 : 是 根据 聚类的族间距离 ( 聚类分组相似性 ) 将不同的聚类分组进行合并 ;
③ 划分层次聚类 : 是 根据 聚类的族间距离 ( 聚类分组相似性 ) 将不同的聚类分组进行划分 ( 拆分 ) ;




族间距离 使用到的变量



公式中 用到的 变量 :


① 样本表示 : $p$ 和 $q$ 表示 分别 处于两个聚类分组中的 两个样本 ;
② 样本距离表示 : $d(p, q)$ 表示  $p$ 样本对象 与 $q$ 样本对象的距离 ;
③ 聚类 ( 族 ) 表示 : $C_i$ 和 $C_j$ 分别表示两个 聚类 / 族 / 聚类分组 ;
④ 聚类距离表示 : $d(C_i, C_j)$ 表示 $C_i$ 聚类 与 $C_j$ 聚类 之间的距离 ;
⑤ 聚类中心点 : $m_i$ 是 $C_i$ 聚类的中心点 , $m_j$ 是 $C_j$ 聚类的中心点 ;
⑥ 样本个数 : $n_i$ 是 $C_i$ 聚类的样本个数 , $n_j$ 是 $C_j$ 聚类的样本个数 ;




族间距离 最小距离



$C_i \,, C_j$ 族间距离 最小距离 公式  :


$d_{min}(C_i , C_j) = min _{p \in C_i , q \in C_j} d(p, q)$


$d_{min}(C_i , C_j)$ 表示两个聚类的最小距离 ;
$p$ 是属于 $C_i$ 聚类中的任意样本 ;
$q$ 是属于 $C_j$ 聚类中的任意样本 ;


总结 : 两个聚类中两个最近的样本之间的距离就是 聚类间的 最小距离 ;




族间距离 最大距离



$C_i \,, C_j$ 族间距离 最大距离 公式  :


$d_{max }(C_i , C_j) = max _{p \in C_i , q \in C_j} d(p, q)$


$d_{max }(C_i , C_j)$ 表示两个聚类的最大距离 ;
$p$ 是属于 $C_i$ 聚类中的任意样本 ;
$q$ 是属于 $C_j$ 聚类中的任意样本 ;


总结 : 两个聚类中两个最远的样本之间的距离就是 聚类间的 最大距离 ;




族间距离 中心点距离



$C_i \,, C_j$ 族间距离 中心点距离 公式  :


$d_{mean }(C_i , C_j) = d(m_i, m_j)$


$d_{mean }(C_i , C_j)$ 表示两个聚类的 中心点距离 ;
$m_i$ 是 $C_i$ 聚类的中心点 ;
$m_j$ 是 $C_j$ 聚类的中心点 ;
$d(m_i, m_j)$ 表示 $m_i$ 样本 和 $m_j$ 样本 之间的距离 ;


总结 : 两个聚类中的中心点样本之间的距离就是 聚类间的 中心点距离 ;




族间距离 平均距离



$C_i \,, C_j$ 族间距离 平均距离 公式  :


$d_{avg}(C_i , C_j) = \frac{1}{n_i n_j}\sum_{p \in C_i}\sum_{q \in C_j} d(p, q)$


$d_{mean }(C_i , C_j)$ 表示两个聚类的 中心点距离 ;
$p$ 是属于 $C_i$ 聚类中的任意样本 ;
$q$ 是属于 $C_j$ 聚类中的任意样本 ;
$n_i$ 是 $C_i$ 聚类的样本个数 ;
$n_j$ 是 $C_j$ 聚类的样本个数 ;
$\sum_{p \in C_i}\sum_{q \in C_j} d(p, q)$ 表示 聚类 $C_i$ 中每一个点 到 聚类 $C_j$ 中所有点的距离 , 这里 $C_i$ 中每个点都对应 $n_j$ 个距离 , $n_i$ 个点 , 对应 $n_i \times n_j$ 个距离 ;


总结 : 两个聚类中的 平均距离 就是 聚类间的 所有点的距离的平均距离 ;




基于层次聚类 ( 聚合层次聚类 ) 步骤



聚合层次聚类步骤 :


① 原理 : 根据 聚类分组 的 族间距离 对相似的 聚类分组 进行 逐步合并 ;
② 步骤一 : 每个样本都构成 聚类分组 , 称为 原子聚类 ;
③ 步骤二 : 计算所有 聚类 之间的距离 ; 可以采用 最小距离 , 最大距离 , 中心点距离 , 平均距离 中的一个 ;
④ 步骤三 : 将距离最近的两个 聚类分组 合并 , 聚类的个数 减少 $1$ 个 ;
⑤ 步骤四 : 转到 步骤二 计算聚类间距离 , 步骤三 合并近距离聚类 ; 如果满足算法终止条件 , 那么停止聚类 , 否则一直循环迭代 , 最终合并成一个聚类 ;




基于层次聚类 ( 聚合层次聚类 ) 算法终止条件



算法终止条件 : 是由 用户 指定的 , 如 :
① 聚类分组 ( 族 ) 个数 : 当聚类的个数达到阈值 , 算法终止 ;
② 聚类半径 : 每个 聚类的半径 都超过某个阈值 ;




族半径 计算公式



族 ( 聚类 ) 半径计算公式 :


$R=\frac{1}{n}\sum _{i=1}^n d(p_i - m)$


$R$ 表示聚类半径 ;
$n$ 表示聚类中的 样本 个数 ;
$m$ 代表聚类中心点 ;
$d(p_i - m)$ 表示聚类中第 $i$ 个样本距离中心点的距离 ;




基于层次聚类总结



1 . 基于层次聚类 的核心 : 是计算 两个 聚类分组 ( 族 ) 之间的距离 , 根据 族间距离 进行 聚类合并 ;


2 . 适用场景 : 如果 每个 聚类 密度差不多 , 族间距离 分离的很清晰 , 那么使用不同的 族间距离 进行聚类 产生的聚类结果 基本一致 ;


3 . 算法缺陷 : 基于层次距离不适用于以下情况 ; 聚类分组 分离的不明显 ; 形状不是球形 , 凹形的 ; 聚类间大小不等 ; 各个聚类间样本密度不同 ;

from scipy.cluster import hierarchy
0.层次聚类的概念
层次聚类和k-means一样都是很常用的聚类方法。层次聚类是对群体的划分，最终将样本划分为树状的结构。他的基本思路是每个样本先自成一类，然后按照某种规则进行合并，直到只有一类或者某一类的样本只有一个点。层次聚类又分为自底而上的聚合层次聚类和自顶而下的分裂层次聚类。
0.1 聚合层次聚类
每一个点初始为1类，得到N(样本点个数)类，计算每一类之间的距离，计算方法有很多，具体可以参考距离的计算方法。聚合层次聚类方法的终止条件是所有样本点都处于同一类了，或者两类之间的距离超过设置的某个阈值。大多数层次聚类都是聚合层次聚类。
0.2 分裂层次聚类
和聚合层次聚类是反着的，属于自上而下的一种聚类方法。刚开始的时候所有的样本点都位于同一类，然后一步步划分，终止条件是所有的样本点都位于单独的一类，或者两类之间的距离超过设置的某个阈值。
下面这个图可以比较好的说明这个过程：
层次聚类的两种方法
1.凝聚层次聚类算法步骤
1.1 算法过程
1)N个样本单独成类，G1(0)、G2(0)、G3(0)、……、GN(0)，0代表初始状态。
2)更新距离矩阵D(n)，找出D(n)中最小值，把对应的两类合并为1类。
3)更新距离矩阵D(n+1)，重复步骤2-3。
当两类之间的最小距离小于给定的阈值或者所有样本都单独成类的时候，结束算法。
1.2算法案例
有个老师带了五个学生，想给学生分组，让他们分组学习，采用层次聚类来对学生进行聚类，基础数据如下图。
学生基础数据
先来算距离D(0)，就采用欧式距离就好了。
初始距离矩阵
找到最小的那两个合并为1类。
合并后的新数据
然后计算更新后的距离D(1)
合并的后新距离
以后的以此类推：
聚类的整体过程
我们看到其实124是一类，35是一类。
画出图来就是下面这个格式：
聚类结果
3.Python处理层次聚类的包
用的是在scipy.cluster里的hierarchy方法，下面来看代码，支持hierarchical clustering 和 agglomerative clustering。
首先来看一些基本函数的用法
linkage
scipy.cluster.hierarchy.linkage(data,method = 'single')
method 参数是类距离的计算公式
singele 两个类之间最短的点的距离
complete 两个类之间最长距离的点的距离
centroid 两个类所有点的中点的距离
pdist计算样本点之间的两两距离
scipy.cluster.hierarchy.distance.pdist(data, metric='euclidean')
metric参数是求距离的方法，默认是欧氏距离，可选的还有：
‘braycurtis’, ‘canberra’, ‘chebyshev’, ‘cityblock’, ‘correlation’, ‘cosine’, ‘dice’, ‘euclidean’, ‘hamming’, ‘jaccard’, ‘jensenshannon’, ‘kulsinski’, ‘mahalanobis’, ‘matching’, ‘minkowski’, ‘rogerstanimoto’, ‘russellrao’, ‘seuclidean’, ‘sokalmichener’, ‘sokalsneath’, ‘sqeuclidean’, ‘yule’
关于求距离的函数我可能还会再更一篇文章，感兴趣的朋友可以等一下。笔者之前算字符相似度自己还写了一个杰尔卡德相似度，现在看看真实太费事了。
dendrogram(linkage)
scipy.cluster.hierarchy.dendrogram(linkage)，这个函数是画图用的。
import numpy
import pandas
from sklearn import datasets
import scipy.cluster.hierarchy as hcluster
import scipy
#iris = datasets.load_iris()
#data = iris.data
#target = iris.target
points=scipy.randn(20,4)
# Compute and plot first dendrogram.
linkage = hcluster.linkage(points, method='centroid')
hcluster.dendrogram(linkage,  leaf_font_size=10.)
p = hcluster.fcluster( linkage,  3, criterion='maxclust')
聚类结果如下图所示：
聚类结果
以上就是层次聚类的简单应用，当然有不同的需求可以继续探索一些函数的参数，这个方法还是很好用的。