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

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

1、会计学1数据挖掘课程完整数据挖掘课程完整(wnzhng)基于网格的基于网格的聚类算法聚类算法第一页，共31页。基于基于(jy)网格的聚类网格的聚类n n基本思想是将每个属性的可能值分割成许多相邻的区间，创建网基本思想是将每个属性的可能值分割成许多相邻的区间，创建网基本思想是将每个属性的可能值分割成许多相邻的区间，创建网基本思想是将每个属性的可能值分割成许多相邻的区间，创建网格单元的集合（对于的讨论我们假设属性值是序数的、区间的或格单元的集合（对于的讨论我们假设属性值是序数的、区间的或格单元的集合（对于的讨论我们假设属性值是序数的、区间的或格单元的集合（对于的讨论我们假设属性值是序数的、区间的或

2、者连续的）。者连续的）。者连续的）。者连续的）。n n每个对象落入一个网格单元，网格单元对应的属性区间包含每个对象落入一个网格单元，网格单元对应的属性区间包含每个对象落入一个网格单元，网格单元对应的属性区间包含每个对象落入一个网格单元，网格单元对应的属性区间包含(bohn)(bohn)该对象的值。该对象的值。该对象的值。该对象的值。n n优点是它的处理速度很快，其处理时间独立于数据对象的数目，优点是它的处理速度很快，其处理时间独立于数据对象的数目，优点是它的处理速度很快，其处理时间独立于数据对象的数目，优点是它的处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。

3、只与量化空间中每一维的单元数目有关。只与量化空间中每一维的单元数目有关。只与量化空间中每一维的单元数目有关。2第1页/共31页第二页，共31页。STING:统计统计(tngj)信息网格信息网格n nSTINGSTINGSTINGSTING是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。是一种基于网格的多分辨率聚类技术，它将空间区域划分为矩形单元。n n针对不同级别的分辨率，通常存在多个级别的矩形单元，针对不同级别的分辨率，通常存在多个级别的矩形单元，针对不同

4、级别的分辨率，通常存在多个级别的矩形单元，针对不同级别的分辨率，通常存在多个级别的矩形单元，n n这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。这些单元形成了一个层次结构：高层的每个单元被划分为多个低一层的单元。n n关于每个网格单元属性的统计信息（例如平均值、最大值和最小值）被预先关于每个网格单元属性的统计信息（例如平均值、最大值和最小值）被预先关于每个网格单元属性的统计信息（例如平均值、最大值和最小值）被预先关于每个网格单元属性的统计

5、信息（例如平均值、最大值和最小值）被预先计算和存储计算和存储计算和存储计算和存储(cn ch)(cn ch)(cn ch)(cn ch)。这些统计信息用于回答查询。这些统计信息用于回答查询。这些统计信息用于回答查询。这些统计信息用于回答查询。3第2页/共31页第三页，共31页。STING:统计统计(tngj)信息网格信息网格网格中常用参数网格中常用参数网格中常用参数网格中常用参数count-count-count-count-网格中对象数目网格中对象数目网格中对象数目网格中对象数目mean-mean-mean-mean-网格中所有值的平均值网格中所有值的平均值网格中所有值的平均值网格中所有值的

6、平均值stdev-stdev-stdev-stdev-网格中属性值的标准偏差网格中属性值的标准偏差网格中属性值的标准偏差网格中属性值的标准偏差min-min-min-min-网格中属性值的最小值网格中属性值的最小值网格中属性值的最小值网格中属性值的最小值max-max-max-max-网格中属性值的最大值网格中属性值的最大值网格中属性值的最大值网格中属性值的最大值distribution-distribution-distribution-distribution-网格中属性值符合的分布类型网格中属性值符合的分布类型网格中属性值符合的分布类型网格中属性值符合的分布类型(lixng)(lixng

7、)(lixng)(lixng)。如正态分布、均匀分。如正态分布、均匀分。如正态分布、均匀分。如正态分布、均匀分布、指数分布或者布、指数分布或者布、指数分布或者布、指数分布或者nonenonenonenone（分布类型（分布类型（分布类型（分布类型(lixng)(lixng)(lixng)(lixng)未知）未知）未知）未知）4第3页/共31页第四页，共31页。STING:统计统计(tngj)信息网格信息网格5STINGSTING聚类的层次结构聚类的层次结构第4页/共31页第五页，共31页。STING:统计统计(tngj)信息网格信息网格6 level i level i+1 level i+2

8、 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页第六页，共31页。STING:STING:统计统计统计统计(tngj)(tngj)信息网格信息网格信息网格信息网格7假设当前层的属性x的统计信息记为n,m,s,min,max,dist,而ni,mi,si,mini,maxi是相对(xingdu)于当前层来说，对应于更低一层的统计参数。那么n,m,s,min,max,dist可以用以下方法计

9、算:dist 第6页/共31页第七页，共31页。STING:STING:统计统计统计统计(tngj)(tngj)信息网格信息网格信息网格信息网格8第7页/共31页第八页，共31页。STING:统计统计(tngj)信息网格信息网格n n当数据加载到数据库时。最底层的单元参数直接由数据计算，若当数据加载到数据库时。最底层的单元参数直接由数据计算，若当数据加载到数据库时。最底层的单元参数直接由数据计算，若当数据加载到数据库时。最底层的单元参数直接由数据计算，若分布类型事先知道，可以用户直接指定，而较高层的分布类型可分布类型事先知道，可以用户直接指定，而较高层的分布类型可分布类型事先知道，可以用户直接

10、指定，而较高层的分布类型可分布类型事先知道，可以用户直接指定，而较高层的分布类型可以基于它对应的低层单元多数的分布类型，用一个阈值过滤过程以基于它对应的低层单元多数的分布类型，用一个阈值过滤过程以基于它对应的低层单元多数的分布类型，用一个阈值过滤过程以基于它对应的低层单元多数的分布类型，用一个阈值过滤过程的合取来计算，若低层分布彼此不同，则高层分布设置为的合取来计算，若低层分布彼此不同，则高层分布设置为的合取来计算，若低层分布彼此不同，则高层分布设置为的合取来计算，若低层分布彼此不同，则高层分布设置为nonenonenonenone。n n高层单元的统计参数可以很容易高层单元的统计参数可以很容

11、易高层单元的统计参数可以很容易高层单元的统计参数可以很容易(rngy)(rngy)(rngy)(rngy)的从低层单元的参数计的从低层单元的参数计的从低层单元的参数计的从低层单元的参数计算得到。算得到。算得到。算得到。9第8页/共31页第九页，共31页。STING:统计统计(tngj)信息网格信息网格统计处理思想：统计处理思想：统计处理思想：统计处理思想：使用自顶向下的方法回答空间数据的查询使用自顶向下的方法回答空间数据的查询使用自顶向下的方法回答空间数据的查询使用自顶向下的方法回答空间数据的查询 从一个预先选择的层次开始通常包含少量的单元，为当前层的每个单元计从一个预先选择的层次开始通常包含

12、少量的单元，为当前层的每个单元计从一个预先选择的层次开始通常包含少量的单元，为当前层的每个单元计从一个预先选择的层次开始通常包含少量的单元，为当前层的每个单元计算置信区间算置信区间算置信区间算置信区间不相关的单元不再考虑不相关的单元不再考虑不相关的单元不再考虑不相关的单元不再考虑(kol)(kol)(kol)(kol)当检查完当前层，接着检查下一个低层次当检查完当前层，接着检查下一个低层次当检查完当前层，接着检查下一个低层次当检查完当前层，接着检查下一个低层次重复这个过程直到达到底层重复这个过程直到达到底层重复这个过程直到达到底层重复这个过程直到达到底层10第9页/共31页第十页，共31页。S

13、TING:统计统计(tngj)信息网格信息网格算法步骤：算法步骤：算法步骤：算法步骤：1 1 1 1 从一个层次开始从一个层次开始从一个层次开始从一个层次开始2 2 2 2 对于这一层次的每个单元格，我们计算查询相关的属性对于这一层次的每个单元格，我们计算查询相关的属性对于这一层次的每个单元格，我们计算查询相关的属性对于这一层次的每个单元格，我们计算查询相关的属性(shxng)(shxng)(shxng)(shxng)值值值值3 3 3 3 从计算的属性从计算的属性从计算的属性从计算的属性(shxng)(shxng)(shxng)(shxng)值及其约束条件中，我们将每一个单元格标注成相关或者

14、值及其约束条件中，我们将每一个单元格标注成相关或者值及其约束条件中，我们将每一个单元格标注成相关或者值及其约束条件中，我们将每一个单元格标注成相关或者不相关不相关不相关不相关4 4 4 4 如果这一层是底层，则转到步骤如果这一层是底层，则转到步骤如果这一层是底层，则转到步骤如果这一层是底层，则转到步骤6 6 6 6，否则就行步骤，否则就行步骤，否则就行步骤，否则就行步骤5 5 5 55 5 5 5 我们由层次结构转到下一层依照步骤我们由层次结构转到下一层依照步骤我们由层次结构转到下一层依照步骤我们由层次结构转到下一层依照步骤2 2 2 2进行计算进行计算进行计算进行计算6 6 6 6 查询结果

15、满足，转到步骤查询结果满足，转到步骤查询结果满足，转到步骤查询结果满足，转到步骤8 8 8 8，否则转到步骤，否则转到步骤，否则转到步骤，否则转到步骤7 7 7 77 7 7 7 恢复数据到相关的单元格进一步处理以得到满意结果，转到步骤恢复数据到相关的单元格进一步处理以得到满意结果，转到步骤恢复数据到相关的单元格进一步处理以得到满意结果，转到步骤恢复数据到相关的单元格进一步处理以得到满意结果，转到步骤8 8 8 88 8 8 8 停止停止停止停止11第10页/共31页第十一页，共31页。STING:统计统计(tngj)信息网格信息网格应用应用n nSTING STING STING STING

16、 能够用来帮助各种不同的空间查询能够用来帮助各种不同的空间查询能够用来帮助各种不同的空间查询能够用来帮助各种不同的空间查询(chxn)(chxn)(chxn)(chxn)。这最常见的请求查询。这最常见的请求查询。这最常见的请求查询。这最常见的请求查询(chxn)(chxn)(chxn)(chxn)是区域查询是区域查询是区域查询是区域查询(chxn)(chxn)(chxn)(chxn)。n n例如查询例如查询例如查询例如查询(chxn)(chxn)(chxn)(chxn)满足一定条件的区域。查找加利福尼亚州地区的房屋以得到房屋所在区域相关方面数满足一定条件的区域。查找加利福尼亚州地区的房屋以得到

17、房屋所在区域相关方面数满足一定条件的区域。查找加利福尼亚州地区的房屋以得到房屋所在区域相关方面数满足一定条件的区域。查找加利福尼亚州地区的房屋以得到房屋所在区域相关方面数据。查询据。查询据。查询据。查询(chxn)(chxn)(chxn)(chxn)的对象是房屋，价格是其中的一个属性。区域须满足约束条件：哪些区域面积至少是的对象是房屋，价格是其中的一个属性。区域须满足约束条件：哪些区域面积至少是的对象是房屋，价格是其中的一个属性。区域须满足约束条件：哪些区域面积至少是的对象是房屋，价格是其中的一个属性。区域须满足约束条件：哪些区域面积至少是A,A,A,A,单元地区至少有单元地区至少有单元地区至

18、少有单元地区至少有c c c c栋房屋栋房屋栋房屋栋房屋,至少至少至少至少d%d%d%d%的房屋其价格在的房屋其价格在的房屋其价格在的房屋其价格在a a a a到到到到b b b b之间的置信度为之间的置信度为之间的置信度为之间的置信度为1-t.1-t.1-t.1-t.且且且且mn,.mn,.mn,.mA*C*d%(p2*nA*C*d%(p2*nA*C*d%(p2*nA*C*d%成立成立成立成立?)?)?)?)，若相关，则标记该网格为，若相关，则标记该网格为，若相关，则标记该网格为，若相关，则标记该网格为relevantrelevantrelevantrelevant否则标记为否则标记为否则标

19、记为否则标记为n n not-relevant.not-relevant.not-relevant.not-relevant.处理层次结构中的下一层。这个处理过程反复进行。处理层次结构中的下一层。这个处理过程反复进行。处理层次结构中的下一层。这个处理过程反复进行。处理层次结构中的下一层。这个处理过程反复进行。直直直直 n n 到到达最底层到到达最底层到到达最底层到到达最底层 。最后返回满足。最后返回满足。最后返回满足。最后返回满足(mnz)(mnz)(mnz)(mnz)查询要求的相关单元的区域。查询要求的相关单元的区域。查询要求的相关单元的区域。查询要求的相关单元的区域。n n 查找结束查找结

20、束查找结束查找结束 。13第12页/共31页第十三页，共31页。STING:统计统计(tngj)信息网格信息网格优点如下：优点如下：优点如下：优点如下：计算是独立于查询的；计算是独立于查询的；计算是独立于查询的；计算是独立于查询的；有利于并行处理和增量有利于并行处理和增量有利于并行处理和增量有利于并行处理和增量(zn lin)(zn lin)(zn lin)(zn lin)更新；更新；更新；更新；效率很高。效率很高。效率很高。效率很高。STINGSTINGSTINGSTING算法扫描数据库一次来计算单元的统计信息，因此产生聚类的算法扫描数据库一次来计算单元的统计信息，因此产生聚类的算法扫描数据

21、库一次来计算单元的统计信息，因此产生聚类的算法扫描数据库一次来计算单元的统计信息，因此产生聚类的时间复杂度是时间复杂度是时间复杂度是时间复杂度是o(n)o(n)o(n)o(n)，其中，其中，其中，其中n n n n是对象的数目。在层次结构建立后，查是对象的数目。在层次结构建立后，查是对象的数目。在层次结构建立后，查是对象的数目。在层次结构建立后，查询处理时间是，这里询处理时间是，这里询处理时间是，这里询处理时间是，这里g g g g是最低层网格单元的数目是最低层网格单元的数目是最低层网格单元的数目是最低层网格单元的数目o(g)o(g)o(g)o(g)，通常远小于，通常远小于，通常远小于，通常远

22、小于n n n n。14第13页/共31页第十四页，共31页。STING:统计统计(tngj)信息网格信息网格缺点如下：缺点如下：缺点如下：缺点如下：如果粒度比较细，处理的代价会显著增加；但是，如果网格结构最低如果粒度比较细，处理的代价会显著增加；但是，如果网格结构最低如果粒度比较细，处理的代价会显著增加；但是，如果网格结构最低如果粒度比较细，处理的代价会显著增加；但是，如果网格结构最低层的粒度太粗，将会降低聚类分析的质量；层的粒度太粗，将会降低聚类分析的质量；层的粒度太粗，将会降低聚类分析的质量；层的粒度太粗，将会降低聚类分析的质量；在构建一个父亲单元时没有考虑孩子在构建一个父亲单元时没有考

23、虑孩子在构建一个父亲单元时没有考虑孩子在构建一个父亲单元时没有考虑孩子(hi zi)(hi zi)(hi zi)(hi zi)单元和其相邻单元之间单元和其相邻单元之间单元和其相邻单元之间单元和其相邻单元之间的关系，因此，结果簇的形状是的关系，因此，结果簇的形状是的关系，因此，结果簇的形状是的关系，因此，结果簇的形状是isotheticisotheticisotheticisothetic，即所有的聚类边界或，即所有的聚类边界或，即所有的聚类边界或，即所有的聚类边界或者是水平的，或者是竖直的，没有斜的分界线。者是水平的，或者是竖直的，没有斜的分界线。者是水平的，或者是竖直的，没有斜的分界线。者是

24、水平的，或者是竖直的，没有斜的分界线。尽管该技术有快速的处理速度，但可能降低簇的质量和精确性尽管该技术有快速的处理速度，但可能降低簇的质量和精确性尽管该技术有快速的处理速度，但可能降低簇的质量和精确性尽管该技术有快速的处理速度，但可能降低簇的质量和精确性15第14页/共31页第十五页，共31页。CLIQUE:CLIQUE:一种一种一种一种(y zh(y zh n n)类似于类似于类似于类似于AprioriApriori的子空间聚类方法的子空间聚类方法的子空间聚类方法的子空间聚类方法 CLICQUE CLICQUE CLICQUE CLICQUE算法是基于网格的空间聚类算法，但它同时非常好地结算

25、法是基于网格的空间聚类算法，但它同时非常好地结算法是基于网格的空间聚类算法，但它同时非常好地结算法是基于网格的空间聚类算法，但它同时非常好地结 合了基于合了基于合了基于合了基于密度的聚类算法思想，因此既可以像基于密度的方法发现任意形状密度的聚类算法思想，因此既可以像基于密度的方法发现任意形状密度的聚类算法思想，因此既可以像基于密度的方法发现任意形状密度的聚类算法思想，因此既可以像基于密度的方法发现任意形状(xngzhun)(xngzhun)(xngzhun)(xngzhun)的簇，又可以像基于网格的方法处理较大的多维数据集。的簇，又可以像基于网格的方法处理较大的多维数据集。的簇，又可以像基于网

26、格的方法处理较大的多维数据集。的簇，又可以像基于网格的方法处理较大的多维数据集。CLIQUE CLIQUE CLIQUE CLIQUE把每个维划分成不重叠的区间，从而把数据对象的整个嵌入空间划分成把每个维划分成不重叠的区间，从而把数据对象的整个嵌入空间划分成把每个维划分成不重叠的区间，从而把数据对象的整个嵌入空间划分成把每个维划分成不重叠的区间，从而把数据对象的整个嵌入空间划分成单元。它使用一个密度阀值识别稠密单元，一个单元是稠密的，如果映射到单元。它使用一个密度阀值识别稠密单元，一个单元是稠密的，如果映射到单元。它使用一个密度阀值识别稠密单元，一个单元是稠密的，如果映射到单元。它使用一个密度

27、阀值识别稠密单元，一个单元是稠密的，如果映射到它的对象超过该密度阀值它的对象超过该密度阀值它的对象超过该密度阀值它的对象超过该密度阀值16第15页/共31页第十六页，共31页。CLIQUE:CLIQUE:一种一种一种一种(y zh(y zh n n)类似于类似于类似于类似于AprioriApriori的子空间聚类的子空间聚类的子空间聚类的子空间聚类方法方法方法方法算法概述：算法概述：算法概述：算法概述：算法需要两个参数值，一个是网格的步长，一具是密度阈值。算法需要两个参数值，一个是网格的步长，一具是密度阈值。算法需要两个参数值，一个是网格的步长，一具是密度阈值。算法需要两个参数值，一个是网格的

28、步长，一具是密度阈值。网格步长决定了空间的划分，而密度阈值用来定义密集网格。网格步长决定了空间的划分，而密度阈值用来定义密集网格。网格步长决定了空间的划分，而密度阈值用来定义密集网格。网格步长决定了空间的划分，而密度阈值用来定义密集网格。聚类思想：聚类思想：聚类思想：聚类思想：算法首先扫描所有网格，当发现第一个密集网格时，便以该网格开始扩展，算法首先扫描所有网格，当发现第一个密集网格时，便以该网格开始扩展，算法首先扫描所有网格，当发现第一个密集网格时，便以该网格开始扩展，算法首先扫描所有网格，当发现第一个密集网格时，便以该网格开始扩展，扩展原则是若一个网格与已知密集区域内的网格邻接并且其自身也

29、是密集扩展原则是若一个网格与已知密集区域内的网格邻接并且其自身也是密集扩展原则是若一个网格与已知密集区域内的网格邻接并且其自身也是密集扩展原则是若一个网格与已知密集区域内的网格邻接并且其自身也是密集的，则将该网格加入到该密集区域中、直到不再有这样的网格被发现为止。的，则将该网格加入到该密集区域中、直到不再有这样的网格被发现为止。的，则将该网格加入到该密集区域中、直到不再有这样的网格被发现为止。的，则将该网格加入到该密集区域中、直到不再有这样的网格被发现为止。算法再继续扫描网格并重复上述过程，直至所有网格被遍历。以自动地发现算法再继续扫描网格并重复上述过程，直至所有网格被遍历。以自动地发现算法再

30、继续扫描网格并重复上述过程，直至所有网格被遍历。以自动地发现算法再继续扫描网格并重复上述过程，直至所有网格被遍历。以自动地发现最高维的子空间，高密度聚类存在于这些子空间中，并且它对元组的输入最高维的子空间，高密度聚类存在于这些子空间中，并且它对元组的输入最高维的子空间，高密度聚类存在于这些子空间中，并且它对元组的输入最高维的子空间，高密度聚类存在于这些子空间中，并且它对元组的输入顺序顺序顺序顺序(shnx)(shnx)不敏感，无需假设任何规范的数据分布。它随输入数据的大不敏感，无需假设任何规范的数据分布。它随输入数据的大不敏感，无需假设任何规范的数据分布。它随输入数据的大不敏感，无需假设任何规

31、范的数据分布。它随输入数据的大小线性地扩展，当数据的维数增加时具有良好的可伸缩性。小线性地扩展，当数据的维数增加时具有良好的可伸缩性。小线性地扩展，当数据的维数增加时具有良好的可伸缩性。小线性地扩展，当数据的维数增加时具有良好的可伸缩性。17第16页/共31页第十七页，共31页。CLIQUE:CLIQUE:一种类似于一种类似于一种类似于一种类似于AprioriApriori的子空间的子空间的子空间的子空间(kngjin)(kngjin)聚类方法聚类方法聚类方法聚类方法n nCLIQUECLIQUECLIQUECLIQUE识别候选搜索空间的主要策略是使用稠密单元关于维度的单调性。识别候选搜索空间

32、的主要策略是使用稠密单元关于维度的单调性。识别候选搜索空间的主要策略是使用稠密单元关于维度的单调性。识别候选搜索空间的主要策略是使用稠密单元关于维度的单调性。n n在子空间聚类的背景下，单调性陈述如下：在子空间聚类的背景下，单调性陈述如下：在子空间聚类的背景下，单调性陈述如下：在子空间聚类的背景下，单调性陈述如下：n n 一个一个一个一个k-k-k-k-维维维维(k1)(k1)(k1)(k1)单元单元单元单元c c c c至少至少至少至少(zhsho)(zhsho)(zhsho)(zhsho)有有有有m mm m个点，仅当个点，仅当个点，仅当个点，仅当c c c c的每个的每个的每个的每个(k

33、-1)-(k-1)-(k-1)-(k-1)-维投影维投影维投影维投影n n (它是它是它是它是(k-1)-(k-1)-(k-1)-(k-1)-维单元维单元维单元维单元)至少至少至少至少(zhsho)(zhsho)(zhsho)(zhsho)有有有有m mm m个点。个点。个点。个点。n n 如下图嵌入数据空间包括如下图嵌入数据空间包括如下图嵌入数据空间包括如下图嵌入数据空间包括3 3 3 3个维：个维：个维：个维：n n age,salary age,salary age,salary age,salary和和和和vacationvacationvacationvacation。例如，子空间。

34、例如，子空间。例如，子空间。例如，子空间ageageageage和和和和salarysalarysalarysalary中的一个二维中的一个二维中的一个二维中的一个二维n n 单元包含单元包含单元包含单元包含m mm m个点，仅当该单元在每个维上的投影都至少个点，仅当该单元在每个维上的投影都至少个点，仅当该单元在每个维上的投影都至少个点，仅当该单元在每个维上的投影都至少(zhsho)(zhsho)(zhsho)(zhsho)包含包含包含包含m mm m个点。个点。个点。个点。18第17页/共31页第十八页，共31页。19Salary(10,000)2030405060age5431267020

35、30405060age54312670Vacation(week)ageVacationSalary3050=3第18页/共31页第十九页，共31页。CLIQUE:CLIQUE:一种类似于一种类似于一种类似于一种类似于AprioriApriori的子空间的子空间的子空间的子空间(kngjin)(kngjin)聚类聚类聚类聚类方法方法方法方法相关定义：相关定义：相关定义：相关定义：网格密度：网格中所包含的空间对象的数目。网格密度：网格中所包含的空间对象的数目。网格密度：网格中所包含的空间对象的数目。网格密度：网格中所包含的空间对象的数目。密集网格：给定刻度阈值密集网格：给定刻度阈值密集网格：给定

36、刻度阈值密集网格：给定刻度阈值,当网格当网格当网格当网格g g g g的密度的密度的密度的密度时，网格时，网格时，网格时，网格g g g g是是是是 密集网格，否则是非密集网格。密集网格，否则是非密集网格。密集网格，否则是非密集网格。密集网格，否则是非密集网格。网格刻度连通区域：设网格刻度连通区域：设网格刻度连通区域：设网格刻度连通区域：设GridsGridsGridsGrids为一个为一个为一个为一个(y)(y)(y)(y)网格集合，若集合中的所有网格相互邻网格集合，若集合中的所有网格相互邻网格集合，若集合中的所有网格相互邻网格集合，若集合中的所有网格相互邻接且均是密集网格，则称接且均是密集

37、网格，则称接且均是密集网格，则称接且均是密集网格，则称GridGridGridGrid是网格是网格是网格是网格 密度连通区域。密度连通区域。密度连通区域。密度连通区域。20第19页/共31页第二十页，共31页。CLIQUE:CLIQUE:一种类似于一种类似于一种类似于一种类似于AprioriApriori的子空间的子空间的子空间的子空间(kngjin)(kngjin)聚类方聚类方聚类方聚类方法法法法21第20页/共31页第二十一页，共31页。CLIQUE:CLIQUE:一种一种一种一种(y zh(y zh n n)类似于类似于类似于类似于AprioriApriori的子空间聚类方的子空间聚类方

38、的子空间聚类方的子空间聚类方法法法法以二维空间以二维空间以二维空间以二维空间(kngjin)(kngjin)(kngjin)(kngjin)为例说明该算法：为例说明该算法：为例说明该算法：为例说明该算法：=4=4=4=422第21页/共31页第二十二页，共31页。基于基于基于基于(jy)(jy)网格的聚类网格的聚类网格的聚类网格的聚类-总结总结总结总结优点优点优点优点:可能是非常有效的。给定每个属性的划分可能是非常有效的。给定每个属性的划分可能是非常有效的。给定每个属性的划分可能是非常有效的。给定每个属性的划分(hu fn)(hu fn)(hu fn)(hu fn)，单遍数据扫描就可，单遍数据

39、扫描就可，单遍数据扫描就可，单遍数据扫描就可以确定每个对象的网格单元和网格单元的计数。此外，尽管潜在的网格以确定每个对象的网格单元和网格单元的计数。此外，尽管潜在的网格以确定每个对象的网格单元和网格单元的计数。此外，尽管潜在的网格以确定每个对象的网格单元和网格单元的计数。此外，尽管潜在的网格单元数量可能很高，但是只需要为非空单元创建网格。这样，定义网格、单元数量可能很高，但是只需要为非空单元创建网格。这样，定义网格、单元数量可能很高，但是只需要为非空单元创建网格。这样，定义网格、单元数量可能很高，但是只需要为非空单元创建网格。这样，定义网格、将每个对象指派到一个单元并计算每个单元的密度的时间复

40、杂度和空间将每个对象指派到一个单元并计算每个单元的密度的时间复杂度和空间将每个对象指派到一个单元并计算每个单元的密度的时间复杂度和空间将每个对象指派到一个单元并计算每个单元的密度的时间复杂度和空间复杂度为复杂度为复杂度为复杂度为O(m)O(m)O(m)O(m)，其中，其中，其中，其中，m mm m是点的个数。如果邻接的、已占据的单元可以是点的个数。如果邻接的、已占据的单元可以是点的个数。如果邻接的、已占据的单元可以是点的个数。如果邻接的、已占据的单元可以有效的访问（例如，通过使用搜索树）则整个聚类过程将非常高效，例有效的访问（例如，通过使用搜索树）则整个聚类过程将非常高效，例有效的访问（例如，

41、通过使用搜索树）则整个聚类过程将非常高效，例有效的访问（例如，通过使用搜索树）则整个聚类过程将非常高效，例如具有如具有如具有如具有O(mlogm)O(mlogm)O(mlogm)O(mlogm)的时间复杂度。的时间复杂度。的时间复杂度。的时间复杂度。缺点：（缺点：（缺点：（缺点：（1 1 1 1）像大多数基于密度的聚类算法一样、基于网格的聚类非常依赖于）像大多数基于密度的聚类算法一样、基于网格的聚类非常依赖于）像大多数基于密度的聚类算法一样、基于网格的聚类非常依赖于）像大多数基于密度的聚类算法一样、基于网格的聚类非常依赖于密度阈值的选择。（太高，簇可能或丢失；太低，本应分开的簇可能被密度阈值的

42、选择。（太高，簇可能或丢失；太低，本应分开的簇可能被密度阈值的选择。（太高，簇可能或丢失；太低，本应分开的簇可能被密度阈值的选择。（太高，簇可能或丢失；太低，本应分开的簇可能被合并）；（合并）；（合并）；（合并）；（2 2 2 2）如果存在不同密度的簇和噪声，则也许不可能找到适合于）如果存在不同密度的簇和噪声，则也许不可能找到适合于）如果存在不同密度的簇和噪声，则也许不可能找到适合于）如果存在不同密度的簇和噪声，则也许不可能找到适合于数据空间所有部分的值；（数据空间所有部分的值；（数据空间所有部分的值；（数据空间所有部分的值；（3 3 3 3）随着维度的增加，网格单元个数迅速增加）随着维度的增

43、加，网格单元个数迅速增加）随着维度的增加，网格单元个数迅速增加）随着维度的增加，网格单元个数迅速增加（指数增长）。即对于高维数据，基于网格的聚类倾向于效果很差。（指数增长）。即对于高维数据，基于网格的聚类倾向于效果很差。（指数增长）。即对于高维数据，基于网格的聚类倾向于效果很差。（指数增长）。即对于高维数据，基于网格的聚类倾向于效果很差。23第22页/共31页第二十三页，共31页。算法算法算法算法(sun f(sun f)评估评估评估评估聚类评估主要包括如下任务：聚类评估主要包括如下任务：聚类评估主要包括如下任务：聚类评估主要包括如下任务：估计估计估计估计(gj)(gj)(gj)(gj)聚类趋

44、势聚类趋势聚类趋势聚类趋势确定数据集中的簇数确定数据集中的簇数确定数据集中的簇数确定数据集中的簇数测定聚类质量测定聚类质量测定聚类质量测定聚类质量24第23页/共31页第二十四页，共31页。算法评估算法评估算法评估算法评估(pn(pn )估计聚类趋势估计聚类趋势估计聚类趋势估计聚类趋势n n聚类趋势评估确定给定的数据集是否具有可以导致有意义的聚类的非随机结聚类趋势评估确定给定的数据集是否具有可以导致有意义的聚类的非随机结聚类趋势评估确定给定的数据集是否具有可以导致有意义的聚类的非随机结聚类趋势评估确定给定的数据集是否具有可以导致有意义的聚类的非随机结构。构。构。构。n n聚类要求数据的非均匀分

45、布。聚类要求数据的非均匀分布。聚类要求数据的非均匀分布。聚类要求数据的非均匀分布。n n“如何评估数据集的聚类趋势如何评估数据集的聚类趋势如何评估数据集的聚类趋势如何评估数据集的聚类趋势?”?”?”?”直观地看，我们可以评估数据集被均匀分直观地看，我们可以评估数据集被均匀分直观地看，我们可以评估数据集被均匀分直观地看，我们可以评估数据集被均匀分布产生的概率。这可以通过空间布产生的概率。这可以通过空间布产生的概率。这可以通过空间布产生的概率。这可以通过空间(kngjin)(kngjin)(kngjin)(kngjin)随机性的统计检验来实现。为了随机性的统计检验来实现。为了随机性的统计检验来实现

46、。为了随机性的统计检验来实现。为了解释这一思想，我们考虑一种简单但有效的统计量解释这一思想，我们考虑一种简单但有效的统计量解释这一思想，我们考虑一种简单但有效的统计量解释这一思想，我们考虑一种简单但有效的统计量霍普金斯统计量。霍普金斯统计量。霍普金斯统计量。霍普金斯统计量。n n霍普金斯统计量是一种空间霍普金斯统计量是一种空间霍普金斯统计量是一种空间霍普金斯统计量是一种空间(kngjin)(kngjin)(kngjin)(kngjin)统计量，检验空间统计量，检验空间统计量，检验空间统计量，检验空间(kngjin)(kngjin)(kngjin)(kngjin)分布的分布的分布的分布的变量的空

47、间变量的空间变量的空间变量的空间(kngjin)(kngjin)(kngjin)(kngjin)随机性。给定数据集随机性。给定数据集随机性。给定数据集随机性。给定数据集D D D D，它可以看做随机变量，它可以看做随机变量，它可以看做随机变量，它可以看做随机变量O O O O的一个的一个的一个的一个样本，我们想要确定样本，我们想要确定样本，我们想要确定样本，我们想要确定O O O O在多大程度上不同于数据空间在多大程度上不同于数据空间在多大程度上不同于数据空间在多大程度上不同于数据空间(kngjin)(kngjin)(kngjin)(kngjin)中的均匀分中的均匀分中的均匀分中的均匀分布。布

48、。布。布。n n 25第24页/共31页第二十五页，共31页。算法算法算法算法(sun f(sun f)评估评估评估评估估计聚类趋势估计聚类趋势估计聚类趋势估计聚类趋势霍普金斯统计量霍普金斯统计量霍普金斯统计量霍普金斯统计量-计算计算计算计算（1 1 1 1）均匀地从）均匀地从）均匀地从）均匀地从D D D D的空间中抽取的空间中抽取的空间中抽取的空间中抽取n n n n个点个点个点个点p1,pnp1,pnp1,pnp1,pn。也就是说，。也就是说，。也就是说，。也就是说，D D D D的空间中的每的空间中的每的空间中的每的空间中的每 个点都以个点都以个点都以个点都以 相同的概率包含在这个相同

49、的概率包含在这个相同的概率包含在这个相同的概率包含在这个(zh ge)(zh ge)(zh ge)(zh ge)样本中。对于每个点样本中。对于每个点样本中。对于每个点样本中。对于每个点pi(1in),pi(1in),pi(1in),pi(1in),我们找出我们找出我们找出我们找出 pi pi pi pi在在在在D D D D中的最邻近，并令中的最邻近，并令中的最邻近，并令中的最邻近，并令xixixixi为为为为pipipipi与它在与它在与它在与它在D D D D中的最近邻之间的距离，即中的最近邻之间的距离，即中的最近邻之间的距离，即中的最近邻之间的距离，即 xi=mindist(pi,v)(

50、xi=mindist(pi,v)(xi=mindist(pi,v)(xi=mindist(pi,v)(其中其中其中其中vD)vD)vD)vD)（2 2 2 2）均匀地从）均匀地从）均匀地从）均匀地从D D D D中抽取中抽取中抽取中抽取n n n n个点个点个点个点q1,qn.q1,qn.q1,qn.q1,qn.对于每个点对于每个点对于每个点对于每个点qi(1in),qi(1in),qi(1in),qi(1in),我们找出我们找出我们找出我们找出qiqiqiqi在在在在 D-qi D-qi D-qi D-qi中的最邻近，并令中的最邻近，并令中的最邻近，并令中的最邻近，并令yiyiyiyi为为为