DBSCAN

DBSCAN(Density-Based Spatial Clu答看威米亚陆欢stering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。

• 中文名称 聚类算法
• 外文名称 Density-Based Spatial Clustering of Applications with Noise
• 简称 DBSCAN
• 性质 有代表性的基于密度的聚类算法
• 定义 密度相连的点的最大集合

概念

　　DBSCAN中的几个定义:

　　Ε邻域:给来自定对象半径为Ε内的区域称为该对象的Ε邻域;

　　核心对象360百科:如果给定对象Ε邻域内的样本点数大于等于MinPts，则称该对象为核心对象;

　　直接密度可达:对于样本集合D，如果样本点q在p的Ε邻域内，并且p析完办滑因粉呼求支肉为核心对象，那么对象q陈故盐从对象p直接密度可达。

　　密度本盾直兴认厚树可达:对于样本集合D，给定一串样本点p是六1,p2….pn，p= p1,q= pn,假如对象pi从pi-1直接密度可达，那么对象q从对象p密度可达。

　　密度相连:存在样本集合D业中的一点o，如果对象o到对象p和对象q都是密度可达的，那么p和q密度相联。

　素认茶　可市验拒少以发现，密度可达是直接密度可达的传递闭包，并且这种关系是非对称的。密止混致给布春即课度相连是对称关系。D出补统晶如省奏装烧高旧BSCAN目的是找到密度相连对剧济呼有女装怕象的最大集合。

　　Eg: 假设半径Ε=3，MinPts=3，点p的E邻域中有点{m,p,p货讲连题飞1,p2,o}, 点m的E邻域中有点{m,q,p,m1,m2},点q作曾的E邻域中有点{q,m},点o的E邻域中有点{o,p,s},点s的E邻域中有点{触酒究收教歌绝际o,s,s1}.

　　那么核心对象有p,按m,o,s(q不是核心对象，因为它对应的E邻域中点数量等于2，小于MinPts=3);

　　点m从点p直接密度可达，因为m在p的E邻域内，并且p为核侵别祖造海充谈心对象;

　　点q从点p密度可达，因为点q从点m专富者袁井矛神论刚装直接密度可达，并且点m从点p直接密度可达;

　　点q到点s密度相连，因为点q从点p密度可达字衡念还首味矿差，并且s从点p密度可达。

描述

　　DBSCAN算法描述:

　　输入便宁九围害红写待创: 包含茅习趋n个对象的数据库，半径e，最少数目MinPts;

　　输出:所有生成的簇，达到密度要求。

　　(1)Repe管其华品车转资带卷有at

　　(2)从数据库中抽出一个未处理的点;

　　(3)IF抽出的点是核心点 THEN 找出所有从该点密度相连的对象，形成一个簇;

　　(4)ELSE 抽出的点是边缘点(非核心对象)，跳出本次循环，寻找下一个点;

　　(5)UNTIL 所有的点都被处理。

　　DBSCAN对用户定义的参数很敏感，细微的不同都可能导致差别很大的结果，而参数的选择无规律可循，只能靠经验确定。

步骤

　来自　DBScan需要二个参数360百科: 扫描半径 (eps)和最小包含点数(minPts)。 任选一个未被访问(unvisit括提场ed)的点开始，找低兰前抗室年英想出与其距离在eps之内(包括eps)的所有附近点。

　　如果 附近点的数量 ≥ minPts，则当前点与其附近点形成一个灶淋簇，并且出发点被标记为已访问(visited)。 然后递归，以相同的方法处理凯步山松史业该簇内所有未被标记为已访问(visited)的点，从而对簇进行扩展。

　　如果 附近点的数量 < minPts，则该点暂时被标记作为噪声点。

　　如果簇充分地被扩展，即簇内的所胜双星画有点被标记为殃仔协已访问，然后用同样的算法去处理未被访多热乌问的点。

伪码

　　具体算法描述如下:

　　(1)检测数据库中白浆捆户尚未检查过的对象p，如果p未被处理(归为某个簇或者标记为噪声)，则检查其邻域，若包含的对象数不小于minPts，建立新簇C，将其中的所有点加入候选集N;

　　(2)对候选计喜善运讨失经集N 中所有尚未被处理的对象q，检查其邻域，若至少包含minPts个对象，则将这些对象加入N;如果q 未归入任何一个簇，则将q 加入C;

　　(3)重复步骤2)，继续检查N 中未处理的对象，当前候选集N为空;

　　(4)重复步骤1)~3)，直到所落束误粉象视帮服已需六有对象都归入了某个簇趋罪凳或标记为噪声。

　　其伪代关码描述如下:

　　输入:数据对象集合D，半径Eps，密度阈值MinPts

　　输出:聚类C

　　DBSC妈况元罪宪一旧硫约到AN(D, Eps, MinPts)

　　Begin

　　init C=0; //初始化簇的个数为0

　　for each unvisited point p in D

　　mark p as visited; //将p标记为已访问

　　N 向历圆黄= getNeighbours (p, Eps);

　　if sizeOf(N) < MinPts then

　　mark p as Noise; //如口感玉每备果满足sizeOf(N) < Min露太青个十根育红Pts，则将p标记表轮派护为噪声

　　else

　　酒方项独买从指让存C= next cluster; //建立新簇C

　　ExpandCluster (p, N, C, Eps, MinPts);

　　end if

　　end for

云尔者　　End

　　其中ExpandCluster算法伪码如下:

　　ExpandCluster(p, N, C, Eps, MinPts)

　　add p to cluster C; //首先将核心点加入C

　　for each unvisited point p' in N

　　mark p' as visited;

　　N' = getNeighbours (p', Eps); //对N邻域内的所有点在进行半径检查

　　if sizeOf(N') >= MinPts then

　乎新术烧货接打使苗我入　N = N+N'; //如果大于MinPts，就扩展N的数目

　　end if

　　if p' is not member of any cluster

　　a更轴顶纪底dd p' to cluster C; //将p' 加入簇C

　　end if

　　end for

　　End ExpandCluster

好处

　　1. 与K-means方法相比，DBSCAN不需要事先知道要形成的簇类的数量。

　　2. 与右末损止K-means方法相比，DBSCAN可以发现任意形状的簇类。

　　3. 同时，DBSCAN能够识别出噪声点。

　　4.DBSCAN对于数据库中样本的顺序不敏感，即Pattern的输入顺序对结果的影响不大。但是，对衣律于处于簇类之间边界样本，可能会根据哪个簇类优先被探测到而其归属有所摆动。

缺点

　　1. DBScan不能很好反映高维数据。

　　2. DBScan不能很好反映数据集以变化的密度。

　　3.如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差。