层次聚类算法原理
一、聚类算法的分类
层次聚类
合并算法

一、聚类算法的分类


层次聚类


划分聚类：图论、Kmean


基于密度：DBSCAN


基于网格



层次聚类
通过计算不同类别数据节点间的相似度来创建一颗有层次的嵌套树（聚类树）。
创建方法：自下而上合并，自上而下分裂。
合并算法
通过计算两类数据点间的相似性，组合最相似的两类，并反复迭代。

相似性由一个类别点与所有点之间的距离来确定。

距离越小，相似度越高。
相似度确定方法：

Single Linkage：两点集（类）间距离最近的两点间距，做作为点集（类）间距离。容易受极端值影响。
Complete Linkage：两点集间距离最远的两点间距，作为点集间距离。易受极端值影响。
Average Linkage：两点集间所有点间距离的均值，作为点集间距离。计算量大。

前言
聚类分析是研究分类问题的分析方法，是洞察用户偏好和做用户画像的利器之一。聚类分析的方法非常多，能够理解经典又最基础的聚类方法 —— 层次聚类法(系统聚类) 的基本原理并将代码用于实际的业务案例是本文的目标，同时这也会为理解后续与聚类相关的推文如 K-Means 等打下基础。
本文将详细介绍如何 利用 Python 实现基于层次聚类的客户分群，主要分为两个部分：

层次聚类详细原理介绍
Python 代码实战讲解


本文源数据与代码在公众号 “ 数据分析与商业实践 “ 后台回复 ” 层次聚类 “ 即可获取~~

原理部分
原理介绍
既然它们能被看成是一类的，所以要么它们距离近，要么它们或多或少有共同的特征。拿到数据集后，直接根据特征或指标来将样本分类的做法其实更适合业务能力比较强的人或有了十分明确的指标如男女各一类等硬性要求，所以本文以样本之间的距离为聚类指标。为了能够更好地深入浅出，我们调整了一下学习顺序，将小部分数学公式往后放，先从聚类结果的显示与分析入手。
下面是有关层次聚类的几个常见问题。
1、为什么都说层次树是层次聚类法独有的聚类结果图？
因为树形图的横坐标会将每一个样本都标出来，并展示聚类的过程。几十个样本时候层次树就已经 “无法” 查看了，更何况成百上千的数据样本。



2、层次树是怎么建立的？建立的基本步骤？
其实层次树的建立过程表示的就是聚类的过程，只不过通过层次树我们可以看出类之间的层次关系（这一类与那一类相差多远），同时还可以通过层次树决定最佳的聚类个数和看出聚类方式（聚类顺序的先后）
基本步骤比较简洁，只要短短的 3 步：

计算每两个观测之间的距离
将最近的两个观测聚为一类，将其看作一个整体计算与其它观测（类）之间的距离
一直重复上述过程，直至所有的观测被聚为一类

建立层次树的三个步骤虽然简洁，但其实也有令人迷惑的地方，所以为了让各位更好的从整体上去理解聚类过程而不是圄于细节，这里先直接放一个聚类过程图和对应的层次树


3、怎么从层次树中看出聚类过程？
这一个简短的问题中其实暗含不少门道，第一： 当两个点被分为一类时，是从横坐标出发向上延伸，后形成一条横杠；当两个类被分为一类时，是横杠中点向上延伸。 这第一点中，横杠的数量就表示当所有的点都被圈为一类的时候经过了多少次聚类。



同样，横杠距离横坐标轴的高度也有玄机，毕竟每生成一个横杠就表示又有一次聚类了，所以我们可以通过横杠的高度判断聚类的顺序，结合上图右半部分的圆圈和数字标号也可以看出。



所以聚类顺序便如下表：



第二，整棵层次树是由一棵棵小树组成，每棵小树代表了一个类，小树的高度即是两个点或两个类之间的距离，所以两个点之间的距离越近，这棵树就越矮小。



下面这一段仔细阅读的话对理解点与点，类与类，点与类之间的距离是如何在层次树上体现很有帮助。先从最矮的高度只有 d1 小树说起，这就是类 1,3 中两个孤立的点 1 和 3 之间的距离；同理，d2 为类2,5 中点 2 和 5 之间的距离。
而至于 d3, d4, d5 这三个距离，他们并不像 d1 和 d2 那般表示的是一棵完整的树的高度，而更像是 “ 生长的枝干 ”，因为从第一点中的 “ 当两个类被分为一类时，是横杠中点向上延伸。” 可以看出 d3 是从类 2,5 横杠的中点往上延伸的，所以它表示会与另外的类聚成一起并形成一棵更大的树，图中即类 2,5 和点 4 被聚成一个新的类 2,5,4。
同理：

d4 表示类 2,5,4 与类 1,3 聚成新类 1,3,2,5,4
d5 表示类 1,3,2,5,4 与点 6 聚成类 1,3,2,5,4,6

4、怎么从层次树中看出聚类情况？可以通过决定纵轴分界线可决定这些数据到底是分成多少类



定好分界线后，只需要看距离这条线横杠和单独的竖线即可，上图中距离红线的横杠有两条（分别表示类1,2 和类2,5），单独的竖线也有两条，从横坐标轴 4 和 6 上各延伸出的一条。同理可用到下图



为什么最好不要分成 3 组：13，254，6 呢？
因为树的高度表示两个点之间的距离，所以 4 到 类25 的距离只比到 类13 的距离要多如下图所示的一点点，所以硬是把 4 跟 25 分成一类就有点牵强了，正因为这种牵强的分类方式可能会让我们忽略 4 这个点单独的价值，所以我们不如直接将 4 看成单独的一类。


推导与计算
接下来就是需要更加动脑的数学原理和公式部分了，我们需要知晓点与点，类与类，点与类这三种距离如何计算。



最包罗万象的是明考斯基距离，因为 q 分别取 1 和 2 的时候就表示是绝对值距离和欧氏距离。点与点的距离很好求，我们一般用的都是欧氏距离，即初中学习的直角三角形三边关系，上图右上角点AC之间的距离（ab² + bc²） 后再开根号
而至于类与类之间的距离求法，其实经过了一个演变，篇幅原因本文只会一笔带过那些不常用的方法并将重心放在最常用和主流的方法上。


平均联接和重心法都已经比较少用了，现大多采用较少受异常值影响且不知数据分布的情况下依然能有较好表现的 Ward 法。


其实 Ward 法的公式与方差分析相似，都是通过组间距离来定夺点点/点类/类类间的距离，Ward 法许多详细的数学推导在网上有很多，这里我们直接展示最容易理解的一种：



上图为已知的五个点和它们 x，y 轴坐标，SS 为 Ward 最小方差法的公式。



当两个点被聚为一类时，这一类的组间差异 SS 便为其中一点的某一坐标与另外的所有坐标加加减减的一系列操作（通俗解释，其实直接看上图的 SS 计算过程已经可以理解。）
了解 Ward 最小方差法的基本求解公式后，我们可以从最简单的聚类形式开始：5个点聚成4类。这意味着其中两个点会被聚在一起，剩下三个点各自为一类，所以总共会出现 C52 = 10 种情况，每种情况的组内 SS 分别如下表：



同理，如果这 5 个点聚成 3/2/1 类的情况如下表：



需要注意的是：聚成两类后计算出 AB 这两个的利方差最小后，在后续聚成3类，2类的时候就直接把A和B两个看成是同一个个体了，所以不会再出现A和B分开的局面。
结合两个表，我们便可以得出如下结论：

如果需要被聚成 4 类，AB为一类，剩下3个点各为一类最好（SS 最小）
如果需要被聚成 3 类，AB，DE为一类，剩下的 C 单独为一类最好
如果需要被聚成 2 类，AB，CDE各为一类
如果需要被聚成 1 类，对不起，我觉得没什么分析的必要

在进入代码实战前，我们简单总结一下原理部分提到的知识点：

层次树的阅读
两个点之间的距离公式
Ward 法求类内的组间差异，用以决定聚出的类别个数

代码实战
在正式实战前，需要注意以下几点，首先原始数据通常需要经过处理才能用于分析：

缺失值
异常值（极大或极小）
分类变量需要转化为哑变量（0/1数值）
分类变量类别不宜过多

其次由于变量的量纲的不一样引起计算距离的偏差，我们需要对数据进行标准化。同时不同的统计方法对数据有不同的要求：

决策树和随机森林允许缺失值和异常值
聚类分析和回归模型则不支持缺失值

在处理数据时，也有两个问题值得关注，
1、聚类的时候，所有的 X 必须都是连续变量，为什么？
分类变量无法计算距离，如某个变量表示的是性别，男和女；教育程度为小学，初中，高中，大学，那该变量在各个个体之间的距离怎么计算？所以做聚类分析时尽可能用分类变量。
2、那这些分类变量的价值难道就无法利用了吗？
可以先根据其他的连续变量聚类，而后对分出来的类做描述性统计分析，这时候就可以用上分类变量的价值了。另外一种方法是可以在第一步就把分类变量也用上的聚类方法，不过需要结合实际业务。
以市场客户调研为例，属于 “ 客户的需求与态度 ” 这个分支，目的是依据调查问卷结果针对需求的数据分群，而调查分卷的问题中回答 “yes” 或者 “no” 类型的问题通常又会占一大部分，这时候我么可以通过合并多个问题回答的结果来将多个分类变量组合，生成一个连续变量，以电信客户的使用和需求情况为例：



当然也还可以计算分类变量之间的 cos 相似度，即直接把分类变量设成距离。总之，分类变量在聚类当中是一定需要处理的。
现在终于到了正式的代码阶段，如果前面的原理都理解好了，代码的理解则可不费吹灰之力。这里我们使用一份公开的城市经济数据集，参数如下：

AREA：城市名称
Gross：总体经济情况指数
Avg：平均经济情况指数





这些城市的指标分布如下波士顿矩阵图，篇幅原因绘图代码省略，后台回复关键字获取的源程序会一并提供。



sklearn 里面没有层次聚类的函数，所以从 scipy 中导入



下面是层次聚类可视化：层次树




最后说一下，未来还会有 K-Means 等聚类方法的推文。作为深入浅出聚类方法的开端，我们只需知道层次聚类相比 K-Means 的好处是它不用事先指定我们需要聚成几类 (K-Means 算法代码中的参数 k 指定)
这样一来，我们只需要把计算全权交给程序，最终能得出一个比较精准的结果。但缺点是随之而来的计算复杂度的增加。
所以层次聚类更适合小样本；K-Means 更适合大样本，在数据挖掘中也更常见，本文分享就到这里，本文代码数据后台回复“层次聚类”获取

基于层次的聚类方法，是对给定的数据进行层次的分解，直到某种条件满足为止。首先将数据点组成一颗聚类树，根据层次，自底向上或是自顶向下分解。层次的方法可以分为凝聚的方法和分裂的方法。

凝聚的方法，也称为自底向上的方法，初始时每个数据点都被看成是单独的一个簇，然后通过逐步合并相近的数据点或簇，形成越来越大的簇，直到所有的数据点都在一个簇中，或者达到某个终止条件为止。

凝聚的方法：

步骤1：用异常侦测等方法去离群点。

为了提高凝聚方法的分类效率和优化分类效果，首先应用异常侦测等方法去离群点。我们通常采用基于概率分布模型的方法，一元或多元正太分布分析方法，如果数据点不能很好地拟合一个概率模型，或者说它不服从该分布，则将该数据点标识为离群点。

步骤2：用密度分类的方法将数据分成许多小类。

采用了诸如DBSCAN的基于密度的划分算法，将数据划分足够小的类，以便减少凝聚算法的高昂成本，并且该步骤可逆，即如果后面的凝聚算法得不到一个全局优解，可以重复本步。

步骤3：自底向上凝聚算法（AGNES-AGglomerative NESting）.

自底向上凝聚的逻辑算法如下：

输入：包含n个数据点的数据库，终止条件簇的数目k。

输出：k个簇，达到终止条件规定簇数目。

将每个数据点当成一个初始簇；

重复以下步骤：

1）根据两个簇中最近的数据点找到最近的两个簇。

2）合并两个簇，生成新的簇的集合。

3）达到定义的簇的数目时终止。
分裂的方法，也称为自顶向下的方法。它与凝聚层次聚类恰好相反，初始时将所有的数据点置于一个簇中，然后逐渐细分为更小的簇，直到最终每个数据点都在单独的一个簇中，或者达到某个终止条件为止。

1）用异常侦测等方法去离群点。步骤同上；

2）DIANA(DIvisive ANAlysis,自顶向下分裂算法)逻辑算法。

自顶向下分裂算法步骤如下：

输入：包含n个数据点的数据库，终止条件簇的数目k。

输出：k个簇，达到终止条件规定簇数目。

1）将所有数据点设为初始簇数目。

2）找出S中与其他点平均相异度最大的点X1,将X1放入新簇S1。

3）根据S中剩余点到最近的距离重新分簇，于是产生两个新簇S1和S2。

4）将S1和S2中直径大的簇，重复2）、3）步。

5）生成k个新簇时终止。

6）应用轮廓系数方法对分裂方法聚类结果评估。

分裂法在生活中也是可以看到的。例如，下火车或下公交车的人群按照目的地分裂：先按照大方向分裂，再按小方向分类，最后再到各自的目的地。
综合层次聚类方法：

1.BIRCH算法

BICH(Balanced Iterative Reducing and Clustering using Hierarchies)算法是一个综合性的层次聚类方法，它利用层次方法的平衡迭代进行归约和聚类。其核心是用一个聚类特征(CF)三元组表示一个簇的有关信息，从而使簇中的点可用对应的聚类特征表示。它通过构造满足分支因子和簇直径限制的聚类特征树来求聚类。该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。

聚类特征是一个三维向量，CF(n,LS,SS),其中n是数据点的个数，LS是n个点的线性和，SS是n个点的平方和。通过CF可以方便地求中心、半径、直径及类内、类间距离。CF树有两个参数：
分支因子beta,通过它定义每个非叶子结点的子女的最大数目。

阈值T,存储在叶节点中的子簇的最大直径。

算法实现流程如下：

1）用异常侦测等方法去离群点。同上；

2）扫描数据库，建立一个初始的CF树。它可以被看做一个数据的多层压缩，试图保留数据内在的聚类结构。当一个数据点被插入到最近的叶节点(子聚类)中时，随着数据点的插入，CF树被动态地构造，不要求所有的数据读入内存，可在外存上逐个读入数据项。因此，BIRTH方法对增量或动态聚类也非常有效。

3）采用某个聚类算法对CF树的叶节点进行聚类。在这个阶段可以执行任何聚类算法，例如典型的划分方法。BIRCH算法试图利用可用的资源来生成最好的聚类结果。通过一次扫描就可以进行比较好地聚类，故该算法的计算复杂度是O(n),n是数据点的数目。

4）应用轮廓系数方法对分裂方法聚类结果评估。同上

该算法的优点是数据点数目具有线性易伸缩性，并具有良好的聚类质量，一次扫描就可以进行较好的聚类。缺点是BIRCH算法只适用于类的分布呈凸形及球形的情况，对不可视的高维数据则不可行。

BIRCH逻辑算：

输入：包括n个数据点的数据集合D=[x1,x2,…,xn]及阈值T。

输出：簇集合。

过程：

1）扫描数据集，建立初始的CF树。

2）对每个数据点xi执行如下操作。

3）为xi找一个正确的待插入的叶子节点。

4）如果阈值条件不被破环，则将xi插入到叶子节点中，并从被插入的叶子节点到根节点依次更新CF三元组。

5）否则，如果有叶子节点空间，则将xi作为单独的簇插入到树中，并更新CF三元组。

6）否则分类叶子节点，重新安排CF三元组。

CURE算法：

CURE(Clustering Using Representatives)算法中既有层次部分，也有划分部分，所以CURE也是一个综合性的聚类算法。

前面讲到的聚类算法倾向于处理簇为球形、且簇的大小相似的聚类问题，并且对孤点较为敏感。CURE采用了多个点代表一个簇的方法，可以较好地处理以上问题。并且在处理大数据量的时候采用了随机抽样、分区的方法，来提高其效率，使得其可以高效地处理大量数据。

算法实现流程如下：

1）用异常侦测等方法去离群点，同上；

2）对原始数据进行随机抽样，将样本进行等量划分，划分后便形成了以这些样本点为代表的分区。

3）对于每一个分区，再使用层次聚类算法中的凝聚算法。再凝聚算法中的每一步，距离最近的代表性点所对应的簇将被合并。它们之间的距离被定义为两个簇中代表性点之间距离的最小值。

4）应用轮廓系数方法对分裂方法聚类结果评估。同上

CURE算法的具体步骤如下：

1）从原始数据集中抽取一个随机样本S。

2）为了加速聚类，把样本划分成p份，每份大小相等。

3）对每个划分进行局部聚类。

4）根据局部聚类结果，通过随机抽样剔除孤立点。主要有两种措施：如果一个簇增长得太慢，就去掉它；在聚类结束的时候，非常小的类被剔除。

5）对上一步中产生的局部的簇进一步聚类。从每个簇中选择c(常数)个数，然后通过应用收缩因子a,将这些分散的点向簇的质心方向收缩。当a为1的时候，所有点都收缩成一点，即质心。通过多个有代表性的点，簇的形状可以更好地被表达出来。

6）用相应的簇标签来记数据。

CURE算法的优点是它回避用所有点或单个质心来表示一个簇的传统方法，而实将一个簇用多个具有代表性的点来表示，是CURE可以适应非球形的几何形状。

另外，收缩因子降低了噪声对聚类的影响，从而使CURE对孤点的处理更加健壮，而且能识别非球形和大小变化比较大的簇，对于大型数据库具有良好的伸缩性。缺点是参数设置对聚类结果有很大的影响，不能处理分类属性。CURE的复杂的复杂度O(n),其中n是数据点的数目。

层次聚类算法又称为树聚类算法[8,9],它使用数据的联接规则,透过一种层次架构方式,反复将数据进行分

裂或聚合,以形成一个层次序列的聚类问题解.本文仅以层次聚类算法中的层次聚合算法为例进行介绍.层次聚

合算法的计算复杂性为O(n2),适合于小型数据集的分类.

2.1.1 层次聚合算法

该算法由树状结构的底部开始逐层向上进行聚合,假定样本集S={o1,o2,…,on}共有n 个样本.

HA1[初始化]. 置每个样本oi 为一个类; /*共形成n 个类:o1,o2,…,on*/

HA2[找最近的两个类]. ( , ) min , , ( , ) distance or ok ou ov S ou ov distance ou ov ∀ ∈ ≠ = ;

/*从现有的所有类中找出距离最近(相似度最大)的两个类or 和ok*/

HA3[合并or 和ok]. 将类or 和ok 合并成一个新类ork; /*现有的类数将减1*/

HA4. 若所有的样本都属于同一个类,则终止本算法;否则,返回步骤HA2.