2
STING:统计信息网格
? STING是一种基于网格的多分辨率聚类技术，它 将空间区域划分为 矩形单元。 ? 针对不同级别的分辨率，通常存在多个级别的 矩形单元， ?这些单元形成了一个 层次结构：高层的每个单 元被划分为多个低一层的单元。 ? 关于每个网格单元属性的统计信息（例如平均 值、最大值和最小值）被预先计算和存储。这 些统计信息 用于回答 查询。
到步骤8 8 停止
11
STING:统计信息网格——应用
? STING 能够用来帮助各种不同的空间查询。这最常见的请求查询是区域查询。 ? 例如查询满足一定条件的区域。查找加利福尼亚州地区的房屋以得到房屋所
在区域相关方面数据。查询的对象是房屋，价格是其中的一个属性。区域须 满足约束条件：哪些区域面积至少是A,单元地区至少有c栋房屋,至少d%的房 屋其价格在a到b之间的置信度为1-t.且m<n,.
4
STING:统计信息网格
STING聚类的层次结构
5
STING:统计信息网格
level i
level i+1
level i+2
a cell of (i-1)th level corresponds to 4 cells of (i)th level
6
STING:统计信息网格
假设当前层的属性x的统计信息记为n,m,s,min,max,dist,而ni,mi,si,mini,maxi是相对 于当前层来说，对应于更低一层的统计参数。那么n,m,s,min,max,dist 可以用以下方法计算:
? CLIQUE把每个维划分成不重叠的区间，从而把数据对象的整个嵌入 空间划分成单元。它使用一个密度阀值识别稠密单元，一个单元是稠 密的，如果映射到它的对象超过该密度阀值
16
CLIQUE :一种类似于 Apriori的子空间聚类方法
dist
7
STING:统计信息网格
8
STING: 统计信息网格
? 当数据加载到数据库时。最底层的单元参数直接 由数据计算，若分布类型事先知道，可以用户直 接指定，而较高层的分布类型可以基于它对应的 低层单元多数的分布类型，用一个阈值过滤过程 的合取来计算，若低层分布彼此不同，则高层分 布设置为none 。
3
STING:统计信息网格
网格中常用参数 ? count-网格中对象数目 ? mean-网格中所有值的平均值 ? stdev-网格中属性值的标准偏差 ? min-网格中属性值的最小值 ? max-网格中属性值的最大值 ? distribution -网格中属性值符合的 分布类型。 如正
态分布、均匀分布、指数分布或者 none（分布类 型未知）
? 高层单元的统计参数可以很容易的从低层单元的
参数计算得到 。
9
STIN询
从一个预先选择的层次开始－通常包含少量的单元， 为当前层的每个单元计算置信区间 ? 不相关的单元不再考虑 ? 当检查完当前层，接着检查下一个低层次 ? 重复这个过程直到达到底层
? 在构建一个父亲单元时没有考虑孩子单元和其相邻单元之 间的关系，因此，结果簇的形状是isothetic ，即所有的
聚类边界或者是水平的，或者是竖直的，没有斜的分界线。
? 尽管该技术有快速的处理速度，但可能降低簇的质量和精 确性
15
CLIQUE :一种类似于 Apriori的子空间聚类方法
? CLICQUE算法是基于网格的空间聚类算法，但它同时非常好地结 合了基于密度的聚类算法思想，因此既可以像基于密度的方法发现任 意形状的簇，又可以像基于网格的方法处理较大的多维数据集。
? 效率很高。
? STING 算法扫描数据库一次来计算单元的统计信息， 因此产生聚类的时间复杂度是o(n) ，其中n是对象的数 目。在层次结构建立后，查询处理时间是，这里g是最 低层网格单元的数目o(g) ，通常远小于n。
14
STING:统计信息网格
缺点如下：
? 如果粒度比较细，处理的代价会显著增加；但是，如果网 格结构最低层的粒度太粗，将会降低聚类分析的质量；
? 假设选择第一层作为查询过程的开始点(也可以选择包含少量单元网格的 其他层)并假设最底层的网格的属性price近似服从标准分布，高层网格 的price属性的分布可能是NONE。
[a,b] ? 假设houses的price在 的概率p，我们可以求得p置信区间(或者估 )[p 计其概率范围 1,p2],可以检查每个网格单元是否与给定查询相关
(p2*n>A*C*d% 成立?)，若相关，则标记该网格为relevant否则标记为 not-relevant .处理层次结构中的下一层。这个处理过程反复进行。直 到到达最底层 。最后返回满足查询要求的相关单元的区域。 查找结束 。
13
STING:统计信息网格
优点如下： ? 计算是独立于查询的； ? 有利于并行处理和增量更新；
基于网格的聚类方法
1
基于网格的聚类
? 基本思想是将每个属性的可能值分割成许多相邻 的区间，创建网格单元的集合（对于的讨论我们 假设属性值是序数的、区间的或者连续的）。
? 每个对象落入一个网格单元，网格单元对应的属 性区间包含该对象的值。
? 优点是它的处理速度很快，其处理时间独立于数 据对象的数目，只与量化空间中每一维的单元数 目有关。
查询语言（sql语言） ? SELECT REGION
FROM house-map
WHERE DENSITY∞) in [c, AND PRICE range [a, b] WITH percent [ d
AND AREA (A, +) AND LOCATION California
12
STING:统计信息网格
10
STING:统计信息网格
算法步骤： 1 从一个层次开始 2 对于这一层次的每个单元格，我们计算查询相关的属性值 3 从计算的属性值及其约束条件中，我们将每一个单元格标
注成相关或者不相关 4 如果这一层是底层，则转到步骤6，否则就行步骤5 5 我们由层次结构转到下一层依照步骤2进行计算 6 查询结果满足，转到步骤8，否则转到步骤7 7 恢复数据到相关的单元格进一步处理以得到满意结果，转