聚类分析—密度聚类 PPT课件.ppt

聚类分析—密度聚类_PPT课件数据挖掘
Topic3--聚类分析
密度聚类
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)
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
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,p2,…..,pi>,满足p1=p,pi=q,pi直接密度可达pi+1,则称p密度可达q)
p
q
MinPts = 5
Eps = 1 cm
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
由一个核心对象和其密度可达的所有对象构成一个聚类。
2018/1/2
a为核心对象,b为边界对象,且a直接密度可达b,
但b不直接密度可达a,因为b不是一个核心对象
2018/1/2
c直接密度可达a,a直接密度可达b,所以c密度可达b,
同理b不密度可达c,但b和c密度连通