0% found this document useful (0 votes)
52 views

Frequent Pattern Based Clustering Methods

Uploaded by

tanya.sharma
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
52 views

Frequent Pattern Based Clustering Methods

Uploaded by

tanya.sharma
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 23

Frequent Pattern based

Clustering methods

unit4/frequent pattern based clustering


1
methods
What Is Frequent Pattern Analysis?
• Frequent pattern: a pattern (a set of items, subsequences, substructures, etc.)
that occurs frequently in a data set
• First proposed by Agrawal, Imielinski, and Swami [AIS93] in the context of
frequent itemsets and association rule mining
• Motivation: Finding inherent regularities in data
– What products were often purchased together?— Beer and diapers?!
– What are the subsequent purchases after buying a PC?
– What kinds of DNA are sensitive to this new drug?
– Can we automatically classify web documents?
• Applications
– Basket data analysis, cross-marketing, catalog design, sale campaign
analysis, Web log (click stream) analysis, and DNA sequence analysis.
unit4/frequent pattern based clustering
methods
Why Is Freq. Pattern Mining Important?

• Freq. pattern: An intrinsic and important property of datasets


• Foundation for many essential data mining tasks
– Association, correlation, and causality analysis
– Sequential, structural (e.g., sub-graph) patterns
– Pattern analysis in spatiotemporal, multimedia, time-series,
and stream data
– Classification: discriminative, frequent pattern analysis
– Cluster analysis: frequent pattern-based clustering
– Data warehousing: iceberg cube and cube-gradient
– Semantic data compression: fascicles
– Broad applications
Basic Concepts: Frequent Patterns
Tid Items bought • itemset: A set of one or more items
10 Beer, Nuts, Diaper • k-itemset X = {x1, …, xk}
20 Beer, Coffee, Diaper
• (absolute) support, or, support
30 Beer, Diaper, Eggs count of X: Frequency or
40 Nuts, Eggs, Milk occurrence of an itemset X
50 Nuts, Coffee, Diaper, Eggs, Milk
• (relative) support, s, is the fraction
Customer Customer of transactions that contains X (i.e.,
buys both buys diaper the probability that a transaction
contains X)
• An itemset X is frequent if X’s
support is no less than a minsup
threshold
Customer
buys beer
Basic Concepts: Association Rules
Tid Items bought
• Find all the rules X → Y with
10 Beer, Nuts, Diaper
20 Beer, Coffee, Diaper
minimum support and confidence
30 Beer, Diaper, Eggs – support, s, probability that a
40 Nuts, Eggs, Milk transaction contains X  Y
50 Nuts, Coffee, Diaper, Eggs, Milk
– confidence, c, conditional
Customer
buys both
Customer probability that a transaction
buys
diaper having X also contains Y
Let minsup = 50%, minconf = 50%
Freq. Pat.: Beer:3, Nuts:3, Diaper:4, Eggs:3, {Beer,
Customer Diaper}:3
buys beer ◼ Association rules: (many more!)
◼ Beer → Diaper (60%, 100%)
◼ Diaper → Beer (60%, 75%)
Closed Patterns and Max-Patterns
• A long pattern contains a combinatorial number of sub-
patterns, e.g., {a1, …, a100} contains (1001) + (1002) + … + ( 11 00 00) =
2100 – 1 = 1.27*1030 sub-patterns!
• Solution: Mine closed patterns and max-patterns instead
• An itemset X is closed if X is frequent and there exists no super-
pattern Y ‫כ‬X, with the same support as X (proposed by
Pasquier, et al. @ ICDT’99)
• An itemset X is a max-pattern if X is frequent and there exists
no frequent super-pattern Y ‫כ‬X (proposed by Bayardo @
SIGMOD’98)
• Closed pattern is a lossless compression of freq. patterns
– Reducing the # of patterns and rules
Closed Patterns and Max-Patterns
• Exercise. DB = {<a1, …, a100>, < a1, …, a50>}
– Min_sup = 1.
• What is the set of closed itemset?
– <a1, …, a100>: 1
– < a1, …, a50>: 2
• What is the set of max-pattern?
– <a1, …, a100>: 1
• What is the set of all patterns?
– !!
Computational Complexity of Frequent Itemset Mining

• How many itemsets are potentially to be generated in the worst case?


– The number of frequent itemsets to be generated is senstive to the minsup
threshold
– When minsup is low, there exist potentially an exponential number of
frequent itemsets
– The worst case: MN where M: # distinct items, and N: max length of
transactions
• The worst case complexty vs. the expected probability
– Ex. Suppose Walmart has 104 kinds of products
• The chance to pick up one product 10-4
• The chance to pick up a particular set of 10 products: ~10-40
• What is the chance this particular set of 10 products to be frequent 103
times in 109 transactions?
Chapter 5: Mining Frequent Patterns, Association and
Correlations: Basic Concepts and Methods

• Basic Concepts

• Frequent Itemset Mining Methods

• Which Patterns Are Interesting?—Pattern

Evaluation Methods

• Summary
unit4/frequent pattern based clustering 9
methods
Scalable Frequent Itemset Mining Methods

• Apriori: A Candidate Generation-and-Test Approach

• Improving the Efficiency of Apriori

• FPGrowth: A Frequent Pattern-Growth Approach

• ECLAT: Frequent Pattern Mining with Vertical Data

Format
The Downward Closure Property and Scalable
Mining Methods
• The downward closure property of frequent patterns
– Any subset of a frequent itemset must be frequent
– If {beer, diaper, nuts} is frequent, so is {beer, diaper}
– i.e., every transaction having {beer, diaper, nuts} also contains
{beer, diaper}
• Scalable mining methods: Three major approaches
– Apriori (Agrawal & Srikant@VLDB’94)
– Freq. pattern growth (FPgrowth—Han, Pei & Yin
@SIGMOD’00)
– Vertical data format approach (Charm—Zaki & Hsiao
@SDM’02)
Apriori: A Candidate Generation & Test Approach

• Apriori pruning principle: If there is any itemset which is


infrequent, its superset should not be generated/tested!
(Agrawal & Srikant @VLDB’94, Mannila, et al. @ KDD’ 94)
• Method:
– Initially, scan DB once to get frequent 1-itemset
– Generate length (k+1) candidate itemsets from length k
frequent itemsets
– Test the candidates against DB
– Terminate when no frequent or candidate set can be
generated
The Apriori Algorithm—An Example
Supmin = 2 Itemset sup
Database TDB Itemset sup
{A} 2
L1 {A} 2
Tid Items C1 {B} 3
{B} 3
10 A, C, D {C} 3
1st scan {C} 3
20 B, C, E {D} 1
{E} 3
30 A, B, C, E {E} 3
40 B, E
C2 Itemset sup C2 Itemset
{A, B} 1
L2 Itemset sup 2nd scan {A, B}
{A, C} 2
{A, C} 2 {A, C}
{A, E} 1
{B, C} 2 {A, E}
{B, C} 2
{B, E} 3
{B, E} 3 {B, C}
{C, E} 2
{C, E} 2 {B, E}
{C, E}

C3 Itemset L3 Itemset sup


3rd scan
{B, C, E} {B, C, E} 2
ern based g
clusterin
The Apriori Algorithm (Pseudo-Code)
Ck: Candidate itemset of size k
Lk : frequent itemset of size k

L1 = {frequent items};
for (k = 1; Lk !=; k++) do begin
Ck+1 = candidates generated from Lk;
for each transaction t in database do
increment the count of all candidates in Ck+1 that are
contained in t
Lk+1 = candidates in Ck+1 with min_support
end
return k Lk;
Implementation of Apriori
• How to generate candidates?
– Step 1: self-joining Lk
– Step 2: pruning
• Example of Candidate-generation
– L3={abc, abd, acd, ace, bcd}
– Self-joining: L3*L3
• abcd from abc and abd
• acde from acd and ace
– Pruning:
• acde is removed because ade is not in L3
– C4 = {abcd}
How to Count Supports of Candidates?

• Why counting supports of candidates a problem?


– The total number of candidates can be very huge
– One transaction may contain many candidates
• Method:
– Candidate itemsets are stored in a hash-tree
– Leaf node of hash-tree contains a list of itemsets and
counts
– Interior node contains a hash table
– Subset function: finds all the candidates contained in a
transaction
Counting Supports of Candidates Using Hash Tree

Subset function
Transaction: 1 2 3 5 6
3,6,9
1,4,7
2,5,8

1+2356

13+56 234
567
145 356 367
136 345 368
357
12+356
689
124
457 125 159
458
Candidate Generation: An SQL Implementation
• SQL Implementation of candidate generation
– Suppose the items in Lk-1 are listed in an order
– Step 1: self-joining Lk-1
insert into Ck
select p.item1, p.item2, …, p.itemk-1, q.itemk-1
from Lk-1 p, Lk-1 q
where p.item1=q.item1, …, p.itemk-2=q.itemk-2, p.itemk-1 < q.itemk-1
– Step 2: pruning
forall itemsets c in Ck do
forall (k-1)-subsets s of c do
if (s is not in Lk-1) then delete c from Ck
• Use object-relational extensions like UDFs, BLOBs, and Table functions for efficient
implementation [See: S. Sarawagi, S. Thomas, and R. Agrawal. Integrating association
rule mining with relational database systems: Alternatives and implications.
SIGMOD’98]
Scalable Frequent Itemset Mining Methods

• Apriori: A Candidate Generation-and-Test Approach

• Improving the Efficiency of Apriori

• FPGrowth: A Frequent Pattern-Growth Approach

• ECLAT: Frequent Pattern Mining with Vertical Data Format

• Mining Close Frequent Patterns and Maxpatterns

19
19
Further Improvement of the Apriori Method

• Major computational challenges


– Multiple scans of transaction database
– Huge number of candidates
– Tedious workload of support counting for candidates
• Improving Apriori: general ideas
– Reduce passes of transaction database scans
– Shrink number of candidates
– Facilitate support counting of candidates
Partition: Scan Database Only Twice
• Any itemset that is potentially frequent in DB must be frequent
in at least one of the partitions of DB
– Scan 1: partition database and find local frequent patterns
– Scan 2: consolidate global frequent patterns
• A. Savasere, E. Omiecinski and S. Navathe, VLDB’95

DB1 + DB2 + + DBk = DB


sup1(i) < σDB1 sup2(i) < σDB2 supk(i) < σDBk sup(i) < σDB
21
DHP: Reduce the Number of Candidates
• A k-itemset whose corresponding hashing bucket count is below the
threshold cannot be frequent
count itemsets
– Candidates: a, b, c, d, e 35 {ab, ad, ae}
– Hash entries 88 {bd, be, de}

• {ab, ad, ae} . .


.
• {bd, be, de} .
.
.
• …
102 {yz, qs, wt}
– Frequent 1-itemset: a, b, d, e Hash Table
– ab is not a candidate 2-itemset if the sum of count of {ab, ad, ae} is
below support threshold
• J. Park, M. Chen, and P. Yu. An effective hash-based algorithm for mining
association rules. SIGMOD’95
Sampling for Frequent Patterns

• Select a sample of original database, mine frequent patterns


within sample using Apriori
• Scan database once to verify frequent itemsets found in
sample, only borders of closure of frequent patterns are
checked
– Example: check abcd instead of ab, ac, …, etc.
• Scan database again to find missed frequent patterns
• H. Toivonen. Sampling large databases for association rules. In
VLDB’96

You might also like