Database Reference
In-Depth Information
AprioriGen
(L
k−1
)
Eingabe:
Menge haufiger (k
1)-Itemmengen L
k−1
Ausgabe:
Obermenge der Menge haufiger k-Itemmengen
−
C
k
:=
∅
for all
p, q
∈
L
k−1
mit p
= q
do
if
die ersten k
−
2Elementevonp und q sind gleich,
% Items sind geordnet:
p =
{
e
1
,..., e
k−2
,e
p
}
,
%
e
1
<e
2
<
···
<e
k−2
<e
p
q =
{
e
1
,..., e
k−2
,e
q
}
%
e
1
<e
2
<
···
<e
k−2
<e
q
und e
p
<e
q
then
C
k
:= C
k
∪{{
e
1
,..., e
k−2
,e
p
,e
q
}}
end if
end for
for all
c
C
k
do
for all
(k
∈
−
1)-Teilmengen s von c
do
% Teilmengencheck
if
s
L
k−1
then
C
k
:= C
k
\{
∈
c
}
end if
end for
end for
return
C
k
Abbildung 5.25
Der
AprioriGen
-Algorithmus
Beispiel 5.31
Nehmen wir an, die Items seien durch Großbuchstaben gekennzeich-
net und alphabetisch geordnet, und L
3
enthalte die Mengen
{
A, B, C
}
,
{
A, B, D
}
,
{
A, C, D
}
,
{
A, C, E
}
,
{
B, C, D
}
. Durch geeignete Vereinigungen entstehen zunachst
die Kandidatenmengen
{
A, B, C, D
}
,
{
A, C, D, E
}
in C
4
. Hieraus wird die Itemmen-
ge
{
A, C, D, E
}
wieder entfernt, weil die Teilmenge
{
A, D, E
}
nicht in L
3
enthalten
ist. Nach Ablauf des Algorithmus
AprioriGen
ist also C
4
=
{{
A, B, C, D
}}
.
von
AprioriGen
erst gar nicht als
Kandidatenmenge betrachtet wird. Zwar konnte
Beachten Sie, dass die Menge
{
A, B, C, E
}
{
A, B, C, E
}
durch Vereinigung
der beiden in L
3
enthaltenenen Mengen
{
A, B, C
}
und
{
A, C, E
}
gebildet werden,
aber
stimmen nicht - wie von
AprioriGen
verlangt - in
den ersten zwei kleinsten Elementen uberein. Durch den Teilmengencheck musste
{
{
A, B, C
}
und
{
A, C, E
}
wieder entfernt werden, da die Teilmenge ohne das kleinste Element,
also die Menge {B, C, E}, nicht in L
3
enthalten ist.
A, B, C, E
}
Sowohl im
Apriori
- als auch im
AprioriGen
-Algorithmus mussen Teilmengen
uberpruft werden. Um diese Tests e
zient durchzufuhren, werden die Kandidaten-
mengen in einem Hash-Baum abgelegt (s. [2]).
Schließlich mussen aus den haufigen Itemmengen noch die gesuchten Assozia-
tionsregeln mit einer Konfidenz
minconf
bestimmt werden. Ahnlich wie bei der
Erzeugung haufiger Itemmengen nutzt man dabei gewisse Teilmengenbeziehungen
aus. Betragt namlich fur Itemmengen X, Y mit Y
≥
⊂
X die Konfidenz einer Re-