1、DBSCAN聚类算法 LI XIN 1 目录 基于密度的聚类算法的介绍 DBSCAN算法的介绍 DBSCAN算法在生物学领域的应用 2 基于密度聚类算法 开发原因： 弥补层次聚类算法和划分式聚类算法往往只能发现凸型的聚类簇 的缺陷。 核心思想： 只要一个区域中的点的密度大过某个阈值，就把它加到与之相 近的聚类中去。 稠密样本点 低密度区域（noise） 3 基于密度聚类算法 4 密度的定义 传统基于中心的密度定义为： 数据集中特定点的密度通过该点Eps半径之内的点计数(包括本身)来估计。 显然，密度依赖于半径。 5 DBSCAN点分类 基于密度定义，我们将点分为： 稠密区域内部的点(核心点)
2、稠密区域边缘上的点(边界点) 稀疏区域中的点(噪声或背景点). 6 DBSCAN点分类 核心点(core point) :在半径Eps内含有超过MinPts数目的点， 则该点为核心点 这些点都是在簇内的 边界点(border point):在半径Eps内点的数量小于MinPts，但 是在核心点的邻居 噪音点(noise point):任何不是核心点或边界点的点. MinPts：给定点在E领域内成为核心对象的最小领域点数 7 DBSCAN: 核心点、边界点和噪音点 8 DBSCAN: 核心点、边界点和噪音点 Original PointsPoint types: core, border and
3、 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)。
4、密度可达：如果存在一个对象链 ，对 于 ， 是从 关于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 解答 根据以上概念知道：由于有标记的各
5、点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 DBS
6、CAN算法伪代码 输入：数据集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个对象
7、，则 将 中未归入任何一个簇的对象加入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是 点的个数。最坏情况下
8、时间复杂度是O(N2) 在低维空间数据中,有一些数据结构如KD树，使得可以有效的检索特定点给 定距离内的所有点，时间复杂度可以降低到O(NlogN) 18 DBSCAN算法的一些问题 空间复杂度 低维或高维数据中，其空间都是O(N)，对于每个点它只需要维持少量数据 ，即簇标号和每个点的标识(核心点或边界点或噪音点) 19 如何合适选取EPS和MinPts 对于在一个类中的所有点,它们的第k个最近邻大概距离是一样的 噪声点的第k个最近邻的距离比较远 所以, 尝试根据每个点和它的第k个最近邻之间的距离来选取 然后: Eps取什么？ MinPts取什么？ 20 DBSCAN算法的优缺点 优点 基于密
9、度定义，相对抗噪音，能处理任意形状和大小的簇 缺点 当簇的密度变化太大时，会有麻烦 对于高维问题，密度定义是个比较麻烦的问题 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 = dp / ds （10500bp） （dp：突变位置的平均距离 ds：突变域的大小） MinPts：P0.05 二项式检验 Eps和MinPts不是一成不变的 27 Thanks 28
