SQL based frequent pattern mining [Elektronische Ressource] / von: Xuequn Shang

Sujets

• Informatik

Informations

• Publié par: otto-von-guericke-universitat_magdeburg
• Publié le: 01 janvier 2005
• Nombre de lectures: 17
• Langue: English

Extrait

SQL Based Frequent Pattern Mining
Dissertation
zur Erlangung des akademischen Grades
Doktoringenieurin (Dr.-Ing.)
vorgelegt der Fakult˜at fur˜ Informatik
der Otto-von-Guericke-Universit˜at Magdeburg
von: MSc. Xuequn Shang
geb. am 8. M˜arz 1973 in Shaanxi, China
Magdeburg, den 14. Februar 2005iic? Copyright by Xuequn Shang 2005
All Rights Reserved
iiiivDeclaration
I hereby declare that this submission is my own work and to the best of my knowl-
edge it contains no materials previously published or written by another person, nor
material which to a substantial extent has been accepted for the award of any other
degree or diploma at University of Magdeburg or any other educational institution,
except where due acknowledgement is made in the thesis. Any contribution made
to the research by others, with whom I have worked at University of Magdeburg or
elsewhere, is explicitly acknowledged in the thesis.
I also declare that the intellectual content of this thesis is the product of my own
work, except to the extent that assistance from others in the project’s design and
conception or in style, presentation and linguistic expression is acknowledged.
vZusammenfassung
DataMiningingrossrelationalenDatenbankenwird zunehmendeingesetzt und seine
Bedeutungistheutevollanerkannt. Trotzdemf˜alltdiePerformanzvonSQL-basiertem
Data Mining hinter spezialisierten Implementierungen zuruc˜ k. Dies liegt an den
unangemessenhohenKostenderWissensextraktionundderfehlendenUnterstutzung˜
durch Konstrukte der deklarativen Anfragesprache. Frequent Pattern Mining, d.h.
die Suche nach sich wiederholenden Mustern in Daten, ist die Grundlage fur˜ eine
ReihevonessentiellenMining-Aufgaben. DieswardieMotivationfur˜ dieEntwicklung
SQL-basierterAns˜atzefur˜ dasFrequentPatternMiningimRahmendieseForschungs-
vorhabens.
In dieser Arbeit werden Ans˜atze untersucht, um unter Verwendung von SQL Fre-
quent Patterns in einer Transaktionstabelle zu flnden. Von diesen basieren die meis-
ten auf dem Apriori-Algorithmus. Diese Methoden weisen jedoch durch die teuren
Operationen zur Kandidatengenerierung und deren -test eine unzureichende Perfor-
manz auf, insbesondere bei der Suche nach besonders aussagekr˜aftigen und/oder lan-
gen Mustern. Hierfur˜ wurde im hier beschriebenen Dissertationsprojekt eine Klasse
von SQL-basierten Methoden zum schrittweisen Finden und Verfeinern von Mustern
entwickelt. Die Gemeinsamkeit dieser Methoden besteht im Teile und Herrsche-
Ansatz zur Zerlegung von Mining-Aufgaben und in der Anwendung einer Muster-
verfeinungsmethode zur Vermeidung des kombinatorischen Efiekts, der fur˜ die Kan-
didatengenerierung ein typisches Problem darstellt. Apriori-basierte Algorithmen er-
forderen bei der Verwendung von SQL entweder mehrere Scans ub˜ er die Datenbank
oder aufw˜andige Verbundoperationen. Demgegenub˜ er vermeiden die hier vorgestell-
ten SQL-basierten Algorithmen mehrere Durchl˜aufe ub˜ er die Ausgangstabellen als
viauch die Berechnung komplexer Verbunde zwischen Tabellen.
Eine umfassende Untersuchung der Performanz wurde unter Verwendung eines
DBMS (IBM DB2 UDB EEE V8) durchgefuhrt˜ und die Ergebnisse herk˜ommlicher
Apriori-basierter Ans˜atze wurden mit denen der in dieser Arbeit vorgestellten Meth-
oden verglichen. Empirische Ergebnisse zeigen, dass die vorgestellten Algorithmen
zu einer e–zienten Berechnung fuhren.˜ Darub˜ er hinaus unterstutzen˜ die meisten
Datenbankmanagementsysteme heutzutage die Parallelisierung, deren Eignung zur
Unterstutzung˜ des Frequent Pattern Mining im Rahmen dieser Arbeit untersucht
wurde.
viiAbstract
Dataminingonlargerelationaldatabaseshasgainedpopularityanditssigniflcanceis
wellrecognized. However,theperformanceofSQLbaseddataminingisknowntofall
behind specialized implementation since the prohibitive nature of the cost associated
with extracting knowledge, as well as the lack of suitable declarative query language
support. Frequent pattern mining is a foundation of several essential data mining
tasks. These facts motivated us to develop original SQL-based approaches for mining
frequent patterns.
In this work, we investigate approaches based on SQL for the problem of flnd-
ing frequent patterns from a transaction table. Most of them adopt Apriori-like
approaches. However those methods may sufier from the inferior performance since
the costly candidate-generation-and-test operation especially when mining datasets
withproliflcpatternsand/orlong patterns. Wedevelopaclass ofe–cientSQL based
pattern growth methods for mining frequent patterns. The commonality of these
approaches is that they use a divide and conquer method to decompose mining tasks
and then use a pattern growth method to avoid the combinatory problem inherent
to candidate-generation-and-test approach. Apriori algorithms with the help of SQL
either require several scans over the data or require many and complex joins between
the input tables. While our SQL-based algorithms avoid making multiple passes over
the large original input table and complex joins between the tables.
A comprehensive performance study evaluates on DBMS (IBM DB2 UDB EEE
V8) and compares the p results between SQL based frequent pattern min-
ing approaches based on Apriori and the approaches in this thesis. The empirical
results show that our algorithms can get e–cient performance. Moreover, recently
viiimost major database systems have included capabilities to support parallelization,
this thesis examined how e–ciently SQL based frequent pattern mining can be par-
allelized and speeded up using parallel database systems.
ixDedication
To my family
x