复旦大学：《商务智能》课程PPT教学课件（商务数据分析）密度聚类——算法详解

密度聚类

密度聚类

于密度的方法 基于密度聚类( Density- Based clustering) ■主要特点: 发现任意形状的聚类 处理噪音 遍扫描 需要密度参数作为终止条件 些有趣的研究 DBSCAN: Ester, et al. (KDD96) OPTICS: Ankerst, et al (sIGmod99) DENCLUE: Hinneburg D Keim(KDD298) CLIQUE: Agrawal, et aL. ( SIGMOD98)

2 基于密度的方法 ◼ 基于密度聚类 (Density-Based Clustering) ◼ 主要特点: ◼ 发现任意形状的聚类 ◼ 处理噪音 ◼ 一遍扫描 ◼ 需要密度参数作为终止条件 ◼ 一些有趣的研究: ◼ DBSCAN: Ester, et al. (KDD’96) ◼ OPTICS: Ankerst, et al (SIGMOD’99). ◼ DENCLUE: Hinneburg & D. Keim (KDD’98) ◼ CLIQUE: Agrawal, et al. (SIGMOD’98)

于密度的聚类:背景I 两个参数: Eps:邻域的最大半径 a MinPts:在Eps-邻域中的最少点数 NEns(p): g belongs to d dist(p, @= MinPts Minpts =5 Eps=1 cm 3

3 基于密度的聚类: 背景I ◼ 两个参数: ◼ Eps: 邻域的最大半径 ◼ MinPts: 在 Eps-邻域中的最少点数 ◼ NEps(p): {q belongs to D | dist(p,q) = MinPts p q MinPts = 5 Eps = 1 cm

密度概念 核心对象( Core objec:一个对象的ε邻域至少包含最小数 目 Minpts个对象, ■不是核心点,但落在某个核心点的Eps邻域内的对象称为边 界点,不属于任何簇的对象为噪声. ■对于空间中的一个对象,如果它在给定半径e的邻域中的对 象个数大于密度阀值 MinPts,则该对象被称为核心对象,否 则称为边界对象 Outlier Border Eps lci ore Minpts =5 4

4 密度概念 ◼ 核心对象 (Core object): 一个对象的–邻域至少包含最小数 目MinPts个对象, ◼ 不是核心点,但落在某个核心点的 Eps 邻域内的对象称为边 界点,不属于任何簇的对象为噪声. ◼ 对于空间中的一个对象，如果它在给定半径e的邻域中的对 象个数大于密度阀值MinPts，则该对象被称为核心对象，否 则称为边界对象。 Core Border Outlier Eps = 1cm MinPts = 5

密度概念 直接密度可达的 Directly density reachable,DDR):给定对 象集合D,如果p是在q的邻域内,而q是核心对象,我们说对 象p是从对象q直接密度可达的(如果q是一个核心对象,p属 于q的邻域,那么称p直接密度可达q。) 密度可达的( density reachable:存在一个从p到q的DDR对 象链(如果存在一条链,满足p1=p,p=q,p 直接密度可达p+1,则称p密度可达q Minpts=5 E ps cm 由一个核心对象和其密度可达的所有对象构成一个聚类

由一个核心对象和其密度可达的所有对象构成一个聚类。 密度概念 ◼ 直接密度可达的(Directly density reachable, DDR): 给定对 象集合D, 如果p是在q的–邻域内, 而q是核心对象, 我们说对 象p是从对象q直接密度可达的(如果q是一个核心对象，p属 于q的邻域，那么称p直接密度可达q。) ◼ 密度可达的(density reachable): 存在 一个从p到q的DDR对 象链(如果存在一条链，满足p1=p，pi=q，pi 直接密度可达pi+1，则称p密度可达q) p q MinPts = 5 Eps = 1 cm

于密度的聚类:背景Ⅱ 密度可达: 点p关于Es,MinP是从q密度可 达的,如果存在一个节点链p1,…,pn, p使得p#是从直接密 度可达的 密度相连的: 点p关于Ep,MinP与点q是密度 相连奖打果存在点力使2和 达的(如果存在0,o密度可达q和p, 则称p和q是密度连通的) 由一个核心对象和其密度可达的所有对象构成一个聚类

6 基于密度的聚类: 背景II ◼ 密度可达: ◼ 点 p 关于Eps, MinPts 是从 q密度可 达的, 如果 存在一个节点链 p1 , …, pn , p1 = q, pn = p 使得 pi+1 是从pi直接密 度可达的 ◼ 密度相连的: ◼ 点 p关于 Eps, MinPts 与点 q是密度 相连的, 如果 存在点 o 使得, p 和 q 都是关于Eps, MinPts 是从 o 密度可 达的(如果存在o，o密度可达q和p， 则称p和q是密度连通的) p q p1 p q o 由一个核心对象和其密度可达的所有对象构成一个聚类

密度概念 Eg:假设半径E=3, MinPts=3, 点p的ε领域中有点{m,pp1p2,O}点m的ε领域中有 点{m,qpm1,m2},点q的ε领域中有{q,m},点o的ε领 域中有点{o,p,S},点S的ε领域中有点{o,ss1}. 那么核心对象有p,m,o,s(q不是核心对象,因为它对应 的E领域中点数量等于2,小于 MinPts=3); 点m从点p直接密度可达,因为m在p的ε领域内,并 且p为核心对象; 点q从点p密度可达,因为点q从点m直接密度可达,并 且点m从点p直接密度可达; 点q到点S密度相连,因为点q从点p密度可达,并 且s从点p密度可达。 由一个核心对象和其密度可达的所有对象构成一个聚类

7 密度概念 ◼ Eg: 假设半径 Ε=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 不是核心对象，因为它对应 的  领域中点数量等于 2 ，小于 MinPts=3) ； ◼ 点 m 从点 p 直接密度可达，因为 m 在 p 的  领域内，并 且 p 为核心对象； ◼ 点 q 从点 p 密度可达，因为点 q 从点 m 直接密度可达，并 且点 m 从点 p 直接密度可达； ◼ 点 q 到点 s 密度相连，因为点 q 从点 p 密度可达，并 且 s 从点 p 密度可达。 由一个核心对象和其密度可达的所有对象构成一个聚类

例子 MinPts=3 ■q是从p密度可达;p不是从q密度可达(q非核心) S和r从O密度可达;O从r密度可达; r,s密度相连

8 例子 ◼ MinPts=3 ◼ q是从p密度可达； p不是从q密度可达（q非核心） ◼ S和r从o密度可达；o从r密度可达； ◼ r, s密度相连

a为核心对象,b为边界对象,且 a直接密度可达b, 但b不直接密度可达a因为b不是 个核心对象 a 2021/8/25

2021/8/25 a为核心对象，b为边界对象，且 a直接密度可达b， 但b不直接密度可达a,因为b不是 一个核心对象

C直接密度可达aa直接密度可达b, 所以C密度可达b, 同理b不密度可达C,但b和C密度 连通 2021/8/25

2021/8/25 c直接密度可达a,a直接密度可达b, 所以c密度可达b， 同理b不密度可达c，但b和c密度 连通