Diploma Thesis DIP-1564

BibliographyKlenk, Thomas: Ein Verfahren zur Suche von sequentiellen Mustern.
University of Stuttgart, Faculty of Computer Science, Diploma Thesis No. 1564 (1997).
87 pages, german.
CR-SchemaH.3.3 (Information Search and Retrieval)
I.2.6 (Artificial Intelligence Learning)
KeywordsKnowledge Discovery; KDD; sequential patterns; Data Mining
Abstract

Ein Teilbereich des {\em Knowledge Discovery in Databases} ist die Suche nach auffälligen Abhängigkeiten zwischen Einträgen in einer Datenbank. Großes Interesse hat in den vergangenen Jahren die Suche nach Assoziationsregeln erregt. Die dabei zum Einsatz kommenden Algorithmen wurden von Agrawal und Srikant verwendet, um eine neue Klasse von interessanten Informationen zu definieren: sequentielle Muster (Sequential Patterns).

Auf einer Menge von Sequenzen, die ihrerseits aus je einer Menge von zeitlich geordneten Ereignissen bestehen, werden häufig auftretende Muster gesucht. Solche Muster könnten zum Beispiel die Erkenntnis beschreiben, daß ein Kunde, der einen Computer kauft, häufig binnen kurzer Zeit auch dazu passende Speichererweiterungen erwirbt.

Ausgehend von dem Verfahren von Agrawal und Srikant werden in dieser Arbeit Erweiterungen erwogen, die hauptsächlich die Aussagekraft der gefundenen Lösungen steigern. Unter anderem wird ein Maß zur Bestimmung der Fortsetzungswahrscheinlichkeit für Muster aus dem Bereich der Assoziationsregeln übertragen. Damit können Abhängigkeiten zwischen Ereignissen, die zeitlich versetzt auftreten, untersucht werden. Desweiteren wird das neue Maß der Reihenfolgensicherheit definiert, mit dem die Wahrscheinlichkeit beschrieben ist, daß die im Muster enthaltenen Ereignisse in der implizierten Reihenfolge auftreten.

Die nichttrivialen Aspekte der Implementierung werden ausführlich besprochen. Die Evaluation der prototypischen Implementierung des erweiterten Verfahrens (eGSP) wird unter anderem mit realen Daten aus dem Qualitätsinformationssystem der Mercedes-Benz AG durchgeführt.

Ein Vergleich mit verwandten Ansätzen und ein Ausblick auf zukünftige Entwicklungsmöglichkeiten runden diese Arbeit ab.

Full text and
other links
PostScript (639187 Bytes)
Access to students' publications restricted to the faculty due to current privacy regulations
Department(s)University of Stuttgart, Institute of Computer Science, Intelligent Systems (Prof. Lehmann)
Entry dateDecember 19, 1997
   Publ. Computer Science