基于密度方法的聚类教育课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,基于密度方法的聚类,主要内容,回顾,密度聚类方法,DBSCAN,算法,OPTICS,算法,网格聚类方法,CLIQUE,算法,回顾,聚类,聚类,(clustering),也称为聚类分析,指将样本分到不同的组中使得同一组中的样本差异尽可能的小，而不同组中的样本差异尽可能的大。,聚类得到的不同的组称为簇,(cluster),。,一个好的聚类方法将产生以下的聚类,最大化类中的相似性,最小化类间的相似性,回顾,聚类的分类：,划分聚类方法,层次聚类方法,密度聚类方法,网格聚类方法,模型聚类方法,在基于划分的聚类中，任务就是将数据划分成K个不相交的点集，使每个子集中的点尽可能同质。,基于划分的方法，其代表算法有,k-means,算法、K-medoids等,划分聚类方法,k-means,算法,k-means,算法基本步骤,从,n,个数据对象任意选择,k,个对象作为初始聚类中心；,根据每个聚类对象的均值,(,中心对象,),，计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分；,重新计算每个,(,有变化,),聚类的均值,(,中心对象,),；,计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条件不满足则回到步骤,2,。,k-means,优缺点,主要优点：,是解决聚类问题的一种经典算法，简单、快速。,对处理大数据集，该算法是相对可伸缩和高效率的。,当结果簇是密集的，它的效果较好。,主要缺点,在簇的平均值被定义的情况下才能使用。,必须事先给出,k,（要生成的簇的数目），而且对初值敏感，对于不同的初始值，可能会导致不同结果。,不适合于发现非凸面形状的簇或者大小差别很大的簇。而且，它对于“躁声”和孤立点数据是敏感的。,层次聚类方法,层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为：,凝聚的层次聚类,：一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。,分裂的层次聚类,：采用自顶向下的策略，它首先将所有对象置于一个簇中，然后逐渐细分为越来越小的簇，直到达到了某个终结条件。,层次凝聚的代表是,AGNES,算法。层次分裂的代表是,DIANA,算法。,层次聚类优缺点,层次聚类方法是不可逆的，也就是说，当通过凝聚式的方法将两组合并后，无法通过分裂式的办法再将其分离到之前的状态，反之亦然。,另外，层次聚类过程中调查者必须决定聚类在什么时候停止，以得到某个数量的分类。,在不必要的情况下应该小心使用层次聚类方法。,划分聚类方法,层次聚类方法,密度聚类方法 ：,基于密度的聚类方法以数据集在空间分布上的稠密程度为依据进行聚类，无需预先设定簇的数量，因此特别适合对于未知内容的数据集进行聚类。,网格聚类方法,模型聚类方法,密度聚类方法,基于密度方法的聚类,密度聚类方法的指导思想是，只要一个区域中的点的密度大于某个域值，就把它加到与之相近的聚类中去。对于簇中每个对象，在给定的半径,的邻域中至少要包含最小数数目（,MinPts,）个对象。,这类算法能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，且对噪声数据不敏感。,代表算法有：,DBSCAN,、,OPTICS,、,DENCLUE,算法等。,基于密度方法的聚类,-DBSCAN,DBSCAN,（,Density-Based Spatial Clustering of Applications with Noise,）一个比较有代表性的基于密度的聚类算法。与层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在有“噪声”的空间数据库中发现任意形状的聚类。,传统基于中心的密度定义为：,数据集中特定点的密度通过该点,半径之内的点计数(包括本身)来估计。,显然，密度依赖于半径。,传统的密度定义：基于中心的方法,基于密度方法的聚类,-DBSCAN,所用到的基本术语,定义,对象的,-,邻域：给定对象在半径,内的区域。,定义,核心对象：如果一个对象的,-,邻域至少包含最小数目,MinPts,个,对象，则称该对象为核心对象。,例,下图中，,=1cm,，,MinPts=5,，,q,是一个核心对象。,定义,直接密度可达：给定一个对象集合,D,，如果,p,是在,q,的,-,邻域内，而,q,是一个核心对象，我们说对象,p,从对象,q,出发是直接密度可达的。,例,在下图中，,=1cm,，,MinPts=5,，,q,是一个核心对象，对象,p1,从对象,q,出发是直接密度可达的。,基于密度方法的聚类,-DBSCAN,所用到的基本术语,密度可达,定义,密度可达的：如果存在一个对象链,p,1,，,p,2,，,，,p,n,，,p,1=,q,，,p,n=,p,，对,p,i,D,，（,1=,i,=,n,），,p,i+1,是从,p,i,关于,和,MitPts,直接密度,可达的，则对象,p,是从对象,q,关于,和,MinPts,密度可达的。,例,在下图中，,=1cm,，,MinPts=5,，,q,是一个核心对象，,p,1,是,从,q,关于,和,MitPts,直接密度可达，,p,是从,p,1,关于,和,MitPts,直接密度,可达，则对象,p,从对象,q,关于,和,MinPts,密度可达的,基于密度方法的聚类,-DBSCAN,所用到的基本术语,图 密度相连,图 噪声,定义,噪声,:,一个基于密度的簇是基于密度可达性的最大的密度相,连对象的集合。不包含在任何簇中的对象被认为是“噪声”。,边界点：,边界点不是核心点，但落在某个核心点的邻域内。,噪声就是那些既不是边界点也不是核心点的对象,定义,密度相连的：如果对象集合,D,中存在一个对象,o,，使得对象,p,和,q,是从,o,关于,和,MinPts,密度可达的，那么对象,p,和,q,是关于,和,MinPts,密度相连的。,DBSCAN算法概念示例,如图所示，,用一个相应的半径表示，设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,DBSCAN,算法根据以上的定义在数据库中发现簇和噪声。簇可等价于集合,D,中，这个簇核心对象密度可达的所有对象的集合。,DBSCAN,通过检查数据集中每个对象的,-,邻域来寻找聚类。如果一个点,p,的,-,邻域包含多于,MinPts,个对象，则创建一个,p,作为核心对象的新簇,C,。然后，,DBSCAN,从,C,中寻找未被处理对象,q,的,-,邻域，如果,q,的,-,邻域包含多,MinPts,个对象，则还未包含在,C,中的,q,的邻点被加入到簇中，并且这些点的,-,邻域将在下一步中进行检测。这个过程反复执行，当没有新的点可以被添加到任何簇时，该过程结束。具体如下：,基于密度方法的聚类,-DBSCAN,DBSCAN,算法描述：,输入：包含,n,个对象的数据库，半径,，最少数目,MinPts,。,输出：所有生成的簇，达到密度要求。,1.REPEAT,2.,从数据库中抽取一个未处理过的点；,3.IF,抽出的点是核心点,THEN,找出所有从该点密度可达的对象，形成一个簇,4.ELSE,抽出的点是边缘点,(,非核心对象,),，跳出本次循环，寻找下一点；,5.UNTIL,所有点都被处理；,DBSCAN算法步骤,输入：数据集D，参数,MinPts,输出：,簇集合,(,1)首先将数据集,D,中的所有对象标记unvisited；,(2)do,(3)从D中随机选取一个unvisited对象p，并将p标记为visited；,if,p,的,邻域 包含的对象数至少为,MinPts,个,创建,新簇C,，并把p添加到c中；,令N为,p,的,邻域 中对象的集合；,(,7,),for,N 中每个点pi,if,pi 是unvisited,标记pi 为visited；,if pi 的,邻域 至少有,MinPts,个 对象，把这些对象添加到N；,if pi 还不是任何簇的对象。将,p,i 添加到 簇C中；,(,12,)end for,(,13,),输出C,(,14,),Else 标记p 为噪声,(,15,),Untill 没有标记为unvisited 的对象,基于密度方法的聚类,-DBSCAN,下面给出一个样本事务数据库（见下表），对它实施,DBSCAN,算法。,根据所给的数据通过对其进行,DBSCAN,算法，以下为算法的步骤（设,n,=12,，用户输入,=1,，,MinPts=4,）,序号,属性,1,属性,2,1,2,1,2,5,1,3,1,2,4,2,2,5,3,2,6,4,2,7,5,2,8,6,2,9,1,3,10,2,3,11,5,3,12,2,4,样本事务数据库,DBSCAN,聚类过程,第,1,步，在数据库中选择一点,1,，由于在以它为圆心的，以,1,为半径的圆内包含,2,个点（小于,4,），因此它不是核心点，选择下一个点。,第,2,步，在数据库中选择一点,2,，由于在以它为圆心的，以,1,为半径的圆内包含,2,个点，因此它不是核心点，选择下一个点。,第,3,步，在数据库中选择一点,3,，由于在以它为圆心的，以,1,为半径的圆内包含,3,个点，因此它不是核心点，选择下一个点。,DBSCAN,聚类过程,第,4,步，在数据库中选择一点,4,，由于在以它为圆心的，以,1,为半径的圆内包含,5,个点，因此它是核心点，寻找从它出发可达的点（直接可达,4,个，间接可达,3,个），聚出的新类,1,，,3,，,4,，,5,，,9,，,10,，,12,，选择下一个点。,DBSCAN,聚类过程,第,5,步，在数据库中选择一点,5,，已经在簇,1,中，选择下一个点。,第,6,步，在数据库中选择一点,6,，由于在以它为圆心的，以,1,为半径的圆内包含,3,个点，因此它不是核心点，选择下一个点。,DBSCAN,聚类过程,第,7,步，在数据库中选择一点,7,，由于在以它为圆心的，以,1,为半径的圆内包含,5,个点，因此它是核心点，寻找从它出发可达的点，聚出的新类,2,，,6,，,7,，,8,，,11,，选择下一个点。,DBSCAN,聚类过程,第,8,步，在数据库中选择一点,8,，已经在簇,2,中，选择下一个点。,第,9,步，在数据库中选择一点,9,，已经在簇,1,中，选择下一个点。,第,10,步，在数据库中选择一点,10,，已经在簇,1,中，选择下一个点。,第,11,步，在数据库中选择一点,11,，已经在簇,2,中，选择下一个点。,第,12,步，选择,12,点，已经在簇,1,中，由于这已经是最后一点所有点都以处理，程序终止。,基于密度方法的聚类-DBSCAN,步骤,选择的点,在,中点的个数,通过计算可达点而找到的新簇,1,1,2,无,2,2,2,无,3,3,3,无,4,4,5,簇,C,1,：,1,，,3,，,4,，,5,，,9,，,10,，,12,5,5,3,已在一个簇,C,1,中,6,6,3,无,7,7,5,簇,C,2,：,2,，,6,，,7,，,8,，,11,8,8,2,已在一个簇,C,2,中,9,9,3,已在一个簇,C,1,中,10,10,4,已在一个簇,C,1,中，,11,11,2,已在一个簇,C,2,中,12,12,2,已在一个簇,C,1,中,算法执行过程：,DBSCAN的时间复杂性,时间复杂度,DBSCAN算法要对每个数据对象进行邻域检查时间性能较低。,DBSCAN的基本时间复杂度是 O(N*找出Eps领域中的点所需要的时间),N是点的个数。最坏情况下时间复杂度是O(N,2,),在低维空间数据中,有一些数据结构如KD树，使得可以有效的检索特定点给定距离内的所有点，时间复杂度可以降低到O(NlogN),DBSCAM的空间复杂性,空间复杂度,在聚类过程中，DBSCAN一旦找到一个核心对象，即以该核心对象为中心向外扩展此过程中核心对象将不断增多，未处理的对象被保留在内存中若数据库中存在庞大的聚类，将需要很大的存来存储核心对象信息，其需求难以预料,当数据量增大时，要求较大的内存支持 I/0 消耗也很大;,低维或高维数据中，其空间都是O(N),基于密度方法的聚类,优点,能克服基于距离的算法只能发现“类圆形”的聚类的缺点，可发现任意形状的聚类，有效地处理数据集中的噪声数据，数据输入顺序不敏感,缺点,输入参数敏感确定参数,，,MinPts,困难，若选取不当，将造成聚类质量下降,由于在,DBSCAN,算法中，变量,，,MinPts,是全局惟一的，当空间聚类的密度不均匀、聚类间距离相差很大时，聚类质量较差。,计算密度单元的计算复杂度大，需要建立空间索引来降低计算量，且对数据维数的伸缩性较差。这类方法需要扫描整个数据库，每个数据对象都可能引起一次查询，因此当数据量大时会造成频繁的,I,/,O,操作。,OPTICS,算法,由于在,DBSCAN,算法中，变量,，,MinPts,是全局惟一的，当空间聚类的密度不均匀、聚类间距离相差很大时，聚类质量较差。,许多现实的数据集内在的聚类结构不能够通过全局的密度参数来描述，数据空间中不同区域的聚类需要不同的局部密度。,OPTICS,算法,尽管,dbscan,能够根据给定的输入参数,，和,MinPts,聚类对象，但是它把选择能产生可接受的聚类结果的参数值的责任留给了用户。这是许多其他算法都存在的问题。但是对于高维数据而言设定准确的参数非常困难。参数设置有细微的不同都可能导致差别很大的聚类结果。全局参数不能很好地刻画其内在的聚类结构。,OPTICS,算法,下图中所描述的数据集不能通过一个全局密度参数同时区分出簇,A,、,B,、,C,、,C1,、,C2,和,C3,，只能得到,A,、,B,、,C,或,C1,、,C2,和,C3,，对于,C1,、,C2,和,C3,而言,A,、,B,、,C,都是噪声。,对于固定的,MinPts,值，和两个,1,2,，关于,1,的,MinPts,簇,C,一定是关于,2,和,MinPts,簇,C,的子集，这就意味着。如果两个对象在同一个基于密度的簇中，则它们也是在同一个具有较低密度要求的簇中。,OPTICS,算法,为了克服在聚类分析中使用一组全局参数的缺点，提出了,OPTICS,聚类分析方法。,P,为对象，数据集,D,，,为距离值，,N(q),为邻域，,MinPts,。两个定义：,P,的,核心距离,：,使得,P,成为核心对象的最小,，是使,p,称为核心对象的最小半径阈值。,若,|,（,N(q)MinPts,，即,P,不是核心对象，核心距离则,无定义。,q,关于,对象,P,的,可达距离,：是使,q,从,p,密度可达的最小半径。,p,的核心距离和,p,q,的欧几里得距离之间的较大值，,p,必须是核心对象且,q,在,p,的邻域内。,若,|,N(p)|MinPts,，即,P,不是核心对象，则无定义,否则，定义为,Max,（核心距离，,|,（,p,q,）,|,）,OPTICS,算法,例,核心距离与可达距离,假设,=6mm,，,MinPts,=5,。,P,的核心距离是,p,于第四个最近的数据对象之间的距离,，,q1,到,p,的可达距离是,p,的核心距离（,=3mm,），因为它比,q1,到,p,的欧氏距离大。,q2,关于,p,的科大距离是,p,到,q2,的欧氏距离，它大于,p,的核心距离。,OPTICS,算法,OPTICS,算法并不显式的产生数据及聚类，而是输出簇排序（,cluster ordering,），这个排序是所有分析对象的线性表，并且代表数据基于密度的聚类结构。,较稠密簇中的对象在簇排序中相互靠近。这个排序等价于从较广泛的参数设置中得到基于密度的聚类。这样,optics,不需要用户提供特定密度阈值。,簇排列可以用来提取基本聚类信息，导出内在的聚类结构，也可以提供聚类的可视化。,OPTICS,算法,为了构造不同的类,，,对象需要按特定的次序处理，这个次序选择这样的对象，及关于最小的,值，它是密度可达的，以便较高密度（较低 值）的簇先完成。,optics 算法计算给定数据库中所有对象的排序，并且存储每个对象核心距离和相应的可达距离。,optics 维护一个称作order seeds 的表来来产生输出排列，orderseeds 中的对象按到各自的最近核心对象的可达距离排序，及按每个对象的最小可达距离排序。,OPTICS,算法,寻找簇,Reachability-distance,undefined,Cluster-order,of the objects,数据集的簇排序可以用图形描述，这有助于可视化和理解数据集中聚类结构。例如下图是一个简单的二维数据集的可达性图。,可达距离,未定义,OPTICS,算法并不直接寻找各个簇,而是将基于密度查找簇所需要的信息记录下来,这些信息反映了数据空间基于密度的簇结构。同时从这些密度信息可以直接发现各个簇。,OPTICS,采取了两个方法来达到目标,1),定义了对象的核心距离和可达距离,以反映对象附近的密度大小,;2),在迭代查找可达对象时,对种子对象依可达距离进行排序,从而在簇扩展时优先扩展密度值较大区域的点,。这样,OPTICS,算法实现了数据库所有对象的排序,这一对象序列就可以反映出数据空间基于密度的簇结构信息。基于这些信息可以容易地确定合适的,值,并随之发现各个簇。另外,OPTICS,还提供了自动的簇发现方法。,OPTICS,算法较好地解决了,DBSCAN,算法的对输入参数,敏感的问题,但是由于采用了复杂的处理方法以及额外的磁盘,IPO,操作,使得,OPTICS,实际运行的速度远远低于,DBSCAN,。,不同密度、形状、大小的簇,参数的影响,减小，则可达距离为无穷大的点增多；,MinPts,减小，核心对象增多，图象更尖锐,基于网格的方法（,Grid-Based Methods,）,聚类高维数据是聚类分析中一个非常重要的任务，而一般聚类方法无法处理这些数据。用户感兴趣的通常是某个高维数据空间的若干个子空间，对该空间内数据点的聚类要比原始空间更好一些。高维数据中，通常只有少数几维与某些簇相关，其他不相关的维数据可能会产生大量的噪声而屏蔽真实的簇。,为聚类高维数据集便提出了,基于网格的方法的聚类。,基于网格的方法（,Grid-Based Methods,）,将数据空间划分成为有限个单元（,cell,）的网格结构，所有的处理都是以单个单元为对象的。,这种方法的主要优点是它的处理速度很快，处理时间独立于数据对象的数目，只与每一维所划分的单元数目有关,代表算法有：,CLIQUE,算法。,CLQUE,是一个综合了基于密度和基于网格方法的聚类算法，对于大型数据库中的高维数据的聚类比较有效,在高维数据的子空间中识别稠密的聚类，所产生的理解结果与所给的输入数据无关。,CLIQUE,：高维度数据的自动子空间聚类算法,CLIQUE,：聚类高维空间,CLIQUE,的中心思想如下：,给定一个多维数据点的大集合，数据点在数据空间中通常不是均衡分布的。,CLIQUE,区分空间中稀疏的和,“,拥挤的,”,区域，以发现数据集合,全局分布模式。,将数据空间中的每个维划分成等长且数量相等的间隔段，即单元。如果一个单元中的包含数据点超过了某个输入模型参数，则该单元是密集的。在,CLIQUE,中，一个聚类被定义为相连的密集单元的最大集合。,问题描述,要能自动地识别一个高维数据的子空间,限制在只对原始空间的子空间的搜索而不是使用一个新的维度,为了识别数据点的密度，将数据空间划分并找出在每个单元中数据点的数量。,聚类是子空间中相连的高密度单元的并集，即将聚类映射到轴对称的超矩形中。,聚类在空间中的描述,设,A,A1,A2,Ad,是一个有界的、全部有序的域的集合。而,S,A1A2,Ad,是一个,d,维的数字空间，,A1,，,A2,，,，,Ad,定义为,S,的维。,输入是由,d,维点集,V,v1,v2,vm,组成的，其中,Vi=,Vi,的第,j,个元素来自域,Aj,。,将数据空间,S,划分成非重叠矩形单元。单元的划分方法是在每一个维上将维分割成,个等长的间隔段，,是输入参数。,每一个单元,u,是由每一个属性一个间隔段组成的交集。形式为,u1,u2,ud,，其中,ui=li,hi,）是在,Ai,的划分中的右边界开放的间隔段。,聚类在空间中的描述,一个点,V,属于单元,u=u1,u2,.ud,当对所有的,ui,，有,livihi,。,一个单元的选择性（,selectivity,）：单元内数据点的数量与单元的总数据点数量之比。,称单元,u,是稠密的：若单元的选择性大于密度阈值,。,聚类在空间中的描述,两个,k,维单元,u1,，,u2,是连接的，即他们之间有一个公共面,。,若存在,k-1,维，假设是维,A,t1,，,A,t2,，,A,tk-1,，单元,u1,r,t1,r,t2,r,tk,及,u2=r,t1,，,r,t2,，,r,tk-1,是相连的，,则有,r,tj,=r,tj,，并且有,h,tk,l,tk,或者,h,tk,l,tk,。,若,RC,R,，则称一个区域,R,包含于一个聚类,C,中。若没有其他,R,的超集包含于聚类,C,中，则称区域,R,是最大的。,一个聚类的最小描述是具有最大区域的聚类的非冗余的覆盖。,例子（一）,在下图中，二维空间（,age,salary,）划分成,1010,格一个单元是间隔段的交集；例如单元,u,（,30 age35,）（,1salary2,）。一个区域是单元的矩形的并集。,A,与,B,是两个区域：,A,（,30 age50,）（,4 salary8,）,B=,（,40 age60,）（,2 salary6,）。,假设 阴影部分是稠密的单元，,A B,是一个聚类。,该聚类的最小描述为,：（,30 age50,）（,4 salary8,）（,40 age60,）（,2 salary6,）。,例子（二）：,图二：原始数据空间的子空间中的聚类,在图二中，假设,20,，没有,2-,维单元是稠密的，在原始数据空间中就没有聚类。,但将数据点投影到维,salary,上，就有三个,1,维密度单元，其中两个是相连的，因此，在,1,维,salary,子空间上就有两个聚类：,C,5salary7,及,D,2 salary3.,由于在,age,子空间中没有密度单元，故在该子空间中就没有聚类。,CLIQUE,算法,由以下几部分组成：,1,）含有聚类子空间的识别。,2,）聚类的识别。,3,）对聚类产生最小的描述。,含有聚类子空间的识别,自下而上算法,定理,（单调性）,若在,k,维数据空间的点集,S,是一个聚类，则,S,也是在这个数据空间的任意（,k-1,）维投影中一个聚类的一部分。,该算法利用聚类针对维度的单调性的准则减少搜索空间,算法步骤,1.,遍历一遍数据库确定,1,维的密度单元，即将,n,维数据空间划分为不重叠的矩形单元。,2.,利用单调性定理：在确定了,k-1,维密度单元之后，确定候选的,k,维密度单元,3.,直到不再有候选单元产生，算法结束,聚类的识别,输入：密度单元的集合,D,输出：,D,的划分,问题就变成在下面定义的图中发现连通图：图的顶点对应着密度单元，当且仅当两个密度单元有公共面时对应的顶点之间有一条边,利用度优先深搜索算法发现图中的连通图，即从,D,中的某个密度单元,u,开始，将第一个聚类的编号赋予给该单元，再去发现与它相连的单元，之后，若在图中还存在没有被访问的单元，重复此过程。,生成最小的聚类描述,步骤：,1,、使用贪心算法由若干最大矩形来覆盖聚类即对每个聚类，确定覆盖连接密集单元聚类的最大区域。,2,、去掉多余的矩形从而产生最小的覆盖,贪心增长算法,从任意的一个密度单元,u1,开始,用贪心法寻找覆盖,u1,的最大区域,R1,，将,R1,加到,R,中,找另一个单元,u2,，但在,R,中没有任何最大区域覆盖,u2,，找出其最大区域,R2,直到任何单元都有,R,中的某个最大区域所覆盖。,为了得到覆盖密度单元的一个最大区域，从,u,开始沿着维,a1,，从单元的两个方向增长，通过使用包含在,C,中相连的密度单元，增长,u,，得到一个矩形区域。再沿着维,a2,增长此区域，得到一个尽可能较大的矩形区域。沿着所有的维重复此过程，就产生覆盖,u,的最大区域。,最小覆盖,从覆盖中移走最小的大区域，该大区域是冗余的，即其中的每个单元都包含在其他的大区域中。,重复上述过程，直到在没有可移走的大区域为止。,CLIQUE,的有效性,CLIQUE,自动地发现最高维的子空间，高密度聚类存在于这些子空间中。,CLIQUE,对元组的输入顺序不敏感，无需假设任何规范的数据分布。,CLIQUE,随输入数据的大小线性地扩展，当数据的维数增加时具有良好的可伸缩性。,但是，由于方法大大简化，聚类的精确性可能会降低。,