VIGNAN substantially reduces the number of rules to

be presented.
INSTOFINFORMATION An efficient algorithm CLOSET, for
TECHNOLOGY mining closed itemsets, with the
development of three techniques:
DUVVADA,
(1) Applying a compressed frequent
VISAKHAPATNAM. pattern tree FP-tree structure for
mining closed itemsets without

TITLE: CLOSET- An Efficient candidate generation,

Algorithm for Mining Frequent Closed (2) Developing a single prefix path

Itemsets compression technique to identify

frequent closed itemsets quickly, and
(3) Exploring a partition bases
PRESENTED BY :
projection mechanism for scalable
P.BHAKTHAVATHSALANAIDU
mining in large databases. CLOSET
K.K.S.SWAROOP
is efficient and scalable over lager
[email protected]
databases and is faster than the
[email protected]
previously proposed methods.
INTRODUCTION:
It has been well recognized that
CLOSET: An Efficient frequent pattern mining plays an essential
role in many important data mining tasks,
Algorithm for Mining
e.g. associations, sequential patterns ,
Frequent Closed Itemsets episodes, partial periodicity, etc. However, it
ABSTRACT is also well known that frequent pattern
Association mining may often derive mining often generates a very large number
an undesirably large set of frequent itemsets of frequent itemsets and rules, which
and association rules. Recent studies have reduces not only efficiency but also
proposed an interesting alternative: mining effectiveness of mining since users have to
frequent closed itemsets and their sift through a large number of mined rules to
corresponding rules, which has the same find useful ones.
power as association mining but There is an interesting alternative:
instead of mining the complete set of
frequent itemsets and their associations, rules of the form “A⇒B” where A and B are
association mining only their corresponding sets of items, it is defined as
rules. An important implication is that Support(A⇒B) = # tuples containing
mining frequent closed itemset has the same both A and B
power as mining the complete set of total # of
frequent itemsets, but it will substantially tuples
reduce redundant rules to be generated and Association rules that satisfy both a user
increase both efficiency and effectiveness of specified minimum confidence and user
mining. specified minimum support threshold are
Definition: Association rule mining referred to as Strong Association Rules.
searches for interesting relationships among Association Rule Mining is a two step
items in a given data set. process:
Interestingness Measures: 1. Find all frequent itemsets: each of
Certainty: Each discovered pattern should these itemsets will occur at least as
have a measure of certainty associated with frequently as a pre-determined
it that assesses the validity or minimum support count.
“trustworthiness” of the pattern. A certainty 2. Generate strong association rules
measure for association rules of the form from the frequent itemsets: These
“A⇒B”, where A and B are sets of items, is rules must satisfy minimum support
Confidence. Given a set task-relevant data and minimum confidence.
tuples, the confidence of “is defined as The Apriori Algorithm: Finding Frequent
“A⇒B” is defined as Itemsets Using Candidate Generation:
Confidence (A⇒B) = # tuples Apriori is an influential algorithm for
containing both A and B mining frequent itemsets for Boolean
# tuples association rules. The names of the
containing A algorithm are based on the fact that the
Utility : The potential usefulness of a algorithm uses prior knowledge of frequent
pattern is a factor defining its itemset properties. Apriori employs an
interestingness. It can be estimated by a iterative approach known as a level-wise
utility function, such as support. The support search where k-itemsets are used to explore
of an association pattern refers to the (k+1)-itemsets. The finding of each Lk
percentage of task-relevant data tuples for requires one full scan of the database.
which the pattern is true. For association Two step process of finding frequent items:
The join step: To find Lk, a set of candidate TID List Of
k-itemsets is generated by joining Lk-1 with Item_IDs
itself. This set of candidates is denoted Ck. T100 I1,I2,I5
T200 I2,I4
Let l1 and l2 be itemsets in Lk-1. The notation T300 I2,I3
li[j] refers to the jth item in li. By T400 I1,I2,I4
T500 I1,I3
convention, Apriori assumes that items T600 I2,I3
within a transaction or itemset are sorted in T700 I1,I3
T800 I1,I2,I3,I5
lexicographic order. The join, Lk-1  Lk-1, T900 I1,I2,I3
is performed; where members of Lk-1 are
joinable if there first (k-2) items are in 1) In the first iteration of the algorithm,
common. That is, members l1 and l2 are each items is a member of the set of
joined if candidate 1-itemsets, C1. The

(l1[1]=l2[1])∧(l1[2]=l2[2])∧(l1[3]=l2[3])∧(l1[4]= algorithm simply scans all of the

l2[4]). The condition l1[k-1]<l2[k-1] simply transactions in order to count the

ensures that no duplicates are generated. The number of occurrence of each item.

resulting itemset formed by joining l1 and l2 2) Suppose that the minimum

is l1[1]l1[2]…l1[k-1]l2[k-1] transactions support count required is

The prune step: Ck is a superset of Lk, that 2. The set of frequent 1-itemsets, L1,

is its members may or may not be frequent, can then be determined. It consists of

but all of the frequent, but all of the frequent the candidate 1-itemsets satisfying

k-itemsets are included in Ck. A scan of the minimum support.

database to determine the count of each 3) To discover the set of frequent 2-

candidate in Ck would result in the itemsets, L2 the algorithm uses L1

determination of Lk. Ck, however can be 1X1 L1 to generate a candidate set of

huge, and so this could involve heavy 2-itemsets C2.

computation. To reduce the size of Ck, the

Apriori property is used as follows. Any (k-
1)-itemset that is not frequent cannot be a In this way we will find candidate sets

subset of a frequent either and so can be until a candidate set is null.

removed from Ck. This subset testing can be

done quickly by maintaining a hash tree of
all frequent itmesets.
Example:-
 • for each frequent itemset l, generate
all nonempty subsets of l.
• for every nonempty subset of l,
output the rule “s⇒(l-s)” if support
count(l) ≥ min_conf,

support count(s)
where min_conf is the minimum
confidence threshold.
Since the rules are generated from frequent
itemsets, each one automatically satisfies
minimum support. Frequent itemsets can be
stored ahead of time in hash tables along
Generating Association Rules from with their counts so that they can be
Frequent Itemsets accessed quickly.
Once the frequent itemsets from transactions Eg:- Suppose the data contain the frequent
in a database D have been found, it is itemset l= {I1,I2,I5}. What are the
straightforward to generate strong association rules that can be generated from
association rules from them. This can be l?
done using the following equation for The nonempty subsets of l are {I1, I2}, {I1,
confidence. Where the conditional I5}, {I2, I5}, {I1}, {I2} and {I5}. The
probability is expressed in terms of itemset resulting association rules are as shown
support count. below, each listed with its confidence.

Confidence (A⇒B) = support count (A U B) I1∧I2⇒I5, confidence = 2/4 = 50%

Support count (A) I1∧I5⇒I2, confidence = 2/2 = 100%

where support count (AUB) is the number of I2∧I5⇒I2, confidence = 2/2 = 100%
transactions containing the itemsets AUB, I1⇒I2∧I5, confidence = 2/6 = 33%
and support count (A) is the number of I2⇒I1∧I5, confidence = 2/7 = 29%
transactions containing the itemset A. Based I5⇒I1∧I2, confidence = 2/2 = 100%
on this equation, association rules can be If the minimum confidence threshold is, say,
generated as follows: 70% then only the second, third and last
rules above are output, since these are the An FP-tree is then
only ones generated that are strong. constructed as follows. First, create the root
Mining Frequent Itemsets without of the tree, labeled with “null”. Scan
Candidate Generation database D a second time. The items in each
The Apriori algorithm suffers from two non- transaction are processed in L order and a
trivial costs: branch is created for each transaction. For
1) It may need to generate a huge example, the scan of the first transaction,
number of candidate sets. “T100:I1, I2, I5”, which contains three items
2) It may need to repeatedly scan the (I2, I1, I5) in L order, leads to the
database and checks large set of construction of the first branch of the tree
candidates by pattern matching with three nodes:<(I2:1, (I1:1), (I5:1)>,
An interesting method that mines the where I2 is linked as child of the root, I1 is
complete set of frequent itemsets without linked to I2 and I5 is linked to I2. The
candidate generation is called frequent- second transaction, T200, contains the items
pattern growth of simply FP-growth, I2 and I4 in L order, which would result in a
which adopts a divide-and –conquer strategy branch where I2 is linked to the root and I4
as follows: compress the database is linked to I2. However this branch would
representing frequent items into a set of share a common prefix, (I2:2), with the
conditional databases, each associated with existing path for T100. Therefore, we
one frequent item, and mine each such instead increment the count of the I2 node
database separately. when considering the branch to be added for
Reexamine the mining of transaction a transaction, the count of each node along a
database, using the frequent-pattern growth common prefix is incremented by 1, and
approach. nodes for the item following the prefix are
The first scan of the database is the same as created and linked accordingly.
Apriori, which derives the set of frequent To facilitate tree traversal, an item
items (1-items) and their support counts. Let header table is built so that each item points
the minimum count be 2. The set of frequent to its occurrence in the tree via a chain of
items is sorted in the order of descending node-links. The tree obtained after scanning
support count. This resulting set or list is all of the transactions is
denoted L. Thus, we have L=[I2: 7,I1: 6,I3:
6,I4: 2,I5: 2].
 growth is achieved by the concatenation
tree.
Let’s first consider I5 which is the
last item in L, rather than the first. The
reasoning behind this will become apparent
as we explain the FP-tree mining process. I5
occurs in two branches of the FP-tree. The
paths formed by these branches are < (I2, I2,
I5:1)> and < (I2, I1, I3, I5:1)>. Therefore
considering I5 as a suffix, its corresponding
two prefix paths are < (I2I1:1)> and < (I2,
I1, I3:1) >, which form its conditional
pattern base. Its conditional FP-tree contains
only a single path, (I2:2, I1:2); I3 is not
included because its support count of 1 is
less than the minimum support count. The
single path generates all the combinations of
Item Conditional Conditional Frequent
frequent patterns: I2 I5:2, I1 I5:2, I2 I1 I5:2.
pattern FP-tree patterns
In the same way find the frequent
base generated
I5 {(I2 I1: 1) , <I2:2, I1: I2 I5: 2, itemsets for all other Items. The FP-growth
(I2 I1 I3: 2> I1 I5: 2, method transforms the problem of finding
1)} I2 I1 I5: 2 long frequent patterns to looking for shorter
I4 {(I2 I1: 1) , <I2: 2> I2 I4: 2 ones recursively and then concatenating the
(I2: 1)} suffix. It uses the least frequent items as
suffix, offering good selectivity. The method
The mining of the FP-tree proceeds
substantially reduces the search costs.
as follows. Start from each frequent length-1
pattern, construct its conditional pattern base
CLOSET: An Efficient Algorithm for
(a sub database which consists of the set of
Mining Frequent Closed Itemsets
prefix paths in the FP-tree co-occurring with
the suffix pattern), then construct its
PROBLEM DEFINITION:
(conditional) FP-tree and perform mining
An itemset X is contained in
recursively on such a tree. The pattern
transaction <tid,Y> if X⊆ Y. Given a
transaction database TDB, the support of an large database, which is called the frequent
itemset X, denoted as sup(X), is the number closed itemset mining problem
of transactions in TDB which contain X. An
association rule R: X⇒Y is an implication
between two itemsets X and Y where X,
Y⊂I and X∩Y =∅. The support of the rule,
denoted as sup(X⇒Y), is defined as sup
For the transaction database in table1 with
(XUY). The confidence of the rule, denoted
min_sup = 2, the divide and conquer method
as conf(X⇒Y), is defined as sup
for mining frequent closed itemset.
(XUY)/sup(X).
1) Find frequent items. Scan TDB to
The requirement of mining the complete set
find the set of frequent items and
of association rules leads to two problems:
derive a global frequent item list,
1) There may exist a large number of
called f_list, and f_list = {c:4, e:4,
frequent itemsets in a transaction
f:4, a:3, d:2}, where the items are
database, especially when the
sorted in support descending order
support threshold is low.
any infrequent item, such as b are
2) There may exist a huge number of
omitted..
association rules. It is hard for users
2) Divide search space. All the frequent
to comprehend and manipulate a
closed itemsets can be divided into 5
huge number of rules.
non-overlap subsets based on the
An interesting alternative to this problem is
f_list: (1) the ones containing items
the mining of frequent closed itemsets and
d,(2) the ones containing item a but
their corresponding association rules.
no d, (3) the ones containing item f
Frequent closed itemset: An itemset X is a
but no a not d, (4) the ones
closed itemset if there exist no itemset X’
containing e but no f, a nor d, and (5)
such that (1) X’ is a proper superset of X
the one containing only c. once all
and (2) every transaction containing X also
subsets are found, the complete set of
contains X’. A closed itemset X is frequent
frequent closed itemsets is done.
if its support passes the given support
threshold.
How to find the complete set of
frequent closed itemsets efficiently from
 In the same way find the frequent closed
itemsets for a, f, e, and c.

4) The set of frequent closed itemsets

fund is {acdf :2, a :3, ae :2, cf :4, cef :3, e :
4}
Optimization 1: Compress transactional
and conditional databases using FP-tree
structures. FP-tree compresses databases for
frequent itemset mining. Conditional
databases can be derived from FP-tree
efficiently.
Optimization 2: Extract items appearing in
3) Find subsets of frequent closed every transaction of conditional databases.
itemsets. The subsets of frequent Optimization 3: Directly extract frequent
closed itemsets can be mined by closed itemsets from FP-tree.
constructing corresponding Optimization 4: Prune search branches.
conditional database and mine each
recursively. PERFORMANCE STUDY
Find frequent closed itemsets containing d. Comparison of A-close, CHARM,
Only transaction containing d are needed. and CLOSET, CLOSET out performs both
The d-conditional database, denoted as CHARM and A-close. CLOSET is efficient
TDB|d, contains all the transactions having d, and scalable in mining frequent closed
which is {cefa, cfa}. Notice that item d is itemsets in large databases. It is much faster
omitted in each transaction since it appears than A-close, and also faster than CHARM.
in every transaction in the d-conditional
database. CONCLUSION
The support of d is 2. Items c, f and a appear CLOSET leads to less and more
twice respectively in TDB|d. Therefore, cfad: interesting association’s rules then the other
2 is a frequent closed itemset. Since this previously proposed methods.
itemset covers every frequent items in TDB|d
finishes.