STINGグリッドベースクラスタリングとは？仕組みと構築アルゴリズムを徹底解説

グリッドベースクラスタリングの概要

グリッドベースのクラスタリング手法は、マルチ解像度（マルチレゾリューション）のグリッドデータ構造を活用します。この手法では、対象となる領域を有限個のセルに量子化し、それらのセルがグリッド構造を形成します。クラスタリングに関するすべての処理は、このグリッド構造上で実行されます。

この手法の最大の利点は処理速度の速さです。処理時間はデータオブジェクトの数にはほとんど依存せず、量子化された空間における各次元のセル数のみに依存します。そのため、大規模なデータセットに対しても効率的に動作します。

グリッドベースクラスタリングでは、マルチ解像度のグリッドデータ構造を用い、密度の高いグリッドセルをクラスタとして形成します。代表的な手法として、STING、WaveCluster、CLIQUEなどが挙げられます。

STING（Statistical Information Grid）とは

STINGは「Statistical Information Grid（統計情報グリッド）」アプローチと呼ばれる手法です。空間領域を長方形のセルに分割し、異なる解像度に対応した複数のレベルのセルを持ちます。上位レベルの各セルは、次の下位レベルで複数のより小さなセルに分割されます。

各セルの統計データは事前に計算・保存されており、クエリに対して即座に回答できます。上位レベルのセルの統計情報は、下位レベルのセルの統計情報から簡単に算出できます。保存される統計情報には以下が含まれます。

• count（個数）、mean（平均）、s（標準偏差）、min（最小値）、max（最大値）
• 分布の種類（正規分布、一様分布など）

STINGの階層構造

STINGは、クアッドツリー（四分木）と同様の階層的アプローチに従い、空間領域を長方形のセルへと分割します。空間データベースを一度だけスキャンし、各セルの統計パラメータを決定します。

STINGは階層型アプローチの一種と見なすことができます。最初のステップは階層記述の作成です。作成されたツリーは、領域を象限ごとに再帰的に分割していきます。

STING構築アルゴリズム

ツリー作成のプロセスを以下のアルゴリズムに示します。空間内の各セルはツリーのノードに対応し、属性非依存のデータ（count）と属性依存のデータ（平均、標準偏差、最小値、最大値、分布）の両方で記述されます。

ツリーのノード数はデータベース内のアイテム数より少ないため、STING BUILDの計算量はO(n)となります。

入力

D // 階層構造に配置するデータ
k // 最下位レベルで必要なセルの数

出力

T // ツリー

STING BUILDアルゴリズム

// 上から下へ空のツリーを作成
T = データ値を初期化したルートノード; // 初期状態ではルートノードのみ
i = 1;
repeat
　　for each node in level i do
　　　　初期値を持つ4つの子ノードを作成;
　　i = i + 1;
until 4^i = k;

// 下から上へツリーを構築
for each item in D do
　　Dの位置に対応するリーフノードjを決定;
　　アイテムの属性値に基づいてjの値を更新;
　　i := log4(k);
　　repeat
　　　　i := i - 1;
　　　　for each node j in level i do
　　　　　　4つの子の属性値に基づいてjの値を更新;
　　until i = 1;

STINGの特徴と利点

STINGには以下のような特徴があります。

• 高速なクエリ処理： 各セルの統計情報が事前計算されているため、クエリへの応答が非常に速くなります。
• 増分的な更新： ボトムアップ方式でグリッドを更新できるため、新しいデータの挿入にも柔軟に対応できます。
• 並列処理との親和性： セルごとに独立して統計情報を計算できるため、並列化が容易です。
• 注意点： グリッド構造に依存するため、クラスタの境界精度はセルの解像度（粒度）に左右されるという限界があります。