データサイエンス情報局様のテキストをRで実装しました。
丁寧な手計算による説明で、クラスタリングの仕組みがよく分かりました。
この場を借りて、御礼申し上げます。

1 データファイル.

dat <- data.frame(suugaku=c(70,100,50,80,40),kokugo=c(90,80,90,60,100))
library(magrittr)

## 
## Attaching package: 'magrittr'

## The following object is masked from 'package:purrr':
## 
##     set_names

## The following object is masked from 'package:tidyr':
## 
##     extract

rownames(dat) <- LETTERS[1:5]
dat

	suugaku	kokugo
A	70	90
B	100	80
C	50	90
D	80	60
E	40	100

1.1 距離行列.

dat.d <- dist(dat)
dat.d

##          A        B        C        D
## B 31.62278                           
## C 20.00000 50.99020                  
## D 31.62278 28.28427 42.42641         
## E 31.62278 63.24555 14.14214 56.56854

2 クラスタリング.

併合によりクラスターができたら、新クラスターとの距離を新たに計算して更新する。
更新の計算方法が「最小距離法」「最大距離法」「群平均法」「ウォード法」で異なっている。その違いに注意してみていこう。

2.1 最短距離法.

dat.hcs <- hclust(dat.d, method = "single")
round(cophenetic(dat.hcs) ,1)

##      A    B    C    D
## B 31.6               
## C 20.0 31.6          
## D 31.6 28.3 31.6     
## E 20.0 31.6 14.1 31.6

plot(dat.hcs, hang = -1)

コーフェン行列.
コーフェン行列とは、個体間の距離を要素に持つ行列であり、距離が同じであれば同じクラスターに属する。コーフェン行列から容易にデンドログラムを描くことができる。

2.2 最大距離法.

dat.hcc <- hclust(dat.d, method = "complete")
round(cophenetic(dat.hcc),1)

##      A    B    C    D
## B 31.6               
## C 63.2 63.2          
## D 31.6 28.3 63.2     
## E 63.2 63.2 14.1 63.2

plot(dat.hcc, hang = -1)

2.3 群平均法.

dat.hcg <- hclust(dat.d, method = "average")
round(cophenetic(dat.hcg),1)

##      A    B    C    D
## B 46.1               
## C 25.8 46.1          
## D 46.1 28.3 46.1     
## E 25.8 46.1 14.1 46.1

plot(dat.hcg, hang = -1)

「最小距離法」「最大距離法」「群平均法」はユークリッド距離が基本になり、通常の計算と変わるところはない。
ウォード法はクラスター内変動を距離と考えるので、ユークリッド距離との関係に注意する必要がある。

2.4 ウォード法.

dat.hcw <- hclust(dat.d, method = "ward.D2")
round(cophenetic(dat.hcw) ,1)

##      A    B    C    D
## B 67.3               
## C 29.4 67.3          
## D 67.3 28.3 67.3     
## E 29.4 67.3 14.1 67.3

plot(dat.hcw, hang = -1)

１番目に結合する C,Eの距離は最短法による距離と同じである。

注意.
データ科学便覧様 Rによる階層的クラスタリングに、次のような注意がありました。

ward.D2 Ward 法 (最小分散法)
クラスター内の OTU間の距離平方和の増加量が最小になるクラスターを併合させる．
ward.D は本来の Ward 法の実装ではなく，ward.D2が本物．
ward.D では本来すべき距離の二乗が計算されない．

2.5 ２点間のウォード距離

　　　\(d_{ward}(C_1,C_2)=\left(c_1-\dfrac{c_1+c_2}{2}\right)^2+\left(c_2-\dfrac{c_1+c_2}{2}\right)^2=\dfrac{1}{2}(c_1-c_2)^2=\dfrac{1}{2}C_1C_2~^2\).

　　　\(\therefore \ C_1C_2=\sqrt{2\ d_{ward}(C_1,C_2)}\).

\(\sqrt{2\ d_{ward}(C_1,C_2)}\) は距離の順序を変えないので、この式をウォード距離としてもクラスター併合は変わらない。
東京工業大学情報理工学院機械学習 CSC.T254 岡崎直観先生.

詳しくみていきます。

C,Eのウォード距離.

#C,Eのウォード距離
CE <- rbind(dat[3,],dat[5,])
sum(diag(var(CE)))*1

## [1] 100

\(d_{ward}(C_1,C_2)=\dfrac{1}{2}C_1C_2~^2\) と合致している。
rのコーフェン行列は、ユークリッド距離と整合性を保つため \(\sqrt{2\ d_{ward}(C_1,C_2)}\) を出力している。
実際、\(\sqrt{2\cdot 100}=14.1\)

Aと（C,E）のウォード距離.

ACE <- rbind(dat[1,],dat[3,],dat[5,])
#sum(diag(var(ACE)))*2
#Aと（C,E）のウォード距離
sum(diag(var(ACE)))*2-sum(diag(var(CE)))*1

## [1] 433.3333

コーフェン行列に出力される距離は、 \(\sqrt{2\cdot 433}=29.4\) です。

\(S_{tr} = \dfrac {1}{n_{p} + n_{q} + n_{r}} \{(n_{p} + n_{r}){S_{pr}} + (n_{q} + n_{r})S_{qr} - n_{r}{S_{pq}}\}\) を用いて求めてみます。

ユークリッド平方距離で距離を更新したものを1/2倍し、
２倍したものの平方根がコーフェン行列に出力されることになる。

\(S_{A,CE}=\dfrac{1}{3}(2\cdot 400+2\cdot 1000-1\cdot 200)=866.6\).
コーフェン行列には、\(\sqrt{2 \cdot \dfrac{866.6}{2}}=72=29.4\) が出力される。

階層型クラスタリング