Page 36 - Fister jr., Iztok, and Andrej Brodnik (eds.). StuCoSReC. Proceedings of the 2018 5th Student Computer Science Research Conference. Koper: University of Primorska Press, 2018

inition 5. A rule R satisfies Constraint_Itemsets if its
antecedent (itemset) contains at least one itemset in
Constraint_Itemsets.
Definition 6. The actual occurrence ActOcc(R) of a rule R in D is
the number of records of D that match R's antecedent.
Definition 7. The support of rule R, denoted by Supp(R), is the
number of records of D that match R's antecedent and are labeled
with R's class.
Definition 8. The confidence of rule R, denoted by Conf(R), is
defined by equation (1) as follows:
Conf (R)  Supp(R) (1)
ActOcc(R)
3. PROBLEM STATEMENT
Consider a relational data set D with n attributes. A record of D is
a set of attribute-value pairs, denoted by T. A pattern is a subset of 11) Answer =⋃ k Lk ;
a record. We say, a pattern is a k-pattern if it contains k attribute-
value pairs. All the records in D are categorized by a set of classes
C.
It is required to generate the complete set of Class Association
Rules by Apriori and PART algorithms. Another focus will be on
comparing the advantages and disadvantages of using these two
algorithms.
3.1 Apriori Algorithm
Association rule generation [14] is usually split up into two
separate steps:
1. First, minimum support is applied to find all frequent
itemsets in a database.
2. Second, these frequent itemsets and the minimum
confidence constraint are used to form rules.
While the second step is straight forward, the first step needs more
attention. Finding all frequent itemsets in a database is time
consuming since it involves searching all possible itemsets (item
combinations). The set of possible itemsets is the power set over I
(the set of all items) and has size 2n 1 (excluding the empty set
which is not a valid itemset). Although the size of the powerset
grows exponentially in the number of items n in I, efficient search
is possible using the downward-closure property of support (also
called anti-monotonicity) which guarantees that for a frequent
itemset, all its subsets are also frequent and thus for an infrequent
itemset, all its supersets must also be infrequent. Exploiting this
property, efficient algorithms (e.g., Apriori [2]) can find all
frequent itemsets.
Figure 1 gives the sketch of the Apriori algorithm. Apriori uses a
“bottom up” approach, breadth-first search and a tree structure to
count candidate item sets efficiently. The first pass of the
algorithm simply counts item occurrences to determine the large
1-itemsets. A subsequent pass, say pass k, consists of two phases.
First, the large itemsets Lk1 found in the (k-1)-th pass are used to
generate the candidate itemsets Ck . Next the database is scanned
and the support of candidates in Ck is counted. For fast counting,
we need to efficiently determine the candidates in Ck that are
StuCoSReC Proceedings of the 2018 5th Student Computer Science Research Conference 36
Ljubljana, Slovenia, 9 October
contained in a given transaction t. All the missing details of the
Apriori algorithm can be found in [1] and [2].
1) L1 = {Large 1-itemsets};
2) for ( k =2; Lk1   ; k ++ ) do begin
3) Ck =apriori-gen( Lk 1 ); // New candidates
4) Forall transaction t  D do begin
5) Ct =subset( Ck , t ); // Candidates contained in t
6) Forall candidates c  Ct do
7) c. count++;
8) end
9) Lk ={ c  Ck | c. count  minsup}
10) end
Figure 1: The Apriori algorithm
3.2 PART Algorithm
The PART rule learning algorithm [5] combines the two
approaches C4.5 [11] and RIPPER [6] in an attempt to avoid their
respective problems. Unlike both C4.5 and RIPPER it does not
need to perform global optimization to produce accurate rule sets,
and this added simplicity is its main advantage. It adopts the
separate and conquer strategy in that it builds a rule, removes the
instances it covers, and continues creating rules recursively for the
remaining instances until none are left. It differs from the standard
approach in the way that each rule is created. In essence, to make
a single rule a pruned decision tree is built for the current set of
instances, the leaf with the largest coverage is made into a rule,
and the tree is discarded.
The prospect of repeatedly building decision trees only to discard
most of them is not as bizarre as it first seems. Using a pruned tree
to obtain a rule instead of building it incrementally by adding
conjunctions one at a time avoids the over-pruning problem of the
basic separate and conquer rule learner. Using the separate and
conquer methodology in conjunction with decision trees adds
flexibility and speed. It is indeed wasteful to build a full decision
tree just to obtain a single rule, but the process can be accelerated
significantly without sacrificing the above advantages.
The key idea is to build a “partial” decision tree instead of a fully
explored one. A partial decision tree is an ordinary decision tree
that contains branches to undefined subtrees. To generate such a
tree, we integrate the construction and pruning operations in order
to find a “stable” subtree that can be simplified no further. Once
this subtree has been found tree-building ceases and a single rule
is read off.
The tree-building algorithm is summarized as follows: it splits a
set of examples recursively into a partial tree. The first step
chooses a test and divides the examples into subsets accordingly.
The PART implementation makes this choice in exactly the same
way as C4.5. Then the subsets are expanded in order of their
average entropy, starting with the smallest (the reason for this is
that subsequent subsets will most likely not end up being
expanded, and the subset with low average entropy is more likely
to result in a small subtree and therefore produce a more general
rule). This continues recursively until a subset is expanded into a
leaf, and then continues further by backtracking.