[ML] Ward’s linkage method

정의

Ward's method는 cluster 간의 거리를 측정하는 방법 중 하나이며, centroid 와 매우 유사한 방식이지만, 각 cluster의 샘플 수에 대한 고려가 이루어진 방법이다.

 

간단하게 애기하면 Ward's method에서 두 클러스터의 거리는

• cluster의 data points에서 centroid와의 차이를 제곱하여 더한 error sum of square가
• 두 cluster를 merge할 경우 얼마나 증가하는지로 나타낸다. 

 

incremental of ESS 를 이용하기 때문에 centroid linkage와 기반 논리는 비슷하지만 outlier나 noise에 보다 robust 하고 포함하고 있는 data samples 수가 비슷한 cluster들을 merge하는 경향을 보임.

수식

cluster A와 B 간의 Ward distance에 대한 수식은 다음과 같음.

 

$$\begin{aligned} \text{dist}(A,B)&= \displaystyle \sum_{i\in A\cup B} \| \textbf{x}_i-\boldsymbol{\mu}_{A\cup B} \|^2 - \sum_{i\in A} \|\textbf{x}_i - \boldsymbol{\mu}_{A}\|^2 - \sum_{i\in B} \| \textbf{x}_i - \boldsymbol{\mu}_B \|^2 \\ &=\frac{n_A n_B}{n_A+n_B} \| \boldsymbol {\mu}_A - \boldsymbol{\mu}_B \|^2 \end{aligned}$$

 

• $\textbf{x}$ : data sample vetor.
• $n_A$ : cluster $A$ 의 data samples 갯수.
• $n_B$ : cluster $A$ 의 data samples 갯수.
• $n_{A\cup B}$ : cluster $A$와 cluster $B$를 merge한 경우의 해당 merged cluster의 data samples 갯수.
• $\boldsymbol{\mu}_A$ : cluster $A$의 centroid vector.
• $\boldsymbol{\mu}_B$ : cluster $B$의 centroid vector.
• $\boldsymbol{\mu}_{A\cup B}$ :cluster $A$와 cluster $B$를 merge한 경우의 해당 merged cluster의 centroid vector.