アルゴリズム (階層的クラスター分析)
階層的クラスター分析は階層樹を作るのに使用されます。それぞれが一つのオブジェクトを持ったｎ個のクラスターから始まります。まずは2つのクラスターを１つに統合してより大きなクラスターを最終的に１つの大きなクラスターになるまで行います。このプロセスは樹形図で見ることができます。
階層的クラスター分析でクラスターに分類されるオブジェクトは観測データでも変数でも可能です。
距離行列
距離または不同性行列は、対称行列にゼロ斜線要素を追加した行列です。ij 番目の要素が、i 番目とj 番目のオブジェクト間がどれだけ離れてる、または似ていないかを表しています。2つのオブジェクト間で距離を計算する方法はクラスター観測とクラスター変数で違ってきます。
クラスター観測
Originはクラスター観測に関して、距離を計算する前にまず正規化を行います。欠損値がある観測データは分析から除外されます。
- 標準化変数
- N(0,1) に標準化
変数 /math-1ff32f369704bbf722cb41dd4727b5ea.png "x_j\") は次のように標準化されます。 /math-8a2aa7bf0d735426ff95edf02207ad93.png "(x_j-\bar{x}_j)/\sigma_j") 、そして /math-9a256199940d00c2536a5816e8562a68.png "\bar{x}_j\") と /math-a4ff3192674d9d65f2d0d7d64cf24c70.png "\sigma_j\") はこの変数の平均と標準偏差を表しています。標準化変数は平均０と標準偏差１になります。
- (0,1) に標準化
変数 は次のように正規化されます。 /math-da8bfea696c5d55d5c80213b624edaae.png "(x_j-\mathrm{min}(x_j))/(\mathrm{max}(x_j)-\mathrm{min}(x_j))\") .変数は0から1の間で標準化されます。
Originは３つの距離タイプをサポートします。
- 距離タイプ
はｎ個の観測点とｐ変数を使った正規化行列 /math-61b39f8b9a10e8428d4a1ee092fe90cd.png "x_{ij}\") で、i 番目の観測データとｋ番目の観測データは次のように表わされています。
- ユークリッド距離
/math-9b4e398de3c2f5d2506b9b45fe329ccc.png "d_{ik}=\Big\{\sum_{j=1}^p (x_{ij}-x_{kj})^2 \Big\}^{\frac{1}{2}}")
- 平方ユークリッド距離
/math-00782c326cb91952af29de57a841a9c2.png "d_{ik}=\sum_{j=1}^p (x_{ij}-x_{kj})^2")
- City-Block 距離
/math-95f211a025ebc7daa3e1605459b1cbd2.png "d_{ik}=\sum_{j=1}^p |x_{ij}-x_{kj}|")
- コサイン距離
/math-b9b1c3b4992cc70b4946348c159f37e6.png "d_{ik}=1-\frac{\sum_{j=1}^p x_{ij}x_{kj}}{\sqrt{\sum_{j=1}^p x_{ij}^2}\sqrt{\sum_{j=1}^p x_{kj}^2}}")
- ピアソン相関距離
/math-36d3bef9314267d27776738195752c04.png "d_{ik}=1-\frac{\sum_{j=1}^p (x_{ij}- \bar x_i)(x_{kj}- \bar x_k)}{\sqrt{\sum_{j=1}^p (x_{ij}- \bar x_i)^2}\sqrt{\sum_{j=1}^p (x_{kj}- \bar x_k)^2}}")
ここで、 /math-0ff233a32e8ef8117a1b351b11a3a544.png "\bar x_i=\sum_{j=1}^p x_{ij}") と /math-026de1a29e08504cc940a5d530450259.png "\bar x_k=\sum_{j=1}^p x_{kj}") が成り立ちます。
- Jaccard距離
/math-c8ba27ae461ab7e05dfd221d6f617dfe.png "d_{ik}=\frac{\sum_{j=1}^p ( (x_{ij} \ne x_{kj}) \bigcap (x_{ij} \ne 0 \bigcup x_{kj} \ne 0) ) ? 1:0 }{\sum_{j=1}^p (x_{ij} \ne 0 \bigcup x_{kj} \ne 0) ) ? 1:0}")
クラスター変数
Originはクラスター変数で2つの距離タイプをサポートしています。観測値は共分散や係数を計算する２つの変数のうち、どちらか一方に欠損値がある場合は除かれます。
- 距離タイプ
はｎ個の観測データとｐ変数を使った行列で、i番目の変数とｋ番目の変数は次のように表わされています。
- 相関関係
/math-1fb6205bac10ad6d294c90cb9837e9c5.png "d_{jk}=1-\mathrm{corr}(x_j, x_k)\") /math-c3683cdadf1e9d4e33ea12a052c0f174.png "\mathrm{corr}(x_j, x_k)\") はｊ番目の変数とｋ番目の変数の相関関係を示しています。
- Absolute correlation(絶対相関)
/math-51b38858ea57d12c43210595a9d3661f.png "d_{jk}=1-|\mathrm{corr}(x_j, x_k)|\")
結合法
各ステージで、最も近しい2つのクラスターは統合されます。Originはいくつかの手法を用いて新規クラスターと他のクラスター間の距離を計算しています。クラスターｊとｋを統合してクラスターjkとします。/math-4977ea7b014aa7a99a12a7a0c45b76f6.png "n_i\") 、 /math-f898efd8ac64b6621a2aeed350ce3164.png "n_j\") 、 /math-fd91d2523217931bfcd6f684555f4d7f.png "n_k\") を順にクラスターi、クラスターｊそしてクラスターｋのオブジェクト数とし、/math-2a81a0fc16ebf02e971257997dafa28b.png "d_{ij}\") 、/math-c198e05d8ed1e6f1af582129382f6495.png "d_{ik}\") 、 /math-e2ed69879e29cc9517eb1a1f2ecab0cb.png "d_{jk}\") を2つのクラスター間の距離とします。するとクラスターjkとクラスターi/math-a473b8369dd26440ac973f3cf3de62ed.png "d_{i,jk}\") の距離 は次のように計算されます。
- 単一結合または最短距離
/math-1decc6265d2731648206786ae0cc44e7.png "d_{i,jk}=\mathrm{min}(d_{ij},d_{ik})\")
- 完全結合または最長距離
/math-88af2544aa89b6c5eb3bd10fbfc65fac.png "d_{i,jk}=\mathrm{max}(d_{ij},d_{ik})\")
- 群平均
/math-a117d8802250e31ee98a59d789fb3728.png "d_{i,jk}=\frac{n_j}{n_j+n_k}d_{ij}+\frac{n_k}{n_j+n_k}d_{ik}\")
- 重心
/math-a1e87a55511ee73bf5adfe0699ff3114.png "d_{i,jk}=\frac{n_j}{n_j+n_k}d_{ij}+\frac{n_k}{n_j+n_k}d_{ik}-\frac{n_jn_k}{(n_j+n_k)^2}d_{jk}\")
- メディアン
/math-f7defcfc31776fe2c1319c4424b56a88.png "d_{i,jk}=\frac{1}{2}d_{ij}+\frac{1}{2}d_{ik}-\frac{1}{4}d_{jk}\")
- 最低分散またはWard
/math-ebce4775175a80790a9f3ce946072790.png "d_{i,jk}=\frac{(n_i+n_j)d_{ij}+(n_i+n_k)d_{ik}-n_id_{jk}}{n_i+n_j+n_k}\")
クラスターｊとｋで j<k の場合、統合された新しいクラスターはクラスター段階表でクラスターｊとして表記されます。
樹形図
樹形図は階層的な木のような図で、どの距離で2つのクラスターが統合するのかを表示しています。各段階は１つのユニットとして樹形図では示されています。各段階で一番上にあるユニットは2つのクラスターを統合したものを示しています。その高さは2つの統合したクラスター間の距離を示しています。
樹形図の終点はn個のオブジェクトを表しています。樹形図内のｎ個のオブジェクトは統合されたクラスターが隣り合うようにソートされています。樹形図の最初の終点は常に初めのオブジェクトを表しています。
グループオブジェクト
特定されたｋクラスターのn個のプロジェクトは樹形図またはクラスター段階の情報によって判別できます。ｋクラスターはn-k番目の段階にあり、これは各オブジェクトの所属は初めのn-k段階で知ることができます。そしてオブジェクト１は常にクラスター1に所属しています。
クラスター中心と観測データおよびクラスター間の距離はクラスター観測データのために計算されます。もし正規化が分析内で選択されていた場合、観測データは計算の中で正規化されます。
|