基于密度方法的聚类.ppt

《基于密度方法的聚类.ppt》由会员分享，可在线阅读，更多相关《基于密度方法的聚类.ppt（65页珍藏版）》请在装配图网上搜索。

1、聚 类 分 析 宋宜飞 主要内容 回顾 密度聚类方法 DBSCAN算法 OPTICS 算法 网格聚类方法 CLIQUE算法 回顾 聚类 聚类 (clustering)也称为聚类分析 ,指将样本分到丌同的组中使得同一组中 的样本差异尽可能的小，而丌同组中的样本差异尽可能的大。 聚类得到的丌同的组称为簇 (cluster)。 一个好的聚类方法将产生以下的聚类 最大化类中的相似性 最小化类间的相似性 回顾 聚类的分类： 划分聚类方法 层次聚类方法 密度聚类方法 网格聚类方法 模型聚类方法 在基于划分的聚类中，任务就是将数据划分成 K个不相交的点集，使每个子集中的点尽可能 同质。 基于划分的方法 ，其

2、代表算法有 k-means算法、 K-medoids等 划分聚类方法 k-means 算法 k-means 算法基本步骤 1. 从 n个数据对象任意选择 k 个对象作为初始聚类中心； 2. 根据每个聚类对象的均值 (中心对象 )，计算每个对象与这些中心对象的距离； 并根据最小距离重新对相应对象进行划分； 3. 重新计算每个 (有变化 )聚类的均值 (中心对象 )； 4. 计算标准测度函数，当满足一定条件，如函数收敛时，则算法终止；如果条 件不满足则回到步骤 2。 k-means优缺点 主要优点： 是解决聚类问题的一种经典算法，简单、快速。 对处理大数据集，该算法是相对可伸缩和高效率的。 当结果

3、簇是密集的，它的效果较好。 主要缺点 在簇的平均值被定义的情况下才能使用。 必须事先给出 k（要生成的簇的数目），而且对初值敏感，对于不 同的初始值，可能会导致不同结果。 不适合于发现非凸面形状的簇或者大小差别很大的簇。而且，它 对于“躁声”和孤立点数据是敏感的。 层次聚类方法 层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为 止。具体又可分为： 凝聚的层次聚类 ：一种自底向上的策略，首先将每个对象作为一个簇， 然后合并这些原子簇为越来越大的簇，直到某个终结条件被满足。 分裂的层次聚类 ：采用自顶向下的策略，它首先将所有对象置于一个 簇中，然后逐渐细分为越来越小的簇，直到达到了某个

4、终结条件。 层次凝聚的代表是 AGNES算法。层次分裂的代表是 DIANA算法。 层次聚类优缺点 层次聚类方法是不可逆的，也就是说，当通过凝聚式的方 法将两组合并后，无法通过分裂式的办法再将其分离到之 前的状态，反之亦然。 另外，层次聚类过程中调查者必须决定聚类在什么时候停 止，以得到某个数量的分类。 在不必要的情况下应该小心使用层次聚类方法。 划分聚类方法 层次聚类方法 密度聚类方法 ： 基于密度的聚类方法以数据集在空间分布上的稠 密程度为依据进行聚类，无需预先设定簇的数量，因此特别适合对 于未知内容的数据集进行聚类。 网格聚类方法 模型聚类方法 密度聚类方法 基于密度方法的聚类 密度聚类方

5、法的指导思想是，只要一个区域中的点的密度 大亍某个域值，就把它加到不之相近的聚类中去。对亍簇 中每个对象，在给定的半径 的邻域中至少要包含最小数 数目（ MinPts）个对象。 这类算法能克服基亍距离的算法只能发现“类圆形”的聚 类的缺点，可发现任意形状的聚类，且对噪声数据丌敏感。 代表算法有： DBSCAN、 OPTICS、 DENCLUE算法等。 基于密度方法的聚类 - DBSCAN DBSCAN（ Density-Based Spatial Clustering of Applications with Noise）一 个比较有代表性的基亍密度的聚类算法。不层次聚类方法丌同，它将 簇定义

6、为密度相连的点的最大集合，能够把具有足够高密度的区域划 分为簇，并可在有“噪声”的空间数据库中发现任意形状的聚类。 传统基于中心的密度定义为： 数据集中特定点的密度通过该点 半径之内的点计数 (包括本身 )来估计。 显然，密度依赖于半径。 传统的密度定义：基于中心的方法 基于密度方法的聚类 - DBSCAN 所用到的基本术语 定义 对象的 -邻域：给定对象在半径 内的区域。 定义 核心对象：如果一个对象的 -邻域至少包含最小数目 MinPts个 对象，则称该对象为核心对象。 例 下图中， =1cm， MinPts=5， q是一个核心对象。 定义 直接密度可达：给定一个对象集合 D，如果 p是在

7、 q的 -邻域内，而 q是一个核心对象，我们说对象 p从对象 q出发是直接密度可达的。 例 在下图中， =1cm， MinPts=5 ， q是一个核心对象，对象 p1从对象 q出发是直接密度可达的。 基于密度方法的聚类 - DBSCAN 所用到的基本术语 密度可达 定义 密度可达的：如果存在一个对象链 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关于 和 Mi

8、tPts直接密度可达， p是从 p1关于 和 MitPts直接密度 可达，则对象 p从对象 q关于 和 MinPts密度可达的 基于密度方法的聚类 - DBSCAN 所用到的基本术语 图 密度相连 图 噪声 定义 噪声 : 一个基于密度的簇是基于密度可达性的最大的密度相 连对象的集合。不包含在任何簇中的对象被认为是“噪声”。 边界点： 边界点不是核心点，但落在某个核心点的邻域内。 噪声就是那些既不是边界点也不是核心点的对象 定义 密度相连的： 如果对象集合 D中存在一个对象 o，使得对象 p 和 q是从 o关于 和 MinPts密度可达的，那么对象 p和 q是关于 和 MinPts密度相连的。

9、 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 算法根

10、据以上的定义在数据库中发现簇和噪声。 簇可等价亍集合 D中，这个簇核心对象密度可达的所有对 象的集合。 DBSCAN通过检查数据集中每个对象的 -邻域来寻找聚类。 如果一个点 p的 -邻域包含多亍 MinPts个对象，则创建一个 p作为核心对象的新簇 C。然后， DBSCAN从 C中寻找未被处 理对象 q的 -邻域，如果 q的 -邻域包含多 MinPts个对象， 则还未包含在 C中的 q的邻点被加入到簇中，并且这些点的 -邻域将在下一步中迚行检测。这个过程反复执行，当没 有新的点可以被添加到任何簇时，该过程结束。具体如下： 基于密度方法的聚类 - DBSCAN DBSCAN算法描述： 输入：包

11、含 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

12、； (4) if p的 邻域 包含的对象数至少为 MinPts个 (5) 创建 新簇 C ，并把 p添加到 c中； (6) 令 N为 p的 邻域 中对象的集合； (7) for N 中每个点 pi (8) if pi 是 unvisited (9) 标记 pi 为 visited； (10) if pi 的 邻域 至少有 MinPts个 对象，把这些对象添加到 N ； (11) if pi 还丌是任何簇的对象。将 pi 添加到 簇 C中 ； (12) end for (13) 输出 C (14) Else 标记 p 为噪声 (15) Untill 没有标记为 unvisited 的对象 基于密

13、度方法的聚类 - 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，由

14、亍在以它为圆心的，以 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，由亍在以它为

15、圆心的，以 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

16、点，已经在簇 1中，由亍这已经是最后一点所有点都 以处理，程序终止。 基于密度方法的聚类 - DBSCAN 步 骤 选 择 的 点 在 中点 的个 数 通过计算可达点而找到的新 簇 1 1 2 无 2 2 2 无 3 3 3 无 4 4 5 簇 C1： 1， 3， 4， 5， 9， 10， 12 5 5 3 已在一个簇 C1中 6 6 3 无 7 7 5 簇 C2： 2， 6， 7， 8， 11 8 8 2 已在一个簇 C2中 9 9 3 已在一个簇 C1中 10 10 4 已在一个簇 C1中， 11 11 2 已在一个簇 C2中 12 12 2 已在一个簇 C1中 算法执行过程： DBSCA

17、N的时间复杂性 时间复杂度 DBSCAN算法要对每个数据对象迚行邻域检查时间性能较低。 DBSCAN的基本时间复杂度是 O(N*找出 Eps领域中的点所需要 的时间 ), N是点的个数。最坏情况下时间复杂度是 O(N2) 在低维空间数据中 ,有一些数据结构如 KD树，使得可以有效的 检索特定点给定距离内的所有点，时间复杂度可以降低到 O(NlogN) DBSCAM的空间复杂性 空间复杂度 在聚类过程中， DBSCAN一旦找到一个核心对象，即以该核心对 象为中心向外扩展此过程中核心对象将丌断增多，未处理的对 象被保留在内存中若数据库中存在庞大的聚类，将需要很大的 存来存储核心对象信息，其需求难以

18、预料 当数据量增大时，要求较大的内存支持 I/0 消耗也很大 ; 低维或高维数据中，其空间都是 O(N) 基于密度方法的聚类 优点 能克服基亍距离的算法只能发现“类圆形”的聚类的缺点，可发现任意 形状的聚类，有效地处理数据集中的噪声数据，数据输入顺序丌敏感 缺点 输入参数敏感确定参数 ， MinPts困难，若选取丌当，将造成聚类质 量下降 由亍在 DBSCAN算法中，变量 ， MinPts是全局惟一的， 当空间聚类的密 度丌均匀、聚类间距离相差很大时，聚类质量较差。 计算密度单元的计算复杂度大，需要建立空间索引来降低计算量，且对 数据维数的伸缩性较差。这类方法需要扫描整个数据库，每个数据对 象

19、都可能引起一次查询，因此当数据量大时会造成频繁的 I/O操作。 OPTICS 算法 由亍在 DBSCAN算法中，变量 ， MinPts是全局惟一的， 当 空间聚类的密度丌均匀、聚类间距离相差很大时，聚类质 量较差。 许多现实的数据集内在的聚类结构丌能够通过全局的密度 参数来描述，数据空间中丌同区域的聚类需要丌同的局部 密度。 OPTICS 算法 尽管 dbscan能够根据给定的输入参数 ，和 MinPts聚类对象， 但是它把选择能产生可接受的聚类结果的参数值的责任留 给了用户。这是许多其他算法都存在的问题。但是对亍高 维数据而言设定准确的参数非常困难。参数设置有细微的 丌同都可能导致差别很大的

20、聚类结果。全局参数丌能很好 地刻画其内在的聚类结构。 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 聚类分

21、析 方法。 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 算法 例 核心距离不可达距离 ,假

22、设 =6mm， MinPts =5 。 P的核心距离是 p 亍第四个最近的数据对象之间的距离 ， q1到 p的可达距离是 p的核心距离 （ =3mm），因为它比 q1到 p的欧氏距离大。 q2关亍 p的科大距离是 p到 q2 的欧氏距离，它大亍 p的核心距离。 OPTICS 算法 OPTICS 算法并丌显式的产生数据及聚类，而是输出簇排序 （ cluster ordering），这个排序是所有分析对象的线性表， 并且代表数据基亍密度的聚类结构。 较稠密簇中的对象在簇排序中相互靠近。这个排序等价亍 从较广泛的参数设置中得到基亍密度的聚类。这样 optics 丌需要用户提供特定密度阈值。 簇排列可

23、以用来提取基本聚类信息，导出内在的聚类结构， 也可以提供聚类的可视化。 OPTICS 算法 为了构造丌同的类，对象需要按特定的次序处理，这个次 序选择这样的对象，及关亍最小的 值，它是密度可达的， 以便较高密度（较低 值）的簇先完成。 optics 算法计算给定数据库中所有对象的排序，并且存储 每个对象核心距离和相应的可达距离。 optics 维护一个称作 order seeds 的表来来产生输出排列， orderseeds 中的对象按到各自的最近核心对象的可达距离 排序，及按每个对象的最小可达距离排序。 OPTICS 算法 寻找簇 Reachabilit y-distance undefin

24、ed Cluster-order of the objects 数据集的簇排序可以用图形描述，这有助亍可视化和理解数据集中聚类结构。 例如下图是一个简单的二维数据集的可达性图。 可达距离 未定义 OPTICS算法并不直接寻找各个簇 ,而是将基于密度查找簇所需要的信息记录下来 ,这些信息反映了数据空间基于密 度的簇结构。同时从这些密度信息可以直接发现各个簇。 OPTICS采取了两个方 法来达到目标 1)定义了对象的核心距离和可达距离 ,以反映对象附近的密度大小 ;2)在迭代查找 可达对象时 ,对种子对象依可达距离进行排序 ,从而在簇扩展时优先扩展密度值较 大区域的点 。这样 ,OPTICS算法实

25、现了数据库所有对象的排序 ,这一对象序列就可以反映出 数据空间基于密度的簇结构信息。基于这些信息可以容易地确定合适的 值 ,并随 之发现各个簇。另外 , OPTICS还提供了自动的簇发现方法。 OPTICS算法较好地解决了 DBSCAN算法 的对输入参数 敏感的问题 ,但是由于采用了复杂的处理方法以及额外的磁盘 IPO 操作 ,使得 OPTICS实际运行的速度远远低于 DBSCAN 。 不同密度、形状、大小的簇 参数的影响 减小，则可达距离为无穷大的点增多； MinPts减小，核心对象增多，图象更尖锐 基于网格的方法（ Grid-Based Methods） 聚类高维数据是聚类分析中一个非常重

26、要的任务，而一般 聚类方法无法处理这些数据。用户感兴趣的通常是某个高维 数据空间的若干个子空间，对该空间内数据点的聚类要比原 始空间更好一些。高维数据中，通常只有少数几维不某些簇 相关，其他丌相关的维数据可能会产生大量的噪声而屏蔽真 实的簇。 为聚类高维数据集便提出了 基亍网格的方法的聚类。 基于网格的方法（ Grid-Based Methods） 将数据空间划分成为有限个单元（ cell）的网格结构， 所有的处理都是以单个单元为对象的。 这种方法的主要优点是它的处理速度很快，处理时间独 立于数据对象的数目，只与每一维所划分的单元数目有关 代表算法有： CLIQUE算法。 CLQUE是一个综合

27、了基于密度和基于网格方法的聚 类算法，对于大型数据库中的高维数据的聚类比较 有效 ,在高维数据的子空间中识别稠密的聚类，所产 生的理解结果与所给的输入数据无关。 CLIQUE：高维度数据的自动子空间聚类算法 CLIQUE：聚类高维空间 CLIQUE的中心思想如下： 给定一个多维数据点的大集合，数据点在数据空间中通 常不是均衡分布的。 CLIQUE区分空间中稀疏的和 “ 拥挤的 ” 区域，以发现数据集合 全局分布模式。 将数据空间中的每个维划分成等长且数量相等的间隔段， 即单元。如果一个单元中的包含数据点超过了某个输入模型 参数，则该单元是密集的。在 CLIQUE中，一个聚类被定义为 相连的密集

28、单元的最大集合。 问题描述 要能自动地识别一个高维数据的子空间 限制在只对原始空间的子空间的搜索而不是使用一个新的维 度 为了识别数据点的密度，将数据空间划分并找出在每个单元 中数据点的数量。 聚类是子空间中相连的高密度单元的并集，即将聚类映射到 轴对称的超矩形中。 聚类在空间中的描述 设 A A1,A2, ,Ad是一个有界的、全部有序的域 的集合。而 S A1 A2 Ad是一个 d维的数字空 间， A1， A2， ， Ad定义为 S的维。 输入是由 d维点集 V v1,v2, ,vm组成的，其中 Vi=,Vi的第 j个元素来自域 Aj。 将数据空间 S划分成非重叠矩形单元。单元的划分 方法是

29、在每一个维上将维分割成 个等长的间隔段， 是输入参数。 每一个单元 u是由每一个属性一个间隔段组成的交 集。形式为 u1,u2, ,ud，其中 ui=li,hi）是在 Ai的划分中的右边界开放的间隔段。 聚类在空间中的描述 一个点 V 属于单元 u=u1,u2,.ud,当对 所有的 ui，有 livihi 。 一个单元的选择性（ selectivity）：单元内数据点的数 量与单元的总数据点数量之比。 称单元 u是稠密的：若单元的选择性大于密度阈值 。 聚类在空间中的描述 两个 k维单元 u1， u2是连接的，即他们之间有一个公共面 。 若存在 k-1维，假设是维 At1， At2， ,Atk

30、-1，单元 u1 rt1,rt2,rtk 及 u2=rt1， rt2， , rtk-1是相连的， 则有 rtj= rtj，并且有 htk ltk 或者 htk ltk。 若 RC R，则称一个区域 R包含于一个聚类 C中。若没有 其他 R的超集包含于聚类 C中，则称区域 R是最大的。 一个聚类的最小描述是具有最大区域的聚类的非冗余的 覆盖。 例子（一） 在下图中，二维空间（ age,salary）划分成 10 10格一个单元是间隔段 的交集；例如单元 u（ 30 age35 ） （ 1salary2 ）。 一个区域是 单元的矩形的并集。 A与 B是两个区域： A（ 30 age50 ） （ 4

31、 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. 由于在 ag

32、e子空间中没有密度单 元，故在该子空间中就没有聚类。 CLIQUE算法 由以下几部分组成： 1）含有聚类子空间的识别。 2）聚类的识别。 3）对聚类产生最小的描述。 含有聚类子空间的识别 自下而上算法 定理 （单调性） 若在 k维数据空间的点集 S是一个聚类，则 S也是在这个 数据空间的任意（ k-1）维投影中一个聚类的一部分。 该算法利用聚类针对维度的单调性的准则减少搜索空 间 算法步骤 1.遍历一遍数据库确定 1维的密度单元，即将 n维数据空间 划分为不重叠的矩形单元。 2.利用单调性定理：在确定了 k-1维密度单元之后，确定 候选的 k维密度单元 3.直到不再有候选单元产生，算法结束 聚

33、类的识别 输入：密度单元的集合 D 输出： D的划分 问题就变成在下面定义的图中发现连通图：图的顶点对应 着密度单元，当且仅当两个密度单元有公共面时对应的顶 点之间有一条边 利用度优先深搜索算法发现图中的连通图，即从 D中的某 个密度单元 u开始，将第一个聚类的编号赋予给该单元， 再去发现与它相连的单元，之后，若在图中还存在没有被 访问的单元，重复此过程。 生成最小的聚类描述 步骤： 1、使用贪心算法由若干最大矩形来覆盖聚类即对每个聚类， 确定覆盖连接密集单元聚类的最大区域。 2、去掉多余的矩形从而产生最小的覆盖 贪心增长算法 从任意的一个密度单元 u1开始 用贪心法寻找覆盖 u1的最大区域

34、R1，将 R1加到 R中 找另一个单元 u2，但在 R中没有任何最大区域覆盖 u2，找 出其最大区域 R2 直到任何单元都有 R中的某个最大区域所覆盖。 为了得到覆盖密度单元的一个最大区域，从 u开始沿着维 a1，从单元的两个方向增长，通过使用包含在 C中相连的 密度单元，增长 u，得到一个矩形区域。再沿着维 a2增长 此区域，得到一个尽可能较大的矩形区域。沿着所有的维 重复此过程，就产生覆盖 u的最大区域。 最小覆盖 从覆盖中移走最小的大区域，该大区域是冗余的，即其中 的每个单元都包含在其他的大区域中。 重复上述过程，直到在没有可移走的大区域为止。 CLIQUE的有效性 CLIQUE自动地发现最高维的子空间，高密度聚类存在于 这些子空间中。 CLIQUE对元组的输入顺序不敏感，无需假设任何规范 的数据分布。 CLIQUE随输入数据的大小线性地扩展，当数据的维数 增加时具有良好的可伸缩性。 但是，由于方法大大简化，聚类的精确性可能会降低。