空間データマイニングにおけるクラスタリング手法とは？PAM・CLARA・CLARANSを徹底解説

クラスタ分析（クラスター分析）は統計学の一分野であり、長年にわたり幅広く研究されてきました。この手法を用いる最大の利点は、概念階層のような背景知識を必要とせず、データそのものから興味深い構造やクラスタを直接発見できる点にあります。

しかし、統計学分野で伝統的に使われてきたクラスタリングアルゴリズム（PAMやCLARAなど）は、計算量の観点から非効率であることが指摘されています。こうした効率性の課題に対応するため、CLARANS（Clustering Large Applications based upon Randomized Search）と呼ばれる新しいアルゴリズムが開発されました。

本記事では、空間データマイニングにおける代表的な3つのクラスタリング手法「PAM」「CLARA」「CLARANS」について、それぞれの仕組みと特徴を詳しく解説します。

PAM（Partitioning around Medoids）とは

PAMは、n個のオブジェクトが存在する状況で、まず各クラスタの代表オブジェクトを見つけることによってk個のクラスタを構築する手法です。この代表オブジェクトは、クラスタ内で中心に位置する点であり、「メドイド（medoid）」と呼ばれます。

k個のメドイドを選択した後、アルゴリズムは「一方がメドイド、他方が非メドイド」となるすべての実現可能なオブジェクトのペアを分析しながら、より良いメドイドの組み合わせを繰り返し探索します。各組み合わせに対してクラスタリング品質の尺度が計算され、改善が見込める選択が次の反復のメドイドとして採用されます。

1回の反復にかかるコストは O(k(n−k)²) です。そのため、nやkが大きくなると計算コストが急増し、大規模データには不向きという弱点があります。

CLARA（Clustering Large Applications）とは

CLARAとPAMの大きな違いは、CLARAがサンプリングに基づく点にあります。実際のデータのごく一部だけを標本として抽出し、そのサンプルに対してPAMを適用してメドイドを選出します。

この考え方の根拠は、「サンプルが十分にランダムに選ばれていれば、それはデータセット全体を正しく代表しており、全体から選んだ場合とほぼ同等のメドイドが得られる」というものです。

CLARAは複数のサンプルを抽出し、その中から最も良いクラスタリング結果を出力します。これによりPAMよりも大規模なデータセットを扱えるようになり、各反復の計算量は O(kS²+k(n−k))（Sはサンプルサイズ）まで抑えられます。

CLARANS（Clustering Large Applications based upon RANdomized Search）とは

CLARANSは、PAMとCLARAの両方の利点を組み合わせたアルゴリズムです。データセットの部分集合のみを探索対象としつつ、特定の時点で固定のサンプルに縛られない柔軟な設計になっています。

CLARAは検索の各段階で常に同じサンプルを使い続けますが、CLARANSは検索の各段階においてランダム性を持たせながら新たなサンプルを抽出する点が異なります。

CLARANSにおけるクラスタリング処理は、グラフ探索問題として捉えることができます。グラフの各ノードは「k個のメドイドの集合」という可能な解を表し、現在のクラスタリングからメドイドを1つ置き換えて得られるクラスタリングは、現在の解の「近傍（neighbor）」と定義されます。

まとめ

空間データマイニングのクラスタリングでは、精度と計算効率のトレードオフが重要なポイントになります。PAMは高精度だが計算コストが高く、CLARAはサンプリングにより高速化を実現、そしてCLARANSはランダム化探索によって大規模データへの対応力をさらに高めた手法といえます。