模式识别及Python实现 课件 第7章 聚类分析

PPT下载/xiazai/第七章:聚类分析模式识别及Python实现前言PREFACE前几章主要讨论了数据集中样本类别已知情况下的分类器设计，这些方法都属于有监督学习的范畴。一般来说，有监督模式识别往往需要提供大量已知类别的样本，但是，在很多实际情况中，这是有困难的。此时，如何根据给定的未知标签的数据集实现对测试样本的正确分类是一个值得关注的问题。这就是非监督模式识别的问题，聚类问题属于一种典型的非监督模式识别问题，聚类问题所用的方法叫做聚类分析方法。本章主要讲述聚类分析方法中的典型方法，包括基于模型的方法、基于密度的方法、动态聚类方法以及分级聚类方法。在讲述聚类方法的同时，也会讲述聚类方法用到的距离相似性度量和聚类准则等概念。123基于模型的方法动态聚类方法基于密度的聚类算法目录

CONTENT4分级聚类方法PART

1基于模型的方法PART01​​Model-BasedMethod​​如果事先已经知道样本在特征空间的概率分布，那么可以使用基于模型的方法来解决聚类问题。基于模型的方法有很多种，本节主要讲述比较常用的单峰子集分离的方法。左图是一个样本数据集的密度分布形式，根据密度分布图可以看到这个样本集中的数据在特征空间中大多是集中到两个峰值附近，对于这种聚类问题，通过单峰子集分离的方法可以从两个单峰的中间把样本数据分为两类。示例中样本数据的特征只有一维，单峰子集的寻找比较容易。如果样本数据的特征是高维，则相对比较困难，因此人们通常使用投影的方法，将样本数据根据某种准则投影到一维坐标上，然后在一维上寻找单峰，再使用单峰子集分离的方法解决聚类问题。单峰子集实例图

例7.1设样本分布在下图中的A，B，C三个子集中，请使用单峰子集分离的方法完成聚类划分。

PART

2动态聚类方法PART02DynamicClusteringMethod​​如果事先不知道样本在特征空间的概率分布，那么就无法使用上一节所讲的基于模型的方法。此时，需要使用其他聚类方法来解决聚类问题。动态聚类方法是实际中被普遍采用的一种聚类方法，动态聚类方法一般具备以下三个要点：（1）选定某种距离度量作为样本间的相似性度量。（2）确定某个评价聚类结果质量的准则函数。（3）给定某个初始分类，然后用迭代算法找出使准则函数取得极值的最好聚类结果。

例7.2 下图为一样本集的样本分布情况，试用C均值算法进行聚类，c为2。

PART

3基于密度的聚类算法PART03Density-BasedClusteringAlgorithm​​

1.DBSCAN算法DBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise，具有噪声的基于密度的聚类方法）是一种基于密度的空间聚类算法。该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇，它将簇定义为密度相连的点的最大集合。具体步骤如下：（1）在样本中随机选择一个点。规定圆的半径Eps和圆内最少样本个数MinPts，如果在指定半径Eps的圆内有足够多（≥MinPts）的样本点，那么认为圆心是某一簇的点；如果圆内样本点的个数小于MinPts，则被标记为噪声点。（2）将临近点作为种子点，遍历所有的种子点，如果该点被标记为噪声点，则重新标记为聚类点；如果该点没有被标记过，则标记为聚类点。并且以该点为中心，Eps为半径画圆，如果圆内点数大于等于MinPts，则将圆内的点添加到种子点中（被添加过的点需要重复添加）。（3）重复步骤（2），直到全部种子点被遍历完。（4）标记完一簇以后，重新寻找一个未被标记的点，开始新一轮的聚类。DBSCAN算法需要手动输入两个参数：半径Eps和以Eps为半径的圆内最小样本数MinPts。DBSCAN算法优点和缺点如下：【算法优点】（1）不需要输入聚类个数，可以对任意形状的稠密数据集进行聚类。（2）可以在聚类的同时发现噪声。【算法缺点】（1）当样本集的密度不均匀、聚类间距相差很大时，聚类质量较差，则不适合使用DBSCAN算法进行聚类。（2）当样本集较大时，聚类收敛时间较长。（3）调参相对于传统的K-Means之类的聚类算法稍复杂，主要需要对距离阈值R，邻域样本数阈值MinPts联合调参，不同的参数组合对最后的聚类效果有较大影响。2.增量DBSCAN聚类算法当移动对象轨迹数据呈非均匀分布特性时，采用基于密度的聚类方法较为合适。传统DBSCAN算法是一种基于密度的聚类算法，因具有较强的抗噪声干扰和发现任意形状聚簇等优点而广受欢迎。当面对海量的移动对象的轨迹数据时，传统DBSCAN算法具有较高的复杂度。对于新增数据，传统DBSCAN算法会对整个数据集进行重新聚类，从而无法利用现有的聚类结果，造成极大的资源浪费。为了提高传统DBSCAN算法的聚类质量和聚类效率，可以使用增量DBSCAN算法，该类算法通过增量聚类来实时动态地更新聚类结果，具有更广泛的应用场景。DBSCAN算法的目的在于查找密度相连的最大对象集合，其基本思想是通过遍历集合中的每个点对象来生成簇。对于新增数据，增量DBSCAN聚类算法得到的结果，与用传统DBSCAN算法重新聚类得到的结果是一样的，这就是增量DBSCAN聚类算法的等价性。具有等价性是增量DBSCAN聚类算法，较之于其他增量聚类算法的最大优点。

针对原始聚类局部集的不同变化，对新增数据和现有数据进行相应的增量处理，直至增量数据集Δx中所有数据处理完成。对于增量数据集的插入，增量DBSCAN聚类算法可能出现的四种情况具体如下：（1）添加噪声点

插入数据对象x后，若，则x成为噪声点，初始聚类数据的聚类状态保持不变。因为新增数据x的插入，没有对其Eps邻域内的原有数据造成影响，如图(a)所示，插入对象x后，初始聚类集没有发生任何变化，所以x为噪声。（2）形成新的类簇

插入数据对象x后，若，且，则对象P在x插入之前为噪声点，x插入之后，P成为核心对象，且P不属于任何一个现有的类簇。在密度可达的对象里不存在已有类簇的核心对象时，将创建一个新类。如图(b)，插入x之前，P不满足核心对象的条件，x的插入使P成为核心对象。（3）归入现有类簇

插入数据对象x后，若，且所包含的全部核心对象在x插入之前属于同一类簇，如图(c)所示，则增量数据对象x刚好归入该类簇。此外，还有另外一种特殊情况：所包含的核心对象来自于不同的类簇，当x插入之后，不同类簇间依然密度不可达，如图(d)所示，则增量数据对象x在类簇C1和C2中选择其中一个归入。（4）合并多个类簇

插入数据对象x后，若，且所包含的核心对象属于不同的类簇，由于x的插入，这些包含不同核心对象的不同类簇成为密度可达，则将这些密度可达的类簇合并为一个新簇。2、删除一个对象虽然在增量聚类中，大部分情况下只会插入数据，但删除数据同样会引起初始聚类集的变化。下面讨论当删除一个初始聚类集中的对象x时，初始聚类结果集的变化情况。当删除一个数据对象x时，初始聚类结构也可能出现四种情况：噪声、当前类簇被撤销、减少当前类簇中的对象、当前类簇分裂。针对这四种不同情况的处理如下：（1）噪声

如果被删除对象x是一个噪声，则直接删除，其他数据对象保持不变。（2）当前类簇被撤销

当一个数据对象x被删除，若，且x在删除前是一个核心对象，同时x的Eps邻域内不存在其它核心对象，则删除x的同时，将邻域内的其他对象标记为噪声。（3）减少当前类簇中的对象

当一个数据对象x被删除，若，且x的Eps邻域内的核心对象互相密度可达，则删除x后，一部分对象仍然属于这个类簇，而另一部分对象被标记为噪声。（4）当前类簇分裂

当一个数据对象x被删除，若，且x的Eps邻域内不存在能够相互直接密度可达的核心对象，同时也不能与其他类簇核心对象彼此密度直接可达，则该类簇将被分为多个类簇。3.KANN-DBSCAN传统的DBSCAN算法需要人为确定Eps和MinPts参数，参数的选择直接决定了聚类结果的合理性，因此提出了一种新的自适应确定DBSCAN算法参数的算法，即KANN-DBSCAN算法，该算法基于参数寻优策略，通过利用数据集自身分布特性生成候选Eps和MinPts参数，自动寻找聚类结果的簇数变化稳定区间，并将该区间中密度阈值最少时所对应Eps和MinPts参数作为最优参数。KANN-DBSCAN算法的具体步骤如下：（1）输入数据集，求数据集每个样本的K-最近邻距离；（2）求K-平均最近邻距离作为Eps；（3）求所有样本Eps范围内的样本点数，并求数学期望作为MinPts；（4）求密度阈值；（5）将成对的参数输入DBSCAN寻找最优簇数；（6）选择簇数为N时对应的最大K数作为最优K数。4.VDBSCAN算法传统的密度聚类算法不能识别并聚类多个不同密度的簇，对此提出了变密度聚类算法VDBSCAN，针对密度不稳定的数据集，可有效识别并同时聚类不同密度的簇，避免合并和遗漏。基本思想是根据k-dist图和DK分析，对数据集中的不同密度层次自动选择一组Eps和MinPts值，分别调用DBSCAN算法。PART

4分级聚类方法PART04HierarchicalClusteringMethod​​

分级聚类方法也叫做层次聚类方法，同样是聚类分析方法中比较常见的一种方法。层次聚类分为凝聚式层次聚类和分裂式层次聚类。在ISODATA算法中，我们了解到了分裂和合并操作。在分级聚类方法中，也有分裂和合并操作。凝聚式层次聚类，在初始阶段将每一个样本点都视为一个类，之后每次合并两个距离最近的类，直到所有样本被合并到两个类中。分裂式层次聚类，在初始阶段将整个样本集视为一个类，之后每次分裂出一个类，直到最后剩下单个点的类为止。分级聚类的步骤很简单，这里主要阐述分裂式层次聚类的算法步骤：（1）初始阶段，每个样本形成一个类。（2）执行合并操作，计算任意两个类之间的距离，把距离最小的两个类合并为一类，记录下这两个类之间的距离，其余类保持不变。（3）判断是否所有的样本被合并到两个类中，若是则结束，否则转步骤（2）。通常使用聚类树，也叫做系统树图来描述分级聚类的结果，如左图下半部分所示。图中A，B，C等均为样本，两个样本合并则把两个节点用树枝连起来，树枝的长度