基于密度方法的聚类

聚类分析宋宜飞主要内容回顾密度聚类方法DBSCAN算法OPTICS算法网格聚类方法CLIQUE算法回顾聚类聚类(clustering)也称为聚类分析,指将样本分到不同的组中使得同一组中的样本差异尽可能的小，而不同组中的样本差异尽可能的大。聚类得到的不同的组称为簇(cluster)。一个好的聚类方法将产生以下的聚类最大化类中的相似性最小化类间的相似性回顾聚类的分类：划分聚类方法层次聚类方法密度聚类方法网格聚类方法模型聚类方法在基于划分的聚类中，任务就是将数据划分成K个不相交的点集，使每个子集中的点尽可能同质。基于划分的方法，其代表算法有k-means算法、K-medoids等划分聚类方法算法k-means算法基本步骤1.从n个数据对象任意选择k个对象作为初始聚类中心；2.根据每个聚类对象的均值(中心对象)，计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；3.重新计算每个(有变化)聚类的均值(中心对象)；4.计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤2。优缺点主要优点：是解决聚类问题的一种经典算法，简单、快速。对处理大数据集，该算法是相对可伸缩和高效率的。当结果簇是密集的，它的效果较好。主要缺点在簇的平均值被定义的情况下才能使用。必须事先给出k（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。不适合于发现非凸面形状的簇或者大小差别很大的簇。而且，它对于“躁声”和孤立点数据是敏感的。层次聚类方法层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为：凝聚的层次聚类：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。分裂的层次聚类：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。层次凝聚的代表是AGNES算法。层次分裂的代表是DIANA算法。层次聚类优缺点层次聚类方法是不可逆的，也就是说，当通过凝聚式的方法将两组合并后，无法通过分裂式的办法再将其分离到之前的状态，反之亦然。另外，层次聚类过程中调查者必须决定聚类在什么时候停止，以得到某个数量的分类。在不必要的情况下应该小心使用层次聚类方法。划分聚类方法层次聚类方法密度聚类方法：基于密度的聚类方法以数据集在空间分布上的稠密程度为依据进行聚类，无需预先设定簇的数量，因此特别适合对于未知内容的数据集进行聚类。网格聚类方法模型聚类方法密度聚类方法基于密度方法的聚类密度聚类方法的指导思想是，只要一个区域中的点的密度大于某个域值，就把它加到与之相近的聚类中去。对于簇中每个对象，在给定的半径ε的邻域中至少要包含最小数数目（MinPts）个对象。这类算法能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。代表算法有：DBSCAN、OPTICS、DENCLUE算法等。DBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise）一个比较有代表性的基于密度的聚类算法。与层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的空间数据库中发现任意形状的聚类。传统基于中心的密度定义为：数据集中特定点的密度通过该点ε半径之内的点计数(包括本身)来估计。显然，密度依赖于半径。传统的密度定义：基于中心的方法所用到的基本术语定义对象的ε-邻域：给定对象在半径ε内的区域。定义核心对象：如果一个对象的ε-邻域至少包含最小数目MinPts个对象，则称该对象为核心对象。例下图中，ε=1cm，MinPts=5，q是一个核心对象。定义直接密度可达：给定一个对象集合D，如果p是在q的ε-邻域内，而q是一个核心对象，我们说对象p从对象q出发是直接密度可达的。例在下图中，ε=1cm，MinPts=5，q是一个核心对象，对象p1从对象q出发是直接密度可达的。所用到的基本术语密度可达定义密度可达的：如果存在一个对象链p1，p2，…，pn，p1=q，pn=p，对pi∈D，（1=i=n），pi+1是从pi关于ε和MitPts直接密度可达的，则对象p是从对象q关于ε和MinPts密度可达的。例在下图中，ε=1cm，MinPts=5，q是一个核心对象，p1是从q关于ε和MitPts直接密度可达，p是从p1关于ε和MitPts直接密度可达，则对象p从对象q关于ε和MinPts密度可达的所用到的基本术语图密度相连图噪声定义噪声:一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含在任何簇中的对象被认为是“噪声”。边界点：边界点不是核心点，但落在某个核心点的邻域内。噪声就是那些既不是边界点也不是核心点的对象定义密度相连的：如果对象集合D中存在一个对象o，使得对象p和q是从o关于ε和MinPts密度可达的，那么对象p和q是关于ε和MinPts密度相连的。算法概念示例如图所示，ε用一个相应的半径表示，设MinPts=3，请分析Q,M,P,S,O,R这5个样本点之间的关系。“直接密度可达”和“密度可达”概念示意描述解答：根据以上概念知道：由于有标记的各点M、P、O和R的ε近邻均包含3个以上的点，因此它们都是核对象；M是从P“直接密度可达”；而Q则是从M“直接密度可达”；基于上述结果，Q是从P“密度可达”；但P从Q无法“密度可达”(非对称)。类似地，S和R从O是“密度可达”的；O、R和S均是“密度相连”的。DBSCAN算法根据以上的定义在数据库中发现簇和噪声。簇可等价于集合D中，这个簇核心对象密度可达的所有对象的集合。DBSCAN通过检查数据集中每个对象的ε-邻域来寻找聚类。如果一个点p的ε-邻域包含多于MinPts个对象，则创建一个p作为核心对象的新簇C。然后，DBSCAN从C中寻找未被处理对象q的ε-邻域，如果q的ε-邻域包含多MinPts个对象，则还未包含在C中的q的邻点被加入到簇中，并且这些点的ε-邻域将在下一步中进行检测。这个过程反复执行，当没有新的点可以被添加到任何簇时，该过程结束。具体如下：算法描述：输入：包含n个对象的数据库，半径ε，最少数目MinPts。输出：所有生成的簇，达到密度要求。1.REPEAT2.从数据库中抽取一个未处理过的点；3.IF抽出的点是核心点THEN找出所有从该点密度可达的对象，形成一个簇4.ELSE抽出的点是边缘点(非核心对象)，跳出本次循环，寻找下一点；5.UNTIL所有点都被处理；算法步骤输入：数据集D，参数MinPts,ε输出：簇集合(1)首先将数据集D中的所有对象标记unvisited；(2)do(3)从D中随机选取一个unvisited对象p，并将p标记为visited；(4)ifp的ε邻域包含的对象数至少为MinPts个(5)创建新簇C，并把p添加到c中；(6)令N为p的ε邻域中对象的集合；(7)forN中每个点pi(8)ifpi是unvisited(9)标记pi为visited；(10)ifpi的ε邻域至少有MinPts个对象，把这些对象添加到N；(11)ifpi还不是任何簇的对象。将pi添加到簇C中；(12)endfor(13)输出C(14)Else标记p为噪声(15)Untill没有标记为unvisited的对象下面给出一个样本事务数据库（见下表），对它实施DBSCAN算法。根据所给的数据通过对其进行DBSCAN算法，以下为算法的步骤（设n=12，用户输入ε=1，MinPts=4）序号属性1属性2121251312422532642752862913102311531224样本事务数据库聚类过程第1步，在数据库中选择一点1，由于在以它为圆心的，以1为半径的圆内包含2个点（小于4），因此它不是核心点，选择下一个点。第2步，在数据库中选择一点2，由于在以它为圆心的，以1为半径的圆内包含2个点，因此它不是核心点，选择下一个点。第3步，在数据库中选择一点3，由于在以它为圆心的，以1为半径的圆内包含3个点，因此它不是核心点，选择下一个点。聚类过程第4步，在数据库中选择一点4，由于在以它为圆心的，以1为半径的圆内包含5个点，因此它是核心点，寻找从它出发可达的点（直接可达4个，间接可达3个），聚出的新类{1，3，4，5，9，10，12}，选择下一个点。聚类过程第5步，在数据库中选择一点5，已经在簇1中，选择下一个点。第6步，在数据库中选择一点6，由于在以它为圆心的，以1为半径的圆内包含3个点，因此它不是核心点，选择下一个点。聚类过程第7步，在数据库中选择一点7，由于在以它为圆心的，以1为半径的圆内包含5个点，因此它是核心点，寻找从它出发可达的点，聚出的新类{2，6，7，8，11}，选择下一个点。聚类过程第8步，在数据库中选择一点8，已经在簇2中，选择下一个点。第9步，在数据库中选择一点9，已经在簇1中，选择下一个点。第10步，在数据库中选择一点10，已经在簇1中，选择下一个点。第11步，在数据库中选择一点11，已经在簇2中，选择下一个点。第12步，选择12点，已经在簇1中，由于这已经是最后一点所有点都以处理，程序终止。：{1，3，4，5，9，10，12}553已在一个簇C1中663无775簇C2：{2，6，7，8，11}882已在一个簇C2中993已在一个簇C1中10104已在一个簇C1中，11112已在一个簇C2中12122已在一个簇C1中算法执行过程：的时间复杂性时间复杂度DBSCAN算法要对每个数据对象进行邻域检查时间性能较低。DBSCAN的基本时间复杂度是O(N*找出Eps领域中的点所需要的时间),N是点的个数。最坏情况下时间复杂度是O(N2)在低维空间数据中,有一些数据结构如KD树，使得可以有效的检索特定点给定距离内的所有点，时间复杂度可以降低到O(NlogN)的空间复杂性空间复杂度在聚类过程中，DBSCAN一旦找到一个核心对象，即以该核心对象为中心向外扩