Efficient knowledge discovery in subspaces of high dimensional databases

• Effiziente Wissensextraktion aus Teilräumen hochdimensionaler Datenbanken

Müller, Emmanuel Alexander; Seidl, Thomas (Thesis advisor)

Aachen : Publikationsserver der RWTH Aachen University (2010)
Doktorarbeit

Aachen, Techn. Hochsch., Diss., 2010

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.

Einrichtungen

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