模式识别与数据挖掘 课件 第7章-聚类

第七章

聚类主讲人：某某某PatternRecognitionandDataMining模式识别与数据挖掘目录Contents引言Introduction基本概念BasicConceptsk均值聚类算法K-meansClusteringAlgorithmDBSCAN聚类算法DBSCANClusteringAlgorithm01020304聚类效果的评估ClusteringEvaluation小结与讨论SummaryandDiscussion0607层次聚类算法HierarchicalClusteringAlgorithm05引言Introduction01引言聚类算法本章介绍的聚类与分类器不同,它是无监督学习的一种方法,在处理数据前,并没有预先定义好的类别标签,目标是把相似的东西分到一组。本章将系统探讨聚类分析的核心算法与效果评估。学习内容首先，我们将深入研究经典的k均值聚类算法，理解其基于中心点的划分策略与优化机制；接着探索DBSCAN算法的密度聚类思想，学习其如何发现任意形状的簇并识别噪声点；然后，我们将审视层次聚类算法的自底向上或自顶向下构建过程，观察簇结构的层次化形成。最后，我们将学习如何客观评价聚类效果，掌握内部指标与外部指标相结合的评估体系。基本概念02BasicConcepts基本概念基础术语定义01簇簇是数据点的集合,簇内的数据点之间具有高度的相似性,簇与簇之间应具有较大的区别,即一个簇中的任何数据点与属于其他簇的数据点相比,应具有较大的距离。02簇心每个簇会关联一个中心点,我们称之为簇心。簇心有两种常见的选取方式,一种是选取簇中所有点的均值位置作为簇心，它不一定是簇中的实际数据点;另一种是选择簇中的中心点，对应簇中某个数据点并且簇内所有点到该中心点的距离之和最小。03距离函数为了把相似的物体聚成一个一个的簇,聚类算法通常需要一种方法来衡量数据点之间的相似性或距离，常用的数据相似性或者距离函数,包括欧氏距离、曼哈顿距离、余弦相似性等。基本概念基础术语定义04例子按照数据点之间的距离远近,直观上可以把数据分成两个聚类,对应黑色和蓝色的两个簇。相同颜色的数据点互相距离接近,不同颜色的数据点之间距离较大。簇中的⋆表示计算后各自的簇心。k均值聚类算法03K-meansClusteringAlgorithmk均值聚类算法k均值聚类(k-meansclustering)算法是一种迭代求解的聚类分析方法。在用户给定参数k后,该算法的目标是将数据集中的对象分组成k个聚类,以确保聚类内的相似性最大化,聚类间的相似性最小化。k均值聚类是迄今为止应用最广泛的聚类算法,被评为数据挖掘十大经典算法之一。算法思想k均值聚类根据数据相似性来对数据进行簇的划分,它包含的参数k是由用户预先设定的,它直接决定了最后生成的聚类数目,并且每个数据点最终只属于其中一个簇。根据数据相似性对样本进行簇划分，需预先指定簇数k每个数据点只属于一个簇，k决定最终聚类数量随机选择k个样本作为初始聚类中心通过迭代不断更新样本分配与聚类中心，直至收敛实现过程k均值聚类算法算法流程首先,随机选择两个初始点记为两簇的初始中心点,即⋆标志。对于每个数据点,计算它到当前两个簇心的距离,选出距离最近的簇心,将该数据点分配到对应的聚类中。形成黑和蓝色两个初始聚类结果。在每一个点都分配到初始聚类后,此时聚类的中心点跟上一步随机初始化的中心点相比,已经发生偏移,需要重新计算。重新计算所有蓝色点的平均值以及所有黑色点的平均值,得到两个新的中心点。k均值聚类算法算法流程示例以数据集S为例,逐步拆解k均值聚类算法的运行过程k均值聚类算法算法流程示例由于中心点发生变更,需要重新计算每个点到新的中心点距离,重新分配聚类结果。有不少顶点发生颜色变化,表示这些点的聚类结果发生更新。以此类推,需要迭代地执行更新中心点以及更新聚类结果两个操作。由于聚类结果发生变化,重新计算两个新的聚类的中心点。k均值聚类算法算法流程示例根据新的中心点重新分配聚类结果,此时得到的两个簇已经基本满足理想的聚类状态,即相近的顶点尽可能落在同一个聚类当中。当继续迭代更新聚类中心点的时候,发现中心点的位置已不再发生变化,表明此时k均值聚类算法已经收敛,可以终止算法并返回最终聚类结果。k均值聚类算法算法收敛性对于有n个数据点的数据集{x1,x2,···,xn},k均值聚类算法期望的簇数量为k个簇为C1,C2,···,Ck,对应的簇心为µ1,µ2,···,µk。考虑算法的目标函数—簇内误差平方和(within-clustersumofsquarederror,WCSS):在每次迭代中：样本重新分配不会增加WCSS在簇划分不变时，簇心取簇内样本均值可使WSS最小因此，算法迭代过程中WCSS单调递减且下界为0根据单调收敛定理，k-means算法必然收敛但收敛结果可能为局部最优解，不保证全局最优证明过程k均值聚类算法算法局限性抗噪声弱初始化敏感需预定义k对离群点和噪声数据敏感，异常点会影响簇心位置。对初始聚类中心敏感，容易陷入局部最优，结果不稳定。需要预先指定簇数k，在缺乏先验知识时难以确定。DBSCAN聚类算法04DBSCANClusteringAlgorithmDBSCAN聚类算法DBSCAN(density-basedspatialclusteringofapplicationswithnoise)是一种基于密度的聚类算法,通过对数据空间中的密度区域进行识别和连接,将高密度区域划分为同一类。DBSCAN聚类不需要事先指定聚类的数量,而是通过数据集内部的密度关系自动确定聚类。其次,与基于距离的聚类算法相比,DBSCAN能够发现任何形状的聚类,并且对噪声和异常值具有较强的鲁棒性。算法思想核心点如果一个点的ε-邻域内至少有MinPts个点(包括点本身),这个点被标记为核心点。边界点如果一个点自身邻域内的点数量小于MinPts,且位于某个核心点的邻域内,这个点被标记为边界点。噪声点既不是核心点也不是边界点的其他所有点被视为噪声点。DBSCAN聚类算法直接密度可达给定两个点p和点q,我们称它们直接密度可达,如果p在q的ε-邻域内,p和q都是核心点。给定两个点p和q,如果存在一个点链p1,p2,p3,···,pn,其中p1=p且pn=q,满足对于其中任意一个点pi+1,都与点pi直接密度可达,那么点p是点q密度可达的。在DBSCAN算法中,密度相连的点会被划分到同一个聚类中给DBSCAN算法的基本思想是在一个指定的数据集中,从任何一个数据点开始,探索其周围邻域内的其他数据点。算法首先检查这些邻近点中是否包含核心点或边界点。如果找到核心点,该点会与其邻域内的点通过连线组成一条链。这条链上的所有点随后被归类为同一个簇。这个过程不断重复,逐步将数据点分组,直到所有的点都被访问并分配到某个聚类当中。DBSCAN聚类算法算法流程对每个数据点计算其ε-邻域，判断是否为核心点；以未分配的核心点为起点，创建新聚类并向外扩展；将与核心点直接或间接密度可达的点加入同一聚类；位于核心点邻域内的边界点并入对应聚类；既非核心点也非边界点的样本标记为噪声点；所有数据点完成分类后，算法终止。DBSCAN聚类算法算法流程示例随机选取一个点A,以点A为圆心,以ε为半径作圆,圆中仅有一个点,不满足MinPts=3的阈值要求。因此,将点A标记为噪声点。随机选择一个未访问过的点B,同样以B为圆心,以ε为半径作圆。圆中有B、C、E和F四个点,满足最小阈值要求。因此认定B为某一簇的点,将B标记为蓝色,且扩展聚类的种子点集N={B,C,E,F}。点集S中共有8个点,每个点的邻域大小为ε,密集区域的密度阈值为MinPts。DBSCAN聚类算法算法流程示例扩展聚类。B的下一个种子点为C,C没有被标记过,则标记为聚类点。以点C为圆心,以ε为半径作圆,计算圆内的点数。圆内点数满足MinPts阈值要求,C同样为核心对象。以C圆心的圆内有B、C、D、E,其中D在点集N中,将D加入N。与上一步中点C的操作类似,将E标记为该簇的点,以点E为圆心,以ε为半径作圆,圆中无新种子点产生。对点F做同样处理,将F标记为该簇的点,以点D为圆心,以ε为半径作圆。圆中有四个点,将其中未被标记的点G也加入点集N中。DBSCAN聚类算法算法流程示例继续遍历点集N,将D标记为该簇的点,以点D为圆心,以ε为半径作圆,圆中仅有C和D两个点,不满足MinPts=3的阈值要求,无新种子点产生。访问点集N中最后一个点G,将G标记为该簇的点,作圆,圆中仅有两个点,不满足MinPts=3的阈值要求,无新种子点产生。点集N已空,表明该簇的扩展结束。访问最后一个点H,作圆,圆中仅有点H,不满足MinPts=3的阈值要求,标记为噪声点。综上,点集S中所有点均已访问,在MinPts=3的条件下,最终形成有1个簇{B,C,D,E,F,G},以及两个噪声点A和H。层次聚类算法05HierarchicalClusteringAlgorithm层次聚类算法算法分类层次聚类(hierarchicalclustering)能够揭示数据的自然层次结构。例如,在生物分类学中,从最底层的种到属、科、目、纲、门等,这种层次关系可以通过层级聚类来发现和呈现。通过构建一个树状的层次结构,让用户看到数据在不同粒度上的聚类情况。这种层次结构能够帮助我们更好地理解数据的内在组织方式。自顶向下自底向上层次聚类每一个对象最开始都是一个类簇,每次按一定的准则将最相近的两个类簇合并生成一个新的类簇,如此往复,直至最终所有的对象都属于一个类簇。最开始所有的对象均属于一个类簇,每次按一定的准则将某个类簇划分为多个类簇,如此往复,直至每个对象均是一个独立的类簇。层次聚类算法①ACMSIGMOD被认为是数据管理领域最顶级的国际学术会议。自底向上的层次聚类自底向上层级聚类从每个数据点作为一个独立簇开始，在聚类过程中，不断合并最相似的两个簇，重复合并操作，直到所有数据点合并为一个簇，聚类合并的关键在于簇间距离的定义。簇间距离计算方法单连接（Single-linkage）：两簇中最近两个点之间的距离完全连接（Complete-linkage）：两簇中最远两个点之间的距离平均连接（Average-linkage）：两簇中所有点对距离的平均值层次聚类算法算法流程需要修改文件内容后替换层次聚类算法首先,将每个对象视为一个小类簇。计算每个类簇两两之间的距离,即为对象两两之间的距离。其中B与C两个类簇间的距离最近,为1。将两个距离最近的类簇B和C进行合并。计算新类簇{B,C}与其他类簇的距离,更新类簇距离矩阵。由于{B,C}中C与其他各类簇中的对象均为最近邻,因此分别计算C与A,D,E的距离,此时,在所有类簇中距离最近A和D。已知5个数据点的横纵坐标，将采用欧氏距离和最近邻对数据点进行层次聚类。算法流程示例层次聚类算法将两个距离最近的类簇A和D进行合并。计算新类簇{A,D}与其他类簇的距离。A,C,E互为各自类簇之间的最近邻,因此分别计算两两之间的距离，此时,B,C和E之间距离在所有类簇中距离最近。将两个距离最近的类簇B,C和E进行合并。已知5个数据点的横纵坐标，将采用欧氏距离和最近邻对数据点进行层次聚类。算法流程示例层次聚类算法由于只剩两个类簇,直接将两个类簇进行合并。在树状图中画出新的对象关系。综上,层次聚类过程完成。已知5个数据点的横纵坐标，将采用欧氏距离和最近邻对数据点进行层次聚类。算法流程示例层次聚类算法自顶向下的层次聚类是将所有数据点形成的大类不断进行拆分。算法初始时,所有数据点都被视为属于同一个类簇。然后,算法逐步将大的类簇分裂成更小的聚类,直到每个点都成为一个单独的类簇。类簇的分裂需要对簇中对象之间的距离进行计算,计算方式与章节7.4.1类似。自顶向下的层次聚类算法流程初始化:所有对象形成一个类簇。拆分聚类:选择一个簇进行分裂,通常选择最大或者最不紧密的类簇,将选中的簇分裂成两个子簇。在候选簇的集合中删除原来的簇,并加入两个新的子簇。不断重复计算距离和拆分聚类这两个步骤,直到所有对象都成为单独的簇的条件,聚类算法结束。聚类效果的评估06ClusteringEvaluation聚类效果的评估一个好的聚类方法可以产生高质量的类簇,使得簇内数据之间的相似度高,不同簇之间的相似度低。但当数据量较大的时候,仅靠领域专家难以对所有聚类结果进行一一评估,需要引入客观的量化指标来自动评估聚类效果。指标分类利用已有真实标签，将聚类结果与理想分类进行比较。当具有外部标签的时候,我们可以将聚类算法的结果与标签所代表的理想情况的聚类结果进行比较。不依赖外部标签，仅基于数据特征衡量聚类质量。只能利用数据集的属性特征来评价聚类算法的优劣,通过计算总体相似度、簇间平均相似度或簇内平均相似度来评价聚类质量。外部评价指标内部评价指标评估指标聚类效果的评估外部指标兰德系数(Randindex,RI)通过比较聚类结果与已知的真实类别标签,来衡量聚类结果。如果聚类结果准确性越高,那么聚类结果与真实标签划分应该越相似,所以A和D这两种情况出现得越多。因此,兰德系数定义为A和D两种情况的样本对占全部样本对的比重。对于数据集中任意一对样本来说,聚类结果一共有四种情况:A:在聚类结果和真实类别中都被分到同一个簇。B:在聚类结果中被分到不同簇,但在真实标签中被分到同一个簇。C:在聚类结果中被分到同一个簇,但在真实标签中被分到不同簇。D:在聚类结果和真实标签中都被分到不同簇。其中a,d分别表示A和D两种情况的样本对数量,n表示样本的总数。兰德系数RI取值范围为[0,1]，值越大表示聚类结果越接近真实分类。聚类效果的评估外部指标调整兰德系数(adjustedRandindex,ARI)通过对随机结果进行惩罚来解决这一缺陷,使得ARI接近于0时表示聚类结果与随机结果相似。兰德系数的缺点在于,即使聚类结果是随机产生的,RI也可能得到一个较高的值其中,E[RI]表示对于随机的聚类结果,RI在真实标签下的期望;max(RI)表示RI在当前真实标签下的最大值。ARI通过将观测到的RI与随机情况下期望得到的RI进行比较,从而得到一个调整后的指标。如果ARI的值接近于1,说明聚类结果与真实类别非常一致;如果ARI的值接近于0,说明聚类结果与随机划分相似;如果ARI的值为负,说明聚类结果比随机划分还要差。聚类效果的评估外部指标互信息(mutualinformation,MI)是一个统计学中的概念,用于衡量两个随机变量之间相互依赖的程度。当有真实的标签可以作为参考时,就可用互信息来评估聚类结果与真实标签之间的一致性。假设有两个离散随机变量X和Y,它们的联合概率分布为p(X,Y),边缘概率分布分别为p(X)和p(Y)。那么,它们的互信息I(X;Y)定义为:在聚类评估中,X可以代表真实的类别标签,而Y则代表聚类得到的类别标签。互信息的值越高,表示聚类结果与真实标签之间的关联性越强,即聚类效果越好。然而,互信息的取值范围理论上是0∼∞,这使得不同数据集的聚类结果比较较为困难,通常需要做标准化处理。聚类效果的评估外部指标标准化互信息(normalizedmutualinformation,NMI)的目的是将互信息标准化到固定的区间内,通常是[0,1](即归一化),这样可以更容易地比较不同数据集或不同特征空间下的互信息值。一种常见的归一化方法是基于几何平均数:其中,H(X)和H(Y)分别为X和Y的熵,有关熵的定义，满足下式，对于H(X)和H(Y)都适用。NMI(X;Y)的值始终在[0,1]区间内,满足归一化的要求。当NMI(X;Y)=0时,X和Y互相独立,表示聚类结果和真实标签毫不相关,没有意义;当NMI(X;Y)=1时,X和Y分布完全相同,表示聚类结果和真实标签完全一致。聚类效果的评估内部指标轮廓系数(silhouettecoefficient)用于衡量一个样本与其所属簇的相似度(凝聚度),