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

内容

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


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

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

距離行列

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

クラスター観測

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

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

クラスター変数

Originはクラスター変数で2つの距離タイプをサポートしています。観測値は共分散や係数を計算する2つの変数のうち、どちらか一方に欠損値がある場合は除かれます。

結合法

各ステージで、最も近しい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に所属しています。

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