1、Pattern Recognition &artificial IntelligenceLecture 7: 聚 类 算法（四）1基于密度的聚类算法 DBSCAN：基于高密度连通区域聚类 OPTICS：通过点排序识别聚类结构 DENCLUE: 基于密度分布函数的聚类 2基于密度的聚类方法 划分 和 层次 方法旨在发现球状类。他们很难发现任意形状的类。 改进思想，将 类 看作数据空间中由低密度区域分隔开的高密度对象区域。这是基于密度的聚类方法的主要策略。 基于密度的聚类方法可以用来过滤噪声孤立点数据，发现任意形状的类。3密度概念核心对象 (Core object): 一个对象的 邻域至少包含最小
2、数目 MinPts个对象。边界点： 不是核心点 ，但落在某个核心 点的 Eps 邻域内的对象称为边界点。噪声： 不属于任何类的对象为噪声。边界对象： 对于空间中的一个对象，如果它在给定半径 e的邻域中的对象个数大于密度阀值 MinPts，则该对象被称为 核心对象 ，否则称为 边界对象 。4由一个核心对象和其密度可达的所有对象构成聚类 。直接密度可达的 (Directly density reachable, DDR): 给定对象集合 D, 如果 p是在 q的 邻域内 , 而 q是核心对象 , 我们说对象 p是从对象 q直接密度可达的 (如果 q是一个核心对象， p属于 q的邻域，那么称 p直接
3、密度可达 q。 )密度可达的 (density reachable): 存在一个从 p到 q的 DDR对象链 (如果存在一条链 ，满足 p1=p， pi=q， pi直接密度可达 pi+1，则称 p密度可达 q)密度概念两个参数 : Eps: 邻域的最大半径 MinPts: 在 Eps-邻域中的最少点数 NEps(q): q belongs to D | dist(p,q) = MinPts 密度概念6密度可达 : 点 p 关于 Eps, MinPts 是从 q密度可达的 , 如果 存在一个节点链 p1, , pn, p1 = q, pn = p 使得 pi+1 是从 pi直接密度可达的密度相连
4、的 :点 p关于 Eps, MinPts 与点 q是密度相连的 , 如果 存在点 o 使得 , p 和 q 都是关于 Eps, MinPts 是从 o 密度可达的 (如果存在 o， o密度可达 q和 p，则称 p和 q是 密度连通 的 )pq p1p qo密度概念7Eg: 假设半径 =3 ， MinPts=3 。点 p 的 邻域 中有点m, p, p1, p2, o, 点 m 的 邻域 中有点 m, q, p, m1, m2, 点 q的 邻域 有 q, m,点 o 的 邻域 中有点 o, p, s, 点 s 的 邻域 中有点 o, s, s1. 那么核心对象有 p,m,o,s (q 不是核心对
5、象 ，因为它对应的 领域中点数量等于 2 ，小于 MinPts=3) ； 点 m 从点 p 直接密度可达 ，因为 m 在 p 的 领域内，并且 p 为核心对象； 点 q 从点 p 密度可达 ，因为点 q 从点 m 直接密度可达，并且点 m 从点 p 直接密度可达； 点 q 到点 s 密度相连 ，因为点 q 从点 p 密度可达，并且s 从点 p 密度可达。密度概念：例子8密度概念：例子 MinPts=3 q是从 p密度可达； p不是从 q密度可达（ q非核心） S和 r从 o密度可达； o从 r密度可达； r, s密度相连9DBSCAN (Density Based Spatial Clustering of Applications with Noise) DBSCAN：一种基于 高密度连通区域 的基于密度的聚类方法，该算法将具有足够高密度的区域划分为类，并在具有噪声的空间数据库中发现任意形状的类。它将类定义为 密度相连的点的最大集合 。10
