* Lance-Williams updating formula [#r15b449a]
//ここには %項目の説明を書いてください．よろしければ署名しておいてください．
凝集型階層的クラスタリングでは，各反復で最もクラスタ間の距離が小さいクラスタ \(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)|\]
主な凝集型階層的クラスタリング手法の係数は以下のとおり
|LEFT:|CENTER:|CENTER:|CENTER:|CENTER:|c
||\(\alpha_{a}\)|\(\alpha_{b}\)|\(\beta\)|\(\gamma\)|h
|単リンク法|\(\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)\) の計算量のアルゴリズムが存在する．また，アルゴリズムが空間濃縮・空間拡散するかは係数α，β，γの値に依存している．
> -- しましま
**関連項目 [#seb82dbd]
//英語や同義語のあとに，#brで区切って関連する項目をリストしてください．
-[[Lance-Williams recurrence formula]]
#br
-[[クラスタリング]]
-[[階層的クラスタリング]]
-[[凝集型階層的クラスタリング]]
--[[単リンク法]]
--[[完全リンク法]]
--[[群平均法]]
--[[Ward法]]
--[[セントロイド法]]
--[[メジアン法]]
-[[空間濃縮]]
-[[空間拡散]]
#br
-[[検索:Lance-Williams]]
**リンク集 [#uab3d973]
**関連文献 [#g7879032]
//この%項目%に関連する書籍や論文を紹介してください．
+基本文献~
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]]
+Lance-Williams updating formula について詳しい~
鷲尾 泰俊, 大橋 靖雄, "多次元データの解析", シリーズ 入門 統計的方法 3, 岩波書店 (1989)
![[PukiWiki]](image/ibisforest.png "[PukiWiki]")
