数据挖掘2015最新精品课程完整课件(第15讲)---基于网格的聚类算法

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

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

3、信息用于回答用于回答查询查询。3STING:统计信息网格网格中常用参数网格中常用参数ncount- -网格中对象数目网格中对象数目nmean- -网格中所有值的平均值网格中所有值的平均值nstdev- -网格中属性值的标准偏差网格中属性值的标准偏差nmin- -网格中属性值的最小值网格中属性值的最小值nmax- -网格中属性值的最大值网格中属性值的最大值ndistribution- -网格中属性值符合的网格中属性值符合的分布类型。分布类型。如正如正态分布、均匀分布、指数分布或者态分布、均匀分布、指数分布或者nonenone（分布类（分布类型未知）型未知）4STING:统计信息网格5STINGS

4、TING聚类的层次结构聚类的层次结构STING:统计信息网格6 level i level i+1 level 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 STING:统计信息网格7假设当前层的属性x的统计信息记为n,m,s,min,max,dist,而ni,mi,si,mini,maxi是相对于当前层来说，对应于更低一层的统计参数。那么n,m,s,min,max,dist可以用以下方

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、 in),),我们找出我们找出 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 中的最近邻之间的距离，即中

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

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

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

27、者最显著的或者最显著的) )拐点暗示拐点暗示”正确的正确的”簇数。簇数。 还有一些其他的方法，可以依情况选择合适的方法还有一些其他的方法，可以依情况选择合适的方法。28算法评估测定聚类质量n对于测定聚类的质量，我们有几种方法可供选择。一般而言，根据是对于测定聚类的质量，我们有几种方法可供选择。一般而言，根据是否有基准可用，这些方法可以可以分成两类。这里，基准是一种理想否有基准可用，这些方法可以可以分成两类。这里，基准是一种理想的聚类，通常由专家构建。的聚类，通常由专家构建。n如果有基准可用，则外在方法可以使用它。外在方法比较聚类结构和如果有基准可用，则外在方法可以使用它。外在方法比较聚类结构和基准。如果没有基准可用，则我们可以使用内在方法，通过考虑簇的基准。如果没有基准可用，则我们可以使用内在方法，通过考虑簇的分离情况评估聚类的好坏。基准可以看做一种簇标号形式的监督。因分离情况评估聚类的好坏。基准可以看做一种簇标号形式的监督。因此，外在方法又称为监督方法，而内在方法是无监督方法。此，外在方法又称为监督方法，而内在方法是无监督方法。29算法评估外在方法外在方法核心：外在方法核心：给定基准Cg，对聚类C赋予一个评分Q(C,Cg),一种外在方法是否有效很大程度上依赖于该方法使用的度量Q,度量Q应满足：n簇簇的的同质性同质性：要求聚类中的簇越纯，聚类越好n簇的簇的完全性完全性：要求对