密度聚类算法详解课件.pptVIP

数据挖掘Topic3--聚类分析密度聚类

基于密度的方法nn基于密度聚类(Density-BasedClustering)主要特点:发现任意形状的聚类n处理噪音一遍扫描需要密度参数作为终止条件nnn一些有趣的研究:nnnnnDBSCAN:Ester,etal.(KDD’96)OPTICS:Ankerst,etal(SIGMOD’99).DENCLUE:HinneburgD.Keim(KDD’98)CLIQUE:Agrawal,etal.(SIGMOD’98)2

基于密度的聚类:背景I两个参数:nEps:邻域的最大半径nMinPts:在Eps-邻域中的最少点数nnN(p):{qbelongstoD|dist(p,q)=Eps}Eps直接密度可达的:点p关于Eps,MinPts是从点q直接密度可达的,如果n1)p属于N(q)nEps2)核心点条件:n|N(q)|=MinPtspMinPts=5Eps=1cmEpsq3

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

密度概念直接密度可达的(Directlydensityreachable,DDR):给定对n象集合D,如果p是在q的?–邻域内,而q是核心对象,我们说对象p是从对象q直接密度可达的(如果q是一个核心对象，p属于q的邻域，那么称p直接密度可达q。)密度可达的(densityreachable):存在一个从p到q的DDR对象n链(如果存在一条链p1,p2,…..,pi，满足p=p，p=q，p直1ii接密度可达p，则称p密度可达q)i+1pMinPts=5Eps=1cmq由一个核心对象和其密度可达的所有对象构成一个聚类。

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

密度概念Eg:假设半径Ε=3，MinPts=3，nn点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密度可达。nnnn由一个核心对象和其密度可达的所有对象构成一个聚类。7

例子MinPts=3nq是从p密度可达；p不是从q密度可达（q非核心）nS和r从o密度可达；o从r密度可达；nr,s密度相连n8

a为核心对象，b为边界对象，且a直接密度可达b，但b不直接密度可达a,因为b不是一个核心对象2024/5/15星期三

c直接密度可达a,a直接密度可达b,所以c密度可达b，同理b不密度可达c，但b和c密度连通2024/5/15星期三

DBSCAN(1996)nnDBSCAN(DensityBasedSpatialClusteringofApplicationswithNoise)一个基于密度的聚类算法可以在带有“噪音”的空间数据库中发现任意形状的聚类OutlierBorderEps=1cmCoreMinPts=511

DBSCAN(1996)DBSCAN：一种基于高密度连通区域的基于密度的n聚类方法，该算法将具有足够高密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇。它将簇定义为密度相