Der Begriff des Data Minings gewinnt für die
Verwaltung der Unmengen von Daten, die der aktuelle
Stand der Technik mit sich bringt, zunehmend an Relevanz.
Clustering ist ein wichtiges Teilgebiet des Data Mining
und beschäftigt sich damit, Muster in Datenstrukturen
zu erkennen, um so das gewonnene Wissen entsprechend
zu klassifizieren. Clustering wird mittlerweile in
Anwendungsbereichen, wie z.B. der Bestimmung von Benutzerguppen
auf dem Web oder der Erstellung von thematischen Karten
aus Satellitenbildern, eingesetzt. Nicht selten liegen
die zu clusternden Daten auf unterschiedlichen Rechnerknoten
vor, wobei es notwendig sein kann, eine Aussage darüber
treffen zu müssen, was für Clusterergebnisse
resultieren würden, wenn die Daten auf einem
zentralen Rechnerknoten existieren würden. Als
ineffizient hat es sich erwiesen, große Datenmengen
in dieser Ausgangssituation mit herkömmlichen
zentralen Clusteringverfahren abzuarbeiten. Größere
verteilte Datenmengen werden mittlerweile mit neueren
Clusteringstrategien abgehandelt, den verteilten Clusteringverfahren.
In dieser Arbeit wird ein Verfahren vorgestellt,
welches verteilte Daten dichtebasiert clustert. Dabei
wird jede am Vorgang teilnehmende verteilte Datenmenge
(Site) dichtebasiert geclustert und ein für das lokale
Clustering repräsentierendes Modell generiert. Diese
lokalen Modelle werden an einen globalen Knoten übertragen
und miteinander aggregiert. Aus der Aggregation resultiert
ein sogenanntes globales Modell, welches an jede teilgenommene
lokale Site übermittelt und zur Aktualisierung der
lokalen Modelle verwendet wird. Insgesamt findet ein
dichtebasiertes Clustering verteilter Daten statt.
Die experimentelle Evaluierung unserer Testdaten zeigt,
dass das hier vorgestellte Verfahren, im Gegensatz
zu herkömmlichen zentralen Clusteringverfahren, schnellere
Clusterergebnisse mit minimalem Qualitätsverlust liefert.
Aufgabenstellung
Die Aufgabenstellung dieser Arbeit besteht darin, einen
Algorithmus zu entwickeln, um das dichte-basierte Clustering
für verteilte Daten zu ermöglichen. Ausgangssituation
für den Algorithmus ist eine Menge M von verschiedenen
Domänen, die Daten beinhalten. Auf jeder Domäne
liegt eine Anzahl an unklassifizierten homogenen Daten.
Die Domänen werden in dieser Arbeit auch als Datenmengen,
Datenseiten oder Sites bezeichnet. Aufgabe des zu entwickelnden
Algorithmus soll sein, die vorhandenen verteilten Daten
in solch einer Art und Weise zu clustern, dass das Ergebnis
einem zentralen lokalen Clustering entspricht. Indirekt
entsteht daraus zusätzlich die positive Nebenwirkung,
dass umfangreiche Datenmengen, die gezielt in einzelne Teile
partitioniert und auf einem oder mehreren Rechnern ausgelagert
werden, parallel abgearbeitet werden können. Bei einer
beträchtlichen Anzahl an Gesamtdaten, was eine sehr
große Summe an Daten sämtlicher Domänen
bedeutet, soll der Algorithmus weiterhin qualitative Clusterresultate
mit guten Ergebniszeiten liefern. Ein dichte-basiertes Clusteringverfahren,
ähnlich zum DBSCAN Verfahren aus [EKSX96],
soll alle rechenintensive Schritte durchführen, um
somit die oben erwähnten Anforderungen zu erfüllen.
Tools
Folgende Hilfsmittel wurden in dieser Arbeit verwendet:
JDK 1.3 von Sun, Borland JBuilder, Eclipse,
Photo Impact, MS Excel, Ghostgum GSView 4.3,
PCTeX32 (LaTeX Editor), Ultra Edit,
MS Word, MS Power Point, MS Visio
Einarbeitung in die Thematik, Erarbeitung an Basiswissen,
Abarbeitung der Papers, Aufsuche geeigenter Literatur.
40 Tage
Analyse - Design
Analyse und Design der zu erstellenden Applikation.
Das Programm soll in der Programmiersprache Java realisiert
werden.
15 Tage
Implementierung
Implementierung des Prototyps, der graphischen Komponente
MainFrame, der DBDCUtility, der Klasse DBDCPoint, der
notwendigen Datenstrukturen wie KDTREE und Heap.
7 Tag
Implementierung und Einbettung mehrereUtilities wie
Merge und Knn
1 Tag
Verbesserung der graphischen Oberfläche
5 Tage
Einarbeitung in das WEKA-Framework, Spezifikation
der Speicherformate, Einbindung der WEKA-Klassen
5 Tage
Implementierung und Testen des erweiterten DBSCAN
3 Tage
Implementierung einer Kommandozeilenorientierten Version
des erweiterten DBSCAN
2 Tage
Implementierung und Testen von ExtendedKMeans
3 Tage
Implementierung und Testen der eigenen CURE Version
7 Tage
Implementierung und Testen von GlobalDBDC
3 Tage
Implementierung und Testen des Moduls Umlabeln
5 Tage
Implementierung des Statistik Programms zur Qualitätsbewertung
6 Tage
47 Tage
Evaluierung
Evaluierung von Clusterergebnissen mit Statistik-Programm
5 Tage
Validierung
Validierung: Generation künstlicher Testdaten und
Validierung der verteilten Clusterergebnisse
5 Tage
Erstellung der DA
Erstellung der Formatvorlagen und des Layouts der
Diplomarbeit
5 Tage
Erstellung aller Abbildungen, Graphiken und Formeln
8 Tage
Erstellung des Literaturverzeichnisses und des Abbildungverzeichnisses
1 Tag
Vorbereitung des Statistik Kapitels, Erstellung der
Tabellen, Diagramme und Protokollierung der Testergebnisse
5 Tage
Dokumentation des erstellten Verfahrens und Erstellung
der endgültigen Diplomarbeit
40 Tage
Korrektur und Verbesserung des endgültigen Dokuments
2 Tage
Vorbereitung des Vortrags und der Abbildungen des
Vortrags
7 Tage
68 Tage
Ergebnis
Mit dem hier vorgestellten DBDC-Verfahren wird gezeigt,
dass wenn verteilte Daten auch verteilt abgearbeitet werden,
ein effizientes Clustering erzielt wird. Die Technik mehrere
lokale, repräsentierende Modelle zu einem globalen
Modell miteinander zu aggregieren und dieses auf lokaler
Ebene geschickt einzusetzen, um eine Relation zwischen den
Daten, die die lokalen Modelle repräsentieren, zu generieren,
hat sich als sehr effektiv erwiesen.
Die wesentlichen Vorteile eines verteilten Verfahrens sind
somit ersichtlich. Obwohl die Qualität des Endergebnisses,
im Vergleich zu einem Verfahren, welches die verteilten
Daten auf einem zentralen Rechnerknoten vorliegen hat und
zentral clustert, nicht absolut gleichwertig ist, sind die
vielen bereits angesprochenen Vorteile, wie Effizienz, von
solch starker Bedeutung, dass der DBDC-Algorithmus als erfolgsversprechendes
Verfahren betrachtet werden kann.
Resultierendes Paper
Januzaj E., Kriegel H.-P., Pfeifle M.: Towards Effective and Efficient Distributed Clustering, Proc. Int. Workshop on Clustering Large Data Sets, 3rd Int. Conf. on Data Mining (ICDM 2003), Melbourne, FL, 2003, pp. 49-58.
Paper (pdf 441K)
DBS