Lance-Williams updating formula

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)\) の計算量のアルゴリズムが存在する．また，アルゴリズムが空間濃縮・空間拡散するかは係数α，β，γの値に依存している．