Database Reference
In-Depth Information
gel (X
−
Y )
→
Y mindestens
minconf
, so gilt dies auch fur jede Regel der Form
Y
)
Y
, wobei Y
⊆
(X
Y eine Teilmenge von Y ist (s. Aufgabe 5.32). Folglich
erzeugt man aus einer haufigen Itemmenge X zunachst alle Assoziationsregeln, de-
ren Konklusion nur ein Item enthalt. Mit Hilfe des
AprioriGen
-Algorithmus werden
dann die Konklusionen elementweise erweitert: Ist H
m
eine Menge von m-Item-
Konklusionen einer haufigen Itemmenge X, so setze H
m+1
−
→
:=
AprioriGen
(H
m
).
Fur alle Konklusionen h
m+1
∈
H
m+1
uberpruft man nun die Konfidenz der Re-
gel (X
h
m+1
.Liegtsieuber der Schwelle
minconf
, so wird die Regel
ausgegeben, andernfalls wird h
m+1
aus H
m+1
entfernt (vgl. [2]).
−
h
m+1
)
→
Selbsttestaufgabe 5.32 (Assoziationsregeln)
Seien X, Y, Y
Itemmengen mit
Y
⊆
Y
⊂
X. Zeigen Sie, dass dann gilt:
Y
)
Y
)
confidence
((X
−
→
≥
confidence
((X
−
Y )
→
Y )
Bei jedem Iterationsschritt des
Apriori
-Algorithmus muss die Datenbasis
durchsucht werden, was zu einem ungunstigen Laufzeitverhalten fuhren kann. Eine
Weiterentwicklung dieses Algorithmus ist der
AprioriTid
-Algorithmus, der die Da-
tenbasis selbst nach dem ersten Durchlauf nicht mehr benotigt, allerdings mehr Spei-
cherplatz belegt. Eine Kombination aus beiden Algorithmen ist der
AprioriHybrid
-
Algorithmus, der die Vorteile beider Ansatze vereint (s. [2]).
Oftmals bieten sich in naturlicher Weise Hierarchien an, um die enorme Zahl
verschiedener Items (beispielsweise die Artikel in einem Warenhaus) zu strukturie-
ren: Eine Jeans der Marke XY
ist-eine
Jeans
ist-eine
Hose
ist-ein
Kleidungsstuck.
Interessant sind dann Assoziationsregeln, deren Items auf unterschiedlichen Stufen
dieser Hierarchie angesiedelt sind (wobei der Support einer solchen Regel mit ab-
nehmender Stufung naturlich immer besser wird):
In 40 % aller Transaktionen, bei
denen eine Hose gekauft wird, wird auch eine Bluse oder ein T-Shirt gekauft.
Solche
Assoziationsregeln werden
verallgemeinerte Assoziationsregeln
genannt; sie konnen
mit ahnlichen, erweiterten Verfahren gefunden werden (s. [223]).
Das beschriebene Vorgehen zum Au
nden von Assoziationsregeln mit vorgege-
benem Support und Konfidenz ist vollstandig, da systematisch alle haufigen Item-
mengen erzeugt und nach Regeln durchsucht werden. Ein Problem ist dabei aller-
dings die große Anzahl ausgegebener Regeln, was die Frage nach der tatsachlichen
statistischen Signifikanz
der Regeln aufwirft. Hier zeigten Megiddo und Srikant
[152], dass durch die Parameter Support und Konfidenz auch die Signifikanz der
ausgegebenen Regeln in uberzeugender Weise gesichert werden kann.
Selbsttestaufgabe 5.33 (
AprioriGen
-Algorithmus)
Betrachten Sie das Bei-
spiel 5.31 mit der Menge
L
3
:=
{{
A, B, C
}
,
{
A, B, D
}
,
{
A, C, D
}
,
{
A, C, E
}
,
{
B, C, D
}}
haufiger 3-Itemmengen. Welche Stelle im
AprioriGen
-Algorithmus verhindert, dass
{
in C
4
enthalten ist, obwohl diese Menge ja auch als vierelementige
Vereinigung zweier Mengen aus L
3
zu gewinnen ist? Warum ist es nicht notwendig,
die Menge
A, B, C, E
}
{
A, B, C, E
}
als potentielle haufige 4-Item-Menge heranzuziehen?
