《DBSCAN实用教案》由会员分享，可在线阅读，更多相关《DBSCAN实用教案（22页珍藏版）》请在金锄头文库上搜索。
1、DBSCANDBSCAN是一个基于密度的聚类算法.(他聚类方法大都是基于对象之间的距离进行聚类，聚类结果是球状的簇)基于密度的聚类是寻找(xnzho)被低密度区域分离的高密度区域。第1页/共21页第一页，共22页。密度(md)的定义第2页/共21页第二页，共22页。传统基于中心(zhngxn)的密度定义为：数据集中特定点的密度通过该点Eps半径之内的点计数(包括本身)来估计。显然，密度依赖于半径。传统的密度(md)定义：基于中心的方法第3页/共21页第三页，共22页。基于密度定义，我们将点分为：稠密(chum)区域内部的点(核心点)稠密(chum)区域边缘上的点(边界点)稀疏区域中的点(噪声或
2、背景点). DBSCAN第4页/共21页第四页，共22页。核心点(core point) :在半径Eps内含有超过MinPts数目的点，则该点为核心点这些(zhxi)点都是在簇内的边界点(border point):在半径Eps内点的数量小于MinPts，但是在核心点的邻居噪音点(noise point):任何不是核心点或边界点的点. DBSCAN第5页/共21页第五页，共22页。DBSCAN:核心核心(hxn)点、边界点和噪点、边界点和噪音点音点第6页/共21页第六页，共22页。Original PointsPoint types: core, border and noiseEps = 1
3、0, MinPts = 4DBSCAN:核心(hxn)点、边界点和噪音点第7页/共21页第七页，共22页。DBSCAN算法(sunf)概念Eps邻域：给定对象半径Eps内的邻域称为该对象的Eps邻域，我们用表示点p的Eps-半径内的点的集合，即:核心(hxn)对象：如果对象的Eps邻域至少包含最小数目MinPts的对象，则称该对象为核心(hxn)对象。边界点：边界点不是核心(hxn)点，但落在某个核心(hxn)点的邻域内。噪音点：既不是核心(hxn)点，也不是边界点的任何点第8页/共21页第八页，共22页。DBSCAN算法(sunf)概念直接密度可达：给定一个对象集合D，如果p在q的Eps邻域
4、内，而q是一个核心对象，则称对象p从对象q出发时是直接密度可达的(directlydensity-reachable)。密度可达：如果存在一个对象链，对于，是从关于Eps和MinPts直接密度可达的，则对象p是从对象q关于Eps和MinPts密度可达的(density-reachable)。密度相连(xinlin)：如果存在对象OD，使对象p和q都是从O关于Eps和MinPts密度可达的，那么对象p到q是关于Eps和MinPts密度相连(xinlin)的(density-connected)。第9页/共21页第九页，共22页。DBSCAN算法概念(ginin)示例如图所示，Eps用一个相应的半
5、径表示，设MinPts=3，请分析(fnx)Q,M,P,S,O,R这5个样本点之间的关系。 “直接(zhji)密度可达”和“密度可达”概念示意描述解答：根据以上概念知道：由于有标记的各点M、P、O和R的Eps近邻均包含3个以上的点，因此它们都是核对象；M是从P“直接密度可达”；而Q则是从M“直接密度可达”；基于上述结果，Q是从P“密度可达”；但P从Q无法“密度可达”(非对称)。类似地，S和R从O是“密度可达”的；O、R和S均是“密度相连”的。第10页/共21页第十页，共22页。DBSCAN算法(sunf)原理DBSCAN通过检查数据集中每点的Eps邻域来搜索簇，如果点p的Eps邻域包含的点多于
6、MinPts个，则创建一个以p为核心对象的簇。然后，DBSCAN迭代地聚集从这些核心对象直接密度可达的对象，这个过程可能涉及(shj)一些密度可达簇的合并。当没有新的点添加到任何簇时，该过程结束.第11页/共21页第十一页，共22页。DBSCAN算法(sunf)伪代码输入：数据集D，参数MinPts,Eps 输出：簇集合(1) 首先将数据集D中的所有对象标记为未处理状态(2) for 数据集D中每个对象p do(3) if p已经归入某个簇或标记为噪声(zoshng) then(4) continue;(5) else (6) 检查对象p的Eps邻域 ；(7) if 包含的对象数小于MinPt
7、s then(8) 标记对象p为边界点或噪声(zoshng)点；(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 第12页/共21页第十二页，共22页。DBSCAN聚类算法(sunf)的细节第13页/共21页第十三页，共22页。DBSCAN运行效果运行效果(xiogu)好的时候好的时候Original PointsC
8、lusters 对噪音(zoyn)不敏感 可以处理不同形状和大小的数据第14页/共21页第十四页，共22页。DBSCAN运行运行(ynxng)不好的效果不好的效果Original Points(MinPts=4, Eps=9.75). (MinPts=4, Eps=9.92) 密度变化(binhu)的数据高维数据第15页/共21页第十五页，共22页。DBSCAN的其它(qt)问题第16页/共21页第十六页，共22页。DBSCAN的时间(shjin)复杂性时间复杂度DBSCAN的基本时间复杂度是O(N*找出Eps领域中的点所需要的时间),N是点的个数。最坏情况下时间复杂度是O(N2)在低维空间数
9、据中,有一些数据结构如KD树，使得可以有效的检索( jinsu)特定点给定距离内的所有点，时间复杂度可以降低到O(NlogN)第17页/共21页第十七页，共22页。DBSCAM的空间(kngjin)复杂性空间复杂度低维或高维数据中，其空间都是O(N)，对于每个点它只需要维持少量数据，即簇标号和每个点的标识(biozh)(核心点或边界点或噪音点)第18页/共21页第十八页，共22页。如何合适如何合适(hsh)选取选取EPS和和MinPts思想是这样的对于在一个类中的所有点,它们的第k个最近邻大概距离是一样的噪声点的第k个最近邻的距离比较远所以(suy),尝试根据每个点和它的第k个最近邻之间的距离
10、来选取然后:Eps取什么？MinPts取什么？第19页/共21页第十九页，共22页。DBSCAN算法(sunf)的优缺点优点基于密度(md)定义，相对抗噪音，能处理任意形状和大小的簇缺点当簇的密度(md)变化太大时，会有麻烦对于高维问题，密度(md)定义是个比较麻烦的问题第20页/共21页第二十页，共22页。感谢您的欣赏(xnshng)！第21页/共21页第二十一页，共22页。内容(nirng)总结DBSCAN。传统的密度定义：基于(jy)中心的方法。边界点(border point):在半径Eps内点的数量小于MinPts，但是在核心点的邻居。(MinPts=4, Eps=9.75).。(MinPts=4, Eps=9.92)。噪声点的第k个最近邻的距离比较远。所以, 尝试根据每个点和它的第k个最近邻之间的距离来选取。对于高维问题，密度定义是个比较麻烦的问题。感谢您的欣赏第二十二页，共22页。
