人工智能基础知识笔记四聚类分析
人工智能基础知识笔记四：聚类分析
1、什么是聚类分析？
聚类分析是一种将数据分组的技术，目的是让同一组内的数据点彼此相似，而不同组之间的数据点差异较大。你可以把它想象成整理一堆杂乱无章的物品，把相似的物品放在一起，比如把书放在一个书架，衣服放在衣柜里。聚类分析就是通过算法自动完成这种分类，帮助我们更好地理解数据的结构和模式。
聚类分析分为两种，分类和聚类。
分类：是指已经事先了解事物类别的概念和特性，对未知事物按照已知事物特性将其归入某一类。分类学习主要是监督学习。
聚类：是指事先不了解任何事物类别的知识，只是针对相近或者相似程度，将未知事物归到集中分类中。从统计学角度而言，聚类就是将事物的一些样本数据集合分割成几个簇或者子集，每个类中的数据都具有很大的相似性，不同类别的数据拥有尽可能小的相似性。聚类学些主要是无监督学习。
2、距离和相似性
聚类分析依赖于样本数据的接近程度(距离)或对相似程度的理解或度量。对样本数据，定义不同的距离度量和相似性度量会产生不同的聚类结果。下面来看几种常见的距离和相似性度量公式。
2.1、欧氏距离(Euclidean Distance Metric )
欧氏距离是数学上最常见的距离公式之一，可以简单地描述为多维空间中点与点之间的几何距离。欧氏距离的公式如下所示：
式中，n表示样本数据的维度，Xi、Yi分别表示样本数据的数据分量。
如果样本数据用的是相同的量纲，使用欧氏距离公式能较好地描述样本的相似性。
2.2、曼哈顿距离(Manhattan Distance )
相比欧式距离描述了多维空间中点与点之间的直线距离，曼哈顿距离是计算从一个点到另一个点所经过的折线距离，有时也进一步地描述为多维空间中点坐标在各维的平均差，取平均差之后的计算公式如下所示：
式中，n表示样本数据的维度，Xi、Yi 分别表示样本数据的数据分量，公式中，曼哈顿距离取消了欧氏距离中的平方操作，使得一些离群点的影响会相对减弱。
2.3、闵可夫斯基距离(Minkowski Distance )
对于高维数据，闵可夫斯基距离是一种更加流行的距离度量方法，其公式如下所示：
式中，n代表数据的维度，Xi、Yi 分别表示样本数据的数据分量，p是待选的指数，如果p=1，闵可夫斯基距离变为曼哈顿距离;如果p=2，则闵可夫斯基距离变为欧氏距离。
2.4、 相关性及相关距离
相关距离即样本数据之间的相关性，可以用皮尔森相关系数进行度量。其公式如下所示：
式中，n代表数据的维度，Xi、Yi 分别表示样本数据的数据分量。
通过皮尔森相关系数，可以度量样本数据之间的线性相关性，相关系数取值为[-1,1]，取值越表示相关性越强。可以用
表示相关距离，当相关性增强时，相关系数增加，相关距离会减小，趋向于0。
3、聚类分析的类型
聚类分析从不同的角度有多种分类方法，例如从聚类方法的嵌套性上可以分成基于划分的聚类和基于层次的聚类;从聚类方法的准确性上可以分成精确分类、模糊分类;从分类方法的完全性上，可以分成完全聚类、部分聚类等。本节主要从簇的特性上，介绍聚类的几种常见类型。
3.1、基于原型的聚类(Prototype-Based Clusters)
原型一般指样本空间中一些具有代表性的点。在原型聚类中，属于某一簇的数据与定义这一簇的原型的点具有更近的距离或更大的相似性，而与属于其他簇的原型点具有较远的距离或较小的相似性。对于连续性数据，代表原型的点一般是簇的质点;对于类别数据，质点没有意义，这时候原型表示簇中最有代表性的中间数据;对于其他类型数据，可以将原型看作中间点，这时候的聚类称为基于原型的聚类，也可以称为基于中心的聚类(Center-BasedClusters)。
对于原型聚类算法的实现，通常要先对原型进行初始化，确定每个簇的中心点，然后计算属于每个簇的数据点划分，最后根据新计算的簇，计算更新后的中心点。不断迭代以上过程，直至中心点的变化很小或不再变化。
3.2、基于图的聚类(Graph-Based Clusters)
基于图的聚类是以图论为基础，将聚类问题转化为图的最优划分问题。可以将数据作为图的结点，结点之间的连接表示数据之间的连接，这时一个簇可以看作一些连接的数据对象。在基于图的聚类中，簇内的数据对象相互连接，簇之间的对象间没有连接。基于邻域的聚类就是一种重要的图聚类。在基于邻域的聚类中，只有两个数据点之间的距离小于某个特定值时，这两个对象之间才有连接，它们也被划到同一簇中。这样，在同一个基于邻域的簇中，数据点之间的距离要远小于数据点和另一个簇中的点的距离。
3.3、基于密度的聚类(Density-Based Clusters)
基于密度的聚类就是利用点的密度作为聚类依据。所谓点的密度，就是以这个点作为圆心，以某个值作为半径构成的邻域内点的个数。如果邻域内点的个数高于某个值，称之为高密度点;反之，称之为低密度点。基于密度的聚类方法的指导思想是将空间中密度大于某一阈值的点尽可能地归入一个聚类中。例如，将距离小于邻域半径的高密度点相连，就构成了簇的核心点，与核心点距离小于邻域半径的低密度点为簇的边界点。
4、聚类分析的 算法
4.1 层次聚类
层次聚类法是将相近的有关联的点聚合成簇，产生一个分层次的聚类树。从聚类的特点上看部分的层次聚类方法有图聚类的特性，另一部分的层次聚类法有原型聚类的特性。
该算法出现于1963年，其指导思想是对给定的待聚类数据集合进行层次化分解。具体而言，层次聚类是通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中，不同类别的原始数据点是树的最低层，树的中间结点是聚合的一些簇，树的根结点对应多数据点的聚类。下图是根据原始数据点进行层次聚类得到的一棵具体的聚类树。
4.1.1 层次聚类的 优点
1、 无需预先指定聚类数量：
与K-means等算法不同，层次聚类不需要事先确定聚类的数量，结果可以通过树状图（ dendrogram ）直观展示，用户可以根据需要选择合适的聚类数量。
2、可视化能力强：
层次聚类生成的树状图可以清晰地展示数据点之间的层次关系，帮助用户理解数据的结构。
3、适用于小规模数据：
对于小规模数据集，层次聚类效果较好，能够捕捉到数据中的细节和层次关系。
4、灵活性高：
层次聚类可以基于不同的距离度量（如欧氏距离、曼哈顿距离等）和链接方法（如单链接、全链接、平均链接等），适应不同的数据特性。
4.1.2 层次聚类的 缺点
1、计算复杂度高：
层次聚类的计算复杂度较高，尤其是对于大规模数据集，时间和内存消耗会显著增加，因此不适合处理大规模数据。
2、对噪声和异常值敏感：
层次聚类对噪声和异常值比较敏感，可能会影响聚类结果的质量。
3、不可逆性：
一旦聚类完成，如果发现结果不理想，无法直接调整，通常需要重新运行算法。
4、结果解释依赖主观判断：
虽然树状图提供了直观的层次结构，但最终选择多少个聚类仍然需要人工判断，可能存在主观性。
4.2 K-Means 聚类
K-Means 聚类方法是一种基于原型的聚类方法。与层次聚类不同的是，它是根据预先设定的质心(原型的一种)来对数据样本点进行单一层次的聚类。
4.2.1 K-Means 聚类的 优点
K-Means 聚类是一种常见的聚类方法，它的优点是简单、快速，适合常规数据集。
4.2.2 K-Means 聚类的 缺点
(1)K值确定困难。K值代表了期望将原始数据点分成几个簇,K值的选择对最终的聚类结果影响很大。随机选择K值，有时会带来一些问题。
(2)初始质心的确定会影响聚类结果的稳定性。随机选择初始质心，聚类过程并不一定会收敛到同一结果。
(3)对任意形状的簇，聚类效果不佳。例如对于环形的带状点集，质心无法代表点集，聚类效果很差。
4.3 DBSCAN 聚类原理
DBSCAN(Density-Based Spatial Clustering ofApplications with Noise)聚类是基于密度的一种聚类方法。DBSCAN的主要思想是将数据点的分布看成是连续的。数据点分布密集的区域，拥有较高的密度;数据点分布稀疏的区域，拥有较低的密度;在数据集中寻找被低密度区域分离的高密度区域这些高密度的点集就形成了聚类。
4.3.1、DBSCAN 的优点
(1)不需要事先指定簇的个数。原始数据分成多少个簇，是由算法根据数据点的特性生
成的。
- 可以发现任意形状的簇。算法采用密度可达的方法，逐步对簇进行扩展，因此对的形状没有要求。这一点是K-Means 算法所不具备的。
- 擅长发现离群点(异常点)。异常点在DBSCAN中实际上被判定为噪声点，不归人任何一个簇，也不会影响最终结果。但在其他算法中，如层次聚类、K-Means 中，离群点会被当做正常数据点来看待，会对聚类结果产生不良的影响。
4.3.2、DBSCAN的 缺点
(1)参数选择困难。DBSCAN的参数对结果的影响很大，目前参数选择没有特别有效的方法。当然，聚类方法属于无监督分类，所有涉及的参数选择都会很困难。
(2)效率相对较低。DBSCAN算法需要对每个数据点的邻域中的点进行计算，局部区域内数据点之间的距离要重复计算比对多次，降低了算法效率。
(3)对于高维数据集，效率相对较低，参数选择难度大。