密度聚类算法详解课件

,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,数据挖掘,Topic3-,聚类分析,密度聚类,2,基于密度的方法,基于密度聚类(,Density-Based Clustering),主要特点:,发现任意形状的聚类,处理噪音,一遍扫描,需要密度参数作为终止条件,一些有趣的研究:,DBSCAN:,Ester,et al.(KDD96),OPTICS,:Ankerst,et al(SIGMOD99).,DENCLUE,:Hinneburg&D.Keim (KDD98),CLIQUE,:Agrawal,et al.(SIGMOD98),3,基于密度的聚类:背景,I,两个参数,:,Eps,:,邻域的最大半径,MinPts,:,在,Eps-,邻域中的最少点数,N,Eps,(p),:,q belongs to D,|,dist(p,q)=,MinPts,p,q,MinPts=5,Eps=1 cm,4,密度概念,核心对象(,Core object):,一个对象的,邻域至少包含最小数目,MinPts,个对象,不是核心点,但落在某个核心 点的,Eps,邻域内的对象称为边界点,不属于任何簇的对象为噪声,.,对于空间中的一个对象，如果它在给定半径,e,的邻域中的对象个数大于密度阀值,MinPts,，则该对象被称为,核心对象,，否则称为边界对象。,Core,Border,Outlier,Eps=1cm,MinPts=5,由一个核心对象和其密度可达的所有对象构成一个聚类,。,密度概念,直接密度可达的,(Directly density reachable,DDR):,给定对象集合,D,如果,p,是在,q,的,邻域内,而,q,是核心对象,我们说对象,p,是从对象,q,直接密度可达的,(,如果,q,是一个核心对象，,p,属于,q,的邻域，那么称,p,直接密度可达,q,。,),密度可达的,(density reachable):,存在 一个从,p,到,q,的,DDR,对象链,(,如果存在一条链,，满足,p,1,=p,，,p,i,=q,，,p,i,直接密度可达,p,i+1,，则称,p,密度可达,q,),p,q,MinPts=5,Eps=1 cm,6,基于密度的聚类:背景,II,密度可达:,点,p,关于,Eps,MinPts,是从,q,密度可达的,如果 存在一个节点链,p,1,p,n,p,1,=,q,p,n,=,p,使得,p,i+1,是从,p,i,直接密度可达的,密度相连的:,点,p,关于,Eps,MinPts,与点,q,是密度相连的,如果 存在点,o,使得,p,和,q,都是关于,Eps,MinPts,是从,o,密度可达的,(,如果存在,o,，,o,密度可达,q,和,p,，则称,p,和,q,是,密度连通,的,),p,q,p,1,p,q,o,由一个核心对象和其密度可达的所有对象构成一个聚类,。,7,密度概念,Eg:,假设半径,=3,，,MinPts=3,，,点,p,的,领域中有点,m,p,p1,p2,o,点,m,的,领域中有点,m,q,p,m1,m2,点,q,的,领域中有,q,m,点,o,的,领域中有点,o,p,s,点,s,的,领域中有点,o,s,s1.,那么核心对象有,p,m,o,s(q,不是核心对象,，因为它对应的,领域中点数量等于,2,，小于,MinPts=3),；,点,m,从点,p,直接密度可达，因为,m,在,p,的,领域内，并且,p,为核心对象；,点,q,从点,p,密度可达，因为点,q,从点,m,直接密度可达，并且点,m,从点,p,直接密度可达；,点,q,到点,s,密度相连,，因为点,q,从点,p,密度可达，并且,s,从点,p,密度可达。,由一个核心对象和其密度可达的所有对象构成一个聚类,。,8,例子,MinPts=3,q,是从,p,密度可达；,p,不是从,q,密度可达（,q,非核心）,S,和,r,从,o,密度可达；,o,从,r,密度可达；,r,s,密度相连,2024/11/5,a,为核心对象，,b,为边界对象，且,a,直接密度可达,b,，,但,b,不,直接密度可达,a,因为,b,不是一个核心对象,2024/11/5,c,直接密度可达,a,a,直接密度可达,b,所以,c,密度可达,b,，,同理,b,不,密度可达,c,，但,b,和,c,密度连通,11,DBSCAN(1996),DBSCAN,(Density Based Spatial Clustering of Applications with Noise),一个基于密度的聚类算法,可以在带有“噪音”的空间数据库中发现任意形状的聚类,Core,Border,Outlier,Eps=1cm,MinPts=5,12,DBSCAN(1996),DBSCAN,：一种基于高密度连通区域的基于密度的聚类方法，该算法将具有足够高密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇。它将簇定义为密度相连的点的最大集合；,13,DBSCAN(,续),算法,任意选取一个点,p,得到所有从,p,关于,Eps,和,MinPts,密度可达的点,.,如果,p,是一个核心点,则找到一个聚类,.,如果,p,是一个边界点,没有从,p,密度可达的点,DBSCAN,将访问数据库中的下一个点.,继续这一过程,直到数据库中的所有点都被处理,.,DBSCAN,的复杂度,采用空间索引,复杂度为,O(nlog n),否则为,O(n,2,),DBSCAN,的缺点:,对用户定义的参数是敏感的,参数难以确定(特别是对于高维数据),设置的细微不同可能导致差别很大的聚类.,（数据倾斜分布）全局密度参数不能刻画内在的聚类结构,2024/11/5,DBSCAN,从任一对象,p,开始，根据参数,e,和,MinPts,提取所有从,p,密度可达对象，得到一个聚类。,1.,从任一对象,p,开始。,a),如果,p,是核心对象，则,p,和,p,直接密度可达的所有对象被标记为类,i,。递归,p,直接密度可达的所有对象,q,i,（即用,q,i,代替,p,回到第一步）。,b),如果,p,是一个边界对象，那么,p,被标记为噪声。,2.i+,3.,如果还有没被标记的对象，则从中任选一个作为,p,，回到第一步。,15,DBSCAN(,续),算法,：,DBSCAN,输入：,半径,MinPts,给定点在,邻域内成为核心对象的最小领域点数,D,集合,输出：目标类簇集合,方法：,repeat,1),判断输入点是否为核心对象,2),找出核心对象的,邻域中的所有直接密度可达点,util,所有输入点都判断完毕,repeat,针对所有核心对象的,邻域所有直接密度可达点找到最大密度相连对象集合，,中间涉及到一些密度可达对象的合并。,Util,所有核心对象的,邻域都遍历完毕,作业（,Due date,：,5,月,9,日）,2024/11/5,专题思路：把搜下来的网页进行聚类，将聚类结果显示给用户，用户可以选择其中的一个类，标为关注，类的关键词作为主题，用户就可以跟踪这主题、了解主题的文章的情感（就是其它部分的功能）,双层正方形或者三维同心球,，,其中第一类样本的参数 服从均匀布 ，第二类样本的参数服从均匀分布,随机产生,20000,个样本数据进行聚类,.,17,OPTICS(1999),OPTICS(Ordering Points To Identify the,在前面介绍的,DBSCAN,算法中，有两个初始参数,（邻域半径）和,minPts(,邻域最小点数,),需要用户手动设置输入，并且聚类的类簇结果对这两个参数的取值非常敏感，不同的取值将产生不同的聚类结果，其实这也是大多数其他需要初始化参数聚类算法的弊端。,Clustering Structure),Ankerst,Breunig,Kriegel,和,Sander,提出(,SIGMOD99),为自动和交互的聚类分析,计算一个簇次序,(,cluster ordering).,OPTICS,并不显示的产生结果类簇，而是为聚类分析生成一个增广的簇排序（比如，以可达距离为纵轴，样本点输出次序为横轴的坐标图），这个排序代表了各样本点基于密度的聚类结构。它包含的信息等价于从一个广泛的参数设置所获得的基于密度的聚类，换句话说，,从这个排序中可以得到基于任何参数,E,和,minPts,的,DBSCAN,算法的聚类结果。,18,OPTICS(1999),这个次序代表了数据的基于密度的聚类结构。它包含了信息,等同于从一个广域的参数设置所获得的基于密度的聚类,可用于自动和交互聚类分析,包括发现内在聚类结构,可以使用图形或可视化技术表示,考虑,DBSCAN,对一个恒定的,MinPts,值,关于高密度的(即较小的,值)的聚类结果被完全包含在根据较低密度所获得的密度相连的集合中,扩展,DBSCAN,算法来同时处理一组距离参数值,19,OPTICS(,续),为了同时构建不同的聚类,应当以特定的顺序来处理对象.优先选择最小的,值密度可达的对象,以便高密度的聚类能被首先完成,每个对象需要存储两个值,对象,p,的,核心距离(,core-distance),是使得,p,成为核心对象的最小,。如果,p,不是核心对象,p,的核心距离没有定义,对象,q,关于另一个对象,p,的,可达距离(,reachability-distance,),是,p,的核心距离和,p,与,q,的欧几里得距离,之间的较大值.如果,p,不是一个核心对象,p,和,q,之间的可达距离没有定义,20,OPTICS(,续),例:设,=6,(,mm),MinPts=5.,p,的核心距离是,p,与四个最近的数据对象之间的距离,.,q,1,关于,p,的可达距离是,p,的核心距离(即,=3,mm),因为它比从,p,到,q,1,的欧几里得距离要大.,q,2,关于,p,的可达距离是从,p,到,q,2,的欧几里得距离,它大于,p,的核心距离,=,6,mm,=,3,mm,=,6,mm,=,3,mm,p,p,q1,q2,P,的核心距离,可达距离(,p,q1)=,=3mm,可达距离(,p,q2)=d(p,q2),2024/11/5,例如：假设邻域半径,E=2,minPts=3,，存在点,A(2,3),B(2,4),C(1,4),D(1,3),E(2,2),F(3,2),点,A,为核心对象，在,A,的,E,领域中有点,A,B,C,D,E,F,，其中,A,的核心距离为,E=1,，因为在点,A,的,E,邻域中有点,A,B,D,E3;,点,F,到核心对象点,A,的,可达距离,为,，因为,A,到,F,的欧几里得距离,大于点,A,的核心距离,1.,OPTICS,算法额外存储了每个对象的核心距离和可达距离。基于,OPTICS,产生的排序信息来提取类簇。,2024/11/5,OPTICS,算法,输入：样本集,D,邻域半径,E,给定点在,E,领域内成为核心对象的最小领域点数,MinPts,输出：具有可达距离信息的样本点输出排序,方法：,1,创建两个队列，有序队列和结果队列。（有序队列用来存储核心对象及其该核心对,象的直接可达对象，并按可达距离升序排列；结果队列用来存储样本点的输出次序）；,2,如果所有样本集,D,中所有点都处理完毕，则算法结束。否则，选择一个未处理（即,不在结果队列中）且为核心对象的样本点，找到其所有直接密度可达样本点，如,过该样本点不存在于结果队列中，则将其放入有序队列中，并按可达距离排序；,3,如果有序队列为空，则跳至步骤,2,，否则，从有序队列中取出第一个样本点（即可达距离最小的样本点）进行拓展，并将取