DBSCAN聚类算法复习课程.ppt

《DBSCAN聚类算法复习课程.ppt》由会员分享，可在线阅读，更多相关《DBSCAN聚类算法复习课程.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、DBSCAN聚类算法目目录基于密度的聚类算法的介绍DBSCAN算法的介绍DBSCAN算法在生物学领域的应用 DBSCANDBSCAN点分点分类基于密度定义，我们将点分为：稠密区域内部的点(核心点核心点)稠密区域边缘上的点(边界点界点)稀疏区域中的点(噪声或背景点噪声或背景点).DBSCANDBSCAN点分点分类核心点(core point):在半径Eps内含有超过MinPts数目的点，则该点为核心点 这些点都是在簇内的边界点(border point):在半径Eps内点的数量小于MinPts，但是在核心点的邻居噪音点(noise point):任何不是核心点或边界点的点.MinPts：给定点在

2、E领域内成为核心对象的最小领域点数 DBSCAN:DBSCAN:核心点、核心点、边界点和噪音点界点和噪音点DBSCAN:DBSCAN:核心点、核心点、边界点和噪音点界点和噪音点Original PointsPoint types:core,border and noiseEps=10,MinPts=4DBSCANDBSCAN算法概念算法概念Eps邻域域：给定对象半径Eps内的邻域称为该对象的Eps邻域，我们用 表示点p的Eps-半径内的点的集合，即:核心核心对象象：如果对象的Eps邻域至少包含最小数目MinPts的对象，则称该对象为核心对象。边界点：界点：边界点不是核心点，但落在某个核心点的邻

3、域内。噪音点：噪音点：既不是核心点，也不是边界点的任何点DBSCANDBSCAN算法概念算法概念直接密度可达：直接密度可达：给定一个对象集合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和Min

4、Pts密度相连的(density-connected)。DBSCANDBSCAN算法概念示例算法概念示例如图所示，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均是“密度相连”的DBSCANDBSCAN算法原理算法原理DB

5、SCAN通过检查数据集中每点的Eps邻域来搜索簇，如果点p的Eps邻域包含的点多于MinPts个，则创建一个以p为核心对象的簇。然后，DBSCAN迭代地聚集从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。当没有新的点添加到任何簇时，该过程结束.DBSCANDBSCAN算法算法伪代代码 输入：数据集入：数据集D，参数，参数MinPts,Eps 输出：簇集合出：簇集合(1)首先将数据集D中的所有对象标记为未处理状态(2)for 数据集D中每个对象p do(3)if p已经归入某个簇或标记为噪声 then(4)continue;(5)else(6)检查对象p的Eps邻域 ；(

6、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 DBSCANDBSCAN运行效果好的运行效果好的时候候 对噪音不敏感噪音不敏感 可以可以处理不同形状和大小的数据理不同形状和大小的数据ClustersClustersOriginal PointsOrigin

7、al PointsDBSCANDBSCAN运行不好的效果运行不好的效果Original PointsOriginal Points（MinPts=4,Eps=9.75）(MinPts=4,Eps=9.92)密度密度变化的数据化的数据高高维数据数据DBSCANDBSCAN算法的一些算法的一些问题时间复复杂度度 DBSCAN的基本时间复杂度是 O(N*找出Eps领域中的点所需要的时间),N是点的个数。最坏情况下时间复杂度是O(N2)在低维空间数据中,有一些数据结构如KD树，使得可以有效的检索特定点给定距离内的所有点，时间复杂度可以降低到O(NlogN)DBSCANDBSCAN算法的一些算法的一些问

8、题空空间复复杂度度 低维或高维数据中，其空间都是O(N)，对于每个点它只需要维持少量数据，即簇标号和每个点的标识(核心点或边界点或噪音点)如何合适如何合适选取取EPSEPS和和MinPtsMinPts对于在一个类中的所有点,它们的第k个最近邻大概距离是一样的噪声点的第k个最近邻的距离比较远所以,尝试根据每个点和它的第k个最近邻之间的距离来选取然后:Eps取什么？取什么？MinPts取什么？取什么？DBSCANDBSCAN算法的算法的优缺点缺点优点基于密度定义，相对抗噪音，能处理任意形状和大小的簇缺点当簇的密度变化太大时，会有麻烦对于高维问题，密度定义是个比较麻烦的问题DBSCANDBSCAN的

9、的应用用DBSCANDBSCAN的的应用用DBSCANDBSCAN的的应用用6x6 m BoxEps：100nmMinPts：10DBSCANDBSCAN的的应用用DBSCANDBSCAN的的应用用DBSCANDBSCAN的的应用用198,247 variably sized clusters of somatic mutations within exon proximal domains of the human genome Eps=dp/ds（10500bp）（dp：突变位置的平均距离 ds：突变域的大小）MinPts：P0.05 二项式检验Eps和MinPts不是一成不变的Thanks结束语结束语谢谢大家聆听！谢谢大家聆听！29