【机器学习】层次聚类

本文介绍了层次聚类算法。首先抛出了聚类理论中两个关键问题：何为类，何为相似，同时介绍了聚类中常用两种评价指标：内部指标和外部指标。然后介绍了层次聚类算法：凝聚层次聚类和分裂层次聚类算法，两者皆以样本集作为类表示，常用欧式距离作为相似性度量，分层次聚类。最后介绍了层次聚类算法的特点，可视化，复杂度。

作者 | 文杰

编辑 | yuquanle

聚类理论

一般来说，聚类是在训练样本的标签信息不知的情况下，学习样本内在的性质和规律，将有限的集合划分成类。

根据“方以类聚，物以群分”的思想，类内对象尽可能的相似，类间对象尽可能不相似。因此，吾师言：聚类中两个关键的问题是：何为类？何为类内相似，类间不相似？以下所有的聚类模型皆从这两点出发。

由于缺少样本标签，我们很难定义类和相似性，比如下面的问题：

按照颜色聚类可以分类三类，按照形状聚类可以分类两类，关键问题在于如何定义类，定义相似性。所以吾师还言：聚类一般不是一个任务的最终目标，而是一个预处理的过程。

聚类的评价指标有两种：

可以看出，外部指标有很大的问题，那就是聚类学到的数据规律不一定是标签，这对聚类算法的评价是不可靠的，但是对于只看结果，不评价模型的好坏是可以的，当然拿聚类的结果与有监督学习的结果对比是“无赖”的。

层次聚类的类表示可以看作是基于样本的，表示属于第的样本集合，即作为第类的类表示。类相似性度量可以用“欧式距离”。

层次聚类分为两种，一种是自底向上的凝聚层次聚类，一种是自顶向下的分裂层次聚类。两者的区别在于前者一开始将每一个样本看作一类，通过不断的合并最相似的两个簇，直到类；后者一开始将所有样本看作一类，通过最小化损失（类紧致）分裂为类。

输入：样本数据，相似性度量函数，聚类簇数

输出：类样本

1）初始化每个样本为一个簇:

2）计算样本两两之间的距离:

3）通过相似性度量函数，找出最相似的两个簇进行合并：

最小距离：

最大距离：

平均距离：

4)直到簇数为，否则循环2）

输入：样本数据，损失函数，聚类簇数

输出：类样本

1）初始化所有样本为一个簇:

2）计算样本两两之间的距离:

3）计算当前所有簇，的损失函数，选择损失最大的簇进行二分，计算该簇下两点间距离：

选择簇中最远的两个点作为类中心将簇进行二分;

4)直到簇数为，否则循环2）

值得注意的是分裂层次聚类在进行二分时，可以采用kmeans进行二分，这样时间复杂度就不再是.

层次聚类算法特点：

The End

0 人点赞