Database Reference
In-Depth Information
Apriori
(
D
)
Eingabe:
Datenbasis
D
Ausgabe:
Menge haufiger Itemmengen
L
1
:=
{
haufige 1-Itemmengen
}
k := 2
while
L
k−1
do
C
k
:=
AprioriGen
(L
k−1
)
=
∅
% neue Kandidatenmengen
for all
Transaktionen t
∈D
do
C
t
:=
{
c
∈
C
k
|
c
⊆
t
}
%in
t
enthaltene Kandidatenmengen
C
t
do
c.count := c.count +1
end for
end for
L
k
:=
for all
Kandidaten c
∈
{
c
∈
C
k
|
c.count
≥|D|·
minsupp
}
k := k +1
end while
return
k
L
k
Abbildung 5.24
Der
Apriori
-Algorithmus
die Anzahl der Transaktionen t
∈D
gezahlt, die c enthalten. Fur jede Transaktion
t
werden dazu zunachst die in t enthaltenen Kandidatenmengen C
t
bestimmt.
Im dritten Schritt werden in L
k
alle diejenigen Kandidatenmengen c
∈D
∈
C
k
aufge-
nommen, deren Support in
D
großer als
minsupp
ist (d.h. c.count
≥|D|·
minsupp
).
Als Ergebnis liefert
Apriori
schließlich die Vereinigung aller L
k
.
Der Algorithmus benotigt m Iterationen, wobei m die Kardinalitat der großten
haufigen Itemmengen ist. Seine Ausgabe ist die Menge aller haufigen Itemmengen,
d. h. die Menge aller Itemmengen I mit
support
(I)
minsupp
.
Der Kandidaten-Algorithmus
AprioriGen
nutzt aus, dass jede Teilmenge einer
haufigen Itemmenge wieder haufig sein muss, insbesondere, dass also jede (k
≥
−
1)-
Teilmenge einer Menge aus L
k
in L
k−1
enthalten sein muss. Zwei haufige (k
−
1)-
Itemmengen p, q
2) Elementen ubereinstimmen, werden
vereinigt und ergeben so eine neue k-Itemmenge. Aus der so gewonnenen Men-
ge moglicher Kandidaten werden dann durch den anschließenden
Teilmengencheck
noch diejenigen Mengen entfernt, deren (k
∈
L
k−1
, die in genau (k
−
−
1)-Teilmengen nicht alle in L
k−1
liegen.
1)-Teilmengen haufig sein mussen, konnen wir bereits bei der
Erzeugung der k-Itemmengen eine weitere Einschrankung vornehmen: Der Algo-
rithmus
AprioriGen
in Abbildung 5.25 nimmt an, dass alle Items lexikographisch
geordnet sind, und zwei haufige (k
Da
alle
(k
−
1)-Itemmengen werden nur dann fur die Erzeu-
gung einer k-Itemmenge verwendet, wenn die gemaß dieser Ordnung ersten k
−
2
Elemente e
1
,e
2
,...,e
k−2
in beiden Mengen gleich sind und die Mengen sich daher
nur im jeweils goßten Element unterscheiden.
−
