STING（統計情報グリッド）とは？仕組みと特徴をわかりやすく解説

STING（統計情報グリッド）とは

STINGは「Statistical Information Grid（統計情報グリッド）」の略称で、空間データマイニングで用いられるグリッドベースのマルチ解像度クラスタリング手法です。この手法では、対象となる空間領域を矩形のセルに分割し、そのセル群を階層構造として管理します。上位レベルの各セルは、次の下位レベルにおける複数のセルへと細分化されていきます。

事前計算・保存される統計情報

各グリッドセル内の属性に関する統計データ（平均値、最大値、最小値など）は、あらかじめ計算されて保存されています。上位レベルのセルの統計パラメータは、下位レベルのセルのパラメータから容易に算出できる点が大きな特徴です。

これらのパラメータには、以下のようなものが含まれます。

• 属性非依存パラメータ：count（件数）
• 属性依存パラメータ：mean（平均値）、stdev（標準偏差）、min（最小値）、max（最大値）
• 分布タイプ：セル内の属性値が従う分布の種類（正規分布、一様分布、指数分布、分布不明の場合はnone）

パラメータの算出方法

レコードがデータベースにロードされる際、最下位レベルのセルに対するcount、mean、stdev、min、maxといったパラメータは、レコードから直接計算されます。分布タイプについては、事前に分布が既知であればユーザーが指定でき、未知の場合はχ²検定などの仮説検定によって求めることも可能です。

より上位レベルのセルの分布タイプは、対応する下位レベルのセル群の分布タイプの多数決に基づき、しきい値フィルタリング処理と組み合わせて評価されます。下位セル間で分布が一致せず、しきい値テストに合格しない場合は、上位セルの分布タイプは「none」に設定されます。

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

グリッドベースのクラスタリング手法は、マルチ解像度のグリッドデータ構造を使用します。オブジェクト空間を複数のセルに量子化してグリッド構造を形成し、その上でクラスタリングのための操作を実行します。この手法の最大の利点は処理速度の速さであり、その処理時間は一般にデータオブジェクトの数には依存せず、量子化された空間の各次元におけるセル数のみに依存する点です。

グリッドベースアプローチの代表例としては、以下のような手法が挙げられます。

• STING：グリッドセルに格納された統計データを活用する手法
• WaveCluster：ウェーブレット変換を用いてオブジェクトをクラスタリングする手法
• CLIQUE：高次元データ空間向けに、グリッドと密度を組み合わせたクラスタリング手法

STINGの利点

このアプローチの大きな強みは、クエリに依存しない設計である点です。統計情報はクエリとは独立に存在するため、各グリッドセル内のデータの汎用的な記述として機能し、幅広い種類のクエリへの回答をサポートできます。

さらに、計算量はO(K)であり、ここでKは最下位レベルのグリッドセルの数を表します。通常、Kはオブジェクト総数Nよりもはるかに小さい（K << N）ため、大規模データに対しても非常に効率的な処理が実現できます。