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