h1

h2

h3

h4

h5
h6
http://join2-wiki.gsi.de/foswiki/pub/Main/Artwork/join2_logo100x88.png

Efficient density-based methods for knowledge discovery in databases = Effiziente dichte basierte Methoden zur Wissensextraktion in Datenbanken



Verantwortlichkeitsangabevorgelegt von Ralph Krieger

ImpressumAachen : Publikationsserver der RWTH Aachen University 2008

UmfangVII, 239 S. : Ill., graph. Darst.


Aachen, Techn. Hochsch., Diss., 2008

Zusammenfassung in engl. und dt. Sprache


Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter


Tag der mündlichen Prüfung/Habilitation
2008-07-09

Online
URN: urn:nbn:de:hbz:82-opus-24799
URL: https://publications.rwth-aachen.de/record/50208/files/Krieger_Ralph.pdf

Einrichtungen

  1. Lehrstuhl für Informatik 9 (Datenmanagement und -exploration) (122510)
  2. Fachgruppe Informatik (120000)

Inhaltliche Beschreibung (Schlagwörter)
Data Mining (Genormte SW) ; Cluster-Analyse (Genormte SW) ; Dichtebasiertes Clusterverfahren (Genormte SW) ; Informatik (frei) ; Teilraum clustering (frei) ; Anytime Klassifikation (frei) ; Subspace clustering (frei) ; Anytime Classification (frei)

Thematische Einordnung (Klassifikation)
DDC: 004
ccs: H.2.8

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.

Today's data storage facilities allow recording of billions of transactions from business applications, scientific sensor readings, monitoring systems etc. Scientists developing new drugs, system administrators monitoring complex technical processes, and decision makers being responsible for complex social or technical systems require an overview and even a deeper understanding of their respective data. The knowledge discovery in databases (KDD) process has been designed to identify hidden patterns in large data resources. A central step of the KDD process is the data mining task. Major data mining tasks are clustering and classification. Density-based approaches have proven to be very effective for many data mining methods. However, the good effectiveness often comes at the cost of a high runtime complexity. This thesis presents new efficient density-based approaches for different data mining applications whereas the effectiveness of the new developed methods is always kept in mind. The first part of this thesis is concerned with new density-based clustering methods. Clustering is a data mining task for summarizing data such that similar objects are grouped together while dissimilar ones are separated. Density-based approaches have shown to successfully mine arbitrary shaped clusters even in the presence of noise. In multi-dimensional or high dimensional data, clusters are typically hidden by irrelevant attributes and do not show across the full space. As relevance of attributes is not globally uniform for all clusters, global dimensionality reduction approaches are not adequate. Subspace clustering aims at automatically detecting clusters and their relevant attribute projections. This work presents a new clustering model DUSC which guarantees a comparable and redundancy free subspace clustering result. As the number of possible subspaces is exponential in the number of dimensions subspace clustering is a computationally challenging task. The algorithm eDUSC developed in this work is based on a filter-and-refinement architecture which avoids repeated database scans. Further on, this work proposes a new visualization technique for subspace clusters and a specialized clustering technique for multi-dimensional sequence databases. The second part of this thesis proposes new density-based methods for classification. Classification aims at assigning a class label to unknown objects. Various approaches for classifying objects have been investigated in the last decades. Classifiers based on statistical approaches have been most intensively studied in the literature and results like asymptotical behavior and classification bias have been derived. To apply statistical classifiers the density of objects has to be estimated. In this work, a hierarchy of density estimators is proposed which makes the classification of objects possible anytime. Additionally, a new classification method using subspace clusters for higher dimensionalities is developed in this thesis. The proposed density-based clustering and classification methods are evaluated in terms of both efficiency and effectiveness in thorough experiments on real world and synthetic data.

Fulltext:
Download fulltext PDF

Dokumenttyp
Dissertation / PhD Thesis

Format
online, print

Sprache
English

Externe Identnummern
HBZ: HT015643146

Interne Identnummern
RWTH-CONV-112762
Datensatz-ID: 50208

Beteiligte Länder
Germany

 GO


OpenAccess

QR Code for this record

The record appears in these collections:
Document types > Theses > Ph.D. Theses
Faculty of Mathematics, Computer Science and Natural Sciences (Fac.1) > Department of Computer Science
Publication server / Open Access
Public records
Publications database
122510
120000

 Record created 2013-01-25, last modified 2022-04-22


Fulltext:
Download fulltext PDF
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)