基于密度的聚类和基于网格的两大聚类算法

1、数据挖掘Data Mining肖婷112090501 第十章第十章 聚类聚类 2基于密度的聚类方法n划分和层次方法旨在发现球状簇。他们很难发现划分和层次方法旨在发现球状簇。他们很难发现任意形状的簇。任意形状的簇。n改进思想，将改进思想，将簇簇看作数据空间中由低密度区域分看作数据空间中由低密度区域分隔开的高密度对象区域。这是基于密度的聚类方隔开的高密度对象区域。这是基于密度的聚类方法的主要策略。法的主要策略。n基于密度的聚类方法可以用来过滤噪声孤立点数基于密度的聚类方法可以用来过滤噪声孤立点数据，发现任意形状的簇。据，发现任意形状的簇。DBSCAN：基于高密度连通区域聚类：基于高密度连通区域聚类

2、 OPTICS：通过点排序识别聚类结构：通过点排序识别聚类结构DENCLUE:基于密度分布函数的聚类基于密度分布函数的聚类 3DBSCANn基于密度的簇基于密度的簇是是密度相连密度相连的点的集合的点的集合n主要思想主要思想寻找被寻找被低密度区低密度区域分离的域分离的高密度高密度区域区域只要临近区域的密度（单位大小上对象或数据点的数只要临近区域的密度（单位大小上对象或数据点的数目）超过某个阈值，就继续聚类目）超过某个阈值，就继续聚类 4DBSCANn两个参数：两个参数：EpsEps: : 邻域的最大半径邻域的最大半径MinPtsMinPts: : 一个一个核心对象核心对象以以 EpsEps为半径

3、的邻域内的最小为半径的邻域内的最小顶点数顶点数MinPts = 5Eps = 1 cmpq5DBSCANn密度密度 = = 制定半径制定半径 ( (Eps) )内点的个数内点的个数n如果一个对象的如果一个对象的 EpsEps 邻域至少包含最小数目邻域至少包含最小数目MinPts 个对象，则称该对象为个对象，则称该对象为核心对象核心对象（Core point）n如果一个对象是非核心对象如果一个对象是非核心对象, , 但它的邻域中有核但它的邻域中有核心对象，则称该对象为心对象，则称该对象为边界点边界点（ Border point ）n除核心对象和边界点之外的点是除核心对象和边界点之外的点是噪声点噪

4、声点（ Noise point ）6DBSCAN7DBSCAN密度可达的密度可达的（Density-reachable）对于对于对象对象p p和和核心对象核心对象q q( (关于关于E E和和MinPtsMinPts),),我们称我们称p p是从是从q(q(关关于于E E和和MinPtsMinPts) )直接密度可达直接密度可达，若对象，若对象p p在对象在对象q q的的E E邻域内。邻域内。如果存在一个对象链如果存在一个对象链 p p1 1, , , , p pn n, , p p1 1 = = q q, , p pn n = = p p ，p pi+1 i+1 是从是从p pi i关于关于

5、EpsEps和和MinPtsMinPts 直接密度可达的，则对象直接密度可达的，则对象p p是从对象是从对象q q关于关于EpsEps和和MinPtsMinPts 密度可达的。密度可达的。密度可达性是直接密度可达性的密度可达性是直接密度可达性的传递闭包传递闭包，这种关系是，这种关系是非非对称对称的。的。 只有核心对象之间是只有核心对象之间是相互可达相互可达的。的。pqp18DBSCANn密度相连的密度相连的（Density-connected）如果对象集合如果对象集合D D中存在一个对象中存在一个对象o o，使得对象，使得对象p p和和q q是从是从o o关于关于EpsEps 和和 MinPt

6、sMinPts密度可达的，那么对象密度可达的，那么对象p p和和q q是关于是关于EpsEps 和和 MinPtsMinPts 密度相连的。密度相连的。密度相连性是一个密度相连性是一个对称对称的关系。的关系。pqo9DBSCAN: 算法算法：算法：DBSCAN输入：输入：D-数据对象集合数据对象集合 ；Eps-邻域或称为半径邻域或称为半径 ； MinPts-密度阈值密度阈值输出：基于密度的簇的集合输出：基于密度的簇的集合方法：方法：Step1 读取读取D中任意一个未分类的对象中任意一个未分类的对象p；Step2 检索出与检索出与p的距离不大于的距离不大于Eps的所有对象的所有对象Neps(p)

7、； Step3 如果如果 |Neps(p)|MinPts，则剔除已经打上标记的，则剔除已经打上标记的对象，将余下的未分类对象打上类标签对象，将余下的未分类对象打上类标签newid，然后压入堆栈；，然后压入堆栈；Step6 Seeds.pop，判断，判断Seeds是否为空，是，则执行是否为空，是，则执行Step1 ，否则执行，否则执行Step5。10DBSCANOriginal PointsClusters特点：特点： 抗噪声 能处理任意形状聚类11OPTICS：通过点排序识别聚类结构n对于真实的，高维的数据集合而言，参数的设置对于真实的，高维的数据集合而言，参数的设置通常是依靠经验，难以确定。

8、通常是依靠经验，难以确定。n绝大多数算法对参数值是非常敏感的：设置的细绝大多数算法对参数值是非常敏感的：设置的细微不同可能导致差别很大的聚类结果。微不同可能导致差别很大的聚类结果。nOPTICSOPTICS算法通过对象排序识别聚类结构。算法通过对象排序识别聚类结构。nOPTICSOPTICS没有显式地产生一个数据集合簇，它为自没有显式地产生一个数据集合簇，它为自动和交互的聚类分析计算一个动和交互的聚类分析计算一个簇排序簇排序。n这个次序代表了数据的基于密度的聚类结构。较这个次序代表了数据的基于密度的聚类结构。较稠密中的对象在簇排序中相互靠近。稠密中的对象在簇排序中相互靠近。12OPTICS簇簇

9、排序选择这样的对象：即关于最小的排序选择这样的对象：即关于最小的E E值，它是密度可值，它是密度可达的，以便较高密度（较低达的，以便较高密度（较低E E值）的簇先完成。值）的簇先完成。n对象对象p p的核心距离：的核心距离：使使p p成为核心对象的最小成为核心对象的最小。如果。如果p p不不是核心对象，那么是核心对象，那么p p的核心距离没有任何意义。的核心距离没有任何意义。n可达距离：可达距离：对象对象q q到到对象对象p p的可达距离是指的可达距离是指p p的核心距离的核心距离和和p p与与q q之间欧几里得距离之间欧几里得距离之间的之间的较大值较大值。如果。如果p p不是核心对象，不是核

10、心对象，p p和和q q之间的可达距离没有意义。之间的可达距离没有意义。13OPTICS：通过点排序识别聚类结构算法思路算法思路n首先检查数据对象集合首先检查数据对象集合D D中任一个对象的中任一个对象的E E邻域。设定其邻域。设定其可达距离为可达距离为“未定义未定义”，并确定其核心距离，然后将对象及，并确定其核心距离，然后将对象及其核心距离和可达距离写入文件。其核心距离和可达距离写入文件。n如果如果P P是核心对象，则将对象是核心对象，则将对象P P的的E E邻域内的对象邻域内的对象N (P)N (P)插插入到一个种子队列中，包含在种子队列中的对象入到一个种子队列中，包含在种子队列中的对象p

11、p按按到到其直其直接密度可达的最近的核心对象接密度可达的最近的核心对象q q的的可达距离可达距离排序。排序。n种子队列中具有最小可达距离的对象被首先挑选出来，确种子队列中具有最小可达距离的对象被首先挑选出来，确定该对象的定该对象的E E一邻域和核心距离，一邻域和核心距离，n然后将其该对象及其核心距离和可达距离写入文件中，如然后将其该对象及其核心距离和可达距离写入文件中，如果当前对象是核心对象，则更多的用于扩展的后选对象被插果当前对象是核心对象，则更多的用于扩展的后选对象被插入到种子队列中。入到种子队列中。n这个处理一直重复到再没有一个新的对象被加入到当前的这个处理一直重复到再没有一个新的对象被

12、加入到当前的种子队列种子队列 中。中。OPTICS：通过点排序识别聚类结构n数据集的排序可以用图形描述，有助于可视化和理解数据集数据集的排序可以用图形描述，有助于可视化和理解数据集中聚类结构，例如下图是一个简单的二维数据集的可达图。中聚类结构，例如下图是一个简单的二维数据集的可达图。其中三个高斯其中三个高斯“凸起凸起”反映数据集中比较稠密的部分。反映数据集中比较稠密的部分。1415OPTICS：通过点排序识别聚类结构nStep 1Step 1：有序种子队列初始为空结果队列初始为空：有序种子队列初始为空结果队列初始为空 ； nStep 2Step 2：如果所有点处理完毕：如果所有点处理完毕算法结

13、束算法结束；否则选择一个未处理对象；否则选择一个未处理对象（即不在结果队列中）即不在结果队列中）放人有序种子队列：放人有序种子队列： nStep 3Step 3：如果有序种子队列为空，返回：如果有序种子队列为空，返回Step 2Step 2，否则选择种子队列中的，否则选择种子队列中的第一个对象第一个对象P P进行扩张：进行扩张： nStep 3.1Step 3.1：如果：如果P P不是核心节点转不是核心节点转Step 4Step 4；否则，对；否则，对P P 的的E E邻域内任一邻域内任一未扩张的邻居未扩张的邻居q q 进行如下处理进行如下处理nStep 3.1.1Step 3.1.1：如果：

14、如果q q已在有序种子队列中且从已在有序种子队列中且从P P到到 q q的可达距离小的可达距离小于于旧值旧值，则更新，则更新q q的可达距离，并调整的可达距离，并调整q q到相应位置以保证队列的有序性；到相应位置以保证队列的有序性； nStep 3.1.2Step 3.1.2：如果：如果q q不在有序种不在有序种f f队列中，则根据队列中，则根据P P 到到q q的可达距离将其插的可达距离将其插入有序队列；入有序队列； nStep 4Step 4：从有序种子队列中删除：从有序种子队列中删除P P并将并将P P写入结果队列中，返回写入结果队列中，返回Step 3Step 3DENCLUE基于密度

15、分布函数的聚类DENCLUE是是一种一种基于基于一一组密度分布组密度分布函数的聚类算法函数的聚类算法。该。该算法的原理算法的原理是：是：p每个每个数据点的影响可以用一个数学函数来形式化地模拟，它描述了一个数据数据点的影响可以用一个数学函数来形式化地模拟，它描述了一个数据点在邻域内的影响，被称为点在邻域内的影响，被称为影响函数影响函数。p数据数据空间的空间的整体整体密度密度(全局密度函数全局密度函数)可以可以被模拟为所有数据点的影响函数被模拟为所有数据点的影响函数的的 总和；总和；p聚类聚类可以通过确定密度吸引点可以通过确定密度吸引点(density attractor)来得到，这里的来得到，这

16、里的密度吸引点密度吸引点是全局密度函数的局部最大值是全局密度函数的局部最大值。p一一个点个点 x 是被一个密度吸引点是被一个密度吸引点 x*密度吸引的，如果存在一组点密度吸引的，如果存在一组点 x0，x1，,xk，使得，使得x0=x，xk=x*，对，对 0ik，xi-1 的梯度是在的梯度是在 xi的的方向方向上，也就上，也就是说是说xi-1在在xi的方向上变化最快。的方向上变化最快。 p使用一个使用一个步进式爬山步进式爬山过程，把待分析的数据分配到密度吸引点过程，把待分析的数据分配到密度吸引点 x*所代表的所代表的簇中。簇中。16DENCLUE基于密度分布函数的聚类17DENCLUE基于密度分

17、布函数的聚类算法步骤：算法步骤：（1）对数据点占据的空间推导密度函数；）对数据点占据的空间推导密度函数；（2）通过沿密度增长最大的方向）通过沿密度增长最大的方向(即梯度方向即梯度方向)移动，识别移动，识别密度函数的密度函数的局局 部最大点（这是局部吸引点）部最大点（这是局部吸引点），将每个点关联到一个密度吸引点；将每个点关联到一个密度吸引点；（3）定义与特定的密度吸引点相关联的点构成的簇；）定义与特定的密度吸引点相关联的点构成的簇；（4）丢弃）丢弃与非平凡与非平凡密度吸引点密度吸引点相关联的簇（密度吸引点相关联的簇（密度吸引点 x称为非平凡密称为非平凡密 度吸引点，如果度吸引点，如果f*(x)

18、(其其中中f*是密度函数是密度函数,是指定的阀值是指定的阀值) )；（5）若两个密度吸引点之间存在若两个密度吸引点之间存在密度大于或等于密度大于或等于的路径的路径，则合并他们，则合并他们 所代表的所代表的簇。簇。对所有的密度吸引点重复此过程，直到不再改变时对所有的密度吸引点重复此过程，直到不再改变时 算法中止算法中止。1819基于密度的聚类方法n主要特征：主要特征：发现任意形状的聚类发现任意形状的聚类处理噪声（孤立点数据）处理噪声（孤立点数据）一次扫描一次扫描需要密度参数作为终止条件需要密度参数作为终止条件基于网格的聚类n聚类分析的算法有很多，其中一大类的传统算法聚类分析的算法有很多，其中一大

19、类的传统算法是是基于距离的基于距离的，这种基于距离的缺点在于只能发，这种基于距离的缺点在于只能发现球状的簇、处理大数据集和高维数据集时不够现球状的簇、处理大数据集和高维数据集时不够有效，另一方面它能发现的聚类个数常常依赖于有效，另一方面它能发现的聚类个数常常依赖于用户参数的指定，这对用户来说经常是很困难的。用户参数的指定，这对用户来说经常是很困难的。n基于网格基于网格( (ddingdding-based)-based)指将对象空间量化为有限指将对象空间量化为有限数目的数目的单元单元，形成一个，形成一个网格结构网格结构，所有聚类都在，所有聚类都在这个网格结构上进行。这个网格结构上进行。20基于

20、网格的聚类n基本思想基本思想是将每个属性的可能值分割成许多相邻是将每个属性的可能值分割成许多相邻的区间，创建网格单元的集合（对于的讨论我们的区间，创建网格单元的集合（对于的讨论我们假设属性值是序数的、区间的或者连续的）。假设属性值是序数的、区间的或者连续的）。n每个对象落入一个网格单元，网格单元对应的属每个对象落入一个网格单元，网格单元对应的属性区间包含该对象的值。性区间包含该对象的值。n优点优点是它的处理速度很快，其处理时间独立于数是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数据对象的数目，只与量化空间中每一维的单元数目有关。目有关。21STING:统计信息

21、网格nSTINGSTING是一种基于网格的多分辨率聚类技术，它将是一种基于网格的多分辨率聚类技术，它将空间区域划分为空间区域划分为矩形单元矩形单元。针对不同级别的分辨率，通常存在多个级别的针对不同级别的分辨率，通常存在多个级别的矩形单元，矩形单元，这些单元形成了一个这些单元形成了一个层次结构层次结构：高层的每个单：高层的每个单元被划分为多个低一层的单元。元被划分为多个低一层的单元。关于每个网格单元属性的统计信息（例如平均关于每个网格单元属性的统计信息（例如平均值、最大值和最小值）被预先计算和存储。这值、最大值和最小值）被预先计算和存储。这些些统计信息统计信息用于回答用于回答查询查询。22STI

22、NG:统计信息网格网格中常用参数网格中常用参数ncount- -网格中对象数目网格中对象数目nmean- -网格中所有值的平均值网格中所有值的平均值nstdev- -网格中属性值的标准偏差网格中属性值的标准偏差nmin- -网格中属性值的最小值网格中属性值的最小值nmax- -网格中属性值的最大值网格中属性值的最大值ndistribution- -网格中属性值符合的网格中属性值符合的分布类型。分布类型。如正如正态分布、均匀分布、指数分布或者态分布、均匀分布、指数分布或者nonenone（分布类（分布类型未知）型未知）23STING:统计信息网格24STINGSTING聚类的层次结构聚类的层次结

23、构STING:统计信息网格25 level i level i+1 level i+2 a cell of (i-1)th level corresponds to 4 cells of (a cell of (i-1)th level corresponds to 4 cells of (i)thi)th level level STING:统计信息网格26假设当前层的属性x的统计信息记为n,m,s,min,max,dist,而ni,mi,si,mini,maxi是相对于当前层来说，对应于更低一层的统计参数。那么n,m,s,min,max,dist可以用以下方法计算: dist dist S

24、TING:统计信息网格27STING: 统计信息网格n当数据加载到数据库时。最底层的单元参数直接当数据加载到数据库时。最底层的单元参数直接由数据计算，若分布类型事先知道，可以用户直由数据计算，若分布类型事先知道，可以用户直接指定，而较高层的分布类型可以基于它对应的接指定，而较高层的分布类型可以基于它对应的低层单元多数的分布类型，用一个阈值过滤过程低层单元多数的分布类型，用一个阈值过滤过程的合取来计算，若低层分布彼此不同，则高层分的合取来计算，若低层分布彼此不同，则高层分布设置为布设置为nonenone。n高层单元的统计参数可以很容易的从低层单元的高层单元的统计参数可以很容易的从低层单元的参数计

25、算得到参数计算得到。28STING:统计信息网格统计处理思想：统计处理思想：n使用自顶向下的方法回答空间数据的查询使用自顶向下的方法回答空间数据的查询 从一个预先选择的层次开始通常包含少量的单从一个预先选择的层次开始通常包含少量的单元，为当前层的每个单元计算置信区间元，为当前层的每个单元计算置信区间n不相关的单元不再考虑不相关的单元不再考虑n当检查完当前层，接着检查下一个低层次当检查完当前层，接着检查下一个低层次n重复这个过程直到达到底层重复这个过程直到达到底层29STING:统计信息网格算法步骤：算法步骤：1 1 从一个层次开始从一个层次开始2 2 对于这一层次的每个单元格，我们计算查询相关

26、的属性值对于这一层次的每个单元格，我们计算查询相关的属性值3 3 从计算的属性值及其约束条件中，我们将每一个单元格标从计算的属性值及其约束条件中，我们将每一个单元格标注成相关或者不相关注成相关或者不相关4 4 如果这一层是底层，则转到步骤如果这一层是底层，则转到步骤6 6，否则就行步骤，否则就行步骤5 55 5 我们由层次结构转到下一层依照步骤我们由层次结构转到下一层依照步骤2 2进行计算进行计算6 6 查询结果满足，转到步骤查询结果满足，转到步骤8 8，否则转到步骤，否则转到步骤7 77 7 恢复数据到相关的单元格进一步处理以得到满意结果，转恢复数据到相关的单元格进一步处理以得到满意结果，转

27、到步骤到步骤8 88 8 停止停止30STING:统计信息网格应用nSTING STING 能够用来帮助各种不同的空间查询。这最常见的请求查询是区域能够用来帮助各种不同的空间查询。这最常见的请求查询是区域查询。查询。n例如例如查询满足一定条件的查询满足一定条件的区域区域。查找加利福尼亚州地区的房屋以得到房屋所查找加利福尼亚州地区的房屋以得到房屋所在区域相关方面数据。查询的对象是房屋，价格是其中的一个属性。区域须在区域相关方面数据。查询的对象是房屋，价格是其中的一个属性。区域须满足约束条件：哪些区域面积至少是满足约束条件：哪些区域面积至少是A,A,单元地区至少有单元地区至少有c c栋房屋栋房屋,

28、 ,至少至少d%d%的房的房屋其价格在屋其价格在a a到到b b之间的置信之间的置信度为度为1-t.1-t.且且mn,.mAnA* *C C* *d%成立成立?) )，若相关，则标记该网格为，若相关，则标记该网格为relevantrelevant否则标记为否则标记为 not-relevant not-relevant . .处理层次结构中的下一层。这个处理过程反复进行。直处理层次结构中的下一层。这个处理过程反复进行。直 到到达最底层到到达最底层 。最后返回满足查询要求的相关单元的区域。最后返回满足查询要求的相关单元的区域。 查找结束查找结束 。 32STING:统计信息网格优点如下：优点如下：

29、n计算是独立于查询的；计算是独立于查询的；n有利于并行处理和增量更新；有利于并行处理和增量更新；n效率很高效率很高。STINGSTING算法扫描数据库一次来计算单元的统计信息，因算法扫描数据库一次来计算单元的统计信息，因此产生聚类的时间复杂度是此产生聚类的时间复杂度是o(no(n) )，其中，其中n n是对象的数目。是对象的数目。在层次结构建立后，查询处理时间是，这里在层次结构建立后，查询处理时间是，这里g g是最低层是最低层网格单元的数目网格单元的数目o(go(g) )，通常远小于，通常远小于n n。33STING:统计信息网格缺点如下：缺点如下：n如果粒度比较细，处理的代价会显著增加；但是

30、，如果网如果粒度比较细，处理的代价会显著增加；但是，如果网格结构最低层的粒度太粗，将会降低聚类分析的质量；格结构最低层的粒度太粗，将会降低聚类分析的质量；n在构建一个父亲单元时没有考虑孩子单元和其相邻单元之在构建一个父亲单元时没有考虑孩子单元和其相邻单元之间的关系，因此，结果簇的形状是间的关系，因此，结果簇的形状是isotheticisothetic，即所有的，即所有的聚类边界或者是水平的，或者是竖直的，没有斜的分界线聚类边界或者是水平的，或者是竖直的，没有斜的分界线。n尽管该技术有快速的处理速度，但可能降低簇的质量和精尽管该技术有快速的处理速度，但可能降低簇的质量和精确性确性34CLIQUE

31、 :一种类似于Apriori的子空间聚类方法n CLICQUE算法是基于网格的空间聚类算法，但它同时非常好地算法是基于网格的空间聚类算法，但它同时非常好地结结 合了基于合了基于密度的聚类算法思想，因此既可以像基于密度的方法发现任密度的聚类算法思想，因此既可以像基于密度的方法发现任意形状的簇，又意形状的簇，又可以像可以像基于网格的方法处理较大的多维数据集基于网格的方法处理较大的多维数据集。n CLIQUE把每个维划分成不重叠的区间，从而把数据对象的整个嵌入把每个维划分成不重叠的区间，从而把数据对象的整个嵌入空间划分成单元。它使用一个密度阀值识别稠密单元，一个单元是稠空间划分成单元。它使用一个密度

32、阀值识别稠密单元，一个单元是稠密的，如果映射到它的对象超过该密度阀值密的，如果映射到它的对象超过该密度阀值35CLIQUE :一种类似于Apriori的子空间聚类方法算法算法概述概述： 算法算法需要两个参数值，一个是网格的步长，一具是密度阈值需要两个参数值，一个是网格的步长，一具是密度阈值。 网格步长网格步长决定了空间的划分，而密度阈值用来定义密集网格决定了空间的划分，而密度阈值用来定义密集网格。 聚类思想：聚类思想：n算法算法首先扫描所有网格，当发现第一个密集网格时，首先扫描所有网格，当发现第一个密集网格时，便以该便以该网格开始扩网格开始扩展，扩展原则是若一个网格与已知密集区域内的网格邻接并

33、且其自身也展，扩展原则是若一个网格与已知密集区域内的网格邻接并且其自身也是密集的，则将该网格加入到该密集区域中、直到不再有这样的网格被是密集的，则将该网格加入到该密集区域中、直到不再有这样的网格被发现为止发现为止。n算法算法再继续扫描网格并重复上述过程，直至所有网格被遍历。以自动地再继续扫描网格并重复上述过程，直至所有网格被遍历。以自动地发现最高维的子空间，高密度聚类存在于这些子空间中，并且它对元组发现最高维的子空间，高密度聚类存在于这些子空间中，并且它对元组的输入顺序不敏感，无需假设任何规范的数据分布。它随输入数据的大的输入顺序不敏感，无需假设任何规范的数据分布。它随输入数据的大小线性地扩展

34、，当数据的维数增加时具有良好的可伸缩性。小线性地扩展，当数据的维数增加时具有良好的可伸缩性。36CLIQUE :一种类似于Apriori的子空间聚类方法nCLIQUECLIQUE识别候选搜索空间的主要策略是使用稠密单元关于维度的单识别候选搜索空间的主要策略是使用稠密单元关于维度的单调性。调性。n在子空间聚类的背景下，单调性陈述如下：在子空间聚类的背景下，单调性陈述如下： 一个一个k- k-维维(k1)(k1)单元单元c c至少有至少有m m个点，仅当个点，仅当c c的每个的每个(k-1)-(k-1)-维投影维投影 ( (它是它是(k-1)-(k-1)-维单元维单元) )至少有至少有m m个点。

35、个点。 如下图嵌入数据空间包括如下图嵌入数据空间包括3 3个维：个维： age,salaryage,salary和和vacationvacation。例如，子空间。例如，子空间ageage和和salarysalary中的一个二维中的一个二维 单元包含单元包含m m个点，仅当该单元在每个维上的投影都至少包含个点，仅当该单元在每个维上的投影都至少包含m m个点。个点。3738Salary (10,000)2030405060age543126702030405060age54312670Vacation(week)ageVacationSalary3050 = 3CLIQUE :一种类似于Apri

36、ori的子空间聚类方法相关定义：相关定义：n网格密度：网格中所包含的空间对象的数目。网格密度：网格中所包含的空间对象的数目。n密集网格：给定刻度阈值密集网格：给定刻度阈值, ,当网格当网格g g的密度的密度 时，网格时，网格g g是是 密集网格，否则是非密集网格。密集网格，否则是非密集网格。n网格刻度连通区域：设网格刻度连通区域：设GridsGrids为一个网格集合，若集合中的为一个网格集合，若集合中的所有网格相互邻接且均是密集网格，则称所有网格相互邻接且均是密集网格，则称GridGrid是网格是网格 密度连通区域。密度连通区域。39CLIQUE :一种类似于Apriori的子空间聚类方法40

37、CLIQUE :一种类似于Apriori的子空间聚类方法以二维空间为例说明该算法：以二维空间为例说明该算法： =4 =441基于网格的聚类-总结优点优点: :可能是非常有效的。给定每个属性的划分，单遍数据扫描就可以确定每可能是非常有效的。给定每个属性的划分，单遍数据扫描就可以确定每个对象的网格单元和网格单元的计数。此外，尽管潜在的网格单元数量个对象的网格单元和网格单元的计数。此外，尽管潜在的网格单元数量可能很高，但是只需要为非空单元创建网格。这样，定义网格、将每个可能很高，但是只需要为非空单元创建网格。这样，定义网格、将每个对象指派到一个单元并计算每个单元的密度的时间复杂度和空间复杂度对象指派

38、到一个单元并计算每个单元的密度的时间复杂度和空间复杂度为为O(m)O(m)，其中，其中，m m是点的个数。如果邻接的、已占据的单元可以有效的是点的个数。如果邻接的、已占据的单元可以有效的访问（例如，通过使用搜索树）则整个聚类过程将非常高效，例如具有访问（例如，通过使用搜索树）则整个聚类过程将非常高效，例如具有O(O(mlogmmlogm) )的时间复杂度的时间复杂度。缺点缺点：（：（1 1）像大多数基于密度的聚类算法一样、基于网格的聚类非常依赖）像大多数基于密度的聚类算法一样、基于网格的聚类非常依赖于密度阈值的选择。（太高，簇可能或丢失；太低，本应分开的簇可能于密度阈值的选择。（太高，簇可能或

39、丢失；太低，本应分开的簇可能被合并）；（被合并）；（2 2）如果存在不同密度的簇和噪声，则也许不可能找到适合）如果存在不同密度的簇和噪声，则也许不可能找到适合于数据空间所有部分的值；（于数据空间所有部分的值；（3 3）随着维度的增加，网格单元个数迅速增）随着维度的增加，网格单元个数迅速增加（指数增长）。即对于高维数据，基于网格的聚类倾向于效果很差。加（指数增长）。即对于高维数据，基于网格的聚类倾向于效果很差。42算法评估聚类评估主要包括如下任务聚类评估主要包括如下任务：n估计聚类趋势n确定数据集中的簇数n测定聚类质量43算法评估估计聚类趋势n聚类趋势评估聚类趋势评估确定给定的数据集是否具有可以

40、导致有意义的聚类的确定给定的数据集是否具有可以导致有意义的聚类的非随机结构。非随机结构。聚类要求数据的非均匀分布。聚类要求数据的非均匀分布。n“如何评估数据集的聚类趋势如何评估数据集的聚类趋势? ?”直观地看，我们可以评估直观地看，我们可以评估数据集数据集被均匀分布产生的概率被均匀分布产生的概率。这可以通过。这可以通过空间随机性的统计检验空间随机性的统计检验来实现。来实现。为了解释这一思想，我们考虑一种简单但有效的统计量为了解释这一思想，我们考虑一种简单但有效的统计量霍普金斯霍普金斯统计量统计量。n霍普金斯统计量霍普金斯统计量是一种空间统计量，检验空间分布的变量的空间随是一种空间统计量，检验空

41、间分布的变量的空间随机性。给定数据集机性。给定数据集D D，它可以看做随机变量，它可以看做随机变量O O的一个样本，我们想要的一个样本，我们想要确定确定O O在多大程度上不同于数据空间中的均匀分布。在多大程度上不同于数据空间中的均匀分布。 44算法评估估计聚类趋势霍普金斯统计量霍普金斯统计量- -计算计算（1 1）均匀地从）均匀地从D D的空间中抽取的空间中抽取n n个点个点p p1 1,p,pn n。也就是说，。也就是说，D D的空间中的每的空间中的每 个点都以个点都以 相同的概率包含在这个样本中。对于每个点相同的概率包含在这个样本中。对于每个点p pi i(1(1i in),),我们找出我

42、们找出 p pi i在在D D中的最邻近，并令中的最邻近，并令x xi i为为p pi i与它在与它在D D中的最近邻之间的距离，即中的最近邻之间的距离，即 x xi i=min=mindistdist( (p pi i,v,v)()(其中其中v vD) )（2 2）均匀地从）均匀地从D D中抽取中抽取n n个点个点q q1 1,q,qn n. .对于每个点对于每个点q qi i(1(1i in),),我们找出我们找出q qi i在在 D-q D-qi i 中的最邻近，并令中的最邻近，并令y yi i为为q qi i它在它在D-qD-qi i 中的最近邻之间的距离，即中的最近邻之间的距离，即

43、y yi i=min=mindistdist( (q qi i,v,v)()(其中其中v vD,vq qi i) )（3 3）计算霍普金斯统计量）计算霍普金斯统计量H:H:45算法评估估计聚类趋势n“霍普金斯统计量告诉我们数据集霍普金斯统计量告诉我们数据集D D有多大可能遵循数据空间的均匀有多大可能遵循数据空间的均匀分布分布?”?”如果如果D D是均匀分布的，则是均匀分布的，则yi和和xi将会很接近，因而将会很接近，因而H大约为大约为0.5。然而，如果。然而，如果D是高度倾斜的，则是高度倾斜的，则yi将显著地小于将显著地小于xi，因而，因而H将接将接近近0。n 我们的假设是同质假设我们的假设是

44、同质假设D是均匀分布的，因而不包含有意义的簇。是均匀分布的，因而不包含有意义的簇。非均匀假设非均匀假设(即即D不是均匀分布，因而包含簇不是均匀分布，因而包含簇)是备择假设。我们可以迭是备择假设。我们可以迭代地进行霍普金斯统计量检验，使用代地进行霍普金斯统计量检验，使用0.5作为拒绝备择假设阈值，即如作为拒绝备择假设阈值，即如果果H0.5，则，则D不大可能具有统计显著的簇。不大可能具有统计显著的簇。46算法评估确定簇数l确定数据集中确定数据集中”正确的正确的”簇数是重要的，因为合适的簇数可以控制簇数是重要的，因为合适的簇数可以控制适当的聚类分析粒度，这可以看做在聚类分析的适当的聚类分析粒度，这可

45、以看做在聚类分析的可压缩性可压缩性与与准确性准确性之间寻找好的平衡点。之间寻找好的平衡点。n简单的经验方法：对于简单的经验方法：对于n n个点的数据集，设置簇数个点的数据集，设置簇数p p大约为大约为n/2.在期在期望情况下，每个簇大约有望情况下，每个簇大约有2n个点。个点。n肘方法：给点肘方法：给点k0,k0,我们可以使用一种像我们可以使用一种像k-k-均值这样的算法对数据集均值这样的算法对数据集聚类，并计算簇内方差和聚类，并计算簇内方差和var(kvar(k).).然后，我们绘制然后，我们绘制varvar关于关于k k的曲的曲线。曲线的第一个线。曲线的第一个( (或者最显著的或者最显著的) )拐点暗示拐点暗示”正确的正确的”