什么是基于网格的 STING 聚类？

基于网格的聚类方法使用多分辨率网格数据结构。它将对象区域量化为有限数量的单元格，这些单元格形成一个网格结构，所有聚类操作都在该结构上实现。该方法的优点是其快速的处理时间，通常与数据对象的数量无关，而仅取决于量化空间中每个维度中的多个单元格。

基于网格的聚类使用多分辨率网格数据结构，并使用密集的网格单元格来形成聚类。有一些有趣的方法，例如 STING、wave cluster 和 CLIQUE。

STING - 一种统计信息网格方法。空间区域被分割成矩形单元格。存在对应于不同分辨率方法的各个级别的单元格。每个高级别的单元格在下一级较低级别中被分成多个较小的单元格。每个单元格的统计数据预先计算并存储，并且可以回答查询。高级别单元格的规范可以简单地从低级别单元格的规范计算出来

  • 计数、均值、标准差、最小值、最大值
  • 分布类型 - 正态分布、均匀分布等。

基于统计信息网格的方法 (STING) 采用分层方法将空间区域划分为矩形单元格，类似于四叉树。空间数据库被扫描一次，并为每个单元格确定统计参数。STING 技术可以被视为一种分层方法。第一步是进行分层描述。创建的树将区域分别划分为象限。

创建树的过程如下面的算法所示。空间中的每个单元格对应于树中的一个节点，并用属性无关（计数）数据和属性相关（均值、标准差、最小值、最大值分布）数据来描述。由于树中节点的数量小于数据库中项目的数量，因此 STING BUILD 的复杂度为 O(n)。

算法

输入

D // Data to be placed in the hierarchical structure
k // Number of desired cells at the lowest level

输出

T // Tree
STING BUILD algorithm
// Create an empty tree from top-down
   T = root node with data values initialized; // Initially only root node
   i = 1;
   repeat
      for each node in level i do
      create 4 children nodes with initial values;
   i = i +1;
   until 4i = k;
   // Populate tree from bottom-up for each item in D do
   determine leaf node j related to the position of D;
   update values of j based on attribute values in item;
   i := log4(k);
   repeat
   i: = i - 1;
   for each node j in level i do
update values of j based on attribute values in its 4 children;
until i = 1;

更新于: 2022年2月15日

4K+ 浏览量

开启您的 职业生涯

通过完成课程获得认证

开始学习
广告