CUREクラスタリングアルゴリズムとは？仕組みと特徴をわかりやすく解説

CURE（Clustering Using Representatives）とは

CUREは「Clustering Using Representatives（代表点を用いたクラスタリング）」の略称で、大量のデータセット、外れ値、非球状の形状や不均一なサイズを持つクラスタにも対応できるクラスタリングアルゴリズムです。複数の手法を組み合わせることで、従来の手法が苦手とする複雑なデータ構造にも柔軟に対応します。

CUREの最大の特徴は、クラスタを定義する際に、そのクラスタに属する複数の「代表点」を使用する点にあります。

代表点の選択方法

代表点は、クラスタの幾何学的な形状や構造を捉える役割を担います。まず最初の代表点として、クラスタの中心から最も遠い点が選ばれます。その後の代表点は、すでに選択されたすべての点からできるだけ離れた位置にある点が順に選ばれていきます。

この方法により、代表点はクラスタ全体にまんべんなく分散して配置されます。選択する代表点の数はパラメータとして設定できますが、実験の結果、10以上の値であれば良好な結果が得られることが分かっています。

収縮係数αによる外れ値への対応

代表点が選択された後、それらは収縮係数α（アルファ）に基づいてクラスタの中心方向へ縮小されます。この処理により、外れ値の影響を緩和できます。外れ値は一般に中心から遠い位置にあるため、収縮の影響をより大きく受けます。

例えば、中心から10単位の距離にある代表点は3単位移動し（α = 0.7の場合）、中心から1単位の距離にある代表点は0.3単位しか移動しません。

外れ値の除去プロセス

CUREは階層的クラスタリングのプロセスが持つ特性を活かし、クラスタリングの過程で2段階に分けて外れ値を除去します。

第一の段階では、クラスタの成長が遅い場合に外れ値を検出します。クラスタの成長が遅いということは、そのクラスタの大部分が外れ値で構成されている可能性が高いからです。定義上、外れ値は他の点から離れた位置にあり、他の点とマージされる頻度が低いためです。

CUREでは、この第一段階の外れ値除去は、一般にクラスタ数が初期の点数の1/3になった時点で実行されます。第二段階の外れ値除去は、クラスタ数が目標とするクラスタ数K程度になった時点で実行され、この時点で小さなクラスタが除去されます。

大規模データへの高速化手法

CUREの最悪計算量はO(m²log m)であるため、大規模なデータセットに直接適用することは困難です。そこでCUREは、クラスタリング処理を高速化するために2つの手法を採用しています。

第一の手法は、データから無作為にサンプルを抽出し、そのサンプルデータに対して階層的クラスタリングを実行するものです。その後、最終パスとして、データセット内の残りの各点を、最も近い代表点を持つクラスタに割り当てます。

場合によっては、クラスタリングに必要なサンプルサイズが大きくなりすぎ、さらなる手法が必要になることがあります。この場合、CUREはサンプルデータを複数のパーティションに分割し、各パーティション内の点をクラスタリングします。この事前クラスタリングの後、中間クラスタに対するクラスタリングが行われ、最終的にデータセット内の各点がいずれかのクラスタに割り当てられます。