STINGグリッドベースのクラスタリングとは何ですか？

グリッドベースのクラスタリング手法は、多重解像度グリッドデータ構造を使用します。オブジェクト領域を有限数のセルに量子化し、グリッド構造を形成します。このグリッド構造に、クラスタリングのすべての操作が実装されます。この方法の利点は、処理時間が短いことです。これは、一般にデータオブジェクトの数に依存せず、量子化された空間の各次元の複数のセルのみに依存します。

グリッドベースのクラスタリングは、多重解像度グリッドデータ構造を使用し、高密度グリッドセルを使用してクラスターを形成します。 STING、wave cluster、CLIQUEなどの興味深い方法がいくつかあります。

スティング −統計情報グリッドアプローチ。空間領域は長方形のセルに分割されます。さまざまな解決方法に対応するさまざまなレベルのセルがあります。高レベルの各セルは、次に低いレベルの複数の小さなセルに分割されます。各セルの統計データは事前​​に計算されて保存され、クエリに答えることができます。高レベルのセルの仕様は、低レベルのセルの仕様から簡単に計算できます。

• カウント、平均、秒、最小、最大
• 分布のタイプ-正規、均一など

統計情報グリッドベースのアプローチ（STING）は、階層的アプローチに従って、空間領域を四分木に似た長方形のセルに分割します。空間データベースが1回スキャンされ、セルごとに統計パラメータが決定されます。 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;