クラスター分析に関するノート 情報学部堀田敬介 2004/7/32008/7/ 改訂, 2009/0/3 改訂 ) 類似度の測定 まずはじめに, 各データ間の距離を測るが, 尺度毎に様々な方法が提案されている. 尺度に対応した類似度測定の距離を示す.. 間隔尺度による類似度の測定 n 個の対象があり, 各対象は間隔尺度で m 個の属性 変量 ) が測定されているとする. このとき対象 と q を x [x,,x m ] T, x q [x q,,x qm ] T とし, その距離 d q を測ることを考える. v u ユークリッド距離 d q t m x x q ) 2 ユークリッド平方距離 d q 重み付きユークリッド距離 d q マンハッタン距離 d q ミンコフスキー距離 d q k v u t m v u t m x x q ) 2 w x x q ) 2 x x q x x q k w,...,m) は重み weght) k ならばマンハッタン距離,k 2ならばユークリッド距離となる ) x x q キャンベラ距離 d q x + x q マハラノビス距離 d q x x q ) T Σ x x q ) Σ : 分散共分散行列 ) 内積 d q x T x q x x q 平均 0, 長さ x x q に標準化した際の Pearson の積率相関係数に一致 ) P m x x )x q x q ) Pearson の積率相関係数 r q q Pm q Pm x x ) 2 x q x q ) 2
問題発見技法 6. クラスター分析 2.2 順序尺度による類似度の測定 n 個の対象があり, 各対象は順序尺度で m 個の属性 変量 ) が測定されているとする. このとき対象 と q を x [x,,x m ] T, x q [x q,,x qm ] T とし, 各変量は各固体の順位をあらわす数値, 2,...,m) になっている場合, どの程度対応する変量の順位が一致しているかを, 順位相関係数 r q で計ることを考える. 6 Searman の順位相関係数 r q x x q ) 2 mm +)m ) 上記の順位尺度変量に Pearson の積率相関係数を計算した結果 ) Kendall の順位相関係数 r q F R nn )/2 Kendall の相関係数について,F, R はそれぞれ, F は, j {,...,m} :<j) R は, j {,...,m} :<j) x >x j かつ x q >x qj, または x <x j かつ x q <x qj の個数 x >x j かつ x q <x qj, または x <x j かつ x q >x qj の個数 となる. 即ち, 全変量対 nn )/2 個 ) に対する, 順序が同じ個数と逆になる個数の差の割合を意味する..3 名義尺度 [0,]- データ ) による類似度の測定 n 個の対象があり, 各対象は名義尺度で m 個の属性 変量 ) が測定されており, その値は または 0 であるとする. このとき対象, q 間の類似度 S q を測定することを考える. x [x,,x m ] T, x q [x q,,x qm ] T 類似比 the coeffcent of Jaccard) S q a/a + b + c) 一致係数 the smle matchng coeffcent) S q a + d)/m Russel-Rao 係数 S q a/m Rogers-Tanmoto 係数 S q a + d)/m + b + c) Hamann 係数 S q {a + d) b + c)}/m ただし, ファイ係数 S q ad bc)/{a + b)c + d)a + c)b + d)} 2 a P m k x x q b P m k x x q ) c P m k x )x q d P m k x ) x q ) 対象, q がともに をとる変量の個数対象 が,q が 0 をとる変量の個数対象 が 0,q が をとる変量の個数対象, q がともに 0 をとる変量の個数 であり, となる. a + b + c + d m
問題発見技法 6. クラスター分析 3.4 名義尺度による類似度の測定 変量間類似度 ) n 個の対象があり, 各対象は名義尺度で m 個の属性 変量 ) の度数が測定されているとする. 対象 の属性 の度数を n で表す. 対象 \ 属性... m f f f m....... f f f m....... n f n f n f nm 平均平方根一致係数 C グッドマン クラスカルの λ λ q χ 2 /χ 2 + nm) χ 2 は 2 つの変量間の独立性検定のためのカイ 2 乗統計量 ) max f + max f max f max f 2nm max f max f 2 クラスター分析 : クラスター化の方法 クラスター とクラスター q があわさり一つのクラスター t を作る場合, 新しくできるクラスター t と, q 以外のクラスタ達 r と呼ぼう ) との類似度 S tr を求める必要がある. 今, と q, と r,q と r の元の類似度をそれぞれ S q,s r, S qr としたときに, これらを基にして S tr を求める方法は, 例えば以下のようなものがある.. 最短距離法 nearest neghbor method) 2. 最長距離法 furthest neghbor method) 3. 群平均法 grou average method) 4. 重心法 centrod method) 5. 中央値法 medan method) 6. ウォード法 Ward method) ここでは, 上記 6 つのうち, 重心法とウォード法についてのみ記す. 2. 重心法 centrod method 重心法は, クラスタ間の類似度を各クラスタの重心間の距離で測る方法. クラスタ, q 間,, r 間,q, r 間, 及び t, r 間の類似度 S q,s r,s qr 及び S tr について, S tr n n + S r + n + S qr n n + ) 2 S q
問題発見技法 6. クラスター分析 4 と更新する方法である. クラスタ, q, r, 及び t の重心をそれぞれ x, x q, x r, 及び x t とし, クラスタ, q, r, 及び t 内の対象数をそれぞれ n,,, 及び とする. すると, n +, x t n n + x + n + x q である. クラスタ t, r 間のユークリッド平方距離を d 2 tr とすると, Ã d 2 tr x t x r 2 n x + n! 2 q x q x r n + n + n x x r )+ n 2 q x q x r ) n + n + n 2 n + ) 2 k x x r k 2 n 2 q + n + ) 2 k x q x r k 2 2n n + ) 2 x x r, x q x r ) n n + ) n n + ) 2 k x x r k 2 + n + ) n n + ) 2 k x q x r k 2 2n n + ) 2 x x r, x q x r ) n k x x r k 2 + k x q x r k 2 n n o n + n + n + ) 2 k x x r k 2 + k x q x r k 2 2 x x r, x q x r ) n k x x r k 2 + k x q x r k 2 n n + n + n + ) 2 k x x r ) x q x r )k 2 n k x x r k 2 + k x q x r k 2 n n + n + n + ) 2 k x x q k 2 n d 2 r + d 2 qr n n + n + n + ) 2 d2 q となる. 従って, 重心法では, 類似度 S tr としてユークリッド平方距離 d 2 tr をとったときのみ妥当. 2.2 ウォード法 Ward method クラスタ とクラスタ q を一つのクラスタ t に統合するとき, 他のクラスタ r との類似度 S tr を決める方法の一つ. クラスタ に属する対象 j を x j と表すことにする. x j x j. IR m x mj クラスタ 内の変動 D は D : n x j x ) 2 ただし x n x j n j j であり, 全クラスタ内変動 D は, クラスタ数を K として, D : K D で与えられる. またこのとき, D t D + D q + D q ただし D q n n + x x q ) 2
問題発見技法 6. クラスター分析 5 となる. なぜなら, n +, x t x tj n x j + n j t j j n n j x j + x qj j x qj n x + x q であることに注意すると, D t x tj x t ) 2 j {x 2 tj 2x tj x t + x 2 t } j n {x 2 j 2x j x t + x 2 t } + {x 2 qj 2x qj x t + x 2 t } j j n n n x j x ) 2 +2 x x j n x 2 2 x t x j + n x 2 t j j j + x qj x q ) 2 +2 x q x qj x 2 q 2 x t x qj + x 2 t } j j j n x j x ) 2 + x qj x q ) 2 j j n o + 2n x 2 n x 2 2n x x t + n x 2 t +2 x 2 q x 2 q 2 x q x t + x 2 t n o D + D q + n x 2 + x 2 q x 2 t D + D q + ½n x 2 + x 2q ³ ¾ n 2 x 2 +2n x x q + n 2 q x 2 q nt ½ nt n )n D + D q + x 2 n x x q + n ¾ t ) x 2 q n t D + D q + n x x q ) 2 n + D + D q + D q だからである. さて, ウォード法は, 全クラスタ内変動 D を最も小さくするのが好ましいとする方法, 即ち, 各反復のクラスタリング 例えば, q を統合して t にする ) について, その増分 例では D q ) を最小にすることを考える方法である. この増分 D q ) を類似度 S q とし, 類似度が最も小さいクラスタ同士を統合する. なお, 初期状態 すべてのクラスタが つの対象から構成されている状態 ) では, この値はユークリッド平方距離の 2 となる.
問題発見技法 6. クラスター分析 6 また, 類似度の更新は, 次式で与えられる. D tr ) S tr + + + x t x r ) 2 µ n à n 2 n 2 t ½ x + x q x r 2 x 2 + n2 q n 2 x 2 q + x 2 r + 2n t n 2 x x q 2n x x r 2 x q x r t n x 2 2 x x r + x 2 + n r )+ x 2 q 2 x q x r + x 2 r ) n x 2 +2 x x q + x 2 r n q ) t m m ) n x x r ) 2 + x q x r ) 2 n x x q ) 2 + n + + {n + ) D r + + ) D qr D q } n + + S r + + + S qr + S q!
問題発見技法 6. クラスター分析 7 2.3 6 つの方法を統合する式 G.N. Lance & W.T.Wllams による統一的に扱うための式. 各方法の違いを, パラメータ α, α q, β, γ) の違いで決定できると示した. 平方距離を使用する場合は 2 番目の式となる. Str α S r + α q S qr + βs q + γ S r S qr Str 2 α Sr 2 + α q Sqr 2 + βsq 2 + γ Sr 2 Sqr 2 平方距離用 ) ) 最短距離法 nearest neghbor method) α α q : 2, β : 0, γ : 2 S tr 2 S r + 2 S qr 2 S r S qr Sr for S r S qr, S qr for S r >S qr mn{s r,s qr } 2) 最長距離法 furthest neghbor method) α α q : 2, β : 0, γ : 2 S tr 2 S r + 2 S qr + 2 S r S qr Sr for S r S qr, S qr for S r <S qr max{s r,s qr } 3) 重心法 centrod method) 4) 中央値法 medan method) α : n, α q :, β n, γ : 0 S 2 tr n 2 t n Sr 2 + Sqr 2 n n 2 t S 2 q α α q : 2, β : 4, γ : 0 5) 群平均法 grou average method) 6) ウォード法 Ward method) S tr 2 S r + 2 S qr 4 S q α : n, α q :, β γ : 0 S 2 tr n S 2 r + S 2 qr α : n +, α q : +, β :, γ : 0 + + + S 2 tr n + Sr 2 + + Sqr 2 Sq 2 + + +