h1

h2

h3

h4

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

Efficient knowledge discovery in subspaces of high dimensional databases = Effiziente Wissensextraktion aus Teilräumen hochdimensionaler Datenbanken



Verantwortlichkeitsangabevorgelegt von Emmanuel Alexander Müller

ImpressumAachen : Publikationsserver der RWTH Aachen University 2010

Umfang270 S. : graph. Darst.


Aachen, Techn. Hochsch., Diss., 2010

Zsfassung in engl. und dt. Sprache


Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter


Tag der mündlichen Prüfung/Habilitation
2010-06-09

Online
URN: urn:nbn:de:hbz:82-opus-33895
URL: https://publications.rwth-aachen.de/record/63728/files/3389.pdf

Einrichtungen

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

Inhaltliche Beschreibung (Schlagwörter)
Data Mining (Genormte SW) ; Wissensextraktion (Genormte SW) ; Cluster-Analyse (Genormte SW) ; Dichtebasiertes Clusterverfahren (Genormte SW) ; Ausreißer <Statistik> (Genormte SW) ; Evaluation (Genormte SW) ; Open Source (Genormte SW) ; Informatik (frei) ; Teilraum Clustering (frei) ; Teilraum Ausreißererkennung (frei) ; Teilraumprojektionen (frei) ; hochdimensionale Datenbanken (frei) ; subspace clustering (frei) ; subspace outlier mining (frei) ; subspace projections (frei) ; high dimensional databases (frei)

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

Kurzfassung
In vielen modernen Anwendungen wie der Analyse von Sensornetzwerken, Kundensegmentierung oder Genexpressionsanalyse werden große Datenmengen gesammelt. Da Datenerfassung und Speicherung billig sind, werden Benutzer häufig dazu verleitet so viel wie möglich zu erfassen. In heutigen Anwendungen werden somit für jedes Objekt viele Attribute verwendet um so viel Information wie möglich bereitzustellen. Dabei ist jedoch das wertvolle Wissen, welches man aus diesen Informationen gewinnen kann, in Teilmengen der gegebenen Attribute versteckt. Betrachtet man solche Teilräume, so erweitert man den Suchraum signifikant. Dies stellt neue Herausforderungen für Data Mining Techniken dar, die als Ziel haben dieses Wissen aus hochdimensionalen Datenbanken zu extrahieren. Diese Arbeit untersucht Clustering als eine der Hauptaufgaben des Data Mining. Clustering ist eine etablierte Technik zur Gruppierung von Objekten anhand ihrer Ähnlichkeit zueinander. Da jedoch traditionelle Clusteringansätze nicht fähig sind Gruppierungen in Teilräumen von hochdimensionalen Datenbanken zu erkennen, wurden Subspace Clustering Modelle entwickelt. Diese Modelle erkennen Gruppen von ähnlichen Objekten in Teilmengen der gegebenen Attribute. Da jedoch die Anzahl an möglichen Teilräumen exponentiell mit der Attributzahl steigt, ist die Entwicklung effizienter Techniken zur Wissensextraktion in Teilräumen von hochdimensionalen Datenbanken äußerst wichtig. In dieser Arbeit stellen wir sowohl neue Subspace Clustering Modelle als auch effiziente Methoden für deren Berechnung vor. Wir beginnen mit neuen Subspace Cluster Definitionen, welche die Erkennung von Gruppierungen in beliebigen Teilräumen ermöglichen. Wir beschreiben dabei allgemeine Herausforderungen, die durch die Redundanz in bisherigen Subspace Clustering Modellen bedingt sind und entwickeln neue redundanzfreie Subspace Clustering Definitionen. Unser Ziel ist dabei die Resultatgröße zu reduzieren um durch eine Optimierung der Ergebnismenge nur neues Wissen auszugeben. Durch diese Modellierung sind nicht alle Subspace Cluster für das Resultat von Relevanz. Basierend auf dieser allgemeinen Beobachtung entwickeln wir effiziente Berechnungsmethoden. Unsere neuen Algorithmen überwinden dabei die Effizienzprobleme, die durch den riesigen Suchraum beliebiger Teilraumprojektionen und auch durch die kostenintensiven Datenbankzugriffe bedingt sind. Hierfür wählen wir nur die erfolgversprechendsten Regionen für das Subspace Clustering aus. Insgesamt sind unsere Techniken auf großen hochdimensionalen Datenbanken anwendbar und geben dabei nur wenige aber dafür hochwertige Subspace Cluster aus. Als allgemeinen Beitrag für die Forschungsgemeinschaft vergleichen wir in einer systematischen Evaluierungsstudie eine große Anzahl an Verfahren. Wir untersuchen sowohl die Effizienz als auch die Qualität der wichtigsten Paradigmen. Für eine nachhaltige Forschung stellen wir sicher, dass sich alle empirischen Untersuchungen auf reproduzierbare und vergleichbare Ergebnisse stützen. Unser Evaluierungsrahmenwerk stellen wir als Open Source Projekt zu Verfügung. Dieses bietet eine Basis für zukünftige Forschung in diesem Bereich. Diese Arbeit stellt somit nicht nur neue Methoden zur effizienten Erkennung von Clustern aber auch Outliern vor, sondern ist auch Grundlage für einen reproduzierbaren Vergleich neuster Data Mining Techniken.

In many recent applications such as sensor network analysis, customer segmentation or gene expression analysis tremendous amount of data is gathered. As collecting and storing of data is cheap, users tend to record everything they can. Thus, in today's applications for each object one uses many attributes to provide as much information as possible. However, the valuable knowledge to be learned out of this information is hidden in subsets of the given attributes. Considering any of these subspaces one expands the search space significantly. This poses novel challenges to data mining techniques which aim at extracting this knowledge out of high dimensional databases. This work has its focus on clustering as one of the main data mining tasks. Clustering is an established technique for grouping objects based on mutual similarity. As traditional clustering approaches are unable to detect clusters hidden in subspaces of high dimensional databases, recent subspace clustering models have been proposed that detect groups of similar objects in any subset of the given attributes. However, as the number of possible subspaces scales exponentially with the number of attributes, development of efficient techniques is crucial for knowledge discovery in subspaces of high dimensional databases. In this work we propose both novel subspace clustering models aiming at high quality results and efficient processing schemes for these models. We start with novel subspace cluster definitions ensuring the detection of clusters in arbitrary subspaces. We highlight the general challenges of redundancy in recent subspace clustering models and propose novel non-redundant subspace clustering definitions. In this context, our aim is to reduce result sizes to all and only novel knowledge by optimizing the overall subspace clustering result. According to these models not all subspace clusters are valuable for the final result. Based on this general observation we propose efficient processing schemes. Our novel algorithmic solutions overcome efficiency problems caused by exhaustive search of almost all subspace projections and costly database access. We select only the most promising subspace regions for efficient subspace clustering. Overall, our techniques are scalable to large and high dimensional databases providing only few but high quality subspace clusters. Furthermore, as a general contribution to the community we provide a systematic evaluation study on a broad set of approaches. We show both efficiency and quality characteristics of major paradigms. As major aspect for sustained scientific research we ensure repeatability and comparability for all of our empirical results. Our evaluation framework is available as open source project and provides a basis for future enhancements in this research area. Thus, this thesis provides not only novel methods for efficient cluster and also outlier detection in subspaces of high dimensional data, but it is a fundamental basis for repeatable comparison of recent data mining approaches.

Fulltext:
Download fulltext PDF

Dokumenttyp
Dissertation / PhD Thesis

Format
online, print

Sprache
English

Interne Identnummern
RWTH-CONV-125151
Datensatz-ID: 63728

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-28, last modified 2022-04-22


Fulltext:
Download fulltext PDF
Rate this document:

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