点击上方卡片链接就可以进入专栏，专栏右上角有订阅选项，欢迎大家订阅～

前言

大家好，我是鬼仔，今天带来《机器学习高频面试题详解》专栏的第2章无监督学习里的第1节：聚类算法-层次聚类。这是鬼仔第一次开设专栏，每篇文章鬼仔都会用心认真编写，希望能将每个知识点讲透、讲深，帮助同学们系统性地学习和掌握机器学习中的基础知识，希望大家能多多支持鬼仔的专栏～

目前这篇是试读，后续的文章需要订阅才能查看哦，专栏预计更新30+篇文章（只增不减），具体内容可以看专栏介绍，大家的支持是鬼仔更新的动力！

一、原理

1. 聚类问题

聚类问题，通常是指对一个未被标记的数据集进行分类，使得相似的数据点被分组到同一个簇中，而不同的簇中的数据点应该尽可能地不相似。聚类问题的优化目标是最大化簇内的相似度和最小化簇间的相似度，常用的度量方式包括欧几里得距离、曼哈顿距离、闵可夫斯基距离等。

聚类问题根据簇的数量以及输入数据的标注信息，可以细分为软聚类和硬聚类。软聚类指的是对于一个数据点，它可以被划分至不同的簇中，并给出其属于每个簇的概率。常见的软聚类算法包括 Fuzzy C-Means 算法、模糊聚类、混合高斯模型等。相反，硬聚类则是将每个数据点划分为唯一的一个簇。常见的硬聚类算法包括 k-Means、层次聚类、DBSCAN 等。

聚类问题在数据挖掘、机器学习、图像处理等领域广泛应用。例如，在图像处理中，可以利用聚类算法对图像中的像素进行分组，从而实现图像分割、边缘检测等操作。在机器学习中，聚类算法可以作为特征提取的预处理步骤，从而提高模型的性能。

1.1 样本点距离

在聚类算法中选择合适的样本点距离（即相似度）计算方式是十分重要的，因为相似度的不同计算方式会对聚类结果产生不同的影响。以下是选择相似度计算方式时需要考虑的几个因素：

1）数据类型：不同类型的数据使用不同的相似度计算方法。比如，文本数据可以使用余弦相似度进行度量，而数值型数据可以使用欧氏距离或曼哈顿距离进行度量。

2）特征数量：不同的相似度计算方法对特征数量的敏感程度有所不同。比如，当特征数量很大时，余弦相似度比欧氏距离更加适用。

3）噪声数据：某些相似度计算方法对噪声数据更加敏感，而有些则可以很好的过滤噪声数据。因此在存在噪声数据的情况下需要根据实际情况选择相应的相似度计算方法。

4）数据分布：某些相似度计算方法对数据分布的敏感程度不同。比如，当数据分布比较密集时，欧氏距离比曼哈顿距离更适用。

总之，需要根据具体情况选择最合适的相似度计算方法。在实际应用中，一般需要尝试不同的相似度计算方法，比较它们的聚类效果和效率，从而选出最优的相似度计算方法。

1.2 类间距离

据点划分到同一个簇中，不相似的数据点划分到不同的簇中，所以类间距离通常被用来度量聚类的效果。

常见的类间距离度量方法包括以下几种：

1）最短距离法（单链接法）：将两个簇中距离最近的两个数据点之间的距离作为两个簇之间的距离。

2）最长距离法（完全链接法）：将两个簇中距离最远的两个数据点之间的距离作为两个簇之间的距离。

3）类平均法：将两个簇的所有数据点之间距离的平均值作为两个簇之间的距离。

4）中心法：将两个簇的中心点之间的距离作为两个簇之间的距离。

其中，最短距离法和最长距离法是最常用的两种类间距离度量方式。不同的类间距离度量方法适用于不同类型的数据及聚类算法，正确选择合适的类间距离度量方法可以得到更加准确的聚类结果。

2. 层次聚类

这篇文章主要讲解基于连接的聚类方法：层次聚类（Hierarchical Clustering），如下图所示：

层次聚类是一种将数据对象按照相似度进行层次化结构表示的聚类方法，最终构建出一颗嵌套聚类树。在聚类树中，不同类别的原始数据点是树的最低层，树的顶层是一个聚类的根节点