Projektdokumentation Hierarchical Clustering

Hochschule Wismar
Fakultät für Ingenieurwissenschaften
Bereich Elektrotechnik und Informatik
Projektdokumentation
Hierarchical Clustering
Eingereicht am:
von:
19.Juni 2013
Nico Hassel
Ralf Tessmann
Konrad Klimmey
Inhalt
1 Einleitung................................................................................................................................................ 3
1.1
Einordnung und Definition .......................................................................................................... 3
1.2
Einsatzziele .................................................................................................................................. 4
2 Funktionsweise und Algorithmusbeschreibung ...................................................................................... 5
2.1
Verfahrensarten ........................................................................................................................... 5
2.2
Bestimmung der Cluster-Distanz ................................................................................................. 6
2.3
AHC (Agglomeratives Hierarchisches Clustering) Prinzip ......................................................... 7
3 Cobweb-Verfahren.................................................................................................................................. 9
3.1
3.2
Algorithmus ................................................................................................................................. 9
3.1.1
Operationen zur Hierarchiebildung .................................................................................. 9
3.1.2
Clusternützlichkeit ......................................................................................................... 10
3.1.3
Ablauf............................................................................................................................. 10
3.1.4
Bewertung ...................................................................................................................... 11
Beispiel ...................................................................................................................................... 12
4 Implementierung in Knime ................................................................................................................... 14
5 Ergebnisse und Auswertung ................................................................................................................. 18
5.1
5.2
Zeit- und Speicherkomplexität .................................................................................................. 20
5.1.1
Zeitkomplexität .............................................................................................................. 20
5.1.2
Speicherkomplexität ....................................................................................................... 20
Vergleich des Abstandes zwischen zwei Clustern ..................................................................... 20
6 Probleme und Zusammenfassung ......................................................................................................... 22
6.1
Während des Projektes aufgetretene Probleme ......................................................................... 22
6.2
Zusammenfassung ..................................................................................................................... 23
7 Literaturverzeichnis .............................................................................................................................. 24
Einleitung
1
Im Rahmen des Moduls „Wissensextraktion“ des Master-Studiengangs Multimedia
Engineering wurde eine Projektarbeit zum Thema Hierarchisches Clustern von
Datenmengen durchgeführt.
Im Rahmen dieser Dokumentation werden die theoretischen Grundlagen des
hierarchischen Clusterns und die Funktionsweise des Algorithmus beschrieben.
Weiterhin werden die Ergebnisse einiger Experimente spezieller hierarchischer
Verfahren mit der Entwicklungsumgebung „Knime“ vorgestellt. Dafür wurden
verschiedene Datenmengen analysiert und Workflows generiert um die Performance
und die Qualität der Clusterergebnisse im Vergleich zu anderen Verfahren zu
evaluieren.
1.1
Einordnung und Definition
Das allgemeine Ziel des Clusterings ist die Aufteilung einer Datenbank in mehrere
Gruppen (Cluster), wobei die Elemente innerhalb einer Gruppe möglichst ähnlich und
Elemente aus unterschiedlichen Gruppen möglichst unähnlich sind. Grundlegend
werden dabei nachfolgende Cluster-Verfahren unterschieden.

Partitionierende Verfahren
Der Datenraum wird in nicht überlappende Teilmengen zerlegt. Jedes
Element gehört genau einem Cluster an und jeder Cluster enthält
mindestens ein Element.

Dichtebasierte Verfahren
Cluster sind Gebiete im n-dimensionalen Raum, in denen eine hohe
Objektdichte zu finden ist. Dichte Gebiete sind getrennt von Gebieten mit
geringer Objektdichte. Ziel des Verfahrens ist die Identifizierung solcher
Gebiete mit hoher Objektdichte.

Hierarchische Verfahren
Im Gegensatz zu partitionierenden Algorithmen wird eine Sequenz
ineinander verschachtelter Teilmengen gebildet. Dabei wird eine
Baumstruktur erzeugt, bei der ein Knoten jeweils einen Cluster darstellt.
Die Baumwurzel entspricht dabei einem Cluster mit der gesamten
Datenmenge und die Blätter repräsentieren Cluster mit jeweils nur einem
einzigen Element. Je nach Anwendung und Datenstruktur kann ein
Ausschnitt mit geeigneten Clustering ausgewählt werden bzw. abgeleitet
werden.
1.2
Einsatzziele
Hierarchisches Clustering wird z.B. bei Datenmengen mit hierarchischen Strukturen
eingesetzt, wie z.B. Abstammungslinien bei Lebewesen. Ebenfalls weit verbreitet ist der
Einsatz beim Textmining, wobei ähnliche Dokumente gruppiert werden. Google News
sammelt z.B. News Artikel aus über 4000 Quellen und ordnet die Artikel zu Clustern
zu, die verschiedene Gruppen repräsentieren. Basierend auf Dokumentensammlungen
können dann Vorhersageverfahren gelernt werden, mit denen neue Dokumente richtig
eingegliedert werden. Dieser Prozess wird durch automatische Clusterverfahren deutlich
vereinfacht, da die Kategorisierung einer Dokumentensammlung durch einen Menschen
viel zu aufwendig und teuer wäre.
Bild 1: Einordnung bei Google News [3]
2
2.1
Funktionsweise und Algorithmusbeschreibung
Verfahrensarten
Beim Aufbau einer hierarchischen Cluster-Struktur unterscheidet man zwei Arten:
agglomerative Verfahren und divisive Verfahren. Sie unterscheiden sich vorwiegend
darin, ob Cluster getrennt bzw. verschmolzen werden.
Agglomerative Verfahren (Bottom-Up)
Bei diesem Verfahren wird zunächst jedes Element im Datensatz als ein eigener Cluster
initiiert. Anschließend werden schrittweise jeweils zwei Cluster zu einem neuen Cluster
verschmolzen. Dieser Vorgang läuft solange, bis alle Objekte zu einem einzigen Cluster
zusammengefasst sind. Es werden immer die Cluster miteinander verschmolzen, die
sich maximal ähnlich sind. Der Baum wird demnach von unten nach Oben aufgebaut,
weshalb diese Verfahren auch als Bottom-Up bezeichnet werden. Das Bottom-UpVerfahren ist das am häufigsten angewendete hierarchische Cluster-Verfahren.
Divisive Verfahren (Top-Down)
Im Gegensatz zu den Bottom-Up Verfahren, wird hier die Baumstruktur von der Wurzel
bis zu den Blättern generiert. Es wird mit der kompletten Datenmenge begonnen, die
einen einzigen Cluster darstellt. Anschließend findet eine schrittweise Zerlegung in
einzelne Cluster statt, bis jedes Element wieder einen einzigen Cluster darstellt. Da
dieser Algorithmus sehr aufwendig ist, weil in jeder Interaktion 2k-1 mögliche
Zerlegungen des k-elementaren Clusters in zwei Child-Cluster untersucht werden
müssen, ist die Anwendung in der Praxis nur wenig verbreitet.
Bild 2: Top-Down vs. Bottm-Up Verfahren
2.2
Bestimmung der Cluster-Distanz
Nachfolgend werden die drei am weitesten verbreiteten Berechnungsmethoden für die
Cluster-Distanz beschrieben.
Bild 3: Cluster-Distanzen
Single Link
Beim Single Link- Verfahren wird die Distanz zwischen einem Cluster A und einem
Cluster B als der minimale Abstand über alle Objektpaare aus beiden Clustern definiert.
(
) = min
,
∈ ,
∈
( , )
Complete Link
Die Distanz zwischen Cluster A und B wird hier als der maximale Abstand über alle
Objektpaare auf beiden Clustern definiert:
(
) = max
,
( , )
∈ , ∈
Der Complete-Ansatz erzeugt Cluster mit minimiertem Durchmesser. Dadurch werden
in der Regel eher kleine und stark voneinander separierte Cluster mit ähnlichem
Durchmesser gebildet. Ebenfalls werden eher Cluster mit wenigen Elementen erzeugt.
Average Link
Die Distanz bei der Average Methode zwischen Cluster A und B gibt den
durchschnittlichen Abstand über alle Objektpaar beider Cluster wieder:
(
,
)=
1
| |∗| |
( , )
∈ , ∈
Die Berechnung erfolgt aus allen paarweisen Distanzen der Clusterobjekte und nicht
wie bei Single Link bzw. Complete-Link
Complete Link aus einer einzelnen Distanz zwischen zwei
Objekten. Daher ist hier die Laufzeit bzw. Speicherkomplexität auch höher als bei
anderen Methoden.
Die Distanz
stanz zwischen zwei Clustern lässt sich rekursiv durch die sogenannte Lance
LanceWilliams Rekursionsformel
formel bestimmen:
dist(i + j, k) = ∝ i dist((i, k)+∝ j dist(j, k) + β dist(i, j) + γ| dist(i, k
k) − dist(j, k)|
Die Formel ermöglicht die Berechnung der Distanz zwischen einem
inem neuen Clusters,
bestehend aus Subcluster i und j und dem Cluster k. Die Parameter α,, β und γ werden
spezifisch für das jeweilige Verfahren ausgewählt:
α
α
β
γ
Single-Link
1/2
1/2
0
-1/2
Complete-Link
1/2
1/2
0
1/2
0
0
Average-Link
||
||
| |+| |
| |+| |
Tabelle 1:
1 Parameter Lance-Williams Rekursionsformel
2.3
AHC (Agglomeratives Hierarchisches Clustering) Prinzip
Ein sehr simpler und intuitiver Algorithmus ist der nach dem Bottom
Bottom-Up Prinzip
arbeitende AHC Algorithmus:

Jedes Objekt wird einen eigenem Cluster zugeordnet
zugeordne

Die beiden Cluster, deren Distanz minimal ist, werden verschmolzen.

Schritt 2 wird wiederholt bis nur ein Cluster übrig ist und Abbruchkriterium
nicht erfüllt ist
Für das optionale Abbruchkriterium kann z.B. eine bestimmte Anzahl k von Clustern
festgelegt werden, wodurch bei n Objekten in der Datenbank im 2. Schritt dann nur n-k
statt n Vereinigungsoperationen notwendig wären.
Die erzeugte Cluster-Struktur lässt sich z.B. durch ein Dendrogramm darstellen. Dabei
handelt es sich um ein 2-dimensionales Diagramm, welches die Baumstruktur
widerspiegelt. Ein Knoten entspricht dabei einem Cluster. Auf der X-Achse werden die
Datenobjekte abgetragen und auf der Y-Achse wird angegeben, bei welchem Abstand
zwei Cluster verschmolzen wurden. Zur Bestimmung eines konkreten Clusterings wird
ein horizontaler Schnitt auf einem bestimmten Level durch das Dendrogramm gezogen.
Bild 4: Darstellung der Cluster-Struktur in einem Dendrogramm
Cobweb-Verfahren
3
Ein bekannter Vertreter der hierarchischen Clusterverfahren ist COBWEB. Der
Algorithmus arbeitet inkrementell und nicht iterativ mit der gesamten Datenmenge,
sondern clustert die Daten Instanz für Instanz, wobei jede Instanz genau einmal
behandelt wird. COBWEB lässt sich in die agglomerativen Verfahren einordnen, da
neue Instanzen als Blatt in die Hierarchie eingefügt werden und bis zur Wurzel
miteinander geclustert werden. Das Endprodukt ist ein einziger Cluster, doch während
des Clusterungsprozesses lassen sich die Datenobjekte als hierarchische Baumstruktur
darstellen.
Die Cluster selbst werden mit Wahrscheinlichkeitsangaben beschrieben, welche
angeben wie oft ein Wert bei einem Konzept vorkommt. Dazu werden bei jedem Cluster
alle zugehörigen Objekte gespeichert, aus denen die Häufigkeit der Attribut-Werte
gezählt und daraus die Wahrscheinlichkeiten berechnet werden.
3.1
Algorithmus
Die Bildung der hierarchischen Struktur wird mit vier Grundoperationen vollzogen:
add, new, split und merge. Die Clusterbildung selbst erfolgt über die Berechnung der
Clusternützlichkeit für verschiedene Operationskombinationen und der vergleichenden
Bewertung dieser.
3.1.1
Operationen zur Hierarchiebildung
Add fügt den Datenpunkt D
versuchsweise in jedes bereits vorhandene Cluster
C
ein und bildet eine neue Partition P
D
besteht und bildet eine neue Partition P
.
−
Die Operation new ergänzt die aktuelle Partition P um ein neues Cluster C, das nur aus
.
Merge ist in der Lage, zwei einzelne Cluster zu kombinieren, split hingegen zerlegt
einen
Cluster
in
seine
Nachfolger.
Diese
zwei
Operationen,
auch
Restrukturierungsoperatoren genannt, sollen die Reihenfolgesensitivität gegenüber den
Eingabeobjekten verringern.
3.1.2
Clusternützlichkeit
Die Anordnung der Instanzen erfolgt anhand eines Gütekriteriums, der so genannten
Clusternützlichkeit. Im Allgemeinen wird die Abkürzung CU für Cluster Utility als
Bezeichnung genutzt. Diese ist ein Maß der Qualität einer Aufteilung der Instanzen auf
die einzelnen Cluster. Das Ziel der CU ist die Bewertung verschiedener
Operationsmöglichkeiten und damit die Verbesserung der Ähnlichkeit innerhalb der
Cluster, wie auch die Maximierung von Unterschieden zwischen den verschiedenen
Clustern.
Sie ist für eine Partition (C1 ,...,C
) von Clustern folgendermaßen definiert:
Im Zähler dieses Ausdrucks steht die Summe der a-priori-Wahrscheinlichkeiten aller zu
bewertenden Cluster, jeweils multipliziert mit der Doppelsumme der Differenz
zwischen der Wahrscheinlichkeit dafür, dass das i-te Attribut der betrachteten Instanz
den Attributwert V
annimmt unter der Bedingung, dass die Instanz dem Cluster C
zugeordnet wurde, und der unbedingten Wahrscheinlichkeit dafür, dass das i-te Attribut
den Wert V
hat.
Dieser Term wird durch die Gesamtanzahl der Cluster k geteilt. Dieses k im Nenner ist
ein empirischer Parameter, der Overfitting verhindert.
Es ergibt sich also die Clusternützlichkeit aus dem Vergleich der Anzahl der
Attributwerte, die mit dem neuen Cluster richtig vorhergesagt werden können (1.Term
der Doppelsumme) und der Anzahl derer, die ohne das neue Cluster vorhergesagt
werden können (2.Term der Doppelsumme).
3.1.3
Ablauf
COBWEB startet mit einer leeren Clusterung P, also mit einem Baum, der nur aus der
Wurzel besteht. Für jede Instanz, die in die Hierarchie eingefügt werden soll, muss nun
bestimmt werden, ob sie ein neues Cluster unter der Wurzel bildet oder zu einem bereits
bestehenden Cluster hinzugefügt wird. Dazu dienen die Operatoren add und new. Für
diese werden nun die Partitionen aus P
bzw. P
gespeichert, die die
−
größten und die zweitgrößten Werte bezüglich der CU haben. COBWEB kann nun seine
zwei so genannten Restrukturierungsoperatoren merge und split anwenden. Merge
versucht für den Fall, dass die Instanz einem neuen Cluster zugeordnet wurde, mit Hilfe
der beiden eben erwähnten größten Werte der CU, die betreffenden zwei Cluster zu
vereinigen, um die CU noch weiter zu steigern. Split versucht genau den
entgegengesetzten Fall zu betrachten, nämlich die CU zu steigern, indem ein Cluster mit
der maximalen CU in zwei neue Cluster aufgespalten wird und der Algorithmus
anschließend rekursiv ausgeführt wird, um zu prüfen, ob das Einordnen der Instanz bei
einem der Kinder mehr Effekt hat. Auch für merge und split werden die Partitionen mit
den besten Werten der CU aus P
P
und schließlich terminiert der
Algorithmus, indem er die Partition auswählt, die insgesamt die Category Utility
maximiert.
Der Algorithmus ist nachfolgend in Pseudo-Code angegeben:
3.1.4
Bewertung
Ein Problem bei der Anwendung des COBWEB-Algorithmus ist, dass bei der
Berechnung
der
Category
Utility
die
Unabhängigkeit
der
Wahrscheinlichkeitsverteilungen der einzelnen Attribute vorausgesetzt wird, um gute
Ergebnisse zu erhalten, was aber in der Realität selten auch nur annähernd der Fall ist.
Desweiteren ist die Berechnung und Speicherung der Werte der CU sehr aufwändig,
sowohl was den Laufzeit-, als auch den Speicherplatzbedarf betrifft. Aus diesen
Gründen ist COBWEB für große Datenmengen eher ungeeignet.
3.2
Beispiel
Als kurzes Beispiel soll eine Tabelle mit vier Datensätzen und je vier Attributen dienen.
Es werden die physischen Eigenschaften verschiedener Klassen der Wirbeltiere
abgebildet.
Tabelle 2: Cobweb Beispiel
Der COBWEB-Algorithmus fügt nun die einzelnen Datensätze in die Baumstruktur ein
(Bild4). Bei jedem Schritt wird die Clusternützlichkeit aller Möglichkeiten berechnet
und daraus entschieden welche Operation ausgeführt wird. In diesem Beispiel werden
die Instanzen als eigener Cluster einfügt (new), mit Ausnahme von "Bird" und
"Mammal". Hier ergab die Operation add eine höhere Clusternützlichkeit.
Bild 5: Cobweb Baumstruktur
Zur Veranschaulichung einer solchen Berechnung soll der Algorithmus davon
ausgehen, das "Fish", "Amphibian" und "Mammal" bereits als eigene Cluster mittels
new eingefügt wurden. Nun gilt es zu entscheiden, ob bei der Einführung der neuen
Instanz "Bird" new oder add zu bevorzugen ist. Split und merge sind aus Gründen der
Einfachheit zu vernachlässigen.
CU für new:
Anzahl der Cluster: k=4
Fish (C1):
P_C1 = 0.25 * ((1² - 0.25²) + (1² - 0.25²) + (1² - 0.5²) + (1² - 0.5²))
Amphibian (C2):
P_C2 = 0.25 * ((1² - 0.25²) + (1² - 0.25²) + (1² - 0.5²) + (1² - 0.5²))
Mammal (C3):
P_C3 = 0.25 * ((1² - 0.25²) + (1² - 0.5²) + (1² - 0.5²) + (1² - 0.5²))
Bird (C4):
P_C4 = 0.25 * ((1² - 0.25²) + (1² - 0.5²) + (1² - 0.5²) + (1² - 0.5²))
CU_new = (P_C1 + P_C2 + P_C3 + P_C4) / k
CU_new = 0.8203
CU für add:
Anzahl der Cluster: k=3
Fish (C1):
P_C1 = 0.25 * ((1² - 0.25²) + (1² - 0.25²) + (1² - 0.5²) + (1² - 0.5²))
Amphibian (C2):
P_C2 = 0.25 * ((1² - 0.25²) + (1² - 0.25²) + (1² - 0.5²) + (1² - 0.5²))
Mammal/Bird (C5): P_C5 = 0.5 * (((0.5² - 0.25²) + (1² - 0.5²) + (1² - 0.5²) + (1² - 0.5²))
+ ((0.5² - 0.25²) + (1² - 0.5²) + (1² - 0.5²) + (1² - 0.5²)))
CU_add = (P_C1 + P_C2 + P_C5) / k
CU_add = 1.3750
Die Berechnung zeigt, das ein hinzufügen in einen bereits vorhandenen Cluster die
Clusternützlichkeit erhöht. Das MATLAB-Skript zur Berechnung liegt im Anhang.
Implementierung in Knime
4
Mit Hilfe des Konstanz Information Miner (Knime) können interaktive Datenanalysen
durchgeführt werden. Es ermöglicht die Integration zahlreicher Verfahren des
maschinellen Lernens und des Data-Mining. Die graphische Benutzeroberfläche erlaubt
das einfache und schnelle Aneinandersetzen von Modulen. Diese zusammenhängenden
Module werden als Workflow bezeichnet und dienen der Datenvorverarbeitung,
Modellierung, Analyse und Visualisierung. Die beiden folgenden Workflows
visualisieren hierarchische Clustering-Verfahren die mit der Bottom-up-Methode
arbeiten. In Bild 6 sind ausschließlich Standardwerkzeuge abgebildet. Das in Bild 8
dargestellte Cobweb-Werkzeug ist in einer Erweiterung namens WEKA implementiert.
Bild 6: Hierarchical Clustering (Standardwerkzeug in Knime)
Aufgaben der einzelnen Werkzeuge:

File Reader: Mit dessen Hilfe werden Datensätze eingelesen. Es ist weiterhin
möglich bestimmte Spalten für die spätere Verarbeitung auszuschließen.

Hierarchical Clustering: Dieses Werkzeug führt das hierarchische Clustering
durch. Es ist nur für kleine Datensätze geeignet. Es können ebenfalls bestimmte
Spalten für die spätere Verarbeitung entfernt werden. Darüber hinaus ist es
möglich, dass beim hierarchischen Clustering erstellte Dendrogramm anzeigen
zu lassen (Bild 7). Die genauen Einstellungsmöglichkeiten werden in Tabelle 3
aufgelistet.

Scorer: Vergleicht die Attributwerte zweier Spalten und ermöglicht die
Darstellung einer Confusion Matrix.

Color Manager: Dieses Werkzeug ordnet jedem einzelnen Datensatz eine Farbe
entsprechend des eingeordneten Clusters zu. Es kann für numerische und
nominale Daten eingesetzt werden. Die Farben sind frei wählbar.

Scatter Plot: Mit dessen Hilfe ist es möglich ein Streudiagramm zu generieren.
Dieses Diagramm bezieht sich auf zwei auswählbare Spalten des Datensatzes.
Bild 7: Beim Hierarchical Clustering erzeugtes Dendrogramm
Hierarchical Clustering
Parameter
Beschreibung
Wert
Number output Clusters
Gibt die Anzahl der Ausgabe-Cluster an
3
Distance function
Bestimmt das zu verwendende Abstandmaß.
(Euclidean, Manhattan)
Euclidean
Linkage type
Legt die Distanzberechnung zwischen den
Clustern fest(Average, Single, Complete)
Single
Exclude / Include
Hier wird festgelegt welche Daten relevant sind
Tabelle 3: Eigenschaften Hierachical Clustering
Bild 8: Cobweb (Werkzeug in WEKA-Erweiterung)
Aufgaben der einzelnen Werkzeuge:

File Reader: Mit dessen Hilfe werden Datensätze eingelesen. Es ist weiterhin
möglich bestimmte Spalten für die spätere Verarbeitung auszuschließen.

Cobweb: Dieses Werkzeug ist in der Erweiterung namens WEKA
implementiert. Es führt das hierarchische Clustering aus. Dieses Werkzeug
beinhaltet das Classit-Verfahren für numerische Datensätze und das CobwebVerfahren für nominale Datensätze. Beim Cobweb ist es nicht möglich einzelne
Spalten des Datensatzes auszuschließen. Dieser Schritt muss im File Reader
vorgenommen werden. Desweiteren gibt es keine Funktion sich das
Dendrogramm anzeigen zu lassen. Die genauen Einstellungsmöglichkeiten
werden in Tabelle 4 aufgelistet.

Weka Cluster Assigner: Mit diesem Werkzeug kann man sich anzeigen lassen,
welche Datensätze in welchen Cluster eingeordnet wurden.
Cobweb
Parameter
Beschreibung
Wert
Acuity
Bestimmt die minimale Distanz für numerische Attribute
1
Cutoff
Legt die Grenze für die Clusternützlichkeit fest
0.002
SaveInstanceData
Speichert Informationen für Visualisierungszwecke (False,
True)
False
Seed
Zufällig gewählter Initialwert
42
Tabelle 4: Eigenschaften Cobweb (WEKA)
Bei dem Cobweb-Verfahren ist darauf zu achten, dass die Spalte der Zielattribute nicht
versehentlich mit geladen wird. Beim K-Means- und hierarchical Clustering-Verfahren
werden diese Spalten automatisch entfernt. Bild 9 zeigt wie man Spalten manuell im
File Reader entfernen kann.
Bild 9: File Reader Spalte nicht mit einbeziehen
5
Ergebnisse und Auswertung
Im folgenden Abschnitt werden die Ergebnisse der beiden Clustering-Werkzeuge und
des K-Means-Werkzeuges miteinander verglichen. Dazu werden die einzelnen
Confusion Matrizen des Scorer (hierachical Clustering und K-Means) und die
geclusterten Daten des WEKA Cluster Assigner (Cobweb) ausgewertet. Für den
Vergleich wurde der in Knime vorhandene Datensatz „IrisDataset“ verwendet. Bild 10
und Bild 11 zeigen jeweils ein Beispiel.
Bild 10: geclusterte Daten des WEKA Cluster Assigner
Bild 11: Confusion Matrix des Scorer (Single Link Euklidische Distanz)
Die Qualität der Ergebnisse beim hierarchischen Clustering-Verfahren ist generell höher
als beim K-Means-Verfahren, da der beim hierarchischen Clustering entstandene
Binärbaum beliebig zugeschnitten werden kann. Dadurch ist es möglich eine brauchbare
und zweckmäßige Anzahl von Clustern direkt aus dem Baum abzuleiten. Beim KMeans hingegen werden mehrere Durchläufe mit verschiedenen k durchlaufen, um die
Varianz zu berechnen.
Die besten Ergebnisse wurden mit dem Cobweb-Verfahren erzielt, als der Acuity-Wert
durch Ausprobieren auf 0,57 eingestellt wurde (Tabelle 5). Der Parameter muss den
numerischen Werten in der Datenbank angepasst werden.
Verfahren
Eingestellte Parameter
K-Means
hierachical
Clustering
hierachical
Clustering
hierachical
Clustering
hierachical
Clustering
hierachical
Clustering
hierachical
Clustering
Cobweb
Cobweb
3 Cluster
Euklidische Distanz
Average Link
Euklidische Distanz
Complete Link
Euklidische Distanz
Single Link
Manhattan Distanz
Average Link
Manhattan Distanz
Complete Link
Manhattan Distanz
Single Link
acuity = 0,57
acuity = 1
Punkte richtig
zugeordnet
133
136
126
102
112
134
101
138
nur 2 Cluster erzeugt
Tabelle 5: Ergebnisse der verschiedenen Cluster-Verfahren
5.1
Zeit- und Speicherkomplexität
5.1.1
Zeitkomplexität
Die Berechnung aller Abstände zwischen den Clustern hat eine Komplexität von O(m²).
Bei jedem Schleifendurchlauf werden zwei Cluster miteinander verschmolzen. Deshalb
wird die Schleife m-1 mal durchlaufen. Demzufolge gibt es in der i-ten Wiederholung
m-i+1 Cluster. Anschließend werden zwei Cluster mit dem geringsten Abstand
zueinander ausgewählt. Dabei kann es vorkommen, dass dies eine Komplexität von
O((m-I+1)²) zur Folge hat. Danach werden m-i Abstände zwischen den Clustern
erneuert. Im i-ten Durchlauf entsteht somit eine Komplexität von O((m-i+1)²) bei O(m)
Wiederholungen. Die daraus resultierende Gesamtlaufzeit beträgt O(m³). Durch
geeignete Suchverfahren und Datenstrukturen (geordnete Listen) ist eine Verkürzung
der Laufzeit auf O(m²log m) möglich. Das K-Means-Verfahren ist wesentlich einfacher
aufgebaut und weist eine Zeitkomplexität von O(m²) auf.
5.1.2
Speicherkomplexität
Das Cluster wird für jeden zugeordneten Punkt gespeichert. Der dafür eingesetzte
Speicher ist linear in der Anzahl der Punkte. Wie zuvor, bei der Zeitkomplexität
erwähnt, werden die Abstände zwischen allen Clustern gespeichert. Im Falle eines
symmetrischen Abstandsmaßes beträgt dies O(1/2m²). Damit beträgt die gesamte
Speicherkomplexität O(m²). Das K-Means-Verfahren besitzt wie schon bei der
Zeitkomplexität eine Speicherkomplexität von O(m).
5.2
Vergleich des Abstandes zwischen zwei Clustern
In der Tabelle 5 ist zu erkennen, dass die Auswahl des Verfahrens zur
Abstandsermittlung zwischen zwei Clustern eine große Auswirkung auf das Ergebnis
haben kann. Die geeignete Auswahl des Verfahrens hängt sehr stark von den zu
clusternden Datensätzen und dem zu verwendenden Distanztyp ab (Euklidische- oder
Manhattandistanz). Für den in Knime vorhandenen Datensatz „IrisDataset“ hat sich
herausgestellt, dass für das hierarchical Clustering-Verfahren das Average-LinkVerfahren in Kombination mit der Euklidischen Distanz die besten Ergebnisse liefert.
Verfahren zur Abstandsermittlung

Single Link:
- kann bei großen Datenmengen zu kettenförmigen Clustern
führen  starke Streuung und langgezogene Struktur
- kann Cluster nicht-elliptischer Form entdecken
- ist empfindlich gegenüber Ausreißern und Geräusch

Complete Link: - generiert tendenziell kleine, stark voneinander abgegrenzte
Cluster mit ähnlichem Durchmesser  tendiert dazu, große
Clusters zu spalten
- Clusterelemente haben geringen Abstand
- Erzeugung vieler Cluster mit eher wenig Elementen
- ist wenig empfindlich gegenüber Ausreißern und Geräusch

Average-Link:
- niedrige Empfindlichkeit gegenüber Ausreißern und Geräusch
- bevorzugt kugelförmige Clusters
- Clusterergebnisse liegen in ihrer Struktur zwischen den
langgezogenen Ketten des Single-Links Clustering und den stark
abgegrenzten Clustern des Complete Link Clustering
6
6.1
Probleme und Zusammenfassung
Während des Projektes aufgetretene Probleme
In diesem Abschnitt werden kurz einige Probleme geschildert, die während des
Projektablaufes auftraten.
Obwohl in allen, zum Thema passenden, Dokumentationen bzgl. des CobwebWerkzeuges davon die Rede ist, dass auch nominale Daten verarbeitet werden können,
war es nicht möglich diese zu verarbeiten (Bild 12). Verwendeter Datensatz
„data_dmc2002_train_1750.txt“.
Bild 12: Fehler mit nominalem Datensatz beim Cobweb-Werkzeug
Da die Datensätze der verschiedenen Datamining- Cups zu komplex waren und eine zu
zeitintensive Datenvorbereitung in Anspruch genommen hätte, haben wir uns dazu
entschlossen auf den in Knime vorhandenen Datensatz „IrisDataset“ zurückzugreifen.
Dieser ist ausreichend um die Funktionsweise der einzelnen Clustering-Verfahren zu
veranschaulichen und zu vergleichen.
Desweiteren sind die Visualisierungsmöglichkeiten für die einzelnen WEKAKomponenten nicht besonders vielfältig. So war es uns beispielsweise nicht möglich die
zugeordneten Cluster darzustellen.
6.2
Zusammenfassung
Grundsätzlich lässt sich festhalten, dass das hierarchische Clustering-Verfahren
bedeutend aufwändiger ist als K-Means. Daraus kann man ableiten, dass es für große
Datensätze ungeeignet ist. Die Qualität der Ergebnisse spricht allerdings ganz eindeutig
für das hierarchische Clustering-Verfahren. Aus diesem Grund ist es für detaillierte
Datenanalysen zu empfehlen. Ein weiterer Vorteil ist, dass man im Vorfeld keine
Aussage über die Anzahl der zu erstellenden Cluster treffen muss. Abschließend bleibt
zu sagen, dass das geeignetste Clustering-Verfahren von den vorliegenden Daten
abhängig ist.
7
Literaturverzeichnis
[1]
Schröer, Carsten, Hierarchisches Clustering mit minimalen ClusterDurchmessern, Paderborn, 2009
[2]
Mühlbeier, Georg, Clustering von Dokumenten mittels k-Means und HCL, Ulm,
2007
[3]
Sahoo, Nachiketa, Callan, P., James, Krishnan, Ramayya, Incremental
Hierarchical Clustering of Text Documents
[4]
Witten, Ian H., Frank, Eibe, Hall, Mark A., Data Mining, United States, 2011
[5]
Wroblewski, Michal, Stefanwski, Jerzy, Susmaga, Robert, A Hierarchical
Clustering Algorithm based on the Vector Space Model, Poznan, 2003
[6]
Sharma, Narendra, Bajpai, Aman, Litoriya, Ratnesh, Comparison the various
clustering algorithms of weka tools, Jaypee, 2012
[7]
Eberhardt, Stefan, Semisupervised K-means Clustering, Ulm, 2006
[8]
http://iwi.econ.uni-hamburg.de/IWIWeb/GetDocument.aspx?documentid=1331
[9]
http://www-m9.ma.tum.de/material/felix-klein/clustering/Methoden/
Hierarchisches_Clustern.php