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

《数据挖掘2015最新精品课程完整课件(第15讲)---基于网格的聚类算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

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

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

3、evel6STING:统计信息网格假设当前层的属性x的统计信息记为n,m,s,min,max,dist,而ni,mi,si,mini,maxi是相对于当前层来说，对应于更低一层的统计参数。那么n,m,s,min,max,dist可以用以下方法计算:dist7STING:统计信息网格8STING:统计信息网格当数据加载到数据库时。最底层的单元参数直接由数据计算，若分布类型事先知道，可以用户直接指定，而较高层的分布类型可以基于它对应的低层单元多数的分布类型，用一个阈值过滤过程的合取来计算，若低层分布彼此不同，则高层分布设置为none。高层单元的统计参数可以很容易的从低层

4、单元的参数计算得到。9STING:统计信息网格统计处理思想：使用自顶向下的方法回答空间数据的查询从一个预先选择的层次开始－通常包含少量的单元，为当前层的每个单元计算置信区间不相关的单元不再考虑当检查完当前层，接着检查下一个低层次重复这个过程直到达到底层10STING:统计信息网格算法步骤：1从一个层次开始2对于这一层次的每个单元格，我们计算查询相关的属性值3从计算的属性值及其约束条件中，我们将每一个单元格标注成相关或者不相关4如果这一层是底层，则转到步骤6，否则就行步骤55我们由层次结构转到下一层依照步骤2进行计算6查询结果满足，转到步骤8，否则转到步骤77恢复数据

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

6、percent[d%,l]ANDAREA(A,+)ANDLOCATIONCalifornia12STING:统计信息网格假设选择第一层作为查询过程的开始点(也可以选择包含少量单元网格的其他层)并假设最底层的网格的属性price近似服从标准分布，高层网格的price属性的分布可能是NONE。假设houses的price在[a,b]的概率p，我们可以求得p置信区间(或者估计其概率范围)[p1,p2],可以检查每个网格单元是否与给定查询相关(p2*n>A*C*d%成立?)，若相关，则标记该网格为relevant否则标记为not-relevant.处理层次结构中的下一层。这

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