Computing Issues: Mathematische Regressionsanalyse und Hierarisches Clustering in der Ökonomie/Wirtschaft

Computing Issues: Mathematische Regressionsanalyse und Hierarisches Clustering in der Ökonomie/Wirtschaft

Mathematische Regressionsanalyse und Hierarisches Clustering in der Ökonomie/Wirtschaft

Hierarchical-Clustering und seine Schwächen

Sehr geehrte Damen und Herren,

das was man lernt in seinem Studium, dass was man gesagt bekommt, ergibt sich erst später und wird einem erst klar, nachdem man es "setzen" hat lassen.

So ist es zum Beispiel mit der Vorlesung der "Ökonometrie".
Auch in der Gefahr, dass es nicht ganz richtig ist, was den Stoff der Ökonometrie angeht, schreibe ich meine Gedanken auf.

Es gibt zwei Verfahren in der Ökonometrie, die gerne in Kombination verwendet werden: Das Hierarchical-Clustering und die Regressionsanalyse.
Das Hierarchical-Clustering wird zur Bestimmung von Gruppen verwendet und deren Beziehung dann in der Regressionsanalyse berechnet.
Da die Regressionsanalyse schon sehr ausgeschöpft ist und da der Kern der Frage in der Bestimmung der Gruppen liegt, wird hier auf das Clustering wert gelegt.

Hierarchical-Clustering sucht immer die am Nächsten liegenden Punkte oder Mittelwerte einer Gruppe und verbindet die beiden Punkte zu einer neuen Gruppe. Das Ergebnis sieht wie folgt aus:

Abb. 1 - typisches Beispiel für Hierachical-Clustering ohne Dendrogramm [5]

Nach Wikipedia gibt es zwei Verfahren:

• divisiv - bzw "Top-down"
• und agglomerativ - bzw "Bottom-up"

Eine tiefere Unterscheidung ist in meinem Beitrag von 2009 zu lesen.
Pattern-Recognition anhand von Hierarchical-Clustering mit Hilfe des Cut-Off-Criterium

Leider sind nach Wikipedia die Verfahren Top-Down und Bottom-Up in ihrer Komplexität unterschiedlich.
Top-Down brauch naiv ${\displaystyle O(2^{n})}$ Schritte.
Bottom-Up hingegen nur ${\displaystyle O(n^{3})}$ Schritte.
Natürlich geht der Vorteil mit Verlust von Information/Unterscheidungsmöglichkeiten einher.
Doch dies ist hier nur prognostiziert.

Da ein Hierarchical-Clustering mit dem Hierarchie-Diagramm wie in Abbildung 1 nicht viel hilfreich ist, wird der Abstand zwischen den Clustern beim Vereinigungspunkt auf der Y-Achse abgebildet. Dies ist dann ein "Dendogramm", welches auch gedreht dargestellt werden kann. Ein Beispiel ist in Abb.2 gezeigt.



Abb. 2 - Beispiel für ein typisches Dendrogramm [1]


Hier wird dann das Cut-Off-Criterium angewendet, welches dazu dient die Cluster zu bestimmen.
Dazu gibt es unterschiedliche Verfahren, welche in: Pattern-Recognition anhand von Hierarchical-Clustering mit Hilfe des Cut-Off-Criterium vertieft werden können.
Manchmal reicht ein einzelnes Cut-Off-Criterum nicht aus, weil dann nur eine kleine Menge und eine ganz große Menge entsteht, welche oft nicht der Realität entsprechen. Daher wird gerne ein zweiter Schnitt gemacht, welcher dann nur auf die Große Menge bezogen wird und diese weiter unterteilt. Siehe dazu Abbildung 3. Durch Wiederholung dieses Verfahrens bis auf vorgegebene Größen von Mengen, ist dieses Verfahren sicherlich sinnvoll. Leider sind jedoch dadurch keine großen Mengen mehr erkennbar/unterscheidbar. Im Allgemeinen geht der Vorteil des Clusterns damit verloren. Denn, jede Menge lässt sich natürlich in andere Mengen unterteilen. Und am Ende sind die Mengen immer nur von zwei Elementen Abhängig.



Abb. 3 - Zwei cut-off Kriterien [3]

Trotz dem mehrfachen Unterteilen, liegt das Problem, weshalb Hierarchical-Clustering nicht vollständig als perfektes Verfahren etabliert ist, auch in der Möglichkeit, dass das Clustering "entartet". Man kann sagen: Die Frage der Entartung ist analog zur Frage wo geschnitten werden kann.
Genauso, wie es unter Binärbäumen entartete Bäume gibt, gibt es beim Hierarchical-Clustering auch entartete Hierarchien. Siehe dazu Abbildung 4.
Dies wird ebenfalls im Wikipeida Artikel[1] beschrieben, und dort als "single-link effect" (dt. Ketteneffekt) bezeichnet.

Abb. 4 - Beispiel für Entartung des Hierarchical-Clustering [4]


Es wird versucht mit verschiedenen Verfahren beim Alignment/Linkage das Probelm des single-link effects zu verhindern. Dabei wird zwischen drei Knoten im Hierarchical-Tree unterschieden. Der einzufügende/aligning Knoten (g_a) und die beiden letzten Knoten der aktuell betrachteten Menge (g_b).

Abb. 5 - "Daten und Dendrogramm mit der Centroid-Methode." [1]

Wie in Wikipedia[1] beschrieben, gibt es unterschiedlichste Verfahren zur Verhinderung von single-link effect.
Aktuell sind jedoch nur empfehlenswert, das Average-Linkage und das Centroid-Linkage Verfahren. Das liegt an der Betrachtungsweise. Für die Anwendungen in der Betriebswirtschaft ist es notwendig den natürlichen Gegebenheiten der Welt und dem natürlichem Verhalten von Menschen ähnlich zu sein. Dafür bietet sich das Centroid-Linkage und das Average-Linkage am besten an. Näheres über die Verfahren in [1]. Die beiden Verfahren Centroid und Average sind auch in erster Linie die Wahl, da andere Verfahren wie Median-Berechnung nur sinnvoll sind, wenn die Mittelwert-Berechnung an Aussagekraft verliert.

Der Grund hinter dem Linkage-Verfahren mit drei Gruppen/Mengen liegt, wie schon erwähnt, in der Lösung des single-link effect.
Um die Idee näher zu verstehen, ist es dienlich das Problem kurz zu umschreiben.

Problem der Entartung von Bäumen

Eine Entartung entsteht, wenn eine der zu vereinigenden Gruppen g_a oder g_b eine Stufe zuvor auch schon vereinigt wurden.
Um das zu erklären, ist es praktisch kurz die Eigenschaften eines entarteten Baumes zu beschreiben:

• das zuletzt hinzugefügte Element zu einer Gruppe,
  ist auch wieder Element der nächsten Gruppe,
• der Baum hat genauso viele Ebenen, wie Elemente (n).
  Bei einem ausgeglichen Baum gibt es hingegen nur log(n) Ebenen für n Elemente.

Daraus folgt:
Wenn k = | i - j |, mit |.| = Absolutwert der Ebenen-Nummer i für g_a und j für g_b, dann ergibt sich folgende Regel:
Ist |i-j| < log(n)/2, so führt diese Verbindung zur Entartung.


Nun kann man diese Verbindung auslasse und die nächst beste Gruppe nach dem Linkage-Verfahren betrachten.
Deshalb wird gerne das Linkage-Verfahren variiert um den single-link effect zu vermeiden.

Doch leider hat das Problem der entarteten Bäume wenig mit dem Linkage-Verfahren zu tun. Das Linkage-Verfahren dient nur der Frage, wie die Elemente ausgewählt werden um miteinander verbunden zu werden. Naturgemäß ist da das Kriterium des nähesten oder mittlersten Elementes, innerhalb zwei Gruppen A und B, am passendsten. Beispielsweise gäbe es noch das Verfahren des weitesten entfernten Elementes aus zwei Gruppen als Linkage (Complete-Linkage) zu betrachten, nur wird dies dem natürlichem Verhalten von Personen und Optionen kaum gerecht.


Die Entartung der Bäume liegt demnach nicht an dem Linkage-Verfahren.
Eine naive Lösung wäre nicht das Linkage-Verfahren zu variieren, sondern wie folgt.

Naive Lösung

1. Wenn |i(g_a) - i(g_b)| < log(n)/2 * 0,8 = log(n) 2/5,
   wobei i(g_a) die Ebenen-Nummer bei Vereinigung von Gruppe A ist und 0,8 o.B.d.A ein Wert, der für signifikant kleiner steht, ist,
   dann wähle die nächste, dem Linkage-Verfahren passende Gruppe g_c, welche zu g_a aligned würde. 
2. ist dann |i(g_a) - i(g-c)| >= 2/5 log(n), höre auf und verbinde g_a mit g_c.
3. ist |i(g_a) - i(g_c)| < 2/5 log(n), dann wiederhole Schritt 1,
4. bis keine alternative Gruppe gefunden wurde. So wähle g_b.

Diese Lösung ähnelt in etwa einem AVL-Baum[6]. Der Baum wird ausgeglichen um die "Entartung" zu vermeiden. Der Trick des AVL-Baumes besteht darin, den rechts oder links-lastigen Zweig höher zu stellen, indem ein anderer Root-Knoten gewählt wird. Dabei spricht man von Links-, Rechts- oder Doppelrotation.
Abb. 6 zeigt eine Linksrotation um den rechten schwereren Zweig auszugleichen.

Abb. 6 - Linksrotation [6]

Problem der Naiven Lösung

Leider ist das Problem der Naiven Lösung ganz offensichtlich: Die Mengen A wird mit einer anderen Menge C anstelle der von B verknüpft. Die Menge C ist jedoch von der Lokalisation weiter entfernt als B, und entspricht daher nicht dem Ähnlichkeitsprinzip. Geht es bei der Erstellung des AVL-Baumes nur um eine korrekte Sortierung der Elemente nach > oder <=, so ist ein AVL-Baum ausreichend. Hier im ökonomischen Zweig, geht es jedoch um Erkennung von Gruppen und diese sind nach Rotation, oder Wahl von C anstelle von B, zerstört.

Elegante Lösung

Ist der Datensatz mehr als eindimensional, also ein Vektor, so ist generell eine hierarchische Aufteilung nicht möglich. Die Datensätze besitzen nun eine Position in einem mehrdimensionalen Raum. Sie besitzen eine Lokalisation. D.h. die Datensätze haben mehrere Abstände zu ihren nächsten Nachbarn auf unterschiedlichen Achsen.
Eine Vereinfachung auf den am nahestehend Datensatz/Gruppe/Knotenpunkt ist somit eine Reduktion der anderen Abstände auf den anderen Achsen.
Durch dies Reduktion geht Information verloren, und das Ergebnis entspricht nicht dem gewünschtem Ergebnis.
Im Prinzip ist das Hierarchical-Clustering auf mehrdimensionale Daten ungenügend. Aktuell erstellt es eine Hierarchie, die so nicht die Gruppen der mehrdimensionalen Daten abbildet.

Vielleicht wäre eine Lösung durch einen vollständigen Travelling-Salesman-Path möglich.
Das Travelling-Salesman-Problem ist die Frage nach dem kürzesten Round-Trip, wenn alle Punkte/Städte auf mindestens Intervallskala, miteinander auf direktem Wege erreichbar sind.

Die Lösung wäre:

1. Das TSP auf den Daten X zu lösen
2. Bei der größten Teilstrecke in eine Richtung zu starten
3. Alle Punkte als eine gemeinsame Menge zu sehen, welche mit den TSP-Streckenabschnitten s verbunden sind, die kürzer als der durchschnittlichen Streckenabschnittslänge µ, abzüglich des Fehlers e, sind.
   s < (µ - e) ==> verbinden des vorherigen und nächsten Punktes.

Wie das TSP lösbar ist, wird in einem anderen Blog-Beitrag besprochen.
Siehe tspsolved.blogspot.de  .

Als Fehler e verwenden wir das a-Quantil mit alpha=0,04. D.h. bei z_(1-a/2) = 0,5160 für Normalverteilung, ist der Fehler:



    [7]

Leider ist das TSP auf naive Variante noch O(n!). D.h. zu langsam. Mit der Lösung des TSP wie unter tspsolved.blogspot.de, kommt es zur Veränderung in der Komplexität und einem großen Einfluss auf die Welt.
So kann das TSP einen Beitrag für die Öknometrie leisten.


mit freundlichen Grüßen, hochachtungsvoll, Ihr Sebastian

References

[1] https://de.wikipedia.org/wiki/Hierarchische_Clusteranalyse
[2] http://sebastianboehmercomputing.blogspot.de/2009/12/pattern-recognition-anhand-von.html
[3] http://compbio.pbworks.com/f/partitonal.JPG
[4] http://www.saedsayad.com/images/Clustering_h1.png
[5] http://www2.cs.uregina.ca/~dbd/cs831/notes/clustering/Hiereg.gif
[6] https://de.wikipedia.org/wiki/AVL-Baum
[7] https://de.wikipedia.org/wiki/Konfidenzintervall