数据挖掘课程完整基于网格的聚类算法.pptx

《数据挖掘课程完整基于网格的聚类算法.pptx》由会员分享，可在线阅读，更多相关《数据挖掘课程完整基于网格的聚类算法.pptx（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、基于网格的聚类基于网格的聚类基本思想是将每个属性的可能值分割成许多相邻的区间，创建网格单元的集合（对于的讨论我们假设属性值是序数的、区间的或者连续的）。每个对象落入一个网格单元，网格单元对应的属性区间包含该对象的值。优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。1第1页/共31页STING:统计信息网格统计信息网格STINGSTING是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。针对不同级别的分辨率，通常存在多个级别的矩形单元，这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。关于每个网格单元属性的统计信息（例如平

2、均值、最大值和最小值）被预先计算和存储。这些统计信息用于回答查询。2第2页/共31页STING:统计信息网格统计信息网格网格中常用参数count-网格中对象数目mean-网格中所有值的平均值stdev-网格中属性值的标准偏差min-网格中属性值的最小值max-网格中属性值的最大值distribution-网格中属性值符合的分布类型。如正态分布、均匀分布、指数分布或者nonenone（分布类型未知）3第3页/共31页STING:统计信息网格统计信息网格4STINGSTING聚类的层次结构聚类的层次结构第4页/共31页STING:统计信息网格统计信息网格5 level i level i+1 le

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

4、7页/共31页STING:统计信息网格统计信息网格当数据加载到数据库时。最底层的单元参数直接由数据计算，若分布类型事先知道，可以用户直接指定，而较高层的分布类型可以基于它对应的低层单元多数的分布类型，用一个阈值过滤过程的合取来计算，若低层分布彼此不同，则高层分布设置为nonenone。高层单元的统计参数可以很容易的从低层单元的参数计算得到。8第8页/共31页STING:统计信息网格统计信息网格统计处理思想：使用自顶向下的方法回答空间数据的查询 从一个预先选择的层次开始通常包含少量的单元，为当前层的每个单元计算置信区间不相关的单元不再考虑当检查完当前层，接着检查下一个低层次重复这个过程直到达到底

5、层9第9页/共31页STING:统计信息网格统计信息网格算法步骤：1 1 从一个层次开始2 2 对于这一层次的每个单元格，我们计算查询相关的属性值3 3 从计算的属性值及其约束条件中，我们将每一个单元格标注成相关或者不相关4 4 如果这一层是底层，则转到步骤6 6，否则就行步骤5 55 5 我们由层次结构转到下一层依照步骤2 2进行计算6 6 查询结果满足，转到步骤8 8，否则转到步骤7 77 7 恢复数据到相关的单元格进一步处理以得到满意结果，转到步骤8 88 8 停止10第10页/共31页STING:统计信息网格统计信息网格应用应用STING STING 能够用来帮助各种不同的空间查询。这

6、最常见的请求查询是区域查询。例如查询满足一定条件的区域。查找加利福尼亚州地区的房屋以得到房屋所在区域相关方面数据。查询的对象是房屋，价格是其中的一个属性。区域须满足约束条件：哪些区域面积至少是A,A,单元地区至少有c c栋房屋,至少d%d%的房屋其价格在a a到b b之间的置信度为1-t.1-t.且mn,.mA*C*(p2*nA*C*d%成立?)，若相关，则标记该网格为relevantrelevant否则标记为 not-relevant not-relevant .处理层次结构中的下一层。这个处理过程反复进行。直 到到达最底层 。最后返回满足查询要求的相关单元的区域。查找结束 。12第12页/

7、共31页STING:统计信息网格统计信息网格优点如下：计算是独立于查询的；有利于并行处理和增量更新；效率很高。STINGSTING算法扫描数据库一次来计算单元的统计信息，因此产生聚类的时间复杂度是o(n)o(n)，其中n n是对象的数目。在层次结构建立后，查询处理时间是，这里g g是最低层网格单元的数目o(g)o(g)，通常远小于n n。13第13页/共31页STING:统计信息网格统计信息网格缺点如下：如果粒度比较细，处理的代价会显著增加；但是，如果网格结构最低层的粒度太粗，将会降低聚类分析的质量；在构建一个父亲单元时没有考虑孩子单元和其相邻单元之间的关系，因此，结果簇的形状是isothet

8、icisothetic，即所有的聚类边界或者是水平的，或者是竖直的，没有斜的分界线。尽管该技术有快速的处理速度，但可能降低簇的质量和精确性14第14页/共31页CLIQUE:一种类似于一种类似于AprioriApriori的子空间聚类方法的子空间聚类方法 CLICQUE算法是基于网格的空间聚类算法，但它同时非常好地结 合了基于密度的聚类算法思想，因此既可以像基于密度的方法发现任意形状的簇，又可以像基于网格的方法处理较大的多维数据集。CLIQUE把每个维划分成不重叠的区间，从而把数据对象的整个嵌入空间划分成单元。它使用一个密度阀值识别稠密单元，一个单元是稠密的，如果映射到它的对象超过该密度阀值1

9、5第15页/共31页CLIQUE:一种类似于一种类似于AprioriApriori的子空间聚类方法的子空间聚类方法算法概述：算法需要两个参数值，一个是网格的步长，一具是密度阈值。网格步长决定了空间的划分，而密度阈值用来定义密集网格。聚类思想：算法首先扫描所有网格，当发现第一个密集网格时，便以该网格开始扩展，扩展原则是若一个网格与已知密集区域内的网格邻接并且其自身也是密集的，则将该网格加入到该密集区域中、直到不再有这样的网格被发现为止。算法再继续扫描网格并重复上述过程，直至所有网格被遍历。以自动地发现最高维的子空间，高密度聚类存在于这些子空间中，并且它对元组的输入顺序不敏感，无需假设任何规范的数

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

11、至少有至少有m m个点。个点。如下图嵌入数据空间包括如下图嵌入数据空间包括3 3个维：个维：age,salary age,salary和和vacationvacation。例如，子空间。例如，子空间ageage和和salarysalary中的一个二维中的一个二维 单元包含单元包含m m个点，仅当该单元在每个维上的投影都至少包含个点，仅当该单元在每个维上的投影都至少包含m m个点。个点。17第17页/共31页18Salary(10,000)2030405060age543126702030405060age54312670Vacation(week)ageVacationSalary3050=3

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

13、。密度连通区域。19第19页/共31页CLIQUE:一种类似于一种类似于AprioriApriori的子空间聚类方法的子空间聚类方法20第20页/共31页CLIQUE:一种类似于一种类似于AprioriApriori的子空间聚类方法的子空间聚类方法以二维空间为例说明该算法：以二维空间为例说明该算法：=4=421第21页/共31页基于网格的聚类基于网格的聚类-总结总结优点优点:可能是非常有效的。给定每个属性的划分，单遍数据扫描就可以可能是非常有效的。给定每个属性的划分，单遍数据扫描就可以确定每个对象的网格单元和网格单元的计数。此外，尽管潜在的网格确定每个对象的网格单元和网格单元的计数。此外，尽管

14、潜在的网格单元数量可能很高，但是只需要为非空单元创建网格。这样，定义网单元数量可能很高，但是只需要为非空单元创建网格。这样，定义网格、将每个对象指派到一个单元并计算每个单元的密度的时间复杂度格、将每个对象指派到一个单元并计算每个单元的密度的时间复杂度和空间复杂度为和空间复杂度为O(m)O(m)，其中，其中，m m是点的个数。如果邻接的、已占据是点的个数。如果邻接的、已占据的单元可以有效的访问（例如，通过使用搜索树）则整个聚类过程将的单元可以有效的访问（例如，通过使用搜索树）则整个聚类过程将非常高效，例如具有非常高效，例如具有O(mlogm)O(mlogm)的时间复杂度的时间复杂度。缺点缺点：（

15、：（1 1）像大多数基于密度的聚类算法一样、基于网格的聚类非常）像大多数基于密度的聚类算法一样、基于网格的聚类非常依赖于密度阈值的选择。（太高，簇可能或丢失；太低，本应分开的依赖于密度阈值的选择。（太高，簇可能或丢失；太低，本应分开的簇可能被合并）；（簇可能被合并）；（2 2）如果存在不同密度的簇和噪声，则也许不可）如果存在不同密度的簇和噪声，则也许不可能找到适合于数据空间所有部分的值；（能找到适合于数据空间所有部分的值；（3 3）随着维度的增加，网格）随着维度的增加，网格单元个数迅速增加（指数增长）。即对于高维数据，基于网格的聚类单元个数迅速增加（指数增长）。即对于高维数据，基于网格的聚类倾

16、向于效果很差。倾向于效果很差。22第22页/共31页算法评估算法评估聚类评估主要包括如下任务：估计聚类趋势确定数据集中的簇数测定聚类质量23第23页/共31页算法评估算法评估估计聚类趋势聚类趋势评估确定给定的数据集是否具有可以导致有意义的聚类的非随机结构。聚类要求数据的非均匀分布。“如何评估数据集的聚类趋势?”直观地看，我们可以评估数据集被均匀分布产生的概率。这可以通过空间随机性的统计检验来实现。为了解释这一思想，我们考虑一种简单但有效的统计量霍普金斯统计量。霍普金斯统计量是一种空间统计量，检验空间分布的变量的空间随机性。给定数据集D D，它可以看做随机变量O O的一个样本，我们想要确定O O

17、在多大程度上不同于数据空间中的均匀分布。24第24页/共31页算法评估算法评估估计聚类趋势估计聚类趋势霍普金斯统计量-计算（1 1）均匀地从D D的空间中抽取n n个点p p1 1,p,pn n。也就是说，D D的空间中的每 个点都以 相同的概率包含在这个样本中。对于每个点p pi i(1(1i in),),我们找出 p pi i在D D中的最邻近，并令x xi i为p pi i与它在D D中的最近邻之间的距离，即 x xi i=mindist(p=mindist(pi i,v)(,v)(其中v vD)（2 2）均匀地从D D中抽取n n个点q q1 1,q,qn n.对于每个点q qi i(

18、1(1i in),),我们找出q qi i在 D-q D-qi i 中的最邻近，并令y yi i为q qi i它在D-qD-qi i 中的最近邻之间的距离，即 y yi i=mindist(q=mindist(qi i,v)(,v)(其中v vD,vq qi i)（3 3）计算霍普金斯统计量H:H:25第25页/共31页算法评估算法评估估计聚类趋势估计聚类趋势“霍普金斯统计量告诉我们数据集D D有多大可能遵循数据空间的均匀分布?”?”如果D D是均匀分布的，则yi和xi将会很接近，因而H大约为0.5。然而，如果D是高度倾斜的，则yi将显著地小于xi，因而H将接近0。我们的假设是同质假设D是均匀

19、分布的，因而不包含有意义的簇。非均匀假设(即D不是均匀分布，因而包含簇)是备择假设。我们可以迭代地进行霍普金斯统计量检验，使用0.5作为拒绝备择假设阈值，即如果H0.5，则D不大可能具有统计显著的簇。26第26页/共31页算法评估算法评估确定簇数确定簇数l确定数据集中”正确的”簇数是重要的，因为合适的簇数可以控制适当的聚类分析粒度，这可以看做在聚类分析的可压缩性与准确性之间寻找好的平衡点。简单的经验方法：对于n n个点的数据集，设置簇数p p大约为n/2.在期望情况下，每个簇大约有2n个点。肘方法：给点k0,k0,我们可以使用一种像k-k-均值这样的算法对数据集聚类，并计算簇内方差和var(k

20、).var(k).然后，我们绘制varvar关于k k的曲线。曲线的第一个(或者最显著的)拐点暗示”正确的”簇数。还有一些其他的方法，可以依情况选择合适的方法。27第27页/共31页算法评估算法评估测定聚类质量测定聚类质量对于测定聚类的质量，我们有几种方法可供选择。一般而言，根据是否有基准可用，这些方法可以可以分成两类。这里，基准是一种理想的聚类，通常由专家构建。如果有基准可用，则外在方法可以使用它。外在方法比较聚类结构和基准。如果没有基准可用，则我们可以使用内在方法，通过考虑簇的分离情况评估聚类的好坏。基准可以看做一种簇标号形式的监督。因此，外在方法又称为监督方法，而内在方法是无监督方法。2

21、8第28页/共31页算法评估算法评估外在方法外在方法外在方法核心：给定基准Cg，对聚类C赋予一个评分Q(C,Cg),一种外在方法是否有效很大程度上依赖于该方法使用的度量Q,度量Q应满足：簇的同质性：要求聚类中的簇越纯，聚类越好簇的完全性：要求对于聚类来说，根据基准如果两个对象属于相同的类别，则他们应该被分配到相同的簇。碎布袋：把一个异种对象放入一个纯的簇中应该比放入碎布袋中受更大的 ”处罚”。小簇保持性：把小类别划分成小片比将大类别划分成小片更有害。例子：BcubedBcubed精度和召回率 见P P31831829第29页/共31页算法评估算法评估内在方法当没有数据集的基准可用时，我么必须使

22、用内在方法来评估聚类的质量。一般而言，内在方法通过考察簇的分离情况和簇的紧凑情况来评估聚类。许多内在方法都利用数据集的对象之间的相似性度量。轮廓系数：对于n n个对象的数据集D D，假设D D被划分成k k个簇C C1 1,C,CK K.对于每个对象o o与o o所属的簇的其他对象之间的平均距离y(o).y(o).类似地，b(o)b(o)是o o到不属于o o的所有粗的最小平均距离。假设o oCi(1ik),则 y(o)=(dist(o,o)/(|Ci|-1)(oCi,oo)而b(o)=mindist(o,o)/|Ci|(Cj:1jk,ji)对象o的轮廓系数定义为s(o)=(b(o)-y(o)/maxy(o),b(o)，其值在-1和1之间。y(o)反应o所属的簇的紧凑性，值越小越好；b(o)捕获o与其它簇的分离程度，值越大越好。当s(o)的值接近1时，包含o的簇是紧凑的并且远离其它簇，可取情况；当其值为负时，这意味在期望情况下，o距离其它簇的对象比距离与自己同在簇的对象更近，不可取情况。30第30页/共31页31感谢您的观看！第31页/共31页