カメレオン（Chameleon）とは？動的モデリングを用いた階層型クラスタリングアルゴリズムの解説

カメレオン（Chameleon）は、動的モデリングを用いてクラスタ間の類似度を判定する階層型クラスタリングアルゴリズムです。ROCKやCUREといった既存の階層型クラスタリング手法が抱える弱点を克服するために開発されました。

ROCKおよびその関連手法は、クラスタ内の相互連結性（インターコネクティビティ）を重視する一方で、クラスタ間の近接性に関する情報を軽視していました。逆に、CUREおよびその関連手法はクラスタ間の近接性を考慮するものの、相互連結性を無視しています。

カメレオンでは、クラスタの類似度を「クラスタ内部のオブジェクト同士がどれだけ強く連結しているか」と「クラスタ同士の近さ」の両方に基づいて評価します。具体的には、相互連結性が高く、かつ互いに近くにある2つのクラスタが統合されます。

また、カメレオンは静的なユーザー指定モデルには依存せず、統合対象となるクラスタの内部的な特性に自動的に適応できる点も大きな特徴です。この統合プロセスにより、自然で均質なクラスタの発見が可能となり、類似度関数を定義できるあらゆる種類のデータに適用できます。

k近傍グラフによるスパースグラフの構築

カメレオンでは、k最近傍法（k-nearest-neighbor）のグラフ技術を用いてスパースグラフを作成します。このグラフにおいて、各頂点はデータオブジェクトを表し、あるオブジェクトがもう一方のオブジェクトにとって「最も類似したk個のオブジェクト」の中に含まれる場合、2つの頂点（オブジェクト）間にエッジ（辺）が張られます。各エッジには、オブジェクト間の類似度を反映した重みが割り当てられます。

サブクラスタへの分割と統合

カメレオンは、グラフ分割アルゴリズムを用いてk近傍グラフを多数の比較的小さなサブクラスタに分割します。その後、凝集型の階層的クラスタリングアルゴリズムを使用し、類似度に基づいてサブクラスタを繰り返し統合していきます。この際、最も類似性の高いサブクラスタのペアを特定するために、クラスタ間の相互連結性と近接性の両方が考慮されます。

動的な近傍の捉え方

k近傍グラフは、近傍という概念を動的に捉えます。すなわち、オブジェクトの近傍半径は、そのオブジェクトが存在する領域の密度によって決まります。密度の高い領域では近傍は狭く定義され、疎な領域ではより広く定義されます。

この仕組みにより、DBSCANのようにグローバル（データ全体で共通）な近傍を使用する密度ベースの手法と比較して、より自然なクラスタを得ることができます。さらに、領域の密度はエッジの重みとして記録されます。具体的には、密度の高い領域にあるエッジは、疎な領域のエッジよりも大きな重みを持つ傾向があります。

エッジカットの最小化

グラフ分割アルゴリズムは、k近傍グラフを分割する際に、エッジカット（切断されるエッジの重みの総和）を最小化するように機能します。つまり、クラスタCをサブクラスタC_iとC_jに分割する際、Cを二分することで切断されるエッジの重みが最小になるように分割が行われます。このエッジカットはEC(C_i, C_j)と表記され、クラスタC_iとC_jの間の絶対的な相互連結性を表します。