クラスタリングを勉強してみる（6） grid-based clustering

1. 概要

空間インデックス構造（spatial index structures）の特性をクラスタリングする手法を grid-based clustering と言います。

2. CLIQUE

下図のように、空間を間隔 \xi で格子状に分割し、それぞれをユニットと定義します。また、ユニット中の対象の密度がしきい値 \tau より大きなものを "密である" と定義します。

f:id:somathor:20130423173540j:plain

軸に平行な超矩形領域を考え、それらの交わりを選言標準形で表します。
例えば、第 i 属性を A_i と記すと、

({({4}\le{A_1}\lt{8})\cap({2}\le{A_2}\lt{5})})\cup({({4}\le{A_3}\lt{6})\cap({4}\le{A_4}\lt{8})})


のように領域を表します。領域中のユニットが全て密であり、さらに、この領域が極大である場合、この領域をクラスターとします。

上図の左の2次元の空間を考えると、どのユニットも少数の対象しか含んでいないため、この2次元空間中ではクラスタは存在しません。
しかし、属性 A_2 を無視し、属性 A_1 へ射影した部分空間（図の右）を考えた場合、密な領域 C' や D' を見出すことができます。
CLIQUE は、このような任意の部分空間中のクラスタを発見することができます。

2-1. アルゴリズム

効率的な探索を行うために、Apriori アルゴリズムの d 次元空間中のクラスターは、その任意の d-1 次元部分空間でもクラスタであるという性質を利用します。
CLIQUE のアルゴリズムは、1次元空間での密なユニットを検出してクラスターを見つけ、次元数を一つ増やしてはクラスターを検出する手続きを繰り返します。

2-2. 計算量

\tilde{d} を密なユニットが存在する最も高い次元、K を定数とすると、計算量は以下のようになります。

O(K^{\tilde{d}} + N\tilde{d})

ただし、\tilde{d} に対して指数オーダーであるものの、実際には、\tilde{d} が大きくなることは稀です。

2-3. Pros.

  • データの入力の順序が結果に影響しにくい
  • データ分布を推測する必要がない
  • データの次元が増えた時に、良い拡張性を示す

2-4. Cons.

  • データ集合をユニットに分割するという手法を使用することで、過程が単純になる代わりに、あまり良い分類結果が得られない