节基于密度的聚类

1、2.4 基于密度的聚类算法w 基于密度的聚类算法有：DBSCAN、GDBSCAN、OPTICS、DBCLASD等w 本节介绍基于密度聚类的基本思路和基本概念，然后介绍DBSCANw 基于密度的算法聚类时一般不需给定聚类数k，聚类的个数由算法的结果确定。w DBSCAN(Density Based Spatial Clustering of Applications with Noise)一、基本思路w 属于一个聚类的各点之间距离较小，密度较大。密度类似于相似度。w 密度可以用一定范围内点数来表示。w 在一个点的一定距离范围内点很少，则可认为该点是孤立点（类）。去除孤立点可以减少计算量，同时可以

2、提高聚类精度。w 点的密度是一种关系，能传递。因此若某点是密度高的，与它邻近的其它点可以继续寻找它们的邻近点，看它们是否也是密度高的。二、几个概念w 直接密度可达的n点q的Eps邻域：n点p和q如果满足如下条件：n则称点p是从点q直接密度可达的，并且点q成为核。w 其中Eps和MinPts是需要提供给算法的参数，分别表示点的邻域半径和该邻域的最少点数。),(|)(EpsqpdistDpqNMinPtsqNqNp| )(| )2),() 1w 密度可达的n如果存在点的序列：n其中 是从 直接密度可达的，则称点pi+1是从q关于Eps和MinPts密度可达的。w 密度相连的n如果存在点r,p,q，

3、p和q都是从点r关于Eps和MinPts密度可达的，则称点p是从点q关于Eps和MinPts密度相连的w 基于密度的簇n令D表示数据集，D的一个非空集合C满足下列条件l对任意点p和q，若 且q是从p关于Eps和MinPts密度可达的，则有l p与q是关于Eps和MinPts密度相连的。n则称C是基于密度的簇12,iq p pp1ipipCpCq:,Cqpw 噪声点集n令 是数据集中关于不同参数Eps和MinPts的基于密度的簇，则点集n称作噪声点集w 令p为数据集D中的一个点， ,则集合n是基于密度的簇w 令C是一个关于Eps和MinPts的簇，p为C中某个满足 的点，则C应满足下列条件kCC

4、C,21:|iCpiDpMinPtspN| )(|密度可达的和关于是从MinPtsEpspqDqCMinPtspN| )(|密度可达的和关于是从MinPtsEpspqDqC关于密度可达的图示三、DBSCAN算法w 输入 ，Eps和MinPtsw 随机选择一点 ，检索它的Eps邻域，若该邻域的点数不少于MinPts，则点 是第一个核，它的Eps邻域内的点都是关于 直接密度可达的。w 检索所有从点 的密度可达点，这就生成第一个基于密度的簇。w 访问数据集的下一个点，并同样形成另一个基于密度的簇。w 基于参数Eps和MinPts，若没有新的点是从任何簇中的点密度可达的，则计算结束。D中剩下的点是噪声

5、点集，予以删除。,21nxxxDDxiixixixDBSCAN的特点w 基于密度也需要距离计算w 每个基于密度的簇就是一个聚类w 可以识别孤立点类w 计算时间复杂度为O(nlogn)，因此效率较高w 它需要用户给定控制参数Eps和MinPts，这两个参数对聚类质量有较大影响，而用户往往不能准确设定这两个参数w 高维数据集分布不均匀，难以给出一组全局的参数(Eps和MinPts)来刻画内在的聚类结构。例2-9 用DBSCAN对例2-2 实例聚类：Eps=0.6,MinPts=1实例x属性1属性2属性311.15.20.322.03.50.831.55.00.442.24.00.952.14.20

6、.861.02.00.570.92.10.581.34.80.3例2.9中各点之间的距离矩阵049. 7082. 214. 0012. 144. 248. 2034. 134. 237. 225. 0030. 096. 204. 308. 132. 1056. 181. 183. 171. 055. 063. 1045. 011. 321. 35 . 173. 146. 099. 108765432187654321计算有关点的邻域w 随机选择点x1，根据上述距离矩阵，可以给出Eps的邻域为 ，其点数=2MinPts，因此x1是核。w 再给出 的Eps邻域，没有增加新的点，点 互相直接密度可达

7、的，它们成为一个基于密度的簇。w 再选择x2，求它的Eps邻域为x4， x4的Eps邻域为x5， x5的邻域没有新点，因此它们构成基于密度的簇。,83xx83,xx831,xxx求基于密度的簇w 同样可发现x6 ，x7构成基于密度的簇。w 因此我们找到三个基于参数Eps=0.6和MinPts=1的簇w 如果设Eps=0.5，则x2将从第二簇中分离出来，成为孤立点。该点可以删除。,;,;,76542831xxxxxxxxOPTICS简介w OPTICS(Ordering Points to Identify the Clustering Structure)w OPTICS与DBSCAN在结果上是等价的，时间复杂度相同。w OPT