层次聚类算法及通过python的scipy进行计算_凝聚层次聚类 python代码自己指定终止条件

0. 层次聚类基本原理

0.1 原理介绍

专业一点来说，层次聚类通过 计算不同类别数据点间的相似度 来创建一棵有层次的嵌套聚类树。

层次聚类的好处是不需要指定具体类别数目的，其得到的是一颗树，聚类完成之后，可在任意层次横切一刀，得到指定数目的簇。

按照 层次分解是自下而上，还是自顶向下，层次的聚类方法可以进一步分为以下两种：

• 自下而上的 凝聚方法（agglomerative：先将所有样本的每个点都看成一个簇，然后找出距离最小的两个簇进行合并，不断重复到预期簇或者其他终止条件），
  凝聚方法的代表算法：AGNES，Agglomerative Nesting

• 自顶向下的 分裂方法（divisive：先将所有样本当作一整个簇，然后找出簇中距离最远的两个簇进行分裂，不断重复到预期簇或者其他终止条件）。

• 分裂方法的代表算法：DIANA，Divisive Analysis。
  

AGNES 算法步骤：

（1） 初始化，每个样本当做一个簇。

（2） 计算任意两簇距离，找出 距离最近的两个簇，合并这两簇。

（3） 重复步骤 2……

直到，最远两簇距离超过阈值，或者簇的个数达到指定值，终止算法

DIANA 算法步骤：

（1） 初始化，所有样本集中归为一个簇

（2） 在同一个簇中，计算任意两个样本之间的距离，找到 距离最远 的两个样本点a,b，将 a,b 作为两个簇的中心;

（3） 计算原来簇中剩余样本点距离 a，b 的距离，距离哪个中心近，分配到哪个簇中

（4） 重复步骤2、3 ……

直到，最远两簇距离不足阈值，或者簇的个数达到指定值，终止算法

0.2 距离度量

在上面说的 AGNES 提到了 合并距离最近的两簇，这里的距离是如何度量的呢？
簇间距离的计算方法有许多，包括：
最小距离，最大距离，均值距离，（类）平均距离，中间距离，重心距离

• （1）最小距离，取两个类中距离最近的两个样本的距离作为这两个簇的距离
• （2）最大距离，取两个类中距离最远的两个样本的距离作为这两个簇的距离

补充：

当算法选择“最小距离”作为簇间距离时，有时称之为 最近邻聚类算法。并且，当最近两个簇之间的距离超过阈值时，算法终止，则称其为 单连接算法。

当算法选择“最大距离”作为簇间距离时，有时称之为 最远邻聚类算法。并且，当最近两个簇之间的最大距离超过阈值时，算法终止，则称其为全连接算法。

1.什么是层次聚类？

常用于 1维数据 的自动分组，如下图所示，

1. 把数据用【主成分分析】的方法把数据从多维压缩为1维，
2. 然后使用层次聚类算法，把它们的树结构计算出来，
3. 然后根据树的结构，把它们分解成为我们需要的组，例如我们需要分为3组，就使用图中的黄色直线，根据树结构分成3组即可。

层次聚类算法分为两类：自上而下和自下而上。
凝聚层级聚类(HAC)是自下而上的一种聚类算法。HAC首先将每个数据点视为一>个单一的簇，然后计算所有簇之间的距离来合并簇，直到所有的簇聚合成为一个簇为止。

具体步骤：

• 首先我们将每个数据点视为一个单一的簇，然后选择一个测量两个簇之间距离的度量标准。例如我们使用 average linkage 作为标准，它将两个簇之间的距离定义为第一个簇中的数据点与第二个簇中的数据点之间的平均距离。
• 在每次迭代中，我们将两个具有最小 average linkage 的簇合并成为一个簇。
• 重复步骤 2 知道所有的数据点合并成一个簇，然后选择我们需要多少个簇。

层次聚类
优点：
（1）不需要知道有多少个簇
（2）对于距离度量标准的选择并不敏感
缺点：效率低

2. 如何用python实现

1. 对数据进行聚类

import scipy.cluster.hierarchy as hcluster
linkage = hcluster.linkage(data, method='single')
# data:训练样本
# method:类距离的计算方式（single：两个类之间最短距离的点的距离、complete:两个类之间最长距离的点的距离、centroid：两个类之间所有点的中点的距离）
1
2
3
4

2. 将聚类结果绘图

import scipy.cluster.hierarchy as hcluster
hcluster.dendrogram(linkage)
#linkage：层次聚类的结果
# dendrogram()方法为我们展示层次聚类得到的层次图
1
2
3
4

3. 对层次聚类结果进行划分

import scipy.cluster.hierarchy as hcluster
pTarget = hcluster.fcluster(linkage, n, criterion='maxclust')
# linkage:层次聚类的结果
# n:要聚的类数量
# criterion:划分方法，使用maxclust，最大划分法
1
2
3
4
5

参考链接：

[1] 聚类算法——层次聚类算法 2018.2
[2] 层次聚类python，scipy（dendrogram, linkage,fcluster函数）总算有博文说清楚层次聚类Z矩阵的意义了 2021.6
[3] Python scipy.cluster.hierarchy.dendrogram用法及代码示例 ;
[4] python dendrogram_Python中的凝聚层次聚类示例 2020.11
[5] 聚类分析python画树状图–Plotly(dendrogram)用法解析 2018.8