* 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)

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS