开发者学堂课程【高校精品课北京理工大学数据仓库与数据挖掘(下)：Hierarchical Methods】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/1041/detail/15650
Hierarchical Methods
内容介绍：
一、基于层次的聚类算法
二、凝聚聚类算法
三、基于划分的层次聚类
四、层次聚类算法的特点
本课程继续数据仓库与数据挖掘的学习。主要介绍基于层次的聚类算法，在基于层次的聚类算法中，介绍基于层次聚类算法的基本概念，凝聚的层次聚类算法和分裂的层次聚类算法。
一、基于层次的聚类算法
首先来看一下基于层次的聚类算法的一些基本知识。基于层次的聚类算法，它产生的是嵌套类型的蔟。
这些嵌套类型的蔟是以曾次数的结构被组织，可以通过系统树图的形式可视化。
下图就展示了一个系统树图，
1.系统树图
那么首先在这样的一个数据集合中数据对象一和三是最相似的，首先被合并为一个蔟，然后数据的对象二和五相似，也被合并为一个，然后数据对象二五和数据对象四相似，那么合并为一个蔟，那么在此基础之上一三这个蔟和二五四这个蔟又很相似，合并为一个新的蔟，最后和数据对象四相似，那么合并为最终得到一个大蔟，那么这个蔟，就是所有数据对象的集合，也就是通过这样的一个系统的树图，记录了基于层次的一些蔟，它的凝聚的过程。
对于基于层次的聚类算法来说，它主要有两种策略，一种是凝聚的层次聚类算法，一种是划分的层次聚类算法。
2.凝聚的层次聚类算法和分裂的层次聚类算法
（1）、凝聚的层次聚类算法
凝聚的层次聚类算法是属于一种自底向上的层次聚类算法，那么下图的最左边开始，
首先每一个数据对象被认为是一个蔟。计算不同蔟的相似性，合并最相似的两个蔟，依次合并，一直到所有的数据对象在一个蔟中，那么这就是基于凝聚的层次聚类算法。
（2）、分裂层次聚类算法
和基于凝聚的层次聚类算法的过程相反。分裂的层次聚类算法是从这个图的最右边开始，首先所有的数据对象是一个蔟。选择合适的分裂准则，将这个蔟一分为二。然后再在剩下的蔟中选择一个 sse 最大的蔟，再利用分裂准则，继续对这个蔟进行分裂，那么一直分裂分裂到最后，每一个数据对象是一个蔟。基于分裂的层次聚类算法，它是一种置顶向下的过程。
3.树图意义
对于基于层次的聚类算法，它的结果是一个系统树图，这颗系统树图其实记录了所有层次上的聚类结果，如果想要得到某一个层次上的聚类结果，只需要对这个系统树图，在某一个上进行截断就可以，比如说在第一个层次上进行阶段，就可以得到两个蔟，而在第二个层次上阶段就可以得到多个比较细的。也就是系统树图，它记录了蔟何蔟之间的层次关系。
二、凝聚聚类算法
首先介绍凝聚的层次聚类算法，在层次聚类算法中，大部分的聚类算法都是基于凝聚的层次聚类算法。基于凝聚的层次聚类算法的核心就是不断迭代的去合并两个离得最近的蔟。那么，这个是基于凝聚层次聚类算法的过程。
1. 算法
计算邻近矩阵。首先它会计算每一个蔟之间的近邻性矩阵。
然后让每一个数据对象作为一个蔟，根据经领取正合并离的最近的两个蔟。因为两个蔟，一旦合并之后，这个蔟的数目发生变化，就需要去更新邻近矩阵，再更新近邻矩阵之后，再去再近邻矩阵中找到最相近的两个蔟，再进行合并。
重复。那么迭代这个步骤一直到所有的数据对象属于同一个蔟。
2.过程图示
通过一个例子向大家介绍凝聚层次，聚类算法的过程。下图展示的是四个数据对象，就是表示的是四个基因。那么在四个基因中，根据相似度的测量方法，可以计算这四个基因的相似度，会发现其中基因一和基因三。它的相似度是最强的，那首先合并这两个基因，那么形成一个新的蔟。在合并得到这个新的蔟之后，这个时候蔟的数目就由原来的四个变成了三个，那么在这三个蔟中，又发现下两个蔟是最相近的，然后就把这两个蔟进行合并，这个时候出的数目就成三个变成两个，最后将将这两个蔟合并得到最终的蔟，就是所有数据对象在一个蔟中。
那么，根据这样的一个过程，就可以画出一个系统树图，首先是一三两个基因合并，然后是二四两个基因合并，然后最后是这两个蔟进行合并。
3. 近邻性的矩阵的变化情况
来看一下，根据上面的一个过程中，那么近邻性的矩阵的变化情况是怎么样的？假设下图是使用的数据聚集，基于凝聚的层次聚类算法，首先会把每一个数据对象作为一个蔟，然后构建每一个簇和每一个簇之间的近邻矩阵，那么每一个方格代表的是这两个蔟之间的相似度。
那么假设基于凝聚的层次聚类算法运行到某一个过程，那么这个时候，合并后只剩下了五个蔟。
那么计算这五个蔟之间的相似性可以得到这五个蔟的相似性矩阵，或者叫做邻近性矩阵。那么在介绍相似性矩阵之后，会发现其中两个蔟 c2 和 c5，它们的这样的一个相似度是最高的，也就是最邻近的，那么就需要把 c2 和 c5 这两个蔟合并为一个蔟。
那么，合并之后，可以看一下这个时候临近矩阵中就只剩下四个蔟，那么其中的多了一个新蔟，这个时候这个新蔟和其余蔟的相似度就需要被更新。
4.如何更新相似度
那怎么样去更新下了一个相似度？也就是说，在基于凝聚的层次聚类算法中，它的一个核心问题就是如何去更新蔟和蔟之间的相似度。更新蔟和蔟之间的相似度有很多种方法，那么主要是包含单链的方法，全链的方法，中心链的方法和以及基于一些标函数的方法，那么分别介绍一下。
（1）、单链计算方法
首先看一下单链的计算方法，那么单链的计算方法指的是两个蔟的相似性或者是两个蔟的距离可以用这两个蔟中离得最近的两个数据对象之间的相似度或者是距离来代表。
那么，这种单链的相似度测量方法，它的一个缺点是，这种相似性度量方法是基于局部的，它只考虑了两个蔟离得比较近的区域。两个蔟的全体结构是被忽略，其次至于单链的，这种相似性度量方法，它对于噪音和异常点是很敏感的，它只关心的是离得两个比较近的点，那比如离得两个比较近的点，其中有一个点是异常点，那么这样一个单链就会影响这两个蔟的相似度。
（2）、全链相似度计算方法
再看一下全链的相似度计算方法。所谓全链的计算方法，它指的是两个蔟的相似度或距离，用这两个蔟中离得最远的这两个数据对象的相似度或者是距离来代表。和单链的相似度度量方法一样，全链的都相似性度量方法，它对噪音依然是很敏感的，但是如果使用全练的相似度度量方法，它产生的蔟的一个趋势是，它比较喜欢产生比较紧凑的蔟，因为会选这相似度比较高的，也就意味着这两个蔟的整体距离是比较近的。
（3）、组平均相似度测量方法
那么，第三种相似度测量方法，把它称之为叫做组平均。至于组平均的相似度测量方法，主要指的是这两个蔟的相似度或者是距离，是用这两个蔟的所有点对的相似度的平均值或距离的平均值来代表。对于主平均这种相似度测量方法来说，它能够很好的避免异常点的影响，但是它的计算复杂度比较高。
（4）、中心链相似度测量方法
此外，还有这种中心链，也就是两个蔟的相似度或距离，由这两个蔟的原型一般可以用它的中心点来代表，就是由这两个蔟的中心点的距离和相似度来代表。
（5）、目标函数的定义相似度测量方法
此外，还可以用一些。目标函数的定义来定义相似度测量方法，比如说沃德方法，在沃德方法中两个粗的相似性，可以理解为合并这两个蔟对 sse 的降低程度。那么，基于沃德方法的相似度度量方法，它其实和组平均的方法是比较接近的，这种方法它对于噪音和异常点是有比较强的容忍，而且，它比较倾向于去产生一些球形的蔟。
三、基于划分的层次聚类
在介绍完基于凝聚的层次聚类算法之后，介绍一下基于划分的层次聚类。基于划分的层次聚类和基于凝聚的层次聚类过程刚好相反，那么用下图介绍它的过程。
首先所有的数据对象是属于同一个蔟，然后可以选择一个分裂准则，将这个蔟一分为二。在得到若干个蔟之后，可以选择对 sse 贡献最大的这个蔟，再把这个蔟一分为二，那么一直分裂，一直到所有的数据对象全部被分裂，就是每一个数据对象构成一个蔟为止。
四、层次聚类算法的特点
最后总结一下层次聚类算法的特点。
1.一旦合并，无法撤销
在层次聚类算法中，它的一个缺点就是，一旦划分或者一个凝聚动作完成，那么这个过程它是不可逆转的，于是，一旦一个决定被执行，如果产生了大量的误差，这个误差，这个误差是会累积的。
2.没有直接全局最小化
那么其次，聚类中每次凝聚或者是分裂的时候，就是基于一个局部最优策略的，所以说，它是缺乏全局优化的。
3.不同计划下不同问题
因为在层次聚类算法中使用到了各种不同的相似度度量方法，因为这些度量方法的缺陷可能会导致层次聚类算法，它有可能会对异常点噪音敏感，甚至不能够蔟理这样的一个不同尺寸和非蔟状的蔟，那么有可能，它还会倾向于去把一些大的蔟进行分裂。这个就是关于层次聚类算法的缺点。
关于层次聚类算法，就介绍到这里。
