Ward法

質問

Ward法は平方ユークリッド距離ではなく、ユークリッド距離でも作用できるのでしょうか。

回答No.1

stomachman · ベストアンサー

クラスター分析の話でしょうか？
　Ward法ってのはたしかえーと、クラスターAの重心をg(A)、要素数を|A|とすれば、
　　g(A) = (Σ[p∈A] p)/|A|
　　g(A∪B) = (g(A)|A|+g(B)|B|)/(|A|+|B|)
である。ここで要素pとqのユークリッド距離を||p-q||として、クラスターA,Bの間の距離の尺度D(A,B)を
　　D(A,B) = Σ[p∈A∪B]||p-g(A∪B)||^2 - Σ[p∈A]||p-g(A)||^2 - Σ[p∈B]||p-g(B)||^2
とする、という尺度ですよね。大雑把に言えば、A,Bがバラバラであるときのそれぞれの分散と、A∪Bに合体させたときの分散とを比べて、分散があんまり増加しないようならAとBは「近い」。近ければ合体させてもいいんじゃね？という風に手続きを進める訳です。
　ここで、クラスターA,Bの間の距離の尺度D(A,B)を、
　　E(A,B) = Σ[p∈A∪B]||p-g(A∪B)|| - Σ[p∈A]||p-g(A)|| - Σ[p∈B]||p-g(B)||
に差し替えようというのがご質問でしょうか。

　「クラスター間の距離の尺度」はイロイロで、たとえば最も近い要素同士の距離で定義する：
　　F(A,B) = min[p∈A, q∈B] ||p-q||
なんてのもアリですし、あるいは「クラスターの直径」を
　　d(A) = max[p∈A, q∈A] ||p-q||
と定義しておいて、
　　G(A,B) = d(A∪B)^2 - d(A)^2 - d(B)^2
なんてやるのもアリでしょう。要するに、「どんな風にクラスターをまとめたいか」に応じて、テキトーに尺度を作るんですね。だから、E(A,B)が目的に合っているのなら構わんと思います。もちろん、Ward法とは振る舞いが当然異なるわけで、いや、異なるからこそ別の（もっと目的に沿う）尺度を作るんですよね。なのでE(A,B)をWard法と呼んじゃいけません。

　さて「テキトーに作る」という中には、計算がらくちんかどうか、という評価基準も含まれます。
　　Σ[p∈A]||p-g(A)||^2 = (Σ[p∈A]||p||^2)-|A|(||g(A)||^2)
なので、
　　D(A,B) = |A|(||g(A)||^2) + |B|(||g(B)||^2) - (|A|+|B|)(||g(A∪B)||^2)
という関係が成立つ。つまり、|A|と|B|とg(A)とg(B)が計算してあれば、D(A,B)がイッパツで出せるという特長があります。E(A,B)だとそうは行かんでしょう。

お礼

遅くなりすみません。丁寧な解説ありがとうございます。
いまいち分からなかったところもわかりました！