Moin DA
Diplomarbeit
Density Based Distributed Clustering Datenbanksysteme Datenbanksysteme Datenbanksysteme Database Systems

Diplomarbeit

"DICHTE-BASIERTES CLUSTERING VERTEILTER DATEN"

Inhalt - Abstract

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

Personen

Bearbeiter Konstantin Kirsch
Betreuer Eshref Januzaj

Arbeitsplan

Arbeitsabschnitt
Beschreibung
Zeitbedarf
Einarbeitung
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)


Homepages:  homeDBS homeInstitut homeLMU
Last Modified: 2003-July-11

[Home] [Stuff] [Fotogalerie] [IT] [OCI_Treiber] [JDBC] [JSP] [LDAP] [SOAP] [Diplomarbeit] [JAVA] [Profile] [Contact] [MyDomains]