CLIQUEとは？高次元データクラスタリングアルゴリズムの仕組みと特徴

CLIQUEアルゴリズムの概要

CLIQUE（CLustering In QUEst）は、高次元空間における次元成長型部分空間クラスタリング（dimension-growth subspace clustering）向けに提案された最初のアルゴリズムです。次元成長型部分空間クラスタリングでは、クラスタリング処理が1次元の部分空間から開始され、より高次元の部分空間へと段階的に拡張されていきます。

CLIQUEは各次元をグリッド構造のように分割し、セルに含まれるデータポイントの数に基づいて、そのセルが「密（dense）」であるかどうかを判定します。このため、CLIQUEは密度ベースのクラスタリング手法とグリッドベースのクラスタリング手法を統合したアプローチと見なすことができます。

CLIQUEの基本的な考え方

• 多次元データポイントの大規模な集合が与えられた場合、データ空間は通常、データポイントによって一様には占有されていません。CLIQUEのクラスタリングは、空間（またはユニット）内の疎な領域と「混み合った」領域を識別することで、データセット全体の分布パターンを発見します。

• ユニットに含まれる全データポイントの割合が、入力モデルパラメータとして指定された閾値を超える場合、そのユニットは「密」とみなされます。CLIQUEでは、クラスタは相互に連結された密なユニットの最大集合として表現されます。

CLIQUEの2段階の処理プロセス

CLIQUEは、以下の2つのステップで多次元クラスタリングを実行します。

第1ステップ：密なユニットの特定

まず、CLIQUEはd次元のデータ空間を互いに重ならない矩形ユニットに分割し、その中から密なユニットを特定します。この処理は、各次元について1次元ずつ実行されます。

候補探索空間の絞り込みには、相関ルールマイニングで用いられるApriori特性が活用されます。一般に、この特性は探索空間内の項目に関する事前知識を利用することで、探索対象の一部を刈り込む（pruning）ことを可能にします。

CLIQUEにおけるApriori特性は次のとおりです。あるk次元ユニットが密であるならば、その(k−1)次元空間への射影もまた密である。つまり、あるk次元の候補密ユニットについて、その(k−1)次元の射影ユニットを検査した際に密でないものが見つかった場合、そのk次元ユニットも密ではないと判断できます。

この性質により、(k−1)次元空間で発見された密なユニットから、k次元空間における候補密ユニットを生成することが可能になります。その結果、実際に探索される空間は元の空間よりもはるかに小さくなります。最終的に、残った密なユニットを検査してクラスタを決定します。

第2ステップ：クラスタの最小記述の生成

次に、CLIQUEは各クラスタに対して最小限の記述を生成します。具体的には、各クラスタについて、連結された密なユニット群を覆う最大領域を決定し、さらに各クラスタの最小カバー（論理的な記述）を求めます。

CLIQUEの特徴と利点

CLIQUEは、高密度クラスタが存在する最大次元数の部分空間を必ず発見できるという強みを持っています。また、入力オブジェクトの順序に影響されず、特定の正規分布といったデータ分布を仮定する必要もありません。入力サイズに対して線形にスケールし、データの次元数が増加しても優れた拡張性を発揮します。