Information Technology Reference
In-Depth Information
transaction we add a unique transaction identifier to its transaction set. For the
example database from Table 1 the vertical layout is given in Table 2
Table 2.
Vertical layout for vhicles and installed special equipment
Special Equipment Vehicles
AirConditioning
{v
1
,v
4
,v
5
}
2ndAirbag
{v
1
,v
8
}
BatteryTypeC
{v
1
,v
4
,v
5
,v
6
,v
7
,v
8
}
Clutch
{v
2
,v
5
}
RadioTypeE
{v
6
}
The transaction sets of the
n
-itemsets with
n>
1 are determined on the fly
by set intersections. For each itemset
Z
with
Z
=
X ∪ Y
holds
Z.
tids =
X.
tids
∩ Y.
tids
.
Of course this implies that during search space traversal we need to ensure that
we always have the necessary transaction sets at our hands, that is to say in
main memory.
To give an example lets look at the itemset
{
AirConditioning
,
BatteryTypeC
}
.
The transaction set of this itemset can be determined based on the transaction
sets of the corresponding 1-itemsets:
{
AirCondition.
,
BatteryTypeC
}.
tids =
{
AirCondition.
}.
tids
∩{
BatteryTypeC
}.
tids
=
{v
1
,v
4
,v
5
}∩{v
1
,v
4
,v
5
,v
6
,v
7
,v
8
}
=
{v
1
,v
4
,v
5
}
4.3 Algorithms
The framework for frequent itemset generation from above leaves room for sev-
eralalgorithmicinstantiations.Themostwide-spreadofthesealgorithmsisApri-
ori from [3]. Its pseudocode is given in Figure 3. Apriori implements the above
step-wise search space traversel as a breadth-first search together with count-
ing the candidates directly. In the beginning the set of all frequent 1-itemsets,
F
1
, is determined by setting up a counter for each
x ∈I
and passing over the
database. Then each following level of the search space is processed separately
in two phases. First of all the candidate set is generated based on the results
from the previous level. All itemsets
C ∈P
(
I
),
|C|
= level, for which all subsets
of size level
−
1 are frequent,
∀S
C, |S|
= level-1 :
S ∈F
level
−
1
,
are included in the candidate set
C
level
. Second, the support values of all candi-
datesin
C
level
aredeterminedinasinglepassoverthedatabase.Thisprocedureis
