Step2. 中級編
7. 多変量解析

7-5. 階層型クラスター分析2

■サンプル間の距離計算方法

7-4章では、サンプル間の距離を計算するために「ユークリッド距離」を算出しました。距離計算には他にも様々な方法があります。ここではまず、クラスター分析で使われる距離計算方法について詳しく見てみます。

$n$ 次元における2点、 $\boldsymbol{p} = (p_1, p_2, \cdots, p_n)$ と $\boldsymbol{q} = (q_1, q_2, \cdots, q_n)$ の間の距離について考えます。

ユークリッド距離

2点間の直線距離のことで、最も一般的な距離計算方法です。 $p$ と $q$ の間のユークリッド距離は次の式から算出できます。

$\displaystyle d(\boldsymbol{p},\ \boldsymbol{q}) = \sqrt{\sum^n_{i=1} (p_i-q_i)^2}$

各次元における値の単位が異なる場合には、標準偏差 $\sigma_i$ を使って2点間のユークリッド距離（標準化ユークリッド距離）を計算します。

$\displaystyle d(\boldsymbol{p},\ \boldsymbol{q}) = \sqrt{\sum^n_{i=1} \left(\frac{p_i-q_i}{\sigma_i}\right)^2}$

マンハッタン距離

碁盤の目の街を歩いたときの最短距離のことで、 $p$ と $q$ の各次元における距離を計算しその和をとったものになります。

$\displaystyle d(\boldsymbol{p},\ \boldsymbol{q}) = \sum^n_{i=1} |p_i-q_i|$

ミンコフスキー距離

$m$ を任意の整数とするとき、ミンコフスキー距離は次の式から算出できます。ユークリッド距離やマンハッタン距離を一般化したものになります。

$\displaystyle d(\boldsymbol{p},\ \boldsymbol{q}) = \sum^n_{i=1} (|p_i-q_i|^{m})^{\frac{1}{m}}$

この式から分かるように、 $m=2$ のときにはユークリッド距離となり、 $m=1$ のときにはマンハッタン距離となります。

マハラノビス距離

サンプル間の相関関係を考慮した距離計算方法で、 $p$ と $q$ の間のマハラノビス距離は次の式から算出できます。異常データを検知する際に使われる場合があります。

$\displaystyle d(\boldsymbol{p},\ \boldsymbol{q}) = \sqrt{(p-q)^T {\sum}^{-1}(p-q)}$

${\sum}$ は分散共分散行列を表します。

$\displaystyle \sum = \begin{pmatrix} \sigma_{1} & \cdots & \sigma_{1i}& \cdots & \sigma_{1n}\\ \vdots & \ddots & & & \vdots \\ \sigma_{i1}& & \sigma_{i} & & \sigma_{in} \\ \vdots & & & \ddots & \vdots \\ \sigma_{n1}& \cdots & \sigma_{ni}& \cdots & \sigma_{n} \end{pmatrix}$

また、 ${\sum}^{-1}$ は ${\sum}$ の逆行列を表します。

この図から分かるように、マハラノビス距離では確率的に起こりにくい＝距離がより離れている＝より異常な値であると見なします。

チェビシェフ距離

各次元における差の絶対値を算出し、その中から最大となるものが2点間のチェビシェフ距離です。

$\displaystyle d(\boldsymbol{p},\ \boldsymbol{q}) = \displaystyle max_{i} (|p_i-q_i|)$

■クラスター間の距離計算方法

次に、クラスター間の距離算出方法について詳しく見てみます。7-4章で用いた「重心法」以外にもにもさまざまな距離計算方法が用いられます。

$\boldsymbol{x} = (x_1, x_2, \cdots, x_m)$ からなるクラスター $C_1$ と $\boldsymbol{y} = (y_1, y_2, \cdots, y_n)$ からなるクラスター $C_2$ の間の距離 $d(C_1,\ C_2)$ について考えます。

最短距離法

各クラスター内のサンプル間の距離のうち、最も距離が短いものをクラスター間の距離とする方法です。

メリット：計算量が少ない
デメリット：分類感度が低い。外れ値に弱い、鎖効果（クラスターが帯状になる現象のこと）が出やすい

$\displaystyle d(C_1,\ C_2) = min(d(\boldsymbol{x},\ \boldsymbol{y}))$

最長距離法

各クラスター内のサンプル間の距離のうち、最も距離が長いものをクラスター間の距離とする方法です。

メリット：計算量が少ない
デメリット：外れ値に弱い、拡散効果（本当は距離が近いクラスターが結合しない現象のこと）が出やすい

$\displaystyle d(C_1,\ C_2) = max(d(\boldsymbol{x},\ \boldsymbol{y}))$

重心法

各クラスター内のサンプルの重心を算出し、重心間の距離をクラスター間の距離とする方法です。

メリット：計算量が比較的少ない
デメリット：-

$\displaystyle d(C_1,\ C_2) = d \left( \frac{1}{m}\sum^{m}_{\boldsymbol{x} \in C_1} \boldsymbol{x},\ \frac{1}{n}\sum^{n}_{\boldsymbol{y} \in C_1} \boldsymbol{y} \right)$

群平均法

各クラスター内のサンプル間の距離を算出し、すべての距離の平均値をクラスター間の距離とする方法です。

メリット：計算量が比較的少ない、鎖効果や拡散効果が出にくい
デメリット：-

$\displaystyle d(C_1,\ C_2) = \frac{1}{m} \frac{1}{n}\sum^{m}_{\boldsymbol{x} \in C_1} \sum^{n}_{\boldsymbol{y} \in C_2} d(\boldsymbol{x},\ \boldsymbol{y})$

ウォード法

2つのクラスターを結合した後のクラスター内サンプルの重心から各サンプルまでの距離の二乗和（ $\sum^{m+n}_{\boldsymbol{z} \in C_1 \cup C_2} d(\boldsymbol{\bar{z}},\ \boldsymbol{z})^2$ の部分）から、結合前の2つのクラスター内サンプルの重心から各サンプルまでの二乗和（ $\sum^{m}_{\boldsymbol{x} \in C_1} d(\boldsymbol{\bar{x}},\ \boldsymbol{x})^2$ と $\sum^{n}_{\boldsymbol{y} \in C_2} d(\boldsymbol{\bar{y}},\ \boldsymbol{y})^2$ の部分）を引いた値をクラスター間の距離とする方法です。

メリット：分類感度が高いため、クラスター分析で非常によく用いられる
デメリット：計算量が多い

$\displaystyle d(C_1,\ C_2) = \sum^{m+n}_{\boldsymbol{z} \in C_1 \cup C_2} d(\boldsymbol{\bar{z}},\ \boldsymbol{z})^2 - \sum^{m}_{\boldsymbol{x} \in C_1} d(\boldsymbol{\bar{x}},\ \boldsymbol{x})^2 - \sum^{n}_{\boldsymbol{y} \in C_2} d(\boldsymbol{\bar{y}},\ \boldsymbol{y})^2$