聚类分析—密度聚类讲解.ppt

数据挖掘
Topic3-聚类分析
密度聚类
基于密度的方法
基于密度聚类 Density- Based Clustering)
主要特点
发现任意形状的聚类
处理噪音
■一遍扫描
需要密度参数作为终止条件
一些有趣的研究
DBSCAN: Ester, et al. (KDD296)
OPTICS: Ankerst, et al (sIGMoD99)
DENCLUE: Hinneburg D Keim(KDD98)
CLIQUE: Agrawal, et aL. ( SIGMOD98)
2
于密度的聚类:背景I
两个参数
aEps:邻域的最大半径
Minpts:在Eps邻域中的最少点数
NEn (p: a belongs to D I dist(p, q)<= Ep
直接密度可达的:点p关于Eps, Minpts是从点q直接密度可达
的,如果
a1)p属于N2(q)
2)核心点条件:
Npm(q川>= MinPts
MinPts s
Ep
cm
密度概念
核心对象( Core object:一个对象的e邻域至少包含最小数
目 Minpts个对象,
不是核心点,但落在某个核心点的Eps邻域内的对象称为边
界点不属于任何簇的对象为噪声
对于空间中的一个对象,如果它在给定半径e的邻域中的对
象个数大于密度阀值 MinPts,则该对象被称为核心对象,否
则称为边界对象。
Outlier
Border
○
Eps= lcm
ore
Minpts =5
密度概念
直接密度可达的 Directly density reachable,DDR:给定对
象集合D,如果p是在q的E邻域内,而q是核心对象,我们说对
象p是从对象q直接密度可达的(如果q是一个核心对象,p属
于q的邻域,那么称p直接密度可达q。)
密度可达的( density reachable):存在一个从p到q的DDR对
象链(如果存在一条链<p1,p2灬…pi>,满足p1=p,p=q,p1
直接密度可达p+1,则称p密度可达q)
Minpts 5
Eps= 1
由一个核心对象和其密度可达的所有对象构成一个聚类。
于密度的聚类:背景I
密度可达
点p关于Ep, Minpts是从q密度可
达的,如果存在一个节点链P…Pn
度可达场>D使得P是从直接密
■密度相连的
点p关于E,MinP与点q是密度
相连的如果存在点O使得,和q/p
都是关于Eps,MiP是从O密度可
达的(如果存在O,O密度可达q和p,
则称p和q是密度连通的)
由一个核心对象和其密度可达的所有对象构成一个聚类
密度概念
Eg∶假设半径E=3,MnPs=3
点p的E领域中有点{m,pp1p2,o},点m的ε领域中有
点{m,qpm1m2},点q的ε领域中有{q,m},点o的ε领
域中有点{OpS},点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密度相连
a为核心对象,b为边界对象,且
a直接密度可达b,
但b不直接密度可达a因为b不是
个核心对象
a
19/5/30