Lance-Williams updating formula

凝集型階層的クラスタリングでは,各反復で最もクラスタ間の距離が小さいクラスタ \(C_{1a}\) と \(C_{1b}\) を見つける.その後,\(C_1=C_{1a}\cup C_{1b}\) なるクラスタを生成し,この \(C_1\) と,他のクラスタ \(C_2\) との間の距離を更新する必要がある.

現在利用されている主な凝集型階層的クラスタリング手法は,この距離の更新がLance-Williams updating formula によって定数時間で距離を更新できる組み合わせ的な手法である.

\(n_i\) をクラスタ \(C_i\) 内の要素数,\(d(C_i,C_j)\) をクラスタ間の距離としたとき Lance-Williams updating formula は次式: \[d(C_1,C_2)=\alpha_{a} d(C_{1a},C_2) + \alpha_{b} d(C_{1b},C_2) + \beta d(C_{1a},C_{1b}) + \gamma |d(C_{1a},C_2)-d(C_{1b},C_2)|\] 主な凝集型階層的クラスタリング手法の係数は以下のとおり

\(\alpha_{a}\)\(\alpha_{b}\)\(\beta\)\(\gamma\)
単リンク法\(\frac{1}{2}\)\(\frac{1}{2}\)\(0\)\(-\frac{1}{2}\)
完全リンク法\(\frac{1}{2}\)\(\frac{1}{2}\)\(0\)\(\frac{1}{2}\)
群平均法 (UPGMA)\(\frac{n_{1a}}{n_1}\)\(\frac{n_{1b}}{n_1}\)\(0\)\(0\)
WPGMA\(\frac{1}{2}\)\(\frac{1}{2}\)\(0\)\(0\)
Ward法\(\frac{n_{1a}+n_2}{n_1+n_2}\)\(\frac{n_{1b}+n_2}{n_1+n_2}\)\(-\frac{n_2}{n_1+n_2}\)\(0\)
セントロイド法 (重心法)\(\frac{n_{1a}}{n_1}\)\(\frac{n_{1b}}{n_1}\)\(-\frac{n_{1a}n_{1b}}{{n_1}^2}\)\(0\)
メジアン法\(\frac{1}{2}\)\(\frac{1}{2}\)\(-\frac{1}{4}\)\(0\)

ユークリッド距離の場合には \(O(n^2)\) の計算量の,Lance-Williams updating formulaで更新できる任意の距離には \(O(n^2\log n)\) の計算量のアルゴリズムが存在する.また,アルゴリズム空間濃縮空間拡散するかは係数α,β,γの値に依存している.

-- しましま

関連項目

リンク集

関連文献

  1. 基本文献
    G.N.Lance and W.T.Williams, "A general theory of classificatory sorting strategies. I. Hierarchical systems." Computer Journal, vol.9, pp.373-80 (1967)
    GoogleScholarAll:A general theory of classificatory sorting strategies. I. Hierarchical systems
  2. Lance-Williams updating formula について詳しい
    鷲尾 泰俊, 大橋 靖雄, "多次元データの解析", シリーズ 入門 統計的方法 3, 岩波書店 (1989)

トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-02-11 (木) 16:11:10