大規模データセットにおけるk-medoidsアルゴリズムの効率性とは？PAM・CLARA・CLARANSの違いを徹底解説

PAM（Partitioning Around Medoids）のような古典的なk-medoids分割アルゴリズムは、小規模なデータセットに対しては効率的に動作しますが、巨大なデータセットにはうまくスケールしないという課題があります。より大きなデータセットを扱うためには、CLARA（Clustering Large Applications）と呼ばれるサンプリングベースの手法を利用することができます。

CLARA：サンプリングによるスケーラビリティの改善

CLARAの背後にある考え方は次のとおりです。サンプルが十分にランダムな方法で選択されていれば、そのサンプルは元のデータセットを忠実に代表すると考えられます。したがって、サンプルから選ばれた代表オブジェクト（medoids）は、全データセットから選んだ場合とほぼ同等のものになると期待できます。

具体的には、CLARAはデータセットから複数のサンプルを抽出し、それぞれのサンプルに対してPAMを適用し、その中で最も優れたクラスタリング結果を出力として返します。

ただし、CLARAの性能はサンプルサイズに大きく依存します。PAMが与えられたデータセット全体の中から最適なk個のmedoidsを探索するのに対し、CLARAは選択されたサンプルの中からしか探索できない点が本質的な違いです。

CLARANS：ランダム化探索による新たなアプローチ

この制約を克服するために提案されたのが、CLARANS（Clustering Large Applications based upon RANdomized Search）と呼ばれるk-medoids型アルゴリズムです。CLARANSはサンプリング手法とPAMを組み合わせたアプローチを採用しています。CLARAが探索の各段階で固定されたサンプルを使用するのに対し、CLARANSは探索の各段階でランダム性を持ったサンプルを抽出する点が特徴です。

グラフ探索としてのクラスタリング

クラスタリングの手順は、グラフ上の探索問題として捉えることができます。ここで、各ノードは潜在的な解、すなわちk個のmedoidsの集合を表します。2つのノードは、それらのmedoidsの集合が1つのオブジェクトのみ異なる場合に「隣接」している（グラフ内でアークによって結ばれている）とみなされます。

各ノードには、各オブジェクトとその所属クラスタのmedoidとの間の非類似度の合計として定義されるコストを割り当てることができます。

各ステップにおいて、PAMは最小コストの解を求めるために、現在のノードのすべての隣接ノードを調べます。そして、現在のノードはコスト低下が最も大きい隣接ノードへと置き換えられていきます。一方、CLARAはデータセット全体ではなくサンプルに対して処理を行うため、調べる隣接ノードの数が少なく、探索範囲は初期のグラフよりも小さな部分グラフに限定されます。

CLARANSの実験的評価と計算量

実験的な評価では、CLARANSはPAMおよびCLARAの両方よりも高い効率性を示すことが確認されています。さらに、CLARANSはシルエット係数――あるオブジェクトがそのクラスタにどの程度実際に適合しているかを定量化する指標――を用いることで、最も「自然な」クラスタ数を発見することにも活用できます。加えて、外れ値（outliers）の検出にも対応しています。

CLARANSの計算量はO(n²)であり、ここでnはオブジェクトの総数を表します。また、そのクラスタリング品質は採用されるサンプリング手法に依存する点に注意が必要です。さらに、ディスク上に存在するデータオブジェクトを扱う際のCLARANSの性能は、R*-treeなどの空間データ構造を活用する手法を組み込むことで、一層向上させることが可能です。