密度聚类
密度聚类
于密度的方法 基于密度聚类( 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, @<=eps 直接密度可达的:点p关于Ep,MnP是从点q直接密度可达 的,如果 1)p属于NE(y 2)核心点条件: NEps(o>= MinPts Minpts =5 Eps=1 cm 3
3 基于密度的聚类: 背景I ◼ 两个参数: ◼ Eps: 邻域的最大半径 ◼ MinPts: 在 Eps-邻域中的最少点数 ◼ NEps(p): {q belongs to D | dist(p,q) <= Eps} ◼ 直接密度可达的: 点 p 关于Eps, MinPts 是从点q直接密度可达 的, 如果 ◼ 1) p 属于 NEps(q) ◼ 2) 核心点条件: |NEps (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,p2pi>,满足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,p2,…..,pi>，满足p1=p，pi=q，pi 直接密度可达pi+1，则称p密度可达q) p q MinPts = 5 Eps = 1 cm