PROCLUSとは？射影クラスタリングの仕組みと3つのフェーズを解説

PROCLUS（Projected Clustering／射影クラスタリング）は、代表的な次元削減型サブスペースクラスタリング手法の一つです。個々の低次元空間から探索を始めるのではなく、まず高次元属性空間におけるクラスタの大まかな近似を見つけるところから処理を開始するのが特徴です。

重み付けによる反復的なクラスタ更新

各次元にはクラスタごとに重みが割り当てられ、更新された重みは次の反復でクラスタを再構築するために使用されます。この仕組みにより、適切な次元数を持つすべてのサブスペース内の密な領域を効率的に探索でき、低い次元の射影空間で大量の重複クラスタが生成されるのを防ぐことができます。

CLARANSを拡張したメドイド選択と独自の距離尺度

PROCLUSは、CLARANSで用いられるのと同様の山登り法（ヒルクライミング）によって最適なメドイド（代表点）のグループを発見します。ただし、射影クラスタリングに対応できるよう一般化されている点が異なります。

また、「マンハッタン・セグメンタル距離」と呼ばれる距離尺度を採用しています。これは、関連性のある次元の集合上で計算されるマンハッタン距離として定義されるものです。

PROCLUSアルゴリズムの3つのフェーズ

PROCLUSアルゴリズムは、「初期化」「反復」「クラスタ精緻化」の3つのフェーズで構成されています。

1. 初期化フェーズ

初期化フェーズでは、貪欲法（グリーディアルゴリズム）を用いて、互いに十分に離れた初期メドイドの集合を選択します。これにより、選択された集合の中に、各クラスタを代表するオブジェクトが少なくとも1つ含まれることが保証されます。

具体的には、生成すべきクラスタ数に比例したサイズでデータポイントの無作為標本を選択し、その後、貪欲法を適用してさらに小さな最終部分集合を求め、次のフェーズへ引き渡します。

2. 反復フェーズ

反復フェーズでは、削減されたメドイド集合からk個のメドイドを無作為に選択します。そして、クラスタリングの品質が向上する場合には、「悪い」メドイドを新たに無作為に選んだメドイドで置き換えます。

各メドイドに対しては、統計的な期待値と比較して平均距離が小さい次元の集合が選ばれます。メドイドに関連付けられる次元の総数は k×l となります。ここで l は、クラスタ部分空間の平均次元数を指定する入力パラメータです。

3. クラスタ精緻化フェーズ

精緻化フェーズでは、発見されたクラスタに基づいて各メドイドの新しい次元集合を再計算し、ポイントをメドイドに再割り当てするとともに、外れ値（アウトライア）を除去します。PROCLUSは、高次元クラスタの発見において有効かつスケーラブルな手法であることが実証されています。

CLIQUEとの違い

多数の重複クラスタを出力するCLIQUEとは異なり、PROCLUSはポイントの非重複な分割を発見します。こうして得られたクラスタは、高次元データへの理解を深め、その後のさまざまな分析を支援します。

一方、CLIQUEは高密度クラスタが存在しうる最大次元数のサブスペースを必ず発見します。入力オブジェクトの順序に結果が左右されず、特定の正規データ分布を仮定しないという特徴もあります。入力サイズに対して線形にスケールし、データの次元数が増加しても優れたスケーラビリティを発揮します。