Algorithmus (Hierarchische Clusteranalyse)

Inhalt


Die hierarchische Clusteranalyse wird verwendet, um einen hierarchischen Baum zu erstellen. Zu Beginn gibt es n Cluster, jeder mit einem einzelnen Objekt und dann auf jeder n ? 1 Stufen werden zwei Cluster zusammengefügt und bilden einen größeren Cluster, bis sich alle Objekte in einem einzigen Cluster befinden. Der Vorgang kann in einem Dendrogramm gezeigt werden.

Die zu clusternden Objekte in der hierarchischen Clusteranalyse können Beobachtungen oder Variablen sein.

Distanzmatrix

Eine Distanz- oder Unähnlichkeitsmatrix ist eine symmetrische Matrix mit null diagonalen Elementen. Das ij-te Element stellt dar, wie unähnlich sich das i-te und j-te Objekt sind. Die Methoden zum Berechnen der Distanz zwischen zwei Objekten unterscheiden sich je nach dem, ob Beobachtungen oder Variablen geclustert werden.

Beobachtungen clustern

Origin unterstützt die Standardisierung von Daten vor der Distanzberechnung zum Clustern von Beobachtungen. Beobachtungen, die einen oder mehrere fehlende Werte enthält, werden aus der Analyse ausgeschlossen.

  • Variablen standardisieren
    1. Normieren auf N(0,1)
      Eine Variable x_j\ wird normiert zu: (x_j-\bar{x}_j)/\sigma_j, wobei \bar{x}_j\ und \sigma_j\ der Mittelwert und die Standardabweichung der Variable sind. Die standardisierte Variable hat einen Mittelwert bei Null und eine einheitliche Standardabweichung.
    2. Normieren auf (0,1)
      Eine Variable x_j\ wird normiert zu: (x_j-\mathrm{min}(x_j))/(\mathrm{max}(x_j)-\mathrm{min}(x_j))\ . Die Variable wird im Bereich 0 bis 1 standardisiert.

Origin unterstützt drei Distanztypen.

  • Distanztyp
    Für eine standardisierte Matrix x_{ij}\ mit n Beobachtungen und p Variablen kann die Distanz zwischen der i-ten Beobachtung und der k-ten Beobachtung folgendermaßen ausgedrückt werden:
    1. Euklidische Distanz
      d_{ik}=\Big\{\sum_{j=1}^p (x_{ij}-x_{kj})^2 \Big\}^{\frac{1}{2}}
    2. Quadrierte euklidische Distanz
      d_{ik}=\sum_{j=1}^p (x_{ij}-x_{kj})^2
    3. Absolute Distanz (City-Block-Metrik)
      d_{ik}=\sum_{j=1}^p |x_{ij}-x_{kj}|
    4. Kosinus-Distanz
      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. Pearson-Korrelationsdistanz
      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}}
      , wobei \bar x_i=\sum_{j=1}^p x_{ij} und \bar x_k=\sum_{j=1}^p x_{kj}
    6. Jaccard-Distanz
      d_{ik}=\frac{\sum_{j=1}^p ( (x_{ij} \ne x_{kj}) \and (x_{ij} \ne 0 \or x_{kj} \ne 0) ) ? 1:0 } {\sum_{j=1}^p (x_{ij} \ne 0 \or x_{kj} \ne 0) ) ? 1:0}

Variablen clustern

Origin unterstützt zwei Distanztypen zum Clustern von Variablen. Beobachtungen werden aus der Berechnung der Korrelation zwischen zwei Variablen ausgeschlossen, wenn fehlende Werte in einer der beiden Variablen existieren.

  • Distanztyp
    Für eine Matrix x_{ij}\ mit n Beobachtungen und p Variablen kann die Distanz zwischen der j-ten Variablen und der k-ten Variablen folgendermaßen ausgedrückt werden.
    1. Korrelation
      d_{jk}=1-\mathrm{corr}(x_j, x_k)\ wobei \mathrm{corr}(x_j, x_k)\ die Korrelation zwischen der j-ten Variablen und der k-ten Variable ist.
    2. Absolute Korrelation
      d_{jk}=1-|\mathrm{corr}(x_j, x_k)|\

Verknüpfungsmethode

Auf jeder Stufe werden die beiden Cluster, die sich am nahesten sind, zusammengefügt. Origin bietet mehrere Methoden, um die Distanz zwischen dem neuen und den anderen Clustern zu berechnen. Die zwei Cluster j und k werden zu dem Cluster jk zusammengefügt. n_i\ , n_j\ und n_k\ seien die Anzahl der Objekte von Cluster i, Cluster j und Cluster k und d_{ij}\ , d_{ik}\ und d_{jk}\ seien die Distanzen zwischen zwei Clustern. Die Distanz zwischen Cluster jk und Cluster i d_{i,jk}\ kann dann folgendermaßen berechnet werden:

  1. Einzelne Verknüpfung oder Nächster Nachbar
    d_{i,jk}=\mathrm{min}(d_{ij},d_{ik})\
  2. Vollständige Verknüpfung oder Weitesten entfernter Nachbar
    d_{i,jk}=\mathrm{max}(d_{ij},d_{ik})\
  3. Gruppendurchschnitt
    d_{i,jk}=\frac{n_j}{n_j+n_k}d_{ij}+\frac{n_k}{n_j+n_k}d_{ik}\
  4. Zentroid
    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. Median
    d_{i,jk}=\frac{1}{2}d_{ij}+\frac{1}{2}d_{ik}-\frac{1}{4}d_{jk}\
  6. Minimale Varianz oder 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}\

Wenn Cluster j und k, j<k, zusammengefügt werden, wird der neue Cluster in der Tabelle der Clusterstufen als Cluster j bezeichnet.

Dendrogramm

Das Dendrogramm ist ein hierarchischer Baum, der zeigt, bei welcher Distanz zwei Cluster zusammengefügt werden. Jede Stufe wird durch eine Einheit in dem Dendrogramm dargestellt. Der obere Teil der Einheit für jede Stufe stellt den neuen Cluster dar, indem zwei Cluster zusammengefügt wurden. Die Höhe entspricht der Distanz zwischen den zwei zusammengefügten Clustern.

Die Endpunkte des Dendrogramms stellen n Objekte dar. Die n Objekte in dem Dendrogramm werden sortiert, so dass die Cluster, die zusammengefügt wurden, nebeneinander liegen. Der erste Endpunkt im Dendrogramm entspricht immer dem ersten Objekt.

Objekte gruppieren

Die Zugehörigkeit von n Objekten für festgelegte k Cluster kann mit den Informationen aus dem Dendrogramm oder der Tabelle der Clusterstufen bestimmt werden. k Cluster befinden sich auf der n-k-ten Stufe, das heißt, die Zugehörigkeit von jedem Objekt ist durch die ersten n-k-ten Stufen bekannt. Objekt 1 gehört immer zu Cluster 1.

Clusterzentren, die Distanz zwischen Clusterzentren und die Distanz zwischen Beobachtungen und Clustern werden zum Clustern von Beobachtungen berechnet. Beachten Sie, dass Beobachtungen in der Berechnung standardisiert sind, wenn die Standardisierung in der Analyse gewählt wird.
English | Deutsch | 日本語