Efficient density-based methods for knowledge discovery in databases

• Effiziente dichte basierte Methoden zur Wissensextraktion in Datenbanken

Krieger, Ralph; Seidl, Thomas (Thesis advisor)

Aachen : Publikationsserver der RWTH Aachen University (2008)
Doktorarbeit

Aachen, Techn. Hochsch., Diss., 2008

Kurzfassung

Moderne Datenspeicheranlagen ermöglichen die Erfassung von Billionen von Geschäftstransaktionen, wissenschaftlichen Sensormessungen, Meldungen von Überwachungssystemen etc. Verantwortliche Wissenschaftler in der Arzneimittelentwicklung, Systemadministratoren, die komplizierte technische Prozesse überwachen und Entscheidungsträger komplexer sozialer oder technischer Systeme benötigen eine Übersicht über bzw. einen tieferen Einblick in ihre erfassten Daten. Der Knowledge discovery in databases (KDD)-Prozess wurde entwickelt, um versteckte Muster innerhalb großer Datenbanken ausfindig zu machen. Ein zentraler Schritt des KDD Prozesses ist das Data Mining. Hauptaufgaben des Data Minings sind das Clustering und die Klassifikation von Daten. Dichtebasierte Ansätze haben sich als sehr effektive Data Mining Methoden bewährt. Jedoch bringt die hohe Effektivität eine hohe Laufzeitkomplexität mit sich. In dieser Doktorarbeit werden neue, effiziente, dichtebasierte Ansätze für verschiedene Datenanalyseanwendungen vorgestellt, wobei die Effektivität nicht außer Acht gelassen wird. Der erste Teil dieser Arbeit befasst sich mit neuen dichtebasierten Clustering Methoden. Clustering ist eine Data Mining Aufgabe, welche Daten so zusammenfasst, dass Gruppen ähnlicher Objekte von unähnlichen separiert werden. Dichtebasierte Ansätze haben sich als erfolgreich bei der Suche beliebig geformter Cluster innerhalb verrauschter Datensätze herausgestellt. In mehr- oder hochdimensionalen Daten werden Cluster normalerweise durch irrelevante Attribute versteckt und sind daher im vollen Datenraum nicht zu erkennen. Da die Relevanz von Attributen nicht für alle Cluster global einheitlich ist, können globale Dimensionsreduktionstechniken nicht sinnvoll eingesetzt werden. Die Zielsetzung von Subspace Clustering Algorithmen ist das automatische Auffinden von Clustern mit der zugehörigen Attributprojektion. Diese Arbeit präsentiert DUSC, ein neues Clustering Modell, das vergleichbare und redundanzfreie Clustering Ergebnisse garantiert. Aus Sicht des Berechnungsaufwandes stellt Subspace Clustering, wegen der exponentiellen Abhängigkeit der Anzahl möglicher Teilräume von der Anzahl Dimensionen, eine Herausforderung dar. Der Algorithmus eDUSC, welcher im Rahmen dieser Arbeit entwickelt wurde, basiert auf einer Filter-und-Verfeinerungsmethode, wodurch das wiederholte Durchsuchen der Datenbank vermieden wird. Weiterhin werden in dieser Arbeit Visualisierungstechniken für Subspace Cluster vorgestellt, sowie eine spezialisierte Clustering Technik für mehrdimensionale Sequenzdatenbanken. Im zweiten Teil dieser Doktorarbeit werden neue dichtebasierte Methoden zur Klassifikation vorgestellt. Das Ziel der Klassifikation ist die Bestimmung eines Klassenlabels für unbekannte Objekte. In den letzen Jahrzehnten wurden verschiedene Ansätze für die Klassifikation von Objekten vorgestellt. Klassifikatoren, welche auf statistischen Ansätzen basieren, wurden in der Literatur sehr intensiv untersucht und Ergebnisse über das asymptotische Verhalten und die Klassifikationstendenz wurden hergeleitet. Zur Anwendung statistischer Verfahren ist das Schätzen der Dichte für Objekte notwendig. In dieser Arbeit wird eine Hierarchie von Dichteschätzern vorgestellt, die Klassifikation von Objekten zu jedem Zeitpunkt möglich macht. Weiterhin wird in dieser Doktorarbeit ein neuer Klassifikator für hochdimensionale Daten auf Basis von Subspace Clusterings entwickelt. In umfangreichen Experimenten wird mit Hilfe von synthetischen und realen Daten sowohl die Effizienz als auch die Effektivität der vorgestellten dichtebasierten Clustering- und Klassifikationsmethoden untersucht.

Einrichtungen

• Lehrstuhl für Informatik 9 (Process and Data Science) [122510]
• Fachgruppe Informatik [120000]