Suchraumbeschränkung für relationales Data Mining

Abstract

Data Mining und Knowledge Discovery in Databases (KDD) sind Forschungs- und Anwendungsgebiete, die sich mit der Extraktion von nutzbarem Wissen aus Daten befassen. Dazu werden unter anderem Methoden des maschinellen Lernens eingesetzt. Die Induktive Logikprogrammierung ist ein Teilgebiet des Maschinellen Lernens, dessen Gegenstand das Lernen aus multi-relational und prädikatenlogisch repräsentierten Daten ist, während andere Lernverfahren üblicherweise Daten voraussetzen, die in Form einer einzelnen Attribut-Wert-Tabelle vorliegen. Der Einsatz von ILP-Methoden für KDD und Data Mining wird auch als Relationales Data Mining bezeichnet.

Ein Anwendungsgebiet von KDD und Data Mining ist die Teilgruppenanalyse. Dabei wird eine Population von Fällen, die in einer Datenbank repräsentiert sind, nach besonders interessanten Teilgruppen der Population durchsucht, indem mögliche Teilgruppen generiert und mithilfe geeigneter Interessantheitsfunktionen bewertet werden. Die vorliegende Arbeit hat sich zum Ziel gesetzt, Methoden zur sicheren Beschränkung des Suchraums bei der Suche nach interessanten Teilgruppen in multi-relationalen Daten zu erarbeiten und zu evaluieren. Dazu wird ein Verfahren zur Suche nach interessanten Teilgruppen in multi-relationalen Datenbanken entwickelt, das verschiedene Methoden zur Suchraumbeschränkung integriert. Die verschiedenen Methoden zur Suchraumbeschränkung werden in Experimenten evaluiert und das entwickelte Verfahren zur Bearbeitung eines echten Data Mining-Problems eingesetzt.

Die Arbeit bietet im einzelnen: (1) eine Formalisierung der Teilgruppenanalyse im Rahmen der ILP, (2) Optimumschätzfunktionen zu ausgewählten Interessantheitsfunktionen, (3) eine Erweiterung des bekannten Apriori-Suchverfahrens zur Warenkorbanalyse, die es erlaubt, die von Apriori durchsuchte Hypothesensprache einzuschränken, (4) einen ILP-Sprachbias für die Teilgruppenanalyse, der die Anwendung der Teilmengenbedingung des Apriori-Suchverfahrens zur Beschränkung eines ILP-Suchraums erlaubt, (5) einen SQL-Sprachbias für die Teilgruppenanalyse in multi-relationalen Datenbanken, (6) einen Ansatz zur Integration der Suchraumbeschränkung anhand von Taxonomien in einen Apriori-artigen Suchalgorithmus, (7) eine Methode zur Behandlung diskretisierter numerischer Attribute, die die Suchraumbeschränkung anhand von Allgemeinerbeziehungen zwischen Intervallen vereinheitlicht mit der Suchraumbeschränkung anhand von Taxonomien, (8) Experimente zur Wirksamkeit der verschiedenen Möglichkeiten zur Suchraumbeschränkung, (9) die Anwendung der entwickelten Ansätze auf ein echtes Data Mining-Problem mit Bank-Daten und ausführliche Vergleiche mit verwandten Arbeiten.

Die Experimente wurden mit einer prototypischen Implementation der in dieser Arbeit entwickelten Ansätze durchgeführt. Dabei haben sich Teilmengenbedingung und Optimumschätzfunktionen als wirkungsvolle und zuverlässige Methoden zur Beschränkung des Suchraums erwiesen, während der Beitrag der Taxonomien zur Suchraumbeschränkung zwischen verschiedenen Anwendungen stark schwankte und in einigen Fällen nur gering war. Ein wichtiges Ergebnis der Versuche ist, daß die Teilmengenbedingung, die bisher nur zur Suchraumbeschränkung in ein-relationalen Datenbanken eingesetzt werden konnte, für multi-relationale Datenbanken und ILP-Sprachen genauso wirkungsvoll sein kann wie für ein-relationale Datenbanken.

Knowledge discovery and data mining are concerned with the discovery of valid, novel, potentially useful, and understandable patterns in data. Most data mining algorithms require that the data are represented as a single, attribute-value table. In contrast, data mining techniques that are developed within the framework of Inductive Logic Programming (ILP) are applicable directly to multi-relational databases. The application of ILP for data mining is also termed relational data mining.

This thesis develops and investigates pruning techniques that are applicable for pattern discovery within a restricted ILP setting where all patterns describe subgroups of a fixed population of individuals. This variant of pattern discovery is also known as relational subgroup discovery. The main contribution of the thesis is an Apriori-like search algorithm for relational subgroup discovery. Formerly, Apriori-like search was applied only in attribute-value (i. e., non-relational) settings.

In particular, the contributions of the thesis are (1) a formal description of subgroup discovery in the framework of ILP, (2) optimum estimates for the interestingness criteria distributional unusualness and implication intensity, (3) an extension to the well-known Apriori algorithm that allows to constrain the set of patterns searched by Apriori, (4) an ILP language bias that allows the application of an Apriori-like algorithm for relational subgroup discovery, (5) an SQL-based language bias for relational subgroup discovery via SQL queries to a relational database management system, (6) a novel approach for integrating pruning based on structured attributes in an Apriori-like search algorithm, (7) an approach for integrating pruning based on discreetized numerical attributes in an Apriori-like search algorithm, (8) an experimental evaluation of the various pruning methods (namely, optimum estimates, Apriori-like pruning, use of structure in attributes for pruning), (9) the application of the approach for data mining in a real-world financial database, and extensive comparisons with related work.

The experiments provide a comparison of different methods for pruning the search space for subgroup discovery in an ILP framework. Optimum estimates and Apriori-like pruning have produced good and reliable pruning effects, while the effect of pruning based on structured attributes varied for different search settings. In particular, the experiments have shown that Apriori-like pruning can have a similarly good effect for search in a multi-relational data base as it has for search in a single-relation database.

The application of the approach for data mining in a real-world financial database has shown that the language bias is well suited for the task of relational subgroup discovery, and that its expressivity is practically useful.

A detailed english abstract is given in Appendix B of the thesis.