DBSCAN聚类算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,DBSCAN,聚类算法,LI XIN,1,目录,基于密度的聚类算法的介绍,DBSCAN,算法的介绍,DBSCAN,算法在生物学领域的应用,2,基于密度聚类算法,开发原因：,弥补层次聚类算法和划分式聚类算法往往只能发现,凸型的聚类簇,的缺陷。,核心思想：,只要一个区域中的点的密度大过某个阈值，就把它加到与之相近的聚类中去。,稠密样本点,低密度区域（,noise,）,3,基于密度聚类算法,4,密度的定义,传统基于中心的密度定义为：,数据集中特定点的密度通过该点,Eps,半径之内的点计数,(,包括本身,),来估计。,显然，密度依赖于半径。,5,DBSCAN,点分类,基于密度定义，我们将点分为：,稠密区域内部的点,(,核心点,),稠密区域边缘上的点,(,边界点,),稀疏区域中的点,(,噪声或背景点,).,6,DBSCAN,点分类,核心点,(core point):,在半径,Eps,内含有超过,MinPts,数目的点，则该点为核心点,这些点都是在簇内的,边界点,(border point):,在半径,Eps,内点的数量小于,MinPts,，但是在核心点的邻居,噪音点,(noise point):,任何不是核心点或边界点的点,.,MinPts,：给定点在,E,领域内成为核心对象的最小领域点数,7,DBSCAN:,核心点、边界点和噪音点,8,DBSCAN:,核心点、边界点和噪音点,Original Points,Point types:,core,border,and,noise,Eps=10,MinPts=4,9,DBSCAN,算法概念,Eps,邻域,：给定对象半径,Eps,内的邻域称为该对象的,Eps,邻域，我们用 表示点,p,的,Eps-,半径内的点的集合，即,:,核心对象,：如果对象的,Eps,邻域至少包含最小数目,MinPts,的对象，则称该对象为核心对象。,边界点：,边界点不是核心点，但落在某个核心点的邻域内。,噪音点：,既不是核心点，也不是边界点的任何点,10,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),。,11,DBSCAN,算法概念示例,如图所示，,Eps,用一个相应的半径表示，设,MinPts=3,，请分析,Q,M,P,S,O,R,这,5,个样本点之间的关系。,“,直接密度可达”和“密度可达”概念示意描述,12,解答,根据以上概念知道：由于有标记的各点,M,、,P,、,O,和,R,的,Eps,近邻均包含,3,个以上的点，因此它们都是核对象；,M,是从,P“,直接密度可达”；而,Q,则是从,M“,直接密度可达”；基于上述结果，,Q,是从,P“,密度可达”；但,P,从,Q,无法“密度可达”,(,非对称,),。类似地，,S,和,R,从,O,是“密度可达”的；,O,、,R,和,S,均是“密度相连”的,13,DBSCAN,算法原理,DBSCAN,通过检查数据集中每点的,Eps,邻域来搜索簇，如果点,p,的,Eps,邻域包含的点多于,MinPts,个，则创建一个以,p,为核心对象的簇。,然后，,DBSCAN,迭代地聚集从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。,当没有新的点添加到任何簇时，该过程结束,.,14,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,15,DBSCAN,运行效果好的时候,对噪音不敏感,可以处理不同形状和大小的数据,Clusters,Original Points,16,DBSCAN,运行不好的效果,Original Points,（,MinPts=4,Eps=9.75,）,(MinPts=4,Eps=9.92),密度变化的数据,高维数据,17,DBSCAN,算法的一些问题,时间复杂度,DBSCAN,的基本时间复杂度是,O(N*,找出,Eps,领域中的点所需要的时间,),N,是点的个数。最坏情况下时间复杂度是,O(N,2,),在低维空间数据中,有一些数据结构如,KD,树，使得可以有效的检索特定点给定距离内的所有点，时间复杂度可以降低到,O(NlogN),18,DBSCAN,算法的一些问题,空间复杂度,低维或高维数据中，其空间都是,O(N),，对于每个点它只需要维持少量数据，即簇标号和每个点的标识,(,核心点或边界点或噪音点,),19,如何合适选取,EPS,和,MinPts,对于在一个类中的所有点,它们的第,k,个最近邻大概距离是一样的,噪声点的第,k,个最近邻的距离比较远,所以,尝试根据每个点和它的第,k,个最近邻之间的距离来选取,然后,:,Eps,取什么？,MinPts,取什么？,20,DBSCAN,算法的优缺点,优点,基于密度定义，相对抗噪音，能处理任意形状和大小的簇,缺点,当簇的密度变化太大时，会有麻烦,对于高维问题，密度定义是个比较麻烦的问题,21,DBSCAN,的应用,22,DBSCAN,的应用,23,DBSCAN,的应用,6x6,m Box,Eps,：,100nm,MinPts,：,10,24,DBSCAN,的应用,25,DBSCAN,的应用,26,DBSCAN,的应用,198,247 variably sized clusters of,somatic mutations within exon,proximal domains of the human genome,Eps=d,p,/d,s,（,10500bp,）,（,d,p,：突变位置的平均距离,d,s,：突变域的大小）,MinPts,：,P0.05,二项式检验,Eps,和,MinPts,不是一成不变的,27,Thanks,28,