クラスタ間距離

2点間距離 - Tocotonistの日記(晴れのち快晴), 20081112に引き続いてお勉強メモ。

点の距離の測り方を上のどれかに決めるとして、それぞれの点の集合（クラスタ）間の距離 D(X, Y), X, Y: クラスタ を求める．X={x1, x2,..., xm}, Y={y1, y2,..., yn}, |X|=m, |Y|=n とする．
この距離を用いて、ばらばらの点を集合にしていってクラスタ化するのがよくある方法。

距離の定義
X={x1, x2,..., xm}, Y={y1, y2,..., yn} の距離D(X,Y)の求め方。
D(xi,yj)は点xiとyjの距離とする。

一番普通と感じられそうなのは

• 最近隣法
  • D(x,y)=min{D(xi,yj)|1<=int i<=m, 1<=int j<=n}
    • 細長いチェーン状のクラスタをつくりやすい。

その逆として、

• 最遠隣法
  • D(x,y)=max{D(xi,yj)|1<=int i<=m, 1<=int j<=n}
    • 細長いチェーン状のクラスタをつくりにくい。

• 群平均法
  • Group Average Method もしくは UPGMA: Unweighted Pair Group Method using Arithmetic average
  • {sum_{i,j} D(xi,yj)}/(m*n)
    • 結構万能だが、計算時間を食うかも

• 加重平均法
  • WPGMA: Weighted Pair Group Method using Arithmetic average
  • 群平均法にクラスタサイズを重みとする
  • {sum_{i,j} D(xi,yj)}
    • 重みはクラスタサイズに線形の式にしたが、それだけとは限らない
    • クラスタサイズのアンバランスさを補正する

• 重心法
  • UPGMC: Unweighted Pair Group Method using Centroid average
  • D({sum_i xi}/m, {sum_j yj/n})
    • 一回の結合で"距離の逆転"が起きうる

• 重み付き重心法
  • WPGMC: Weighted Pair Group Method using Centroid average
  • D({sum_i xi}/m, {sum_j yj/n})mn
    • 重みはクラスタサイズに線形の式にしたが、それだけとは限らない
    • 一回の結合で"距離の逆転"が起きうる
    • クラスタサイズのアンバランスさを補正する

• ウォード法
  • Ward method
  • D(X,Y)=E(X∪Y)-E(X)-E(Y), ただしE(X)は, Xのすべての点からXの重心までの距離の二乗の総和
    • 普通にクラスタされているX, Yなら正の値となる。