Einführung
Pattern Recognition bezeichnet hier den Prozess zur Klassifikation von Daten. Hierarchical Clustering ist eine Standardtechnik des Clustering. Clustering bedeutet lernen oder klassifizieren auf unsupervised Daten. Das interessante am Unsupervised Learning ist die Möglichkeit direkt neue Klassen und Strukturen in den Daten zu entdecken. Zum Beispiel kann man sich vorstellen, dass eine Bank ihre Daten auf ein Hierarchical Clustering ansetzt und dann unterschiedliche Arten des Finanzverhaltens je nach Alterskohorte und entdeckt. Oder, ein Autohaus entdeckt, dass alle Käufer eines roten Autos ein höheres Kreditausfallrisiko haben (siehe [Witten,Frank]).
Im Allgemeinen lässt sich zur Zeit das Clustering in folgende
"dimensions" nach Yee Whye Teh [Yee] unterscheiden:
1. Top-down vs. bottom-up vs. Monte Carlo search
2. Flat clustering (mixture models) vs. tree-structured
3. Algorithmic vs. probabilistic vs. Bayesian
Technisch ist die Erkennung eine Trennung des Hierarchical Clustering Baums an einer/mehrere bestimmten Höhe/n. Allgemein bekannt ist die einfache Methode der festen cut-off Höhe. Alle Äste in der spezifischen Höhe sind dann die Klassen. Das besondere bei der Trennung ist das Optimalitätskriterium. D.h., das Kriterium nach dem die optimale Höhe festgelegt wird, hinsichtlich der Erkennung "echter" Klassen. Angenommen das Kriterium ist tatsächlich optimal, so bildet sich eine optimale Unterscheidung der Klassen heraus. Das ästhetische an einem optimalem cut-off Kriterium ist, dass dies, meiner Ansicht nach, dem ursprünglichen Wunsch des Menschen entspricht ausreichend zu differenzieren und gleichzeitig so sehr in Kategorien zu denken, um Regeln bilden zu können. Zwischen den Klassen wird differenziert, innerhalb der Klassen wird pauschalisiert. Doch wann muss man differenzieren? Dies würde ein optimales cut-off Kriterium repräsentieren.
| Bisher sind beispielsweise folgende Kriterien für eine Cut-off Entscheidung bekannt: | |
| * | Nach Kannan 2000 [Kannan00]: |
Conductance wobei, sich dieses Kriterium auf einen gewichteten Graph bezieht. S ist dabei eine Menge von Eckpunkten und w(u,v) das Gewicht auf der Kante von u nach v. Liegen die erhobenen Daten als Relational-Werte vor, so repräsentiert das Gewicht den Abstand zwischen zwei Datenpunkten. | |
| * | Dynamic Tree Algorithm (z.B. beschrieben in [Langfelder]) |
"The dynamic tree cut algorithm works through iteration of an adaptive process of cluster decomposition and combination until the number of clusters becomes stable." [Langfelder] | |
| * | Multidimensional Binary Search Tree [Murtagh] |
"As an alternative to the crude non-hierarchical clustering technique just described, a crude, divisive, hierarchical approach is provided by a multidimensional binary search tree—a generalization of a binary search tree. At successive levels of the tree, some co-ordinate is chosen and all points are associated with one or other of two offspring nodes according to whether they take values less than or greater than some cut-off value on this coordinate. Continually subdividing the points in this way, we eventually halt with a set of buckets, where each, of the N points is associated with some one bucket." | |
Vorschlag
Der Vorschlag ist mir bisher so noch nicht begegnet. Es handelt sich jedoch um eine naheliegende Annahme.
Im Allgemeinen bietet sich an das Maximum des Vereinigungskriteriums zu verwenden, um eine cut-off Höhe zu definieren.
Das Vereinigungskriterium, auch Expansion genann, ist das Abstandsmaß, mit dessen Hilfe über den Zusammenschluss der Cluster zu einem neuen Cluster auf einer höheren Hierarchieebene entschieden wird.
Der cut-off wäre dann, wenn der der Abstand zwischen zwei aufeinander folgenden Höhen k und l, auf der Basis des durchschnittlichen Abstands zwischen Clustern in einer Höhe, maximal wird.
D.h. für jede Höhe k wird der Durchschnittlich der Abstände der Cluster berechnet, welche in diesem Schritt k vereinigt wurden. Der maximale Abstand dieser durchschnittlichen Abstände zwischen zwei aufeinander folgenden Höhen ist dann die Cut-Off Höhe.
Cluster_k = Cluster der Ebene k. Die Daten sind auf Ebene Null. Die Wurzel des Baumes auf der letzten Ebene.
Der durschnittliche Abstand ist,
D(k) = MEAN { d(a,b) | \forall a,b nebeneinander \in Cluster_k }.
Die cut-off Höhe k* ist dann,
k* = MAX { D(l)-D(k) | l = k+1 }.
Das Zusammenfügen weiterer Cluster in größerer Höhe als k* würde den maximalen durschnittlichen Abstand zwischen den Clustern zusammenschließen. Es kann sein, dass mehere Maxima mit den gleichen Werten existieren, dann gibt es unterschiedliche Differenzierungsstufen. Z.B. würde dies bezüglich des Kreditausfalls heißen grobe Differenzierung in Arm und Reich auf einer höheren Ebene, und detailiertere Differenzierung zwischen rotem und blauem Auto auf einer Tiefen Ebene.
Graphisch lässt sich das Kriterium auch am Hierarchical Tree, also dem Dendogramm, erklären. Der Cut befindet sich dann an der größten Lücke im Dendogramm entlang der Skale für die Abstände.
Dieses vorgeschlagene Kriterium ist nicht zwingend optimal. Die Frage, wann es sich um ein optimales Kriterium hinsichtlich der Klassifizierung handelt, bleiben offen.
Referenzen:
[Witten,Frank] : Ian H. Witten, Eibe Frank - "Data Mining" 2000
[Yee] : Yee Whye Teh 2008 Vortrag - http://videolectures.net/epsrcws08_teh_hc/ (checked 12.2009)
[Kannan] : R. Kannan, S. Vempala, and A. Vetta. "On Clusterings - Good,
Bad and Spectral." In IEEE Symposium on Foundations of Computer Science,
pp. 367—377. Los Alamitos, CA: IEEE Computer Society, 2000
[Langfelder] : Peter Langfelder, Bin Zhang, Steve Horvath, "Dynamic Tree Cut: in-depth description, tests and applications", Subblement of Genetics 5.2.2009
[Murtagh] : F. Murtagh, "A Survey of Recent Advances in Hierarchical Clustering Algorithms", computer journal, Vol. 26, No. 4, 1983
Auch interesannt ist:
* Gary William Flake, Robert E. Tarjan, and Kostas Tsioutsiouliklis "Graph Clustering and Minimum Cut Trees", Internet Mathematics Vol. 1, No. 4: 385-408, 2004
