クラスタリング結果の評価の尺度基準
このエントリについて
クラスタリングの結果を定量評価するときの基準を数年に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)
データの分布が均一であればクラスタリングの結果は同じ大きさの超球状のクラスタになると想定し、そこからどれだけ離れているかで評価します。 つまりデータ分布の疎密によりクラスタ結果は現実には同じ大きさの球にはならないため、そこから離れている程良いという考えのようです。(正直あまり理解できておりません…詳しくはリンク先を参照)
\( 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クラスタのサンプル間の最小距離で定義される
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 \)のサイズ
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 が一番しっくりくる気がします。クラスタリングを空間分割の目的で使う場合、別の言い方をするとクラスタ間の離散性を気にしない場合はクラスタ内距離二乗和の方が良さそう。
誤りがあればご指摘いただければと思います。
参考
- SYSTAT Cluster Manual
- Development of archetypes of international marketing strategy
- はてなブログにLaTeXで数式を書く (Markdown記法用)
*2:Calinski, T., and J. Harabasz. 1974. A dendrite method for cluster analysis. Communications in Statistics 3: 1–27.
*4:Dunn, J. C. (1973). "A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters". Journal of Cybernetics 3 (3): 32–57.
*5:Davies, David L.; Bouldin, Donald W. (1979). "A Cluster Separation Measure". IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI-1 (2): 224–227.
*6:Duda, R. O., P. E. Hart, and D. G. Stork. 2001. Pattern Classification. 2nd ed. New York: Wiley.