Diplomarbeit

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.

Homepages: DBS Institut LMU
Last Modified: 2003-July-11