Database Reference
In-Depth Information
Die Mengenschreibweise in Pramisse und Konklusion einer Assoziationsregel
bedeutet die konjunktive Verknupfung der beteiligten Elemente. So garantiert be-
reits die Syntax einer Assoziationsregel ein gewisses Maß an Relevanz und Interes-
santheit, im Gegensatz zu Regeln, die beliebige logische Ausdrucke zulassen und oft
schwer zu durchschauen sind. Support und Konfidenz sind zusatzliche Parameter,
an denen die Relevanz einer Regel beurteilt wird. Typischerweise (insbesondere im
wirtschaftlichen Bereich) soll beides relativ hoch sein, so dass sich die klassische
Suche nach Assoziationsregeln folgendermaßen beschreiben lasst:
Finde alle Assoziationsregeln, die in der betrachteten Datenbasis mit
einem Support von mindestens
minsupp
und einer Konfidenz von min-
destens
minconf
gelten, wobei
minsupp
und
minconf
benutzerdefinierte
Werte sind.
Dieses Problem wird in zwei Teilprobleme aufgespalten:
•
Finde alle Itemmengen, deren Support uber der
minsupp
-Schwelle liegt; die-
se Itemmengen werden
haufige Itemmengen
(
frequent itemsets
)oder
große
Itemmengen
(
large itemsets
)genannt.
Finde in jeder haufigen Itemmenge I alle Assoziationsregeln I
→
I
)mit
•
(I
−
I
⊂
I, deren Konfidenz mindestens
minconf
betragt.
Die wesentliche Schwierigkeit besteht in der Losung des ersten Teilproblems. Enthalt
die Menge
insgesamt n Items, so sind theoretisch 2
n
Itemmengen auf ihre Haufig-
keit hin zu untersuchen, was im Allgemeinen naturlich nicht praktikabel ist. Der
in [2] vorgestellte
Apriori
-
Algorithmus
sucht geschickt nach solchen Itemmengen,
indem er sich Folgendes zunutze macht:
Alle Teilmengen einer haufigen Itemmenge sind ebenfalls haufig, und alle Obermen-
gen einer nicht haufigen Itemmenge sind ebenfalls nicht haufig.
Dies ist klar, denn fur zwei Itemmengen I
1
,I
2
I
mit I
1
⊆
I
2
gilt naturlich:
support
(I
2
)
support
(I
1
). Der
Apriori
-Algorithmus bestimmt also zunachst die
einelementigen haufigen Itemmengen und sucht in jedem weiteren Durchlauf in den
Obermengen von haufigen Itemmengen nach weiteren haufigen Itemmengen. Wer-
den keine haufigen Itemmengen mit einer bestimmten Anzahl von Elementen mehr
gefunden, so bricht der Algorithmus ab.
Abbildung 5.24 zeigt den
Apriori
-Algorithmus. Dabei bezeichnet L
k
die Menge
der haufigen k-Itemmengen. C
k
ist die Menge aller im
AprioriGen
-Algorithmus
(s. Abbildung 5.25) erzeugten Kandidatenmengen fur haufige k-Itemmengen. Deren
tatsachliche Haufigkeit wird im
Apriori
-Algorithmus berechnet, um aus C
k
die
haufigen k-Itemmengen herauszufiltern.
Wir erlautern zunachst den Ablauf des
Apriori
-Algorithmus. Im ersten Durch-
lauf bestimmt der Algorithmus die Menge L
1
der haufigen 1-Itemmengen, indem
er einfach zahlt, wie oft jedes Item in den Transaktionen aus
≤
D
vorkommt. Jede
weitere, k-te Iteration (k
≥
2) besteht aus drei Schritten: Im ersten Schritt wer-
den aus den im (k
1)-Durchlauf bestimmten haufigen Itemmengen, L
k−1
, mittels
AprioriGen
die Kandidaten-Itemmengen, C
k
, berechnet. Im zweiten Schritt (for-
Schleife in
Apriori
)wirdfur jede Kandidatenmenge c
−
∈
C
k
in dem Zahler c.count
