グリッドベースクラスタリングとは？STINGなどの代表的な手法を解説

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

グリッドベース（格子ベース）のクラスタリング手法は、マルチレゾリューション（多分解能）のグリッドデータ構造を利用するアプローチです。対象となる領域を有限個のセルに量子化し、これらのセルが形成するグリッド構造上で、クラスタリングに関するすべての操作を実行します。

この手法の最大のメリットは処理速度の速さです。その処理時間は一般的にデータオブジェクトの数には依存せず、量子化された空間における各次元ごとのセル数のみに依存します。そのため、大規模データセットに対しても安定した高いパフォーマンスを発揮します。

代表的なグリッドベース手法の例

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

STING：マルチレゾリューション型のグリッドベース手法

STINGは、空間領域を長方形のセルに分割して扱う、グリッドベースのマルチレゾリューションクラスタリング手法です。複数の解像度レベルに対応した長方形セルの階層構造を持っており、上位レベルの各セルが分割されることで、次の下位レベルの複数のセルが形成されます。各グリッドセル内の属性に関する統計データ（平均値・最大値・最小値など）は事前に計算され、保存されています。

統計パラメータの種類

上位レベルのセルの統計パラメータは、下位レベルのセルのパラメータから容易に算出することができます。これらのパラメータには以下が含まれます。

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

パラメータの計算方法と分布タイプの判定

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

上位レベルのセルの分布タイプは、対応する下位レベルのセル群の分布タイプの多数決に基づいて算出され、閾値フィルタリング処理と組み合わせて判定されます。下位セル間で分布タイプが一致せず、閾値テストを満たさない場合には、上位セルの分布タイプはnoneに設定されます。

トップダウン型クエリ処理への活用

こうした統計パラメータは、トップダウンのグリッドベースアプローチにおいて以下のように活用されます。まず、階層構造の中からクエリ応答処理を開始するレイヤーを決定します。このレイヤーは通常、少数のセルで構成されています。続いて、現在のレイヤー内の各セルについて、与えられたクエリに対するそのセルの関連度を反映した信頼区間（確率の推定範囲）を計算します。この仕組みにより、必要な精度に応じて効率的にクエリ処理を行うことができます。