二分K-Means（Bisecting K-Means）とは？仕組みとアルゴリズムをわかりやすく解説

二分K-Means法の概要

二分K-Means（Bisecting K-Means）は、基本的なK-Meansアルゴリズムをシンプルに発展させたクラスタリング手法です。その考え方は非常に直感的で、K個のクラスタを得るために、まず点集合全体を2つのクラスタに分割し、そのうちの1つを選んでさらに分割するという操作を、クラスタ数がK個に達するまで繰り返します。

K-Meansアルゴリズムの基本

標準的なK-Meansアルゴリズムは、入力パラメータとしてクラスタ数kを受け取り、n個のオブジェクトをk個のクラスタに分割します。このとき、クラスタ内の類似度（intracluster similarity）が高く、クラスタ間の類似度（intercluster similarity）が低くなるように分割を行います。クラスタの類似度は、クラスタ内のオブジェクトの平均値、すなわちクラスタの重心（セントロイド）や重心位置に基づいて評価されます。

平均値の初期値は任意に設定できます。ランダムに選ぶこともあれば、最初のk個の入力データの値をそのまま利用することもあります。収束判定には一般的に二乗誤差（SSE：Sum of Squared Errors）が用いられますが、必ずしもこれに限定されるわけではありません。例えば、固定回数の反復を終了条件とする方法もあります。また、収束しない場合でも確実に処理を停止できるよう、最大反復回数を設定することも可能です。

二分K-Meansのアルゴリズム手順

1. すべての点を1つのクラスタとして含むクラスタリストを初期化する。
2. 以下の手順を繰り返す：
   • クラスタリストから1つのクラスタを取り出す。
   • 選択したクラスタに対して複数回の「試行的」二分割を実施する。
     • i = 1から試行回数まで繰り返す：
     • 基本K-Meansを用いて選択したクラスタを二分割する。
   • 二分割結果の中から、SSE（二乗誤差和）の合計が最小となる2つのクラスタを選択する。
   • 選択した2つのクラスタをクラスタリストに追加する。
3. クラスタリストにK個のクラスタが含まれるまで上記を繰り返す。

分割対象クラスタの選び方

どのクラスタを分割するかを選択する方法はいくつかあります。各ステップで最大サイズのクラスタを選ぶ方法、SSEが最も大きいクラスタを選ぶ方法、あるいはサイズとSSEの両方を組み合わせた基準を用いる方法などがあります。選択基準によって、最終的に得られるクラスタリング結果は異なる点に注意が必要です。

結果の精緻化について

得られたクラスタの重心を初期重心として基本K-Meansアルゴリズムを再度適用することで、最終的なクラスタリング結果をさらに改善できます。これは重要なポイントです。K-MeansアルゴリズムはSSEに関して局所最小となるクラスタリングを見つけることが保証されていますが、二分K-MeansではK-Meansを「局所的」に、つまり個々のクラスタの二分割にのみ使用しています。そのため、最終的に得られるクラスタ集合は、全体のSSEに関する局所最小になるとは限りません。

階層的クラスタリングへの応用

さらに、K-Meansがクラスタを二分割していく過程で生成される一連のクラスタリング結果を記録しておくことで、二分K-Meansを階層的クラスタリング（hierarchical clustering）として活用することもできます。これにより、データの階層構造を把握しながら柔軟なクラスタ分析を行うことが可能になります。