DBSCAN基于密度的聚类算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,基于密度的聚类算法,DBSCAN,聚类算法,DBSCAN,DBSCAN,是一个基于密度的聚类算法,.,(他聚类方法大都是基于对象之间的距离进行聚类，聚类结果是球状的簇),基于密度的聚类是寻找被低密度区域分离的高密度区域。,密度的定义,传统基于中心的密度定义为：,数据集中特定点的密度通过该点,Eps,半径之内的点计数,(,包括本身,),来估计。,显然，密度依赖于半径。,传统的密度定义：基于中心的方法,基于密度定义，我们将点分为：,稠密区域内部的点,(,核心点,),稠密区域边缘上的点,(,边界点,),稀疏区域中的点,(,噪声或背景点,).,DBSCAN,核心点,(,core point),:,在半径,Eps,内含有超过,MinPts,数目的点，则该点为核心点,这些点都是在簇内的,边界点,(,border point):,在半径,Eps,内点的数量小于,MinPts,，但是在核心点的邻居,噪音点,(,noise point):,任何不是核心点或边界点的点,.,DBSCAN,DBSCAN:,核心点、边界点和噪音点,Original Points,Point types:,core,border,and,noise,Eps=10,MinPts=4,DBSCAN:,核心点、边界点和噪音点,DBSCAN,算法概念,Eps,邻域：,给定对象半径,Eps,内的邻域称为该对象的,Eps,邻域，我们用,表示点,p,的,Eps-,半径内的点的集合，即,:,核心对象：,如果对象的,Eps,邻域至少包含最小数目,MinPts,的对象，则称该对象为核心对象。,边界点：,边界点不是核心点，但落在某个核心点的邻域内。,噪音点：,既不是核心点，也不是边界点的任何点,DBSCAN,算法概念,直接密度可达：,给定一个对象集合,D,，如果,p,在,q,的,Eps,邻域内，而,q,是一个核心对象，则称对象,p,从对象,q,出发时是直接密度可达的,(directly density-reachable),。,密度可达：,如果存在一个对象链,，对于,，,是从,关于,Eps,和,MinPts,直接密度可达的，则对象,p,是从对象,q,关于,Eps,和,MinPts,密度可达的,(density-reachable),。,密度相连：,如果存在对象,OD,，使对象,p,和,q,都是从,O,关于,Eps,和,MinPts,密度可达的，那么对象,p,到,q,是关于,Eps,和,MinPts,密度相连的,(density-connected),。,DBSCAN,算法概念示例,如图所示，,Eps,用一个相应的半径表示，设,MinPts=3,，请分析,Q,M,P,S,O,R,这,5,个样本点之间的关系。,“,直接密度可达”和“密度可达”概念示意描述,解答：,根据以上概念知道：由于有标记的各点,M,、,P,、,O,和,R,的,Eps,近邻均包含,3,个以上的点，因此它们都是核对象；,M,是从,P,“,直接密度可达,”,；而,Q,则是从,M,“,直接密度可达,”,；基于上述结果，,Q,是从,P,“,密度可达,”,；但,P,从,Q,无法,“,密度可达,”,(,非对称,),。类似地，,S,和,R,从,O,是,“,密度可达,”,的；,O,、,R,和,S,均是,“,密度相连,”,的。,DBSCAN,算法原理,DBSCAN,通过检查数据集中每点的,Eps,邻域来搜索簇，如果点,p,的,Eps,邻域包含的点多于,MinPts,个，则创建一个以,p,为核心对象的簇。,然后，,DBSCAN,迭代地聚集从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。,当没有新的点添加到任何簇时，该过程结束,.,DBSCAN,算法伪代码,输入：数据集,D,，参数,MinPts,Eps,输出：簇集合,(1),首先将数据集,D,中的所有对象标记为未处理状态,(2)for,数据集,D,中每个对象,p,do,(3)if,p,已经归入某个簇或标记为噪声,then,(4)continue;,(5)else,(6),检查对象,p,的,Eps,邻域 ；,(7)if,包含的对象数小于,MinPts then,(8),标记对象,p,为边界点或噪声点；,(9)else,(10),标记对象,p,为核心点，并建立新簇,C,并将,p,邻域内所有点加入,C,(11)for,中所有尚未被处理的对象,q,do,(12),检查其,Eps,邻域,，,若,包含至少,MinPts,个对象，,则将 中未归入任何一个簇的对象加入,C,；,(13)end for,(14)end if,(15)end if,(16)end for,DBSCAN,聚类算法的细节,DBSCAN,运行效果好的时候,Original Points,Clusters,对噪音不敏感,可以处理不同形状和大小的数据,DBSCAN,运行不好的效果,Original Points,(MinPts=4,Eps=9.75).,(MinPts=4,Eps=9.92),密度变化的数据,高维数据,DBSCAN,的其它问题,DBSCA,N,的时间复杂性,时间复杂度,DBSCAN,的基本时间复杂度是,O(N*,找出,Eps,领域中的点所需要的时间,),N,是点的个数。最坏情况下时间复杂度是,O(N,2,),在低维空间数据中,有一些数据结构如,KD,树，使得可以有效的检索特定点给定距离内的所有点，时间复杂度可以降低到,O(NlogN),DBSCAM,的空间复杂性,空间复杂度,低维或高维数据中，其空间都是,O(N),，对于每个点它只需要维持少量数据，即簇标号和每个点的标识,(,核心点或边界点或噪音点,),如何合适选取,EPS,和,MinPts,思想是这样的对于在一个类中的所有点,它们的第,k,个最近邻大概距离是一样的,噪声点的第,k,个最近邻的距离比较远,所以,尝试根据每个点和它的第,k,个最近邻之间的距离来选取,然后,:,Eps,取什么？,MinPts,取什么？,DBSCAN,算法的优缺点,优点,基于密度定义，相对抗噪音，能处理任意形状和大小的簇,缺点,当簇的密度变化太大时，会有麻烦,对于高维问题，密度定义是个比较麻烦的问题,