5.4.4.1　STING：统计信息网格

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

高层单元的统计参数可以很容易地从低层单元的计算得到。这些统计参数包括：属性无关的参数count（总数）；属性相关的参数m（平均值），stdev（标准偏差），min（最小值），max（最大值），以及该单元中属性值遵循的分布类型。当数据被装载进数据库，底层单元的参数count、m、stdev、min和max直接进行计算。如果分布的类型事先知道，统计参数可以由用户指定，也可以通过假设检验来获得。一个高层单元的分布类型可以基于它对应的低层单元多数的分布类型，用一个阈值过滤过程来计算。如果低层单元的分布彼此不同，阈值检验失败，高层单元的分布类型被置为none（无）。

统计参数的使用可以按照自顶向下的基于网格的方法。首先，在层次结构中选定一层作为查询处理的开始点。通常，该层包含少量的单元。对当前层次的每个单元，我们计算置信度区间（或者估算其概率范围），用以反映该单元与给定查询的关联程度。不相关的单元就不再考虑。低一层的处理就只检查剩余的相关单元。这个处理过程反复进行，一直达到底层。此时，如果查询要求被满足，那么返回相关单元的区域。否则，检索和进一步的处理落在相关单元中的数据，直到它们满足查询要求。

5.4.4.2　STING聚类的层次结构：

通过图5.8，我们可以清晰的理解，STING的层次结构，上一层与下一层的关系。

5.4.4.3　STING算法步骤

算法：STING算法。

输入：数据集，分布检验阈值。

输出：带有集群标签的数据对象。

步骤

（1）从一个层次开始。

（2）对于这一个层次的每个单元格，我们计算查询相关的属性值。

图5.8　STING聚类的层次结构

（3）从计算的属性值以及约束条件下，我们将每一个单元格标记成相关或者不想关。（不相关的单元格不再考虑，下一个较低层的处理就只检查剩余的相关单元）(www.daowen.com)

（4）如果这一层是底层，那么转（6），否则转（5）。

（5）我们由层次结构转到下一层，依照步骤2进行。

（6）查询结果得到满足，转到步骤8，否则（7）。

（7）恢复数据到相关的单元格进一步处理以得到满意的结果，转到步骤（8）。

（8）停止。

5.4.4.4　STING算法的性质及优势和缺点

STING聚类算法性质。

如果粒度趋向于0（即朝向非常底层的数据），则聚类结果趋向于DBSCAN聚类结果。即使用计数count和大小信息，使用STING可以近似地识别稠密的簇。

STING算法的优点：

（1）基于网格的计算是独立于查询的，因为存储在每个单元的统计信息提供了单元中数据汇总信息，不依赖于查询。

（2）网格结构有利于增量更新和并行处理。

（3）效率高。STING扫描数据库一次计算单元的统计信息，因此产生聚类的时间复杂度为o（n），在层次结构建立之后，查询处理时间通常远远小于n。

STING算法的缺点：

（1）由于STING采用了一种多分辨率的方法来进行聚类分析，因此STING的聚类质量取决于网格结构的最底层的粒度。如果最底层的粒度很细，则处理的代价会显著增加。然而如果粒度太粗，聚类质量难以得到保证。

（2）STING在构建一个父亲单元时没有考虑到子女单元和其他相邻单元之间的联系。所有的簇边界不是水平的，就是竖直的，没有斜的分界线，降低了聚类质量。