文档介绍：数据挖掘
-聚类分析
密度聚类
于密度的方法
基于密度聚类( Density- Based Clustering)
主要特点:
发现任意形状的聚类
处理噪音
一遍扫描
需要密度参数作为终止条件
些有趣的研究:
DBSCAN: Ester, et al. (KDD96)
.OPTICS: Ankerst, et al (SIGMOD99)
DENCLUE: Hinneburg D Keim (KDD98)
CLIQUE: Agrawal, et al. ( SIGMOD98)
于密度的聚类:背景I
两个参数
aEp:邻域的最大半径
Minpts:在Eps-邻域中的最少点数
NEps(p): q belongs to D I dist(p, 9)<= ep
■直接密度可达的:点P关于Ep,MinP是从点q直接密度可达
的,如果
aD)P属于N2(q)
2)核心点条件:
WEps (q)l>=MinPts
MinPts= 5
密度概念
核心对象( Core object):一个对象的ε-邻域至少包含最小数
目 Minpts个对象,
不是核心点,但落在某个核心点的Eps邻域内的对象称为边
界点,不属于任何簇的对象为噪声.
对于空间中的一个对象,如果它在给定半径e的邻域中的对
象个数大于密度阀值 Minpts,则该对象被称为核心对象,否
则称为边界对象
Outlier
Border
○
Core
MinPts=5
○
密度概念
直接密度可达的 Directly density reachable,DDR):给定对
象集合D,如果是在q的e邻域内,而q是核心对象,我们说对
象p是从对象q直接密度可达的(如果q是一个核心对象,p属
于q的邻域,那么称p直接密度可达q。)
密度可达的 density reachable:存在一个从p到q的DDR对
象链(如果存在一条链<p1P2…p>,满足p1=p,p=q,p
直接密度可达p+1,则称p密度可达q)
Minpts =5
Eps= l cm
由一个核心对象和其密度可达的所有对象构成一个聚类。
于密度的聚类:背景
密度可达
点P关于ES,MimP是从q密度可
达的,如果存在一个节点链P…,Pn,
P1=q,Dn=P使得P是从p直接密
度可达的
q
密度相连的:
点p关于Es,MinP与点q是密度
相连的,如果存在点O使得,P和q
都是关于Eps,MinP是从o密度可
达的(如果存在O,0密度可达q和p,
则称p和q是密度连通的)
由一个核心对象和其密度可达的所有对象构成一个聚类。
密度概念
Eg∶假设半径E=3,MnP=3,
点p的ε领域中有点{m;pp1p2,o},点m的ε领域中有
点{m,qp,m1,m2},点q的ε领域中有{qm}点O的E领
域中有点{op,S},点S的E领域中有点{o,S,51}
■那么核心对象有pm,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
nq是从p密度可达;p不是从q密度可达(q非核心)
S和从O密度可达;o从「密度可达;
ar,s密度相连
a为核心对象,b为边界对象,且
a直接密度可达b,
但b不直接密度可达a因为b不是
个核心对象
a
c直接密度可达a,a直接密度可达b
所以C密度可达b,
a
同理b不密度可达C,但b和c密度
连通