The Efficient Discovery of Interesting Closed Pattern Collections [Elektronische Ressource] / Mario Boley. Mathematisch-Naturwissenschaftliche Fakultät

Mario Boley

Sujets

• Informatik

Informations

• Publié par: rheinische_friedrich-wilhelms-universitat_bonn
• Publié le: 01 janvier 2011
• Nombre de lectures: 14
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

The E cient Discovery of Interesting
Closed Pattern Collections
Dissertation
zur
Erlangung des Doktorgrades (Dr. rer. nat.)
der
Mathematisch-Naturwissenschaftlichen Fakult at
der
Rheinischen Friedrich-Wilhelms-Universit at Bonn
vorgelegt
von
Mario Boley
aus
Leverkusen
Bonn, 2010Angefertigt mit Genehmigung der Mathematisch-Naturwissenschaftlichen Fakult at der
Rheinischen Friedrich-Wilhelms-Universit at Bonn
1. Gutachter: Prof. Dr. Stefan Wrobel
2.hter: Prof. Dr. Rainer Manthey
Tag der Promotion: 26.9.2011
Erscheinungsjahr: 2011
Mario Boley
University of Bonn
Department of Computer Science III
and
Fraunhofer Institute for Intelligent Analysis
and Information Systems IAIS
Schloss Birlinghoven
53754 Sankt Augustin
Germany
[e-mail]
I, Mario Boley, con rm that this work is my own and is expressed in my own words. Any
uses made within it of the works of other authors in any form (e.g. ideas, equations, gures,
text, tables, programs) are properly acknowledged at the point of their use. A full list of the
references employed has been included.Abstract
Enumerating closed sets that are frequent in a given database is a fundamental data mining
technique that is used, e.g., in the context of market basket analysis, fraud detection, or Web
personalization. There are two complementing reasons for the importance of closed sets|
one semantical and one algorithmic: closed sets provide a condensed basis for non-redundant
collections of interesting local patterns, and they can be enumerated e ciently. For many
databases, however, even the closed set collection can be way too large for further usage and
correspondingly its computation time can be infeasibly long. In such cases, it is inevitable to
focus on smaller collections of closed sets, and it is essential that these collections retain both:
controlled semantics re ecting some notion of interestingness as well as e cient enumerability.
This thesis discusses three di erent approaches to achieve this: constraint-based closed set
extraction, pruning by quantifying the degree or strength of closedness, and controlled random
generation of closed sets instead of exhaustive enumeration.
For the original closed set family, e cient enumerability results from the fact that there is an
inducing e ciently computable closure operator and that its xpoints can be enumerated by
an amortized polynomial number of closure computations. Perhaps surprisingly, it turns out
that this connection does not generally hold for other constraint combinations, as the restricted
domains induced by additional constraints can cause two things to happen: the xpoints of the
closure operator cannot be enumerated e ciently or an inducing closure operator does not even
exist. This thesis gives, for the rst time, a formal axiomatic characterization of constraint
classes that allow to e ciently enumerate xpoints of arbitrary closure operators as well as of
constraint classes that guarantee the existence of a closure operator inducing the closed sets.
As a complementary approach, the thesis generalizes the notion of closedness by quantifying
its strength, i.e., the di erence in supporting database records between a closed set and all its
supersets. This gives rise to a measure of interestingness that is able to select long and thus
particularly informative closed sets that are robust against noise and dynamic changes. More-
over, this measure is algorithmically sound because all closed sets with a minimum strength
again form a closure system that can be enumerated e ciently and that directly ties into the
results on constraint-based closed sets. In fact both approaches can easily be combined.
In some applications, however, the resulting set of constrained closed sets is still intractably
large or it is too di cult to nd meaningful hard constraints at all (including values for their
parameters). Therefore, the last part of this thesis presents an alternative algorithmic paradigm
to the extraction of closed sets: instead of exhaustively listing a potentially exponential number
of sets, randomly generate exactly the desired amount of them. By using the Markov chain
Monte Carlo method, this generation can be performed according to any desired probability
distribution that favors interesting patterns. This novel randomized approach complements
traditional enumeration techniques (including those mentioned above): On the one hand, it is
only applicable in scenarios that do not require deterministic guarantees for the output such
as exploratory data analysis or global model construction. On the other hand, random closed
set generation provides complete control over the number as well as the distribution of the
produced sets.Zusammenfassung
Das Aufzahlen abgeschlossener Mengen (closed sets), die hau g in einer gegebenen Datenbank
vorkommen, ist eine algorithmische Grundaufgabe im Data Mining, die z.B. in Warenkorbana-
lyse, Betrugserkennung oder Web-Personalisierung auftritt. Die Wichtigkeit abgeschlossener
Mengen ist semantisch als auch algorithmisch begrundet: Sie bilden eine nicht-redundante Ba-
sis zur Erzeugung von lokalen Mustern und konnen gleichzeitig e zient aufgez ahlt werden.
Allerdings kann die Anzahl aller abgeschlossenen Mengen, und damit ihre Au istungszeit, das
Ma des e ektiv handhabbaren oft deutlich ub ersteigen. In diesem Fall ist es unvermeidlich,
kleinere Ausgabefamilien zu betrachten, und es ist essenziell, dass dabei beide o.g. Eigen-
schaften erhalten bleiben: eine kontrollierte Semantik im Sinne eines passenden Interessant-
heitsbegri es sowie e ziente Aufz ahlbark eit. Diese Arbeit stellt dazu drei Ansatze vor: das
Einfuhren zusatzlicher Constraints, die Quanti zierung der Abgeschlossenheit und die kontrol-
lierte zufallige Erzeugung einzelner Mengen anstelle von vollstandiger Aufzahlung.
Die e ziente Aufz ahlbarkeit der ursprunglichen Familie abgeschlossener Mengen ruhrt da-
her, dass sie durch einen e zient berechenbaren Abschlussoperator erzeugt wird und dass
desweiteren dessen Fixpunkte durch eine amortisiert polynomiell beschrankte Anzahl von Ab-
schlussberechnungen aufgezahlt werden konnen. Wie sich herausstellt ist dieser Zusammenhang
im Allgemeinen nicht mehr gegeben, wenn die Funktionsdomane durch Constraints einschrankt
wird, d.h., dass die e ziente Aufz ahlung der Fixpunkte nicht mehr moglich ist oder ein erzeu-
gender Abschlussoperator unter Umstanden gar nicht existiert. Diese Arbeit gibt erstmalig eine
axiomatische Charakterisierung von Constraint-Klassen, die die e ziente Fixpunktaufz ahlung
von beliebigen Abschlussoperatoren erlauben, sowie von Constraint-Klassen, die die Existenz
eines erzeugenden Abschlussoperators garantieren.
Als erganzenden Ansatz stellt die Dissertation eine Generalisierung bzw. Quanti zierung
des Abgeschlossenheitsbegri s vor, der auf der Dierenz zwischen den Datenbankvorkommen
einer Menge zu den Vorkommen all seiner Obermengen basiert. Mengen, die bezuglic h dieses
Begri es stark abgeschlossen sind, weisen eine bestimmte Robustheit gegen Veranderungen
der Eingabedaten auf. Desweiteren wird die gewunsc hte e ziente Aufz ahlbarkeit wiederum
durch die Existenz eines e zient berechenbaren erzeugenden Abschlussoperators sichergestellt.
Zusatzlich zu dieser algorithmischen Parallele zum Constraint-basierten Vorgehen, konnen bei-
de Ansatze auch inhaltlich kombiniert werden.
In manchen Anwendungen ist die Familie der abgeschlossenen Mengen, zu denen die bei-
den oben genannten Ansatze fuhren, allerdings immer noch zu gro bzw. ist es nicht m oglich,
sinnvolle harte Constraints und zugehorige Parameterwerte zu nden. Daher diskutiert diese
Arbeit schlie lich noch ein v ollig anderes Paradigma zur Erzeugung abgeschlossener Mengen
als vollstandige Au istung, n amlich die randomisierte Generierung einer Anzahl von Mengen,
die exakt den gewunsc hten Vorgaben entspricht. Durch den Einsatz der Markov-Ketten-Monte-
Carlo-Methode ist es moglich die Verteilung dieser Zufallserzeugung so zu steuern, dass das Zie-
hen interessanter Mengen begunstigt wird. Dieser neue Ansatz bildet eine sinnvolle Erganzung
zu herkommlic hen Techniken (einschlie lich der oben genannten): Er ist zwar nur anwend-
bar, wenn keine deterministischen Garantien erforderlich sind, erlaubt aber andererseits eine
vollstandige Kontrolle ub er Anzahl und Verteilung der produzierten Mengen.Acknowledgements
This thesis was written at the Knowledge Discovery Department of Fraunhofer IAIS in Sankt
Augustin under my thesis supervisor Prof. Dr. Stefan Wrobel and my additional advisor Dr.
Tamas Horv ath. I would like to express my gratitude not only for the thoughtful advice that
both provided but also for the freedom, patience, and trust they granted me. The same holds
true for Dr. Thomas G artner, the head of my research group CAML.
Among the many other people contributing to the motivating spirit at our institution I want
to especially thank the individuals with whom I cooperated on research papers related to this
thesis. In addition to the three aforementioned persons, these are Dr. Henrik Grosskreutz and
Dr. Axel Poigne. Particularly, I really have to stress that many parts of this thesis would
not exist if it were not for Henrik, our good mutual understanding, and of course his software
craftsmanship.
Finally, I have to mention my linear algebra lectur