基于密度方法的聚类.ppt

《基于密度方法的聚类.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、聚类分析宋宜飞主要内容回顾密度聚类方法DBSCAN算法OPTICS算法网格聚类方法CLIQUE算法www.wondershare.com回顾聚类聚类(clustering)也称为聚类分析,指将样本分到不同的组中使得同一组中的样本差异尽可能的小，而不同组中的样本差异尽可能的大。聚类得到的不同的组称为簇(cluster)。一个好的聚类方法将产生以下的聚类最大化类中的相似性最小化类间的相似性www.wondershare.com回顾聚类的分类：划分聚类方法层次聚类方法密度聚类方法网格聚类方法模型聚类方法www.wondershare.c

2、om在基于划分的聚类中，任务就是将数据划分成K个不相交的点集，使每个子集中的点尽可能同质。基于划分的方法，其代表算法有k-means算法、K-medoids等划分聚类方法www.wondershare.comk-means算法k-means算法基本步骤从n个数据对象任意选择k个对象作为初始聚类中心；根据每个聚类对象的均值(中心对象)，计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；重新计算每个(有变化)聚类的均值(中心对象)；计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步

3、骤2。www.wondershare.comk-means优缺点主要优点：是解决聚类问题的一种经典算法，简单、快速。对处理大数据集，该算法是相对可伸缩和高效率的。当结果簇是密集的，它的效果较好。主要缺点在簇的平均值被定义的情况下才能使用。必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。不适合于发现非凸面形状的簇或者大小差别很大的簇。而且，它对于“躁声”和孤立点数据是敏感的。www.wondershare.com层次聚类方法层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体

4、又可分为：凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。层次凝聚的代表是AGNES算法。层次分裂的代表是DIANA算法。www.wondershare.com层次聚类优缺点层次聚类方法是不可逆的，也就是说，当通过凝聚式的方法将两组合并后，无法通过分裂式的办法再将其分离到之前的状态，反之亦然。另外，层次聚类过程中调查者必须决定聚类在什么时候停止

5、，以得到某个数量的分类。在不必要的情况下应该小心使用层次聚类方法。www.wondershare.com划分聚类方法层次聚类方法密度聚类方法：基于密度的聚类方法以数据集在空间分布上的稠密程度为依据进行聚类，无需预先设定簇的数量，因此特别适合对于未知内容的数据集进行聚类。网格聚类方法模型聚类方法密度聚类方法www.wondershare.com基于密度方法的聚类密度聚类方法的指导思想是，只要一个区域中的点的密度大于某个域值，就把它加到与之相近的聚类中去。对于簇中每个对象，在给定的半径ε的邻域中至少要包含最小数数目（MinPts）个对

6、象。这类算法能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。代表算法有：DBSCAN、OPTICS、DENCLUE算法等。www.wondershare.com基于密度方法的聚类-DBSCANDBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise）一个比较有代表性的基于密度的聚类算法。与层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的空间数据库中发现任意形状的聚

7、类。www.wondershare.com传统基于中心的密度定义为：数据集中特定点的密度通过该点ε半径之内的点计数(包括本身)来估计。显然，密度依赖于半径。传统的密度定义：基于中心的方法www.wondershare.com基于密度方法的聚类-DBSCAN所用到的基本术语定义对象的ε-邻域：给定对象在半径ε内的区域。定义核心对象：如果一个对象的ε-邻域至少包含最小数目MinPts个对象，则称该对象为核心对象。例下图中，ε=1cm，MinPts=5，q是一个核心对象。定义直接密度可达：给定一个对象集合D，如果p是在q的ε-邻域内，而

8、q是一个核心对象，我们说对象p从对象q出发是直接密度可达的。例在下图中，ε=1cm，MinPts=5，q是一个核心对象，对象p1从对象q出发是直接密度可达的。www.wondershare.com基于密度方法的聚类-DBSCAN所用到的基本术语密度