TU Darmstadt / ULB / TUprints

Rule Learning: From Local Patterns to Global Models

Sulzmann, Jan-Nikolas (2019)
Rule Learning: From Local Patterns to Global Models.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Text
diss_sulzmann_2018.pdf - Published Version
Copyright Information: CC BY-NC-ND 4.0 International - Creative Commons, Attribution NonCommercial, NoDerivs.

Download (13MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Rule Learning: From Local Patterns to Global Models
Language: English
Referees: Fürnkranz, Prof. Dr. Johannes ; Kramer, Prof. Dr. Stefan
Date: 17 January 2019
Place of Publication: Darmstadt
Date of oral examination: 20 April 2018
Abstract:

In many areas of daily life (e.g. in e-commerce or social networks), massive amounts of data are collected and stored in databases (for future use). Even though the specific information contained in the collected data may already be interesting, more general insights into the data would be more useful. Clearly, a data analysis should aim for a discovery of such pieces of knowledge, but a human inspection becomes less and less feasible to do as the databases become more and more unmanageable. To this end, the KDD process (short for ``Knowledge Discovery in Databases'') provides the tools for a semi-automatic data analysis. Data mining, which is the main component of the KDD process, searches the explicit facts for regularities which represent pieces of knowledge. Usually, these regularities are formulated as local patterns which describe only local characteristics of the data or as global models which explain the whole data. In our work, we will concentrate on local patterns and global models that may be used to predict a feature of interest or class attribute for future and unknown data. Interestingly, predictive local patterns may be used to obtain global predictions in two ways. The integrative approach treats the local patterns as building blocks and builds with their help a global model. The decoding approach aggregates the predictions of the local patterns into a single global prediction. While both approaches are promising, the question, how local patterns may be employed for global modelling, has not been answered satisfactorily yet. To this end, we consider three important aspects of this question in this work.

The first aspect is, how may a set of local patterns be employed to obtain optimal global predictions. The LeGo framework (an acronym for ``from \textbf{l}ocal patt\textbf{e}rns to \textbf{g}lobal m\textbf{o}dels'') provides an approach to answer this question. It divides the data mining process into three subsequent steps: the local pattern discovery generates a set of local patterns, the pattern set discovery step selects a smaller subset from the set of local patterns, and the global modelling employs the reduced pattern set to build a global model. There are many methods available for each step. So, we employ a selection of methods for each step and evaluate their performances with respect to the first considered aspect empirically.

The second aspect is, how may a set of local patterns be utilised to obtain optimal class probabilities. Often class probabilities may be more useful than a simple prediction as they may be used as a confidence measure in the prediction (e.g. in voting schemes). We divide this aspect into two sub tasks: the probability estimation and the probability aggregation. The probability estimation calculates class probabilities given a single local pattern. For this task, we consider basic probability estimation methods and shrinkage which is a technique to smooth the basic probability estimations. Furthermore, we examine the effect of the local pattern discovery on the quality of the probability estimation. The probability aggregation decodes the probability estimations of multiple patterns into a single probability estimation. For this purpose, we evaluate the performances of a selection of aggregation methods.

The third aspect is, how may a set of local patterns be transformed into a compact and understandable model. Usually, local pattern sets are hard to interpret and their utilisation for prediction necessitates additional efforts (e.g. voting schemes). These issues may be solved at once if the local patterns are employed to obtain a global model. To this end, we introduce rule stacking, which is a novel approach for global modelling. Rule stacking advances the standard stacking approach in two aspects: the meta data generation and the additional retransformation of the meta model. In this way, we obtain a compressed and interpretable global model that is directly applicable to future data.

Alternative Abstract:
Alternative AbstractLanguage

Heutzutage werden große Datenmengen in vielen Bereichen des täglichen Lebens (z.B. im E-Commerce oder in sozialen Netzwerken) gesammelt und in Datenbanken (für eine zukünftige Verwendung) abgelegt. Obwohl die spe\-zifischen Informationen in den gesammelten Daten bereits von Interesse sein können, sind allgemeinere Erkenntnisse über die Dateninhalte weitaus nütz\-licher. Eine Datenanalyse sollte aus diesem Grund darauf abzielen, derartiges (Teil-)Wissen zu erlangen. Eine Inspektion der Daten durch Menschen wird jedoch immer weniger praktikabel, da die vorliegenden Datenmengen immer größer und unhandlicher werden. Dieses Problem wird durch den KDD-Prozess (kurz für ``Knowledge Discovery in Databases'') gelöst, der die notwendigen Werkzeuge für eine halbautomatische Datenanalyse zur Verfügung stellt. Dessen Hauptkomponente Data-Mining durchsucht die expliziten Fakten nach Regelmäßigkeiten. %, die jeweils ein Wissenbruchstück darstellen. Üblicherweise werden derartige Regelmäßigkeiten als lokale Muster, die lokale Charakteristika der Daten beschreiben, oder als globale Modelle, die die Daten in ihrer Gesamtheit erklären, formuliert. In unserer Arbeit werden wir uns mit lokalen Mustern und globalen Modellen beschäftigen, die zukünftige und unbekannte Daten bezüglich eines Merkmals oder Klassenattributs klassifizieren. Interessanterweise können vorhersagende lokale Muster auf zwei Weisen eingesetzt werden, um eine einzige globale Vorhersage zu erhalten. Der integrative Ansatz behandelt die lokalen Muster als Bausteine und generiert aus ihnen ein globales Modell. Der dekodierende Ansatz verwendet die Vorhersagen mehrerer lokaler Muster und dekodiert diese in eine gemeinsame Vorhersage. Obwohl beide Ansätze vielversprechend sind, wurde bisher die Frage, wie lokale Muster %für das globale Modellieren zur Modellierung globaler Modelle eingesetzt werden können, noch nicht zufriedenstellend beantwortet. Daher betrachten wir drei wichtige Teilaspekte dieser Frage, die jeweils in einem Teil unserer Arbeit behandelt werden.

Der erste Teil unserer Arbeit befasst sich mit der Frage, wie eine Menge lokaler Muster dazu eingesetzt werden kann, optimale globale Vorhersagen zu erhalten. Das LeGo-Framework (ein Akronym für ``from local patterns to global models'') bietet einen Ansatz, um diese Frage zu behandeln. Es unterteilt den Data-Mining-Prozess in drei aufeinanderfolgende Teilschritte: ``Local Pattern Discovery'' generiert eine Menge lokaler Muster, ``Pattern Set Discovery'' selektiert von dieser eine kleinere Teilmenge und ``Global Modelling'' verwendet diese Teilmenge zur Erstellung eines globalen Modells. Für jeden dieser drei Teilschritte stehen diverse anwendbare Methoden zur Verfügung. Aus diesem Grund selektieren wir für jeden Teilschritt eine Auswahl von Methoden und evaluieren diese mittels eines empirischen Vergleichs.

Der zweite Teil unserer Arbeit behandelt die Frage, wie eine Menge lokaler Muster dazu verwendet werden kann, optimale Klassenwahrscheinlichkeiten vorherzusagen. Häufig sind Klassenwahrscheinlichkeiten nützlicher als eine einfache Vorhersage, da man sie als Konfidenzmaß für die Vorhersage verwenden kann (z.B. bei Abstimmungsschemata). Wir teilen diese Fragestellung in zwei Teilaufgaben auf: die Wahrscheinlichkeitsabschätzung und die Wahrscheinlichkeitsaggregation. Die Wahrscheinlichkeitsabschätzung berechnet für ein gegebenes lokales Muster die Klassenwahrscheinlichkeiten. Für diese Aufgabe betrachten wir einfache Methoden zur Wahrscheinlichkeitsabschätzung und die Technik Shrinkage, die die einfachen Wahrscheinlichkeitsabschätzungen glättet. Des Weiteren untersuchen wir auch den Einfluss der Suche nach lokalen Mustern auf die Performanz der Wahrscheinlichkeitsabschätzung. Die Wahrscheinlichkeitsaggregation dekodiert die Wahrscheinlichkeitsabschätzungen mehrerer lokaler Muster in eine einzige Wahrscheinlichkeitsabschätzung. Hierfür betrachten wir die Performanz ausgewählter Aggregationsmethoden.

Der dritte Teil untersucht die Frage, wie eine Menge lokaler Muster in ein kompaktes und verständliches Modell transformiert werden kann. Üblicherweise sind Mengen lokaler Muster schwierig zu interpretieren und ihre Verwendung zur Vorhersage erfordert zusätzliche Maßnahmen (z.B. Abstimmungsschemata). Diese beiden Probleme werden gleichzeitig gelöst, wenn man die lokalen Muster zur Erstellung eines globalen Modells verwendet. Zu diesem Zweck stellen wir den neuen Ansatz Rule Stacking zur Erstellung glo\-baler Modelle vor. Rule Stacking entwickelt den allgemeinen Stackingansatz in zwei Aspekten weiter: eine alternative Generierung der Metadaten und eine zusätzliche Rücktransformation des Metamodells. Auf diese Weise erhält man ein komprimiertes und interpretierbares globales Modell, das direkt auf zukünf\-tige Daten angewandt werden kann.

German
URN: urn:nbn:de:tuda-tuprints-73879
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science > Knowl­edge En­gi­neer­ing
Date Deposited: 23 Jan 2019 12:35
Last Modified: 23 Jan 2019 12:35
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/7387
PPN: 441391826
Export:
Actions (login required)
View Item View Item