资源描述：
《密度聚类 算法详解课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据挖掘Topic3--聚类分析密度聚类基于密度的方法基于密度聚类(Density-BasedClustering)主要特点:发现任意形状的聚类处理噪音一遍扫描需要密度参数作为终止条件一些有趣的研究:DBSCAN:Ester,etal.(KDD’96)OPTICS:Ankerst,etal(SIGMOD’99).DENCLUE:Hinneburg&D.Keim(KDD’98)CLIQUE:Agrawal,etal.(SIGMOD’98)基于密度的聚类:背景I两个参数:Eps:邻域的最大半径MinPts:在Eps-邻域中的最少点数NEps(p):{qbelongstoD
2、dist(p,q
3、)<=Eps}直接密度可达的:点p关于Eps,MinPts是从点q直接密度可达的,如果1)p属于NEps(q)2)核心点条件:
4、NEps(q)
5、>=MinPtspqMinPts=5Eps=1cm密度概念核心对象(Coreobject):一个对象的–邻域至少包含最小数目MinPts个对象,不是核心点,但落在某个核心点的Eps邻域内的对象称为边界点,不属于任何簇的对象为噪声.对于空间中的一个对象，如果它在给定半径e的邻域中的对象个数大于密度阀值MinPts，则该对象被称为核心对象，否则称为边界对象。CoreBorderOutlierEps=1cmMinPts=5密度概念直接密度可达的(D
6、irectlydensityreachable,DDR):给定对象集合D,如果p是在q的–邻域内,而q是核心对象,我们说对象p是从对象q直接密度可达的(如果q是一个核心对象，p属于q的邻域，那么称p直接密度可达q。)密度可达的(densityreachable):存在一个从p到q的DDR对象链(如果存在一条链，满足p1=p，pi=q，pi直接密度可达pi+1，则称p密度可达q)pqMinPts=5Eps=1cm基于密度的聚类:背景II密度可达:点p关于Eps,MinPts是从q密度可达的,如果存在一个节点链p1,…,pn,p1=q,pn=p使得pi+1是从
7、pi直接密度可达的密度相连的:点p关于Eps,MinPts与点q是密度相连的,如果存在点o使得,p和q都是关于Eps,MinPts是从o密度可达的(如果存在o，o密度可达q和p，则称p和q是密度连通的)pqp1pqo由一个核心对象和其密度可达的所有对象构成一个聚类。密度概念Eg:假设半径Ε=3，MinPts=3，点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，小于Mi
8、nPts=3)；点m从点p直接密度可达，因为m在p的领域内，并且p为核心对象；点q从点p密度可达，因为点q从点m直接密度可达，并且点m从点p直接密度可达；点q到点s密度相连，因为点q从点p密度可达，并且s从点p密度可达。由一个核心对象和其密度可达的所有对象构成一个聚类。例子MinPts=3q是从p密度可达；p不是从q密度可达（q非核心）S和r从o密度可达；o从r密度可达；r,s密度相连a为核心对象，b为边界对象，且a直接密度可达b，但b不直接密度可达a,因为b不是一个核心对象2021/7/29c直接密度可达a,a直接密度可达b,所以c密度可达b，同理b不密度可达c，但b和c密度连通2
9、021/7/29DBSCAN(1996)DBSCAN(DensityBasedSpatialClusteringofApplicationswithNoise)一个基于密度的聚类算法可以在带有“噪音”的空间数据库中发现任意形状的聚类CoreBorderOutlierEps=1cmMinPts=5DBSCAN(1996)DBSCAN：一种基于高密度连通区域的基于密度的聚类方法，该算法将具有足够高密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇。它将簇定义为密度相连的点的最大集合；DBSCAN(续)算法任意选取一个点p得到所有从p关于Eps和MinPts密度可达的点.如果p是
10、一个核心点,则找到一个聚类.如果p是一个边界点,没有从p密度可达的点,DBSCAN将访问数据库中的下一个点.继续这一过程,直到数据库中的所有点都被处理.DBSCAN的复杂度采用空间索引,复杂度为O(nlogn),否则为O(n2)DBSCAN的缺点:对用户定义的参数是敏感的,参数难以确定(特别是对于高维数据),设置的细微不同可能导致差别很大的聚类.（数据倾斜分布）全局密度参数不能刻画内在的聚类结构DBSCAN从任一对象p开始，根据参数e和MinP
