Wissensentdeckung in Datenbanken mit Assoziationsregeln

Abstract

Die Datenanalyse mittels Assoziationsregeln ist eines der am häufigsten eingesetzten Data Mining-Verfahren und geht auf Arbeiten der Forschergruppe um Rakesh Agrawal am Forschungszentrum der IBM in Almaden, Kalifornien, USA, zurück. Dort wurden Anfang der neunziger Jahre Assoziationsregeln als Methode der Abhängigkeitsanalyse eingeführt und erste Algorithmen zur Assoziationsregelgenerierung entwickelt.

In der vorliegenden Arbeit werden die etablierten Verfahren zur Generierung von Assoziationsregeln analysiert und systematisiert, wodurch ein besseres Verständnis der in der Literatur bisher nicht im Zusammenhang dargestellten Verfahren möglich wird. In Verbindung mit einer umfassenden Evaluierung der Laufzeiten und des Speicherbedarfs führt dies zu einer Neubewertung der Ansätze.

Darauf aufbauend werden neue Verfahren zur Generierung von Assoziationsregeln abgeleitet. Diese beruhen auf einer optimierten Beschneidung des Suchraums, auf einem hybriden Vorgehen und auf der Einbeziehung einer eventuell vorhandenen Taxonomie. Im Rahmen einer Evaluierung erreichen die neu entwickelten Algorithmen in vielen Experimenten wesentlich kürzere Laufzeiten und einen geringeren Speicherbedarf als die bisherigen Algorithmen. Die vorgeschlagenen Verfahren sind insgesamt deutlich effizienter als die bisher bekannten Ansätze, insbesondere falls eine Taxonomie zu den Analysedaten zur Verfügung steht.

In Verbindung mit der Effizienz der Verfahren steht die Integration der Regelgenerierung in den Wissensentdeckungsprozeß. Ein iterativer und interaktiver Prozeß setzt kurze Antwortzeiten voraus, die von den Verfahren auf großen Datenmengen oft nicht erreicht werden können. Für diese von algorithmischen Aspekten in den Hintergrund gedrängte Problematik wird im Rahmen der vorliegenden Arbeit ein Regelcache als Lösung vorgeschlagen. Der Regelcache ist so aufgebaut, daß dieser auch für viele Anfragen gültig bleibt, die Selektionen der zugrundeliegenden Datensätze beinhalten, und dadurch für solche Anfragen nicht neu initialisiert werden muß.

Data analysis using association rules belongs to the fundamental data mining approaches and was introduced as a method aiming at dependency analysis by Rakesh Agrawal at the IBM Research Center in Almaden, California, USA.

In this thesis, the established algorithms for association rule mining are analyzed and systemized. The chief goal is to learn more about the algorithms that thus far have not been described coherently. Together with the results of an exhaustive evaluation of runtime and memory usage, this leads to a changed appreciation of the different approaches.

On the basis of the results obtained, new algorithms for the generation of association rules are developed. These algorithms rely on an optimized pruning of the search space, a hybrid approach, and the incorporation of a potentially available taxonomy. In a multitude of experiments carried out during a comprehensive evaluation, the new algorithms achieved not only much shorter runtimes but also a greatly reduced memory usage as compared to established approaches. All in all, the algorithms introduced are much more efficient than conventional approaches, in particular when a taxonomy on the data is available.

Aligned with the efficiency of the algorithms is the aspect of integrating the rule generation into the process of knowledge discovery. An iterative and interactive process assumes short response times that cannot be reached by the algorithms on very huge datasets. For this often neglected problem, an extended rule cache is proposed. This rule cache stays valid even for many mining queries that include selections of the underlying data. Hence, for such queries, the cache does not need to be reinitialized.