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-
Search WWH ::




Custom Search