アルゴリズム (階層的クラスター分析)

内容

  1. 1 距離行列
    1. 1.1 クラスター観測
    2. 1.2 クラスター変数
  2. 2 結合法
  3. 3 樹形図
  4. 4 グループオブジェクト


階層的クラスター分析は階層樹を作るのに使用されます。それぞれが一つのオブジェクトを持った個のクラスターから始まります。まずは2つのクラスターを1つに統合してより大きなクラスターを最終的に1つの大きなクラスターになるまで行います。このプロセスは樹形図で見ることができます。

階層的クラスター分析でクラスターに分類されるオブジェクトは観測データでも変数でも可能です。

距離行列

距離または不同性行列は、対称行列にゼロ斜線要素を追加した行列です。ij 番目の要素が、i 番目とj 番目のオブジェクト間がどれだけ離れてる、または似ていないかを表しています。2つのオブジェクト間で距離を計算する方法はクラスター観測とクラスター変数で違ってきます。

クラスター観測

Originはクラスター観測に関して、距離を計算する前にまず正規化を行います。欠損値がある観測データは分析から除外されます。

  • 標準化変数
    1. N(0,1) に標準化
      変数 x_j\ は次のように標準化されます。 (x_j-\bar{x}_j)/\sigma_j 、そして \bar{x}_j\  \sigma_j\ はこの変数の平均と標準偏差を表しています。標準化変数は平均0と標準偏差1になります。
    2. (0,1) に標準化
      変数 x_j\ は次のように正規化されます。 (x_j-\mathrm{min}(x_j))/(\mathrm{max}(x_j)-\mathrm{min}(x_j))\ .変数は0から1の間で標準化されます。

Originは3つの距離タイプをサポートします。

  • 距離タイプ
    個の観測点と変数を使った正規化行列 x_{ij}\ で、i 番目の観測データと番目の観測データは次のように表わされています。
    1. ユークリッド距離
      d_{ik}=\Big\{\sum_{j=1}^p (x_{ij}-x_{kj})^2 \Big\}^{\frac{1}{2}}
    2. 平方ユークリッド距離
      d_{ik}=\sum_{j=1}^p (x_{ij}-x_{kj})^2
    3. City-Block 距離
      d_{ik}=\sum_{j=1}^p |x_{ij}-x_{kj}|
    4. コサイン距離
      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}}
    5. ピアソン相関距離
      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} が成り立ちます。
    6. 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つの距離タイプをサポートしています。観測値は共分散や係数を計算する2つの変数のうち、どちらか一方に欠損値がある場合は除かれます。

  • 距離タイプ
    個の観測データと変数を使った行列x_{ij}\ で、i番目の変数と番目の変数は次のように表わされています。
    1. 相関関係
      d_{jk}=1-\mathrm{corr}(x_j, x_k)\   \mathrm{corr}(x_j, x_k)\ 番目の変数と番目の変数の相関関係を示しています。
    2. 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とクラスターid_{i,jk}\ の距離 は次のように計算されます。

  1. 単一結合または最短距離
    d_{i,jk}=\mathrm{min}(d_{ij},d_{ik})\
  2. 完全結合または最長距離
    d_{i,jk}=\mathrm{max}(d_{ij},d_{ik})\
  3. 群平均
    d_{i,jk}=\frac{n_j}{n_j+n_k}d_{ij}+\frac{n_k}{n_j+n_k}d_{ik}\
  4. 重心
    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}\
  5. メディアン
    d_{i,jk}=\frac{1}{2}d_{ij}+\frac{1}{2}d_{ik}-\frac{1}{4}d_{jk}\
  6. 最低分散または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つのクラスターが統合するのかを表示しています。各段階は1つのユニットとして樹形図では示されています。各段階で一番上にあるユニットは2つのクラスターを統合したものを示しています。その高さは2つの統合したクラスター間の距離を示しています。

樹形図の終点はn個のオブジェクトを表しています。樹形図内の個のオブジェクトは統合されたクラスターが隣り合うようにソートされています。樹形図の最初の終点は常に初めのオブジェクトを表しています。

グループオブジェクト

特定されたクラスターのn個のプロジェクトは樹形図またはクラスター段階の情報によって判別できます。クラスターはn-k番目の段階にあり、これは各オブジェクトの所属は初めのn-k段階で知ることができます。そしてオブジェクト1は常にクラスター1に所属しています。

クラスター中心と観測データおよびクラスター間の距離はクラスター観測データのために計算されます。もし正規化が分析内で選択されていた場合、観測データは計算の中で正規化されます。