アルゴリズム (階層的クラスター分析)
内容 |
階層的クラスター分析は階層樹を作るのに使用されます。それぞれが一つのオブジェクトを持ったｎ個のクラスターから始まります。まずは2つのクラスターを１つに統合してより大きなクラスターを最終的に１つの大きなクラスターになるまで行います。このプロセスは樹形図で見ることができます。
階層的クラスター分析でクラスターに分類されるオブジェクトは観測データでも変数でも可能です。
距離行列
距離または不同性行列は、対称行列にゼロ斜線要素を追加した行列です。ij 番目の要素が、i 番目とj 番目のオブジェクト間がどれだけ離れてる、または似ていないかを表しています。2つのオブジェクト間で距離を計算する方法はクラスター観測とクラスター変数で違ってきます。
クラスター観測
Originはクラスター観測に関して、距離を計算する前にまず正規化を行います。欠損値がある観測データは分析から除外されます。
- 標準化変数
- N(0,1) に標準化
変数 \(x_j\ \) は次のように標準化されます。 \((x_j-\bar{x}_j)/\sigma_j\) 、そして \(\bar{x}_j\ \) と \(\sigma_j\ \) はこの変数の平均と標準偏差を表しています。標準化変数は平均０と標準偏差１になります。 - (0,1) に標準化
変数 \(x_j\ \) は次のように正規化されます。 \((x_j-\mathrm{min}(x_j))/(\mathrm{max}(x_j)-\mathrm{min}(x_j))\ \) .変数は0から1の間で標準化されます。
- N(0,1) に標準化
Originは３つの距離タイプをサポートします。
- 距離タイプ
はｎ個の観測点とｐ変数を使った正規化行列 \(x_{ij}\ \) で、i 番目の観測データとｋ番目の観測データは次のように表わされています。- ユークリッド距離
\(d_{ik}=\Big\{\sum_{j=1}^p (x_{ij}-x_{kj})^2 \Big\}^{\frac{1}{2}}\) - 平方ユークリッド距離
\(d_{ik}=\sum_{j=1}^p (x_{ij}-x_{kj})^2\) - City-Block 距離
\(d_{ik}=\sum_{j=1}^p |x_{ij}-x_{kj}|\) - コサイン距離
\(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}}\) - ピアソン相関距離
\(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}}\)
ここで、 \(\bar x_i=\sum_{j=1}^p x_{ij}\) と \(\bar x_k=\sum_{j=1}^p x_{kj}\) が成り立ちます。 - Jaccard距離
\(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つの距離タイプをサポートしています。観測値は共分散や係数を計算する２つの変数のうち、どちらか一方に欠損値がある場合は除かれます。
- 距離タイプ
はｎ個の観測データとｐ変数を使った行列\(x_{ij}\ \)で、i番目の変数とｋ番目の変数は次のように表わされています。- 相関関係
\(d_{jk}=1-\mathrm{corr}(x_j, x_k)\ \) \(\mathrm{corr}(x_j, x_k)\ \) はｊ番目の変数とｋ番目の変数の相関関係を示しています。 - Absolute correlation(絶対相関)
\(d_{jk}=1-|\mathrm{corr}(x_j, x_k)|\ \)
- 相関関係
結合法
各ステージで、最も近しい2つのクラスターは統合されます。Originはいくつかの手法を用いて新規クラスターと他のクラスター間の距離を計算しています。クラスターｊとｋを統合してクラスターjkとします。\(n_i\ \)、 \(n_j\ \) 、 \(n_k\ \) を順にクラスターi、クラスターｊそしてクラスターｋのオブジェクト数とし、\(d_{ij}\ \)、\(d_{ik}\ \)、 \(d_{jk}\ \) を2つのクラスター間の距離とします。するとクラスターjkとクラスターi\(d_{i,jk}\ \) の距離 は次のように計算されます。
- 単一結合または最短距離
\(d_{i,jk}=\mathrm{min}(d_{ij},d_{ik})\ \) - 完全結合または最長距離
\(d_{i,jk}=\mathrm{max}(d_{ij},d_{ik})\ \) - 群平均
\(d_{i,jk}=\frac{n_j}{n_j+n_k}d_{ij}+\frac{n_k}{n_j+n_k}d_{ik}\ \) - 重心
\(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}\ \) - メディアン
\(d_{i,jk}=\frac{1}{2}d_{ij}+\frac{1}{2}d_{ik}-\frac{1}{4}d_{jk}\ \) - 最低分散またはWard
\(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に所属しています。
クラスター中心と観測データおよびクラスター間の距離はクラスター観測データのために計算されます。もし正規化が分析内で選択されていた場合、観測データは計算の中で正規化されます。