Lehr- und Forschungseinheit für Datenbanksysteme Datenbanksysteme Database Systems

Projektarbeit

Datenkompression mittels BIRCH in Java

Inhalt

Der Clusteringalgorithmus BIRCH erzeugt einen CF-Tree. Die Phasen zur Erzeugung und Verkleinerung des Baumes werden nach Java portiert.

Problemstellung

BIRCH ist ein hierarchisches Clusteringverfahren, welches durch geschickte Reduzierung (Kompression) der Datten sehr effizient arbeitet. Es baut intern einen sog. CF-Tree auf, der statistische Informationen über die Daten speichert. Die Blätter dieses Baumes werden dann mit einem beliebigen globalen Algorithmus geclustert. Der Algorithmus zur Erzeugung des CF-Baumes soll nach Java portiert, getestet und optimiert werden.

Lösungsansatz

Der BIRCH Algorithmus wird analysiert, unnötige Klassen werden entfernt, sodann wird diese abgespeckte BIRCH Variante nach Java portieren. Zusätzlich wird eine Dokumentation mittels UML-Diagrammen der ursprünglichen wie auch der neuen Klassenstruktur erstellt.
Schließich werden ausführliche Leistungsmessungen durchgeführt.

Ziel

Ziel der Projektarbeit ist die Erstellung einer korrekten und lauffähigen Implementierung des CF-Baum Aufbaualgorithmus in Java zur Integration in dichte-basierte Data Mining Verfahren führen.

Tools

Personen

Bearbeiter Klaus Schneidenwind
Betreuer Markus Breunig

Arbeitsplan

Arbeitsabschnitt Zeitbedarf
BIRCH in C++ zum Laufen bringen 
  • Compilieren unter Linux 
  • Genaueres Verstehen des Algorithmus anhand des Sourcecodes 
  • Klassendiagramm mittels Rational Rose erzeugen.
 1 Woche
BIRCH in C++ abspecken
  • Überflüssigen Balast auskommentieren oder löschen
  • Änderungen mittels Tests validieren.
 3 Wochen
BIRCH in Java Implementieren
  • Einzelne Klassen in Java implementieren
  • Prüfen des Codes auf Richtigkeit
  • Erstellen eines Java Klassendiagramms mit Rational Rose
 4 Wochen
Validieren der Java-Implementierung mittels Tests 1 Woche
Leistungsmessungen durchführen. 1 Woche

Ergebnis

Das Klassendiagramm von BIRCH in C++ wurde erstellt und verwendet, um ein Klassendiagramm für die Java-Implementierung zu erstellen. Hierbei wurde speziell Wert auf die Vereinfachung der Klassenstruktur und das Programmcodes gelegt. Der Quellcode wurde von C++ nach Java portiert. Probleme beim Test und bei der Validierung der Ergebnisse wurden analysiert und gelöst. Leichte Unterschiede im Ergebnisse sind auf Rundungsfehler zurückzuführen. Die Java-Implementierung läuft und ist in das bestehende Data-Mining-Toolkit eingebunden.

Homepages: homeDBShomeInstituthomeLMU
19.06.2000 Klaus Schneidenwind