View
0
Download
0
Category
Preview:
Citation preview
Hochschule Wismar
Fakultät für Ingenieurwissenschaften
Bereich Elektrotechnik und Informatik
Eingereicht am: 19.Juni 2013
von: Nico Hassel
Ralf Tessmann
Konrad Klimmey
Projektdokumentation
Hierarchical Clustering
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 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
3.2 Beispiel...................................................................................................................................................................................................................................................... 12
4 Implementierung in Knime........................................................................................................................................................................................................................................... 14
5 Ergebnisse und Auswertung.......................................................................................................................................................................................................................................... 18
5.1 Zeit- und Speicherkomplexität................................................................................................................................................................................................................... 20
5.1.1 Zeitkomplexität...................................................................................................................................................................................................................... 20
5.1.2 Speicherkomplexität...............................................................................................................................................................................................................20
5.2 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
1 Einleitung
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 Funktionsweise und Algorithmusbeschreibung
2.1 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-Up-Verfahren 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.
dist SL❑ ( A ,B )=min x∈ A , y∈B❑dist (x , y)
Complete Link
Die Distanz zwischen Cluster A und B wird hier als der maximale Abstand über alle Objektpaare auf beiden Clustern definiert:
dist CL❑ ( A ,B )=max x∈ A , y∈B❑dist (x , y )
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:
dist AVG❑ ( A ,B )= 1|A|∗¿B∨¿ ∑
x∈ A, y∈Bdist (x , y )¿
Die Berechnung erfolgt aus allen paarweisen Distanzen der Clusterobjekte und nicht wie bei Single Link bzw. 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 zwischen zwei Clustern lässt sich rekursiv durch die sogenannte Lance-Williams Rekursionsformel bestimmen:
dist (i+ j , k)=∝i❑ dist (i ,k )+∝ j dist ( j , k )+β dist (i , j)+γ∨dist (i , k)−dist ( j ,k )∨¿
Die Formel ermöglicht die Berechnung der Distanz zwischen einem 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
Average-Link |i||i|+| j|
|i||i|+| j|
0 0
Tabelle 1: Parameter Lance-Williams Rekursionsformel
2.3 AHC (Agglomeratives Hierarchisches Clustering) Prinzip
Ein sehr simpler und intuitiver Algorithmus ist der nach dem Bottom-Up Prinzip arbeitende AHC Algorithmus:
Jedes Objekt wird einen eigenem Cluster zugeordnet
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
Place each object in a separate group While (!stop condition && groups number > 1) - find 2 most similar groups - link them
3 Cobweb-Verfahren
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 Di❑versuchsweise in jedes bereits vorhandene Cluster C j❑ein und bildet eine neue Partition Padd− j❑.
Die Operation new ergänzt die aktuelle Partition P um ein neues Cluster C, das nur aus Di❑ besteht und bildet eine neue Partition Pnew❑.
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❑,...,Ck❑) 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 Vij❑annimmt
unter der Bedingung, dass die Instanz dem Cluster Cl❑ zugeordnet wurde, und der unbedingten Wahrscheinlichkeit dafür, dass das i-te Attribut den
Wert Vij❑ 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 Padd− j❑bzw. Pnew❑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 Pmerge❑ Psplit❑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.
4 Implementierung in Knime
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 Cobweb-Verfahren 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 K-Means 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 Punkte richtig zugeordnet
K-Means 3 Cluster 133
hierachical ClusteringEuklidische Distanz
136Average Link
hierachical ClusteringEuklidische Distanz
126Complete Link
hierachical ClusteringEuklidische Distanz
102Single Link
hierachical ClusteringManhattan Distanz
112Average Link
hierachical ClusteringManhattan Distanz
134Complete Link
hierachical ClusteringManhattan Distanz
101Single Link
Cobweb acuity = 0,57 138
Cobweb acuity = 1 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-Link-Verfahren 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 Probleme und Zusammenfassung
6.1 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 Cobweb-Werkzeuges 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 WEKA-Komponenten 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 Cluster- Durchmessern, 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
Recommended