froglog

プログラミングや統計の話など

クラスタリング結果の評価の尺度基準

このエントリについて

クラスタリングの結果を定量評価するときの基準を数年に1回ぐらい調べてる気がするのと、日本語であまりまとまった情報を見ない気がしたので挙げてみます。今回挙げるのはハード(クリスプ)クラスタリングについての指標です。後で追加するかも。

クラスタ内距離二乗和

という呼び方が正しいのかどうかわかりませんが、k-means 法の場合はこの値を繰り返し処理の結果、極小化するようになっており*1、重要な指標となります。 クラスタ内の凝集性を表現します。

\( P_k = \sum_{i=1}^k \sum_{x \in C_{i} } \left( d(x, c_i) \right) ^2 \)

\( k \): クラスタ

\( C_i \): i番目のクラスタ

\( x \): クラスタのメンバー

\( c_i \): i番目のクラスタのセントロイド

Pseudo F

Calinski and Harabasz, 1974*2 によるクラスタ間分散とクラスタ内分散の比からなる指標です。 クラスタ内距離二乗和がクラスタの凝集性のみを見ているのに対し、Pseudo F では複数のクラスタの離散性も考慮しています。 クラスタ同士は疎、かつクラスタ内は密になっている場合を良しとます。

\( Pseudo F = \frac{(T - W_k) / (k - 1)}{W_k / (n - k)} \)

\( T \): 全サンプルの距離二乗和

\( W_k \): クラスタ内距離二乗和

\( k \): クラスタ

\( n \): 全サンプル数

分子がクラスタ間分散、分母がクラスタ内分散を表します。

CCC (Cubic Clustering Criterion)

SAS による指標。*3

データの分布が均一であればクラスタリングの結果は同じ大きさの超球状のクラスタになると想定し、そこからどれだけ離れているかで評価します。 つまりデータ分布の疎密によりクラスタ結果は現実には同じ大きさの球にはならないため、そこから離れている程良いという考えのようです。(正直あまり理解できておりません…詳しくはリンク先を参照)

\( CCC = \ln \left[ \frac{1 - E(R ^ 2)}{1 - R ^ 2} \right] \times K \)

\( E(R ^ 2) \): \( R ^ 2 \)の期待値

\( R ^ 2 \): \( R ^ 2 \)(全サンプル分散およびクラスタ内分散の比??)の観測値

\( K \): variance stabilizing transformation

※サンプルベクトルを構成する次元間に強い相関あると正しく機能しないという記述もあります。

Dunn’s Index

Dunn, 1973 による指標。*4

これも Pseudo F と同じでクラスタ内の凝集性とクラスタ間の離散性の指標ですが、凝集性および離散性の捉え方が違います。 Dunn's Index ではクラスタ内の任意のサンプル間の距離により両者を定義します。

\( Dunn's Index = \min_{1 \leq i \leq k} \left \{ \min_{1 \leq j \leq k, j \neq i} \frac{ \delta (C_i, C_j)}{\max_{1 \leq l \leq k} \Delta (C_l) } \right \} \)

\( \delta (C_i, C_j) \): クラスタ\( i \)とクラスタ\( j \)の距離。2クラスタのサンプル間の最小距離で定義される

\( \Delta (C_i) \): クラスタ\( i \)の直径。クラスタ内の2サンプルの最長距離で定義される

DB's Index

Davies and Bouldin, 1979 による指標。*5

これもクラスタ内の凝集性およびクラスタ間の離散性の指標となります。

\( S_i = \left( \frac{1}{\left | C_i \right |} \sum_{x \in C_{i} } \left( d(x, c_i) \right) ^ 2 \right) ^ \frac{1}{2} \)

\( d_{ij} = d(c_i, c_j) \)

\( R_i = \max_{1 \leq j \leq k, j \neq i} \left \{ \frac{S_i + S_j}{d_{ij}} \right \} \)

\( DB's Index = \frac{1}{k} \sum_{i=1}^{k} R_i \)

\( S_i \): クラスタ\( i \)のメンバーのばらつき

\( \left | C_i \right | \): クラスタ\( i \)のサイズ

\( d_{ij} \): クラスタ\( i \)とクラスタ\( j \)の距離。セントロイド間の距離で定義

Pseudo T-square

前述の指標はクラスタリングの結果全体に対しての指標でしたが、こちらは階層型クラスタリングにおける1階層の処理、即ちクラスタのマージを評価するものです。最適っぽいクラスタ数を決める指標であるとも言えます。 この指標が小さい階層が最適らしいクラスタリング結果だということです。 Duda, Hart and Stork 2001 による考えが元となっています。*6

\( Pseudo T Square = \frac{B_{ij}}{ (W_i + W_j) / (n_i + n_j - 2) } \)

\( B_{ij} \): クラスタ\( i \)とクラスタ\( j \)間の距離二乗和

\( W_i \): クラスタ\( i \)のクラスタ内距離二乗和

\( n_i \): クラスタ\( i \)のメンバー数

まとめ

個人的には Pseudo-F が一番しっくりくる気がします。クラスタリングを空間分割の目的で使う場合、別の言い方をするとクラスタ間の離散性を気にしない場合はクラスタ内距離二乗和の方が良さそう。

誤りがあればご指摘いただければと思います。

参考