MINING ASSOCIATION RULES IN LARGE DATABASES

Topics
 Association rule mining
 Algorithms for scalable mining of (single-dimensional
Boolean) association rules in transactional databases
 Mining various kinds of association/correlation rules
 Constraint-based association mining
 Sequential pattern mining
 Applications/extensions of frequent pattern mining
 Summary
3
What Is Association Mining?
 Association rule mining:
 Finding frequent patterns, associations, correlations, or
causal structures among sets of items or objects in
transaction databases, relational databases, and other
information repositories.
 Frequent pattern: pattern (set of items, sequence,
etc.) that occurs frequently in a database [AIS93]
 Motivation: finding 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?
4
Why Is Frequent Pattern or Assoiciation
Mining an Essential Task in Data Mining?
 Foundation for many essential data mining tasks
 Association, correlation, causality
 Sequential patterns, temporal or cyclic association,
partial periodicity, spatial and multimedia association
 Associative classification, cluster analysis, iceberg cube,
fascicles (semantic data compression)
 Broad applications
 Basket data analysis, cross-marketing, catalog design,
sale campaign analysis
 Web log (click stream) analysis, DNA sequence analysis,
etc.
5
Basic Concepts: Frequent Patterns and
Association Rules
 Itemset X=x1, …, xk
 Find all the rules XY with min
confidence and support
 support, s, probability that a
transaction contains XY
 confidence, c, conditional
probability that a transaction
having X also contains Y.
Let min_support = 50%,
min_conf = 50%:
A  C (50%, 66.7%)
C  A (50%, 100%)
Customer
buys diaper
Customer
buys both
Customer
buys beer
Transaction-id Items bought
10 A, B, C
20 A, C
30 A, D
40 B, E, F
6
Mining Association Rules—an Example
For rule A  C:
support = support(AC) = 50%
confidence = support(AC)/support(A) =
66.6%
Min. support 50%
Min. confidence 50%
Transaction-id Items bought
10 A, B, C
20 A, C
30 A, D
40 B, E, F
Frequent pattern Support
A 75%
B 50%
C 50%
A, C 50%
7
ALGORITHMS FOR SCALABLE
MINING OF (SINGLEDIMENSIONAL
BOOLEAN)
ASSOCIATION RULES IN
TRANSACTIONAL DATABASES
8
Apriori: A Candidate Generation-and-test Approach
 Any subset of a frequent itemset must be frequent
 if beer, diaper, nuts is frequent, so is beer,
diaper
 Every transaction having beer, diaper, nuts also
contains beer, diaper
 Apriori pruning principle: If there is any itemset which is
infrequent, its superset should not be generated/tested!
 Method:
 generate length (k+1) candidate itemsets from length k
frequent itemsets, and
 test the candidates against DB
 The performance studies show its efficiency and scalability
 Agrawal & Srikant 1994, Mannila, et al. 1994
9
The Apriori Algorithm—An Example
Database TDB
1st scan
C1
L1
L2
C2 C2
2nd scan
C3 3rd scan L3
Tid Items
10 A, C, D
20 B, C, E
30 A, B, C, E
40 B, E
Itemset sup
A 2
B 3
C 3
D 1
E 3
Itemset sup
A 2
B 3
C 3
E 3
Itemset
A, B
A, C
A, E
B, C
B, E
C, E
Itemset sup
A, B 1
A, C 2
A, E 1
B, C 2
B, E 3
C, E 2
Itemset sup
A, C 2
B, C 2
B, E 3
C, E 2
Itemset
B, C, E
Itemset sup
B, C, E 2
10
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;
11
Important Details of Apriori
 How to generate candidates?
 Step 1: self-joining Lk
 Step 2: pruning
 How to count supports of candidates?
 Example of Candidate-generation
 L3=abc, abd, acd, ace, bcd
 Self-joining: L3L3  abcd from abc and abd  acde from acd and ace  Pruning:  acde is removed because ade is not in L3  C4=abcd 12 How to Generate Candidates?  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 13 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 14 Example: Counting Supports of Candidates 1,4,7 2,5,8 3,6,9 Subset function 2 3 4 5 6 7 1 4 5 1 3 6 1 2 4 4 5 7 1 2 5 4 5 8 1 5 9 3 4 5 3 5 6 3 5 7 6 8 9 3 6 7 3 6 8 Transaction: 1 2 3 5 6 1 + 2 3 5 6 1 2 + 3 5 6 1 3 + 5 6 15 Efficient Implementation of Apriori in SQL  Hard to get good performance out of pure SQL (SQL- 92) based approaches alone  Make use of object-relational extensions like UDFs, BLOBs, Table functions etc.  Get orders of magnitude improvement  S. Sarawagi, S. Thomas, and R. Agrawal. Integrating association rule mining with relational database systems: Alternatives and implications. In SIGMOD’98 16 Challenges of Frequent Pattern Mining  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 17 DIC: Reduce Number of Scans ABCD ABC ABD ACD BCD AB AC BC AD BD CD A B C D Itemset lattice  Once both A and D are determined frequent, the counting of AD begins  Once all length-2 subsets of BCD are determined frequent, the counting of BCD begins Transactions 1-itemsets 2-itemsets … Apriori 1-itemsets 2-items DIC 3-items S. Brin R. Motwani, J. Ullman, and S. Tsur. Dynamic itemset counting and implication rules for market basket data. In SIGMOD’97 18 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. An efficient algorithm for mining association in large databases. In VLDB’95 19 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 20 DHP: Reduce the Number of Candidates  A k-itemset whose corresponding hashing bucket count is below the threshold cannot be frequent  Candidates: a, b, c, d, e  Hash entries: ab, ad, ae bd, be, de …  Frequent 1-itemset: a, b, d, e  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. In SIGMOD’95 21 Eclat/MaxEclat and VIPER: Exploring Vertical Data Format  Use tid-list, the list of transaction-ids containing an itemset  Compression of tid-lists  Itemset A: t1, t2, t3, sup(A)=3  Itemset B: t2, t3, t4, sup(B)=3  Itemset AB: t2, t3, sup(AB)=2  Major operation: intersection of tid-lists  M. Zaki et al. New algorithms for fast discovery of association rules. In KDD’97  P. Shenoy et al. Turbo-charging vertical mining of large databases. In SIGMOD’00 22 Bottleneck of Frequent-pattern Mining  Multiple database scans are costly  Mining long patterns needs many passes of scanning and generates lots of candidates  To find frequent itemset i1i2…i100  # of scans: 100  # of Candidates: (1001) + (1002) + … + (110000) = 2100-1 = 1.271030 !
 Bottleneck: candidate-generation-and-test
 Can we avoid candidate generation?
23
Mining Frequent Patterns Without
Candidate Generation
 Grow long patterns from short ones using local
frequent items
 “abc” is a frequent pattern
 Get all transactions having “abc”: DB|abc
 “d” is a local frequent item in DB|abc  abcd is
a frequent pattern
24
Construct FP-tree from a Transaction Database

f:4 c:1
b:1
p:1
c:3 b:1
a:3
m:2 b:1
p:2 m:1
Header Table
Item frequency head
f 4
c 4
a 3
b 3
m 3
p 3
min_support = 3
TID Items bought (ordered) frequent items
100 f, a, c, d, g, i, m, p f, c, a, m, p
200 a, b, c, f, l, m, o f, c, a, b, m
300 b, f, h, j, o, w f, b
400 b, c, k, s, p c, b, p
500 a, f, c, e, l, p, m, n f, c, a, m, p

1. Scan DB once, find
   frequent 1-itemset
   (single item pattern)
2. Sort frequent items in
   frequency descending
   order, f-list
3. Scan DB again,
   construct FP-tree
   F-list=f-c-a-b-m-p
   25
   Benefits of the FP-tree Structure
    Completeness
    Preserve complete information for frequent pattern
   mining
    Never break a long pattern of any transaction
    Compactness
    Reduce irrelevant info—infrequent items are gone
    Items in frequency descending order: the more
   frequently occurring, the more likely to be shared
    Never be larger than the original database (not count
   node-links and the count field)
    For Connect-4 DB, compression ratio could be over 100
   26
   Partition Patterns and Databases
    Frequent patterns can be partitioned into subsets
   according to f-list
    F-list=f-c-a-b-m-p
    Patterns containing p
    Patterns having m but no p
    …
    Patterns having c but no a nor b, m, p
    Pattern f
    Completeness and non-redundency
   27
   Find Patterns Having P From P-conditional Database
    Starting at the frequent item header table in the FP-tree
    Traverse the FP-tree by following the link of each frequent item p
    Accumulate all of transformed prefix paths of item p to form p’s
   conditional pattern base
   Conditional pattern bases
   item cond. pattern base
   c f:3
   a fc:3
   b fca:1, f:1, c:1
   m fca:2, fcab:1
   p fcam:2, cb:1
   
   f:4 c:1
   b:1
   p:1
   c:3 b:1
   a:3
   m:2 b:1
   p:2 m:1
   Header Table
   Item frequency head
   f 4
   c 4
   a 3
   b 3
   m 3
   p 3
   28
   From Conditional Pattern-bases to Conditional FP-trees
    For each pattern-base
    Accumulate the count for each item in the base
    Construct the FP-tree for the frequent items of the
   pattern base
   m-conditional pattern base:
   fca:2, fcab:1
   
   f:3
   c:3
   a:3
   m-conditional FP-tree
   All frequent
   patterns relate to m
   m,
   fm, cm, am,
   fcm, fam, cam,
   fcam
    
   
   f:4 c:1
   b:1
   p:1
   c:3 b:1
   a:3
   m:2 b:1
   p:2 m:1
   Header Table
   Item frequency head
   f 4
   c 4
   a 3
   b 3
   m 3
   p 3
   29
   Recursion: Mining Each Conditional FP-tree
   
   f:3
   c:3
   a:3
   m-conditional FP-tree
   Cond. pattern base of “am”: (fc:3)
   
   f:3
   c:3
   am-conditional FP-tree
   Cond. pattern base of “cm”: (f:3)
   
   f:3
   cm-conditional FP-tree
   Cond. pattern base of “cam”: (f:3)
   
   f:3
   cam-conditional FP-tree
   30
   A Special Case: Single Prefix Path in FP-tree
    Suppose a (conditional) FP-tree T has a shared single prefix-path P
    Mining can be decomposed into two parts
    Reduction of the single prefix path into one node
    Concatenation of the mining results of the two parts
   
   a2:n2
   a3:n3
   a1:n1
   
   b1:m1 C1:k1
   C2:k2 C3:k3
   b1:m1 C1:k1
   C2:k2 C3:k3
   r1

• a2:n2
  a3:n3
  a1:n1
  
  r1 =
  31
  Mining Frequent Patterns With FP-trees
   Idea: Frequent pattern growth
   Recursively grow frequent patterns by pattern and
  database partition
   Method
   For each frequent item, construct its conditional
  pattern-base, and then its conditional FP-tree
   Repeat the process on each newly created conditional
  FP-tree
   Until the resulting FP-tree is empty, or it contains only
  one path—single path will generate all the
  combinations of its sub-paths, each of which is a
  frequent pattern
  32
  Scaling FP-growth by DB Projection
   FP-tree cannot fit in memory?—DB projection
   First partition a database into a set of projected DBs
   Then construct and mine FP-tree for each projected
  DB
   Parallel projection vs. Partition projection techniques
   Parallel projection is space costly
  33
  Partition-based Projection
   Parallel projection needs a lot
  of disk space
   Partition projection saves it
  Tran. DB
  fcamp
  fcabm
  fb
  cbp
  fcamp
  p-proj DB
  fcam
  cb
  fcam
  m-proj DB
  fcab
  fca
  fca
  b-proj DB
  f
  cb
  …
  a-proj DB
  fc…
  c-proj DB
  f
  …
  f-proj DB
  …
  am-proj DB
  fc
  fc
  fc
  cm-proj DB
  fff
  …
  34
  FP-Growth vs. Apriori: Scalability With the Support
  Threshold
  0
  10
  20
  30
  40
  50
  60
  70
  80
  90
  100
  0 0.5 1 1.5 2 2.5 3
  Support threshold(%)
  Run time (se c.)
  D1 FP-growth runtime
  D1 Apriori runtime
  Data set T25I20D10K
  35
  FP-Growth vs. Tree-Projection: Scalability with
  the Support Threshold
  0
  20
  40
  60
  80
  100
  120
  140
  0 0.5 1 1.5 2
  Support threshold (%) Runtime (
  sec.)
  D2 FP-growth
  D2 TreeProjection Data set T25I20D100K
  36
  Why Is FP-Growth the Winner?
   Divide-and-conquer:
   decompose both the mining task and DB according to
  the frequent patterns obtained so far
   leads to focused search of smaller databases
   Other factors
   no candidate generation, no candidate test
   compressed database: FP-tree structure
   no repeated scan of entire database
   basic ops—counting local freq items and building sub
  FP-tree, no pattern search and matching
  37
  Implications of the Methodology
   Mining closed frequent itemsets and max-patterns
   CLOSET (DMKD’00)
   Mining sequential patterns
   FreeSpan (KDD’00), PrefixSpan (ICDE’01)
   Constraint-based mining of frequent patterns
   Convertible constraints (KDD’00, ICDE’01)
   Computing iceberg data cubes with complex measures
   H-tree and H-cubing algorithm (SIGMOD’01)
  38
  Max-patterns
   Frequent pattern a1, …, a100  (1001) + (1002) + …
• (110000) = 2100-1 = 1.27*1030 frequent subpatterns!
   Max-pattern: frequent patterns without proper
  frequent super pattern
   BCDE, ACD are max-patterns
   BCD is not a max-pattern
  Tid Items
  10 A,B,C,D,E
  20 B,C,D,E,
  Min_sup=2 30 A,C,D,F
  39
  MaxMiner: Mining Max-patterns
   1st scan: find frequent items
   A, B, C, D, E
   2nd scan: find support for
   AB, AC, AD, AE, ABCDE
   BC, BD, BE, BCDE
   CD, CE, CDE, DE,
   Since BCDE is a max-pattern, no need to check
  BCD, BDE, CDE in later scan
   R. Bayardo. Efficiently mining long patterns from
  databases. In SIGMOD’98
  Tid Items
  10 A,B,C,D,E
  20 B,C,D,E,
  30 A,C,D,F
  Potential
  max-patterns
  40
  Frequent Closed Patterns
   Conf(acd)=100%  record acd only
   For frequent itemset X, if there exists no item y
  s.t. every transaction containing X also contains
  y, then X is a frequent closed pattern
   “acd” is a frequent closed pattern
   Concise rep. of freq pats
   Reduce # of patterns and rules
   N. Pasquier et al. In ICDT’99
  TID Items
  10 a, c, d, e, f
  20 a, b, e
  30 c, e, f
  40 a, c, d, f
  50 c, e, f
  Min_sup=2
  41
  Mining Frequent Closed Patterns: CLOSET
   Flist: list of all frequent items in support ascending order
   Flist: d-a-f-e-c
   Divide search space
   Patterns having d
   Patterns having d but no a, etc.
   Find frequent closed pattern recursively
   Every transaction having d also has cfa  cfad is a
  frequent closed pattern
   J. Pei, J. Han & R. Mao. CLOSET: An Efficient Algorithm for Mining
  Frequent Closed Itemsets”, DMKD’00.
  TID Items
  10 a, c, d, e, f
  20 a, b, e
  30 c, e, f
  40 a, c, d, f
  50 c, e, f
  Min_sup=2
  42
  Mining Frequent Closed Patterns: CHARM
   Use vertical data format: t(AB)=T1, T12, …
   Derive closed pattern based on vertical intersections
   t(X)=t(Y): X and Y always happen together
   t(X)t(Y): transaction having X always has Y
   Use diffset to accelerate mining
   Only keep track of difference of tids
   t(X)=T1, T2, T3, t(Xy )=T1, T3
   Diffset(Xy, X)=T2
   M. Zaki. CHARM: An Efficient Algorithm for Closed Association Rule Mining,
  CS-TR99-10, Rensselaer Polytechnic Institute
   M. Zaki, Fast Vertical Mining Using Diffsets, TR01-1, Department of Computer
  Science, Rensselaer Polytechnic Institute
  43
  Visualization of Association Rules: Pane Graph
  44
  Visualization of Association Rules: Rule Graph
  45
  MINING VARIOUS KINDS OF
  ASSOCIATION/CORRELATION
  RULES
  46
  Mining Various Kinds of Rules or Regularities
   Multi-level, quantitative association rules,
  correlation and causality, ratio rules, sequential
  patterns, emerging patterns, temporal
  associations, partial periodicity
   Classification, clustering, iceberg cubes, etc.
  47
  Multiple-level Association Rules
   Items often form hierarchy
   Flexible support settings: Items at the lower level are
  expected to have lower support.
   Transaction database can be encoded based on
  dimensions and levels
   explore shared multi-level mining
  uniform support
  Milk
  [support = 10%]
  2% Milk
  [support = 6%]
  Skim Milk
  [support = 4%]
  Level 1
  min_sup = 5%
  Level 2
  min_sup = 5%
  Level 1
  min_sup = 5%
  Level 2
  min_sup = 3%
  reduced support
  48
  ML/MD Associations with Flexible Support Constraints
   Why flexible support constraints?
   Real life occurrence frequencies vary greatly
   Diamond, watch, pens in a shopping basket
   Uniform support may not be an interesting model
   A flexible model
   The lower-level, the more dimension combination, and the long
  pattern length, usually the smaller support
   General rules should be easy to specify and understand
   Special items and special group of items may be specified
  individually and have higher priority
  49
  Multi-dimensional Association
   Single-dimensional rules:
  buys(X, “milk”)  buys(X, “bread”)
   Multi-dimensional rules:  2 dimensions or predicates
   Inter-dimension assoc. rules (no repeated predicates)
  age(X,”19-25”)  occupation(X,“student”)  buys(X,“coke”)
   hybrid-dimension assoc. rules (repeated predicates)
  age(X,”19-25”)  buys(X, “popcorn”)  buys(X, “coke”)
   Categorical Attributes
   finite number of possible values, no ordering among values
   Quantitative Attributes
   numeric, implicit ordering among values
  50
  Multi-level Association: Redundancy Filtering
   Some rules may be redundant due to “ancestor”
  relationships between items.
   Example
   milk  wheat bread [support = 8%, confidence = 70%]
   2% milk  wheat bread [support = 2%, confidence = 72%]
   We say the first rule is an ancestor of the second rule.
   A rule is redundant if its support is close to the
  “expected” value, based on the rule’s ancestor.
  51
  Multi-Level Mining: Progressive Deepening
   A top-down, progressive deepening approach:
   First mine high-level frequent items:
  milk (15%), bread (10%)
   Then mine their lower-level “weaker” frequent
  itemsets:
  2% milk (5%), wheat bread (4%)
   Different min_support threshold across multi-levels lead
  to different algorithms:
   If adopting the same min_support across multi-levels
  then toss t if any of t’s ancestors is infrequent.
   If adopting reduced min_support at lower levels
  then examine only those descendents whose ancestor’s support
  is frequent/non-negligible.
  52
  Techniques for Mining MD Associations
   Search for frequent k-predicate set:
   Example: age, occupation, buys is a 3-predicate set
   Techniques can be categorized by how age are treated

1. Using static discretization of quantitative attributes
    Quantitative attributes are statically discretized by using
   predefined concept hierarchies
2. Quantitative association rules
    Quantitative attributes are dynamically discretized into
   “bins”based on the distribution of the data
3. Distance-based association rules
    This is a dynamic discretization process that considers
   the distance between data points
   53
   Static Discretization of Quantitative Attributes
    Discretized prior to mining using concept hierarchy.
    Numeric values are replaced by ranges.
    In relational database, finding all frequent k-predicate sets
   will require k or k+1 table scans.
    Data cube is well suited for mining.
    The cells of an n-dimensional
   cuboid correspond to the
   predicate sets.
    Mining from data cubes
   can be much faster.
   (age) (income)
   ()
   (buys)
   (age, income) (age,buys) (income,buys)
   (age,income,buys)
   54
   Quantitative Association Rules
   age(X,”30-34”)  income(X,”24K –
   48K”)
    buys(X,”high resolution TV”)
    Numeric attributes are dynamically discretized
    Such that the confidence or compactness of the rules
   mined is maximized
    2-D quantitative association rules: Aquan1  Aquan2  Acat
    Cluster “adjacent”
   association rules
   to form general
   rules using a 2-D
   grid
    Example
   55
   Mining Distance-based Association Rules
    Binning methods do not capture the semantics of interval
   data
    Distance-based partitioning, more meaningful discretization
   considering:
    density/number of points in an interval
    “closeness” of points in an interval
   Price($)
   Equi-width
   (width $10)
   Equi-depth
   (depth 2)
   Distancebased
   7 [0,10] [7,20] [7,7]
   20 [11,20] [22,50] [20,22]
   22 [21,30] [51,53] [50,53]
   50 [31,40]
   51 [41,50]
   53 [51,60]
   56
   Interestingness Measure: Correlations (Lift)
    play basketball  eat cereal [40%, 66.7%] is misleading
    The overall percentage of students eating cereal is 75% which is
   higher than 66.7%.
    play basketball  not eat cereal [20%, 33.3%] is more accurate,
   although with lower support and confidence
    Measure of dependent/correlated events: lift
   Basketball Not basketball Sum (row)
   Cereal 2000 1750 3750
   Not cereal 1000 250 1250
   Sum(col.) 3000 2000 5000
   ( ) ( )
   ( )
   , P A P B
   corr P A B A B
   
   
   57
   CONSTRAINT-BASED
   ASSOCIATION MINING
   58
   Constraint-based Data Mining
    Finding all the patterns in a database autonomously? —
   unrealistic!
    The patterns could be too many but not focused!
    Data mining should be an interactive process
    User directs what to be mined using a data mining
   query language (or a graphical user interface)
    Constraint-based mining
    User flexibility: provides constraints on what to be
   mined
    System optimization: explores such constraints for
   efficient mining—constraint-based mining
   59
   Constraints in Data Mining
    Knowledge type constraint:
    classification, association, etc.
    Data constraint — using SQL-like queries
    find product pairs sold together in stores in Vancouver
   in Dec.’00
    Dimension/level constraint
    in relevance to region, price, brand, customer category
    Rule (or pattern) constraint
    small sales (price < $10) triggers big sales (sum >
   $200)
    Interestingness constraint
    strong rules: min_support  3%, min_confidence 
   60%
   60
   Constrained Mining vs. Constraint-Based Search
    Constrained mining vs. constraint-based search/reasoning
    Both are aimed at reducing search space
    Finding all patterns satisfying constraints vs. finding
   some (or one) answer in constraint-based search in AI
    Constraint-pushing vs. heuristic search
    It is an interesting research problem on how to
   integrate them
    Constrained mining vs. query processing in DBMS
    Database query processing requires to find all
    Constrained pattern mining shares a similar philosophy
   as pushing selections deeply in query processing
   61
   Constrained Frequent Pattern Mining: A Mining Query
   Optimization Problem
    Given a frequent pattern mining query with a set of constraints C, the
   algorithm should be
    sound: it only finds frequent sets that satisfy the given
   constraints C
    complete: all frequent sets satisfying the given
   constraints C are found
    A naïve solution
    First find all frequent sets, and then test them for
   constraint satisfaction
    More efficient approaches:
    Analyze the properties of constraints comprehensively
    Push them as deeply as possible inside the frequent
   pattern computation.
   62
   Anti-Monotonicity in Constraint-Based Mining
    Anti-monotonicity
    When an intemset S violates the
   constraint, so does any of its superset
    sum(S.Price)  v is anti-monotone
    sum(S.Price)  v is not anti-monotone
    Example. C: range(S.profit)  15 is antimonotone
    Itemset ab violates C
    So does every superset of ab
   TID Transaction
   10 a, b, c, d, f
   20 b, c, d, f, g, h
   30 a, c, d, e, f
   40 c, e, f, g
   TDB (min_sup=2)
   Item Profit
   a 40
   b 0
   c -20
   d 10
   e -30
   f 30
   g 20
   h -10
   63
   Which Constraints Are Anti-Monotone?
   Constraint Antimonotone
   v  S No
   S  V no
   S  V yes
   min(S)  v no
   min(S)  v yes
   max(S)  v yes
   max(S)  v no
   count(S)  v yes
   count(S)  v no
   sum(S)  v ( a  S, a  0 ) yes
   sum(S)  v ( a  S, a  0 ) no
   range(S)  v yes
   range(S)  v no
   avg(S)  v,   , ,  convertible
   support(S)   yes
   support(S)   no
   64
   Monotonicity in Constraint-Based Mining
    Monotonicity
    When an intemset S satisfies the
   constraint, so does any of its
   superset
    sum(S.Price)  v is monotone
    min(S.Price)  v is monotone
    Example. C: range(S.profit)  15
    Itemset ab satisfies C
    So does every superset of ab
   TID Transaction
   10 a, b, c, d, f
   20 b, c, d, f, g, h
   30 a, c, d, e, f
   40 c, e, f, g
   TDB (min_sup=2)
   Item Profit
   a 40
   b 0
   c -20
   d 10
   e -30
   f 30
   g 20
   h -10
   65
   Which Constraints Are Monotone?
   Constraint Monotone
   v  S yes
   S  V yes
   S  V no
   min(S)  v yes
   min(S)  v no
   max(S)  v no
   max(S)  v yes
   count(S)  v no
   count(S)  v yes
   sum(S)  v ( a  S, a  0 ) no
   sum(S)  v ( a  S, a  0 ) yes
   range(S)  v no
   range(S)  v yes
   avg(S)  v,   , ,  convertible
   support(S)   no
   support(S)   yes
   66
   Succinctness
    Succinctness:
    Given A1, the set of items satisfying a succinctness
   constraint C, then any set S satisfying C is based on
   A1 , i.e., S contains a subset belonging to A1
    Idea: Without looking at the transaction database,
   whether an itemset S satisfies constraint C can be
   determined based on the selection of items
    min(S.Price)  v is succinct
    sum(S.Price)  v is not succinct
    Optimization: If C is succinct, C is pre-counting pushable
   67
   Which Constraints Are Succinct?
   Constraint Succinct
   v  S yes
   S  V yes
   S  V yes
   min(S)  v yes
   min(S)  v yes
   max(S)  v yes
   max(S)  v yes
   count(S)  v weakly
   count(S)  v weakly
   sum(S)  v ( a  S, a  0 ) no
   sum(S)  v ( a  S, a  0 ) no
   range(S)  v no
   range(S)  v no
   avg(S)  v,   , ,  no
   support(S)   no
   support(S)   no
   68
   The Apriori Algorithm — Example
   TID Items
   100 1 3 4
   200 2 3 5
   300 1 2 3 5
   400 2 5
   Database D itemset sup.
   1 2
   2 3
   3 3
   4 1
   5 3
   itemset sup.
   1 2
   2 3
   3 3
   5 3
   Scan D
   C1
   L1
   itemset
   1 2
   1 3
   1 5
   2 3
   2 5
   3 5
   itemset sup
   1 2 1
   1 3 2
   1 5 1
   2 3 2
   2 5 3
   3 5 2
   itemset sup
   1 3 2
   2 3 2
   2 5 3
   3 5 2
   L2
   C2 C2
   Scan D
   C3 itemset L3
   2 3 5
   Scan D itemset sup
   2 3 5 2
   69
   Naïve Algorithm: Apriori + Constraint
   TID Items
   100 1 3 4
   200 2 3 5
   300 1 2 3 5
   400 2 5
   Database D itemset sup.
   1 2
   2 3
   3 3
   4 1
   5 3
   itemset sup.
   1 2
   2 3
   3 3
   5 3
   Scan D
   C1
   L1
   itemset
   1 2
   1 3
   1 5
   2 3
   2 5
   3 5
   itemset sup
   1 2 1
   1 3 2
   1 5 1
   2 3 2
   2 5 3
   3 5 2
   itemset sup
   1 3 2
   2 3 2
   2 5 3
   3 5 2
   L2
   C2 C2
   Scan D
   C3 itemset L3
   2 3 5
   Scan D itemset sup
   2 3 5 2
   Constraint:
   SumS.price < 5 70 The Constrained Apriori Algorithm: Push an Anti-monotone Constraint Deep TID Items 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5 Database D itemset sup. 1 2 2 3 3 3 4 1 5 3 itemset sup. 1 2 2 3 3 3 5 3 Scan D C1 L1 itemset 1 2 1 3 1 5 2 3 2 5 3 5 itemset sup 1 2 1 1 3 2 1 5 1 2 3 2 2 5 3 3 5 2 itemset sup 1 3 2 2 3 2 2 5 3 3 5 2 L2 C2 C2 Scan D C3 itemset L3 2 3 5 Scan D itemset sup 2 3 5 2 Constraint: SumS.price < 5 71 The Constrained Apriori Algorithm: Push a Succinct Constraint Deep TID Items 100 1 3 4 200 2 3 5 300 1 2 3 5 400 2 5 Database D itemset sup. 1 2 2 3 3 3 4 1 5 3 itemset sup. 1 2 2 3 3 3 5 3 Scan D C1 L1 itemset 1 2 1 3 1 5 2 3 2 5 3 5 itemset sup 1 2 1 1 3 2 1 5 1 2 3 2 2 5 3 3 5 2 itemset sup 1 3 2 2 3 2 2 5 3 3 5 2 L2 C2 C2 Scan D C3 itemset L3 2 3 5 Scan D itemset sup 2 3 5 2 Constraint: minS.price <= 1 72 Converting “Tough” Constraints  Convert tough constraints into antimonotone or monotone by properly ordering items  Examine C: avg(S.profit)  25  Order items in value-descending order 
    If an itemset afb violates C
    So does afbh, afb*
    It becomes anti-monotone!
   TID Transaction
   10 a, b, c, d, f
   20 b, c, d, f, g, h
   30 a, c, d, e, f
   40 c, e, f, g
   TDB (min_sup=2)
   Item Profit
   a 40
   b 0
   c -20
   d 10
   e -30
   f 30
   g 20
   h -10
   73
   Convertible Constraints
    Let R be an order of items
    Convertible anti-monotone
    If an itemset S violates a constraint C, so does every
   itemset having S as a prefix w.r.t. R
    Ex. avg(S)  v w.r.t. item value descending order
    Convertible monotone
    If an itemset S satisfies constraint C, so does every
   itemset having S as a prefix w.r.t. R
    Ex. avg(S)  v w.r.t. item value descending order
   74
   Strongly Convertible Constraints
    avg(X)  25 is convertible anti-monotone w.r.t.
   item value descending order R:
    If an itemset af violates a constraint C,
   so does every itemset with af as prefix,
   such as afd
    avg(X)  25 is convertible monotone w.r.t. item
   value ascending order R-1:
    If an itemset d satisfies a constraint C,
   so does itemsets df and dfa, which
   having d as a prefix
    Thus, avg(X)  25 is strongly convertible
   Item Profit
   a 40
   b 0
   c -20
   d 10
   e -30
   f 30
   g 20
   h -10
   75
   What Constraints Are Convertible?
   Constraint Convertible antimonotone
   Convertible
   monotone
   Strongly
   convertible
   avg(S)  ,  v Yes Yes Yes
   median(S)  ,  v Yes Yes Yes
   sum(S)  v (items could be of any value,
   v  0) Yes No No
   sum(S)  v (items could be of any value,
   v  0) No Yes No
   sum(S)  v (items could be of any value,
   v  0) No Yes No
   sum(S)  v (items could be of any value,
   v  0) Yes No No
   ……
   76
   Combing Them Together—A General Picture
   Constraint Antimonotone Monotone Succinct
   v  S no yes yes
   S  V no yes yes
   S  V yes no yes
   min(S)  v no yes yes
   min(S)  v yes no yes
   max(S)  v yes no yes
   max(S)  v no yes yes
   count(S)  v yes no weakly
   count(S)  v no yes weakly
   sum(S)  v ( a  S, a  0 ) yes no no
   sum(S)  v ( a  S, a  0 ) no yes no
   range(S)  v yes no no
   range(S)  v no yes no
   avg(S)  v,   , ,  convertible convertible no
   support(S)   yes no no
   support(S)   no yes no
   77
   Classification of Constraints
   Convertible
   anti-monotone
   Convertible
   monotone
   Strongly
   convertible
   Inconvertible
   Succinct
   Antimonotone Monotone
   78
   Mining With Convertible Constraints
    C: avg(S.profit)  25
    List of items in every transaction in
   value descending order R:
   
    C is convertible anti-monotone
   w.r.t. R
    Scan transaction DB once
    remove infrequent items
    Item h in transaction 40 is
   dropped
    Itemsets a and f are good
   TID Transaction
   10 a, f, d, b, c
   20 f, g, d, b, c
   30 a, f, d, c, e
   40 f, g, h, c, e
   TDB (min_sup=2)
   Item Profit
   a 40
   f 30
   g 20
   d 10
   b 0
   h -10
   c -20
   e -30
   79
   Can Apriori Handle Convertible Constraint?
    A convertible, not monotone nor anti-monotone
   nor succinct constraint cannot be pushed deep
   into the an Apriori mining algorithm
    Within the level wise framework, no direct
   pruning based on the constraint can be made
    Itemset df violates constraint C: avg(X)>=25
    Since adf satisfies C, Apriori needs df to
   assemble adf, df cannot be pruned
    But it can be pushed into frequent-pattern
   growth framework!
   Item Value
   a 40
   b 0
   c -20
   d 10
   e -30
   f 30
   g 20
   h -10
   80
   Mining With Convertible Constraints
    C: avg(X)>=25, min_sup=2
    List items in every transaction in value descending order R:
   
    C is convertible anti-monotone w.r.t. R
    Scan TDB once
    remove infrequent items
    Item h is dropped
    Itemsets a and f are good, …
    Projection-based mining
    Imposing an appropriate order on item projection
    Many tough constraints can be converted into
   (anti)-monotone
   TID Transaction
   10 a, f, d, b, c
   20 f, g, d, b, c
   30 a, f, d, c, e
   40 f, g, h, c, e
   TDB (min_sup=2)
   Item Value
   a 40
   f 30
   g 20
   d 10
   b 0
   h -10
   c -20
   e -30
   81
   Handling Multiple Constraints
    Different constraints may require different or even
   conflicting item-ordering
    If there exists an order R s.t. both C1 and C2 are
   convertible w.r.t. R, then there is no conflict between
   the two convertible constraints
    If there exists conflict on order of items
    Try to satisfy one constraint first
    Then using the order for the other constraint to mine
   frequent itemsets in the corresponding projected
   database
   82
   SEQUENTIAL PATTERN MINING
   83
   Sequence Databases and Sequential
   Pattern Analysis
    Transaction databases, time-series databases vs. sequence
   databases
    Frequent patterns vs. (frequent) sequential patterns
    Applications of sequential pattern mining
    Customer shopping sequences:
    First buy computer, then CD-ROM, and then digital camera,
   within 3 months.
    Medical treatment, natural disasters (e.g., earthquakes),
   science & engineering processes, stocks and markets, etc.
    Telephone calling patterns, Weblog click streams
    DNA sequences and gene structures
   84
   What Is Sequential Pattern Mining?
    Given a set of sequences, find the complete set
   of frequent subsequences
   A sequence database
   A sequence : < (ef) (ab) (df) c b >
   An element may contain a set of items.
   Items within an element are unordered
   and we list them alphabetically.
   is a subsequence
   of
   Given support threshold min_sup =2, <(ab)c> is a
   sequential pattern
   SID sequence
   10
   20 <(ad)c(bc)(ae)>
   30 <(ef)(ab)(df)cb>
   40
   85
   Challenges on Sequential Pattern Mining
    A huge number of possible sequential patterns are
   hidden in databases
    A mining algorithm should
    find the complete set of patterns, when possible,
   satisfying the minimum support (frequency) threshold
    be highly efficient, scalable, involving only a small
   number of database scans
    be able to incorporate various kinds of user-specific
   constraints
   86
   Studies on Sequential Pattern Mining
    Concept introduction and an initial Apriori-like algorithm
    R. Agrawal & R. Srikant. “Mining sequential patterns,” ICDE’95
    GSP—An Apriori-based, influential mining method (developed at IBM
   Almaden)
    R. Srikant & R. Agrawal. “Mining sequential patterns:
   Generalizations and performance improvements,” EDBT’96
    From sequential patterns to episodes (Apriori-like + constraints)
    H. Mannila, H. Toivonen & A.I. Verkamo. “Discovery of frequent
   episodes in event sequences,” Data Mining and Knowledge
   Discovery, 1997
    Mining sequential patterns with constraints
    M.N. Garofalakis, R. Rastogi, K. Shim: SPIRIT: Sequential
   Pattern Mining with Regular Expression Constraints. VLDB 1999
   87
   A Basic Property of Sequential Patterns: Apriori
    A basic property: Apriori (Agrawal & Sirkant’94)
    If a sequence S is not frequent
    Then none of the super-sequences of S is frequent
    E.g, is infrequent  so do and <(ah)b>
   50
   40 <(be)(ce)d>
   30 <(ah)(bf)abf>
   20 <(bf)(ce)b(fg)>
   10 <(bd)cb(ac)>
   Seq. ID Sequence Given support threshold
   min_sup =2
   88
   GSP—A Generalized Sequential Pattern Mining Algorithm
    GSP (Generalized Sequential Pattern) mining algorithm
    proposed by Agrawal and Srikant, EDBT’96
    Outline of the method
    Initially, every item in DB is a candidate of length-1
    for each level (i.e., sequences of length-k) do
    scan database to collect support count for each
   candidate sequence
    generate candidate length-(k+1) sequences from
   length-k frequent sequences using Apriori
    repeat until no frequent sequence or no candidate
   can be found
    Major strength: Candidate pruning by Apriori
   89
   Finding Length-1 Sequential Patterns
    Examine GSP using an example
    Initial candidates: all singleton sequences
    , , , , , ,
   ,
    Scan database once, count support for
   candidates
   50
   40 <(be)(ce)d>
   30 <(ah)(bf)abf>
   20 <(bf)(ce)b(fg)>
   10 <(bd)cb(ac)>
   Seq. ID Sequence
   min_sup =2
   Cand Sup
   3
   5
   4
   3
   3
   2
   1
   1
   90
   Generating Length-2 Candidates
   <(ab)> <(ac)> <(ad)> <(ae)> <(af)>
   <(bc)> <(bd)> <(be)> <(bf)>
   <(cd)> <(ce)> <(cf)>
   <(de)> <(df)>
   <(ef)>
   
   51 length-2
   Candidates
   Without Apriori
   property,
   88+87/2=92
   candidates
   Apriori prunes
   44.57% candidates
   92
   Generating Length-3 Candidates and Finding Length-3 Patterns
    Generate Length-3 Candidates
    Self-join length-2 sequential patterns
    Based on the Apriori property
    , and are all length-2 sequential
   patterns  is a length-3 candidate
    <(bd)>, and are all length-2 sequential
   patterns  <(bd)b> is a length-3 candidate
    46 candidates are generated
    Find Length-3 Sequential Patterns
    Scan database once more, collect support counts for
   candidates
    19 out of 46 candidates pass support threshold
   93
   The GSP Mining Process
   
   … … <(ab)> … <(ef)>
   …
   <(bd)bc> …
   <(bd)cba>
   1st scan: 8 cand. 6 length-1 seq.
   pat.
   2nd scan: 51 cand. 19 length-2 seq.
   pat. 10 cand. not in DB at all
   3rd scan: 46 cand. 19 length-3 seq.
   pat. 20 cand. not in DB at all
   4th scan: 8 cand. 6 length-4 seq.
   pat.
   5th scan: 1 cand. 1 length-5 seq.
   pat.
   Cand. cannot pass
   sup. threshold
   Cand. not in DB at all
   50
   40 <(be)(ce)d>
   30 <(ah)(bf)abf>
   20 <(bf)(ce)b(fg)>
   10 <(bd)cb(ac)>
   Seq. ID Sequence
   min_sup =2
   95
   Bottlenecks of GSP
    A huge set of candidates could be generated
    1,000 frequent length-1 sequences generate
   length-2 candidates!
    Multiple scans of database in mining
    Real challenge: mining long sequential patterns
    An exponential number of short candidates
    A length-100 sequential pattern needs 1030
   candidate sequences!
   1,499,500
   2
   1000 1000 1000 999 
   
    
   100 30
   100
   1
   2 1 10
   100
       
   
   
    
    
    i i
   96
   FreeSpan: Frequent Pattern-Projected
   Sequential Pattern Mining
    A divide-and-conquer approach
    Recursively project a sequence database into a set of smaller
   databases based on the current set of frequent patterns
    Mine each projected database to find its patterns
    J. Han J. Pei, B. Mortazavi-Asi, Q. Chen, U. Dayal, M.C. Hsu, FreeSpan:
   Frequent pattern-projected sequential pattern mining. In KDD’00.
   f_list: b:5, c:4, a:3, d:3, e:3, f:2
   All seq. pat. can be divided into 6 subsets:
   •Seq. pat. containing item f
   •Those containing e but no f
   •Those containing d but no e nor f
   •Those containing a but no d, e or f
   •Those containing c but no a, d, e or f
   •Those containing only item b
   Sequence Database SDB
   < (bd) c b (ac) >
   < (bf) (ce) b (fg) >
   < (ah) (bf) a b f >
   < (be) (ce) d >
   < a (bd) b c b (ade) >
   97
   From FreeSpan to PrefixSpan: Why?
    Freespan:
    Projection-based: No candidate sequence needs to be
   generated
    But, projection can be performed at any point in the
   sequence, and the projected sequences do will not
   shrink much
    PrefixSpan
    Projection-based
    But only prefix-based projection: less projections and
   quickly shrinking sequences
   98
   Prefix and Suffix (Projection)
    , , and are
   prefixes of sequence
    Given sequence
   Prefix Suffix (Prefix-Based Projection)
   <(abc)(ac)d(cf)>
   <(_bc)(ac)d(cf)>
   <(_c)(ac)d(cf)>
   99
   Mining Sequential Patterns by Prefix
   Projections
    Step 1: find length-1 sequential patterns
    , , , , ,
    Step 2: divide search space. The complete set of seq. pat.
   can be partitioned into 6 subsets:
    The ones having prefix ;
    The ones having prefix ;
    …
    The ones having prefix
   SID sequence
   10
   20 <(ad)c(bc)(ae)>
   30 <(ef)(ab)(df)cb>
   40
   100
   Finding Seq. Patterns with Prefix
    Only need to consider projections w.r.t.
    -projected database: <(abc)(ac)d(cf)>, <(_d)c(bc) (ae)>, <(_b)(df)cb>, <(_f)cbc>
    Find all the length-2 seq. pat. Having prefix : ,
   , <(ab)>, , ,
    Further partition into 6 subsets
    Having prefix ;
    …
    Having prefix
   SID sequence
   10
   20 <(ad)c(bc)(ae)>
   30 <(ef)(ab)(df)cb>
   40
   101
   Completeness of PrefixSpan
   SID sequence
   10
   20 <(ad)c(bc)(ae)>
   30 <(ef)(ab)(df)cb>
   40
   SDB
   Length-1 sequential patterns
   , , , , ,
   -projected database
   <(abc)(ac)d(cf)>
   <(_d)c(bc)(ae)>
   <(_b)(df)cb>
   <(_f)cbc>
   Length-2 sequential
   patterns
   , , <(ab)>,
   , ,
   Having prefix
   Having prefix
   -proj. db … -proj. db
   Having prefix
   -projected database …
   Having prefix
   Having prefix , …,
   … …
   102
   Efficiency of PrefixSpan
    No candidate sequence needs to be generated
    Projected databases keep shrinking
    Major cost of PrefixSpan: constructing projected
   databases
    Can be improved by bi-level projections
   103
   Optimization Techniques in PrefixSpan
    Physical projection vs. pseudo-projection
    Pseudo-projection may reduce the effort of
   projection when the projected database fits in
   main memory
    Parallel projection vs. partition projection
    Partition projection may avoid the blowup of
   disk space
   104
   Speed-up by Pseudo-projection
    Major cost of PrefixSpan: projection
    Postfixes of sequences often appear
   repeatedly in recursive projected
   databases
    When (projected) database can be held in main
   memory, use pointers to form projections
    Pointer to the sequence
    Offset of the postfix
   s=
   <(abc)(ac)d(cf)>
   <(_c)(ac)d(cf)>
   
   
   s|: ( , 2)
   s|: ( , 4)
   105
   Pseudo-Projection vs. Physical Projection
    Pseudo-projection avoids physically copying postfixes
    Efficient in running time and space when database
   can be held in main memory
    However, it is not efficient when database cannot fit
   in main memory
    Disk-based random accessing is very costly
    Suggested Approach:
    Integration of physical and pseudo-projection
    Swapping to pseudo-projection when the data set
   fits in memory
   106
   PrefixSpan Is Faster than GSP and FreeSpan
   0
   50
   100
   150
   200
   250
   300
   350
   400
   0.00 0.50 1.00 1.50 2.00 2.50 3.00
   Support threshold (%) Runtime (
   second)
   PrefixSpan-1
   PrefixSpan-2
   FreeSpan
   GSP
   107
   Effect of Pseudo-Projection
   0
   40
   80
   120
   160
   200
   0.20 0.30 0.40 0.50 0.60
   Support threshold (%)
   Runtime (second)
   PrefixSpan-1
   PrefixSpan-2
   PrefixSpan-1 (Pseudo)
   PrefixSpan-2 (Pseudo)
   108
   APPLICATIONS/EXTENSIONS
   OF FREQUENT PATTERN
   MINING
   109
   Associative Classification
    Mine association possible rules (PR) in form of
   condset  c
    Condset: a set of attribute-value pairs
    C: class label
    Build Classifier
    Organize rules according to decreasing
   precedence based on confidence and support
    B. Liu, W. Hsu & Y. Ma. Integrating classification and
   association rule mining. In KDD’98
   110
   Why Iceberg Cube?
    It is too costly to materialize a high dimen. cube
    20 dimensions each with 99 distinct values may lead to
   a cube of 10020 cells.
    Even if there is only one nonempty cell in each 1010
   cells, the cube will still contain 1030 nonempty cells
    Observation: Trivial cells are usually not interesting
    Nontrivial: large volume of sales, or high profit
    Solution:
    iceberg cube—materialize only nontrivial cells of a data
   cube
   111
   Anti-Monotonicity in Iceberg Cubes
    If a cell c violates the HAVING clause, so do all more
   specific cells
    Example. Let Having COUNT()>=50  (, *, Edu, 1000, 30) violates the HAVING clause
    (Feb, *, Edu), (, Van, Edu), (Mar, Tor, Edu): each must have count no more than 30 Month City Cust_grp Prod Cost Price Jan Tor Edu Printer 500 485 Mar Van Edu HD 540 520 … … … … … … CREATE CUBE Sales_Iceberg AS SELECT month, city, cust_grp, AVG(price), COUNT()
   FROM Sales_Infor
   CUBEBY month, city, cust_grp
   HAVING COUNT(*)>=50
   112
   Computing Iceberg Cubes Efficiently
    Based on Apriori-like pruning
    BUC [Bayer & Ramakrishnan, 99]
    bottom-up cubing, efficient bucket-sort alg.
    Only handles anti-monotonic iceberg cubes, e.g.,
   measures confined to count and p+_sum (e.g., price)
    Computing non-anti-monotonic iceberg cubes
    Finding a weaker but anti-monotonic measure (e.g.,
   avg to top-k-avg) for dynamic pruning in computation
    Use special data structure (H-tree) and perform Hcubing
   (SIGMOD’01)
   113
   Spatial and Multi-Media Association: A
   Progressive Refinement Method
    Why progressive refinement?
    Mining operator can be expensive or cheap, fine or
   rough
    Trade speed with quality: step-by-step refinement.
    Superset coverage property:
    Preserve all the positive answers—allow a positive false
   test but not a false negative test.
    Two- or multi-step mining:
    First apply rough/cheap operator (superset coverage)
    Then apply expensive algorithm on a substantially
   reduced candidate set (Koperski & Han, SSD’95).
   114
   Progressive Refinement Mining of Spatial
   Associations
    Hierarchy of spatial relationship:
    “g_close_to”: near_by, touch, intersect, contain, etc.
    First search for rough relationship and then refine it.
    Two-step mining of spatial association:
    Step 1: rough spatial computation (as a filter)
    Using MBR or R-tree for rough estimation.
    Step2: Detailed spatial algorithm (as refinement)
    Apply only to those objects which have passed the rough
   spatial association test (no less than min_support)
   115
   Correlations with color, spatial relationships, etc.
   From coarse to Fine Resolution mining
   Mining Multimedia Associations
   116
   Further Evolution of PrefixSpan
    Closed- and max- sequential patterns
    Finding only the most meaningful (longest)
   sequential patterns
    Constraint-based sequential pattern growth
    Adding user-specific constraints
    From sequential patterns to structured patterns
    Beyond sequential patterns, mining
   structured patterns in XML documents
   117
   Closed- and Max- Sequential Patterns
    A closed- sequential pattern is a frequent sequence s where there is
   no proper super-sequence of s sharing the same support count with s
    A max- sequential pattern is a sequential pattern p s.t. any proper
   super-pattern of p is not frequent
    Benefit of the notion of closed sequential patterns
    , , with min_sup = 1
    There are 2100 sequential patterns, but only 2 are
   closed
    Similar benefits for the notion of max- sequential-patterns
   118
   Methods for Mining Closed- and Max-
   Sequential Patterns
    PrefixSpan or FreeSpan can be viewed as projection-guided depth-first
   search
    For mining max- sequential patterns, any sequence which does not
   contain anything beyond the already discovered ones will be removed
   from the projected DB
    , , with min_sup = 1
    If we have found a max-sequential pattern , nothing will be projected in any projected DB
    Similar ideas can be applied for mining closed- sequential-patterns
   119
   Constraint-Based Sequential Pattern
   Mining
    Constraint-based sequential pattern mining
    Constraints: User-specified, for focused mining of desired patterns
    How to explore efficient mining with constraints? — Optimization
    Classification of constraints
    Anti-monotone: E.g., value_sum(S) < 150, min(S) > 10
    Monotone: E.g., count (S) > 5, S  PC, digital_camera
    Succinct: E.g., length(S)  10, S  Pentium, MS/Office, MS/Money
    Convertible: E.g., value_avg(S) < 25, profit_sum (S) > 160,
   max(S)/avg(S) < 2, median(S) – min(S) > 5
    Inconvertible: E.g., avg(S) – median(S) = 0
   120
   Sequential Pattern Growth for
   Constraint-Based Mining
    Efficient mining with convertible constraints
    Not solvable by candidate generation-and-test methodology
    Easily push-able into the sequential pattern growth framework
    Example: push avg(S) < 25 in frequent pattern growth  project items in value (price/profit depending on mining semantics) ascending/descending order for sequential pattern growth  Grow each pattern by sequential pattern growth  If avg(current_pattern)  25, toss the current_pattern  Why?—future growths always make it bigger  But why not candidate generation?—no structure or ordering in growth 121 From Sequential Patterns to Structured Patterns  Sets, sequences, trees and other structures  Transaction DB: Sets of items  i1, i2, …, im, …  Seq. DB: Sequences of sets:  <i1, i2, …, im, in, ik>, …
    Sets of Sequences:
    , …, , …
    Sets of trees (each element being a tree):
    t1, t2, …, tn
    Applications: Mining structured patterns in XML documents
   122
   Frequent-Pattern Mining: Achievements
    Frequent pattern mining—an important task in data mining
    Frequent pattern mining methodology
    Candidate generation & test vs. projection-based (frequent-pattern
   growth)
    Vertical vs. horizontal format
    Various optimization methods: database partition, scan reduction,
   hash tree, sampling, border computation, clustering, etc.
    Related frequent-pattern mining algorithm: scope extension
    Mining closed frequent itemsets and max-patterns (e.g., MaxMiner,
   CLOSET, CHARM, etc.)
    Mining multi-level, multi-dimensional frequent patterns with flexible
   support constraints
    Constraint pushing for mining optimization
    From frequent patterns to correlation and causality
   123
   Frequent-Pattern Mining: Applications
    Related problems which need frequent pattern mining
    Association-based classification
    Iceberg cube computation
    Database compression by fascicles and frequent
   patterns
    Mining sequential patterns (GSP, PrefixSpan, SPADE,
   etc.)
    Mining partial periodicity, cyclic associations, etc.
    Mining frequent structures, trends, etc.
    Typical application examples
    Market-basket analysis, Weblog analysis, DNA mining,
   etc.
   124
   Frequent-Pattern Mining: Research Problems
    Multi-dimensional gradient analysis: patterns regarding
   changes and differences
    Not just counts—other measures, e.g., avg(profit)
    Mining top-k frequent patterns without support constraint
    Mining fault-tolerant associations
    “3 out of 4 courses excellent” leads to A in data mining
    Fascicles and database compression by frequent pattern
   mining
    Partial periodic patterns
    DNA sequence analysis and pattern classification
   125
   Thank you !!!
   Questions
   126
   Consider the market basket transactions shown in the table below. Assume that
   min_support=40% and min_confidence=60%. Further, assume that the Apriori algorithm
   is used to discover strong association rules among transaction items.
   Transaction ID Items
   1 Bread, Cheeze, Juice
   2 Bread, Cheeze
   3 Beer, Diapers, Cake
   4 Juice, Diapers, Bread, Cheeze
   5 Beer, Diapers
   127
   Itemset Item_Count
   Bread 3
   Cheeze 3
   Juice 2
   Beer 2
   Cake 1
   Diapers 3
4. Generate all possible association rules from the frequent itemsets obtained in the
   previous questions. Calculate the confidence of each rule and identify all the strong
   association rules.
5. Show the step by step generated candidate itemsets (C1) and the qualified frequent
   itemsets (F1) until the largest frequent itemsets are generated. Use table C1 as a template.
   Make sure that you clearly identify all the frequent itemsets.

The post MINING ASSOCIATION RULES IN LARGE DATABASES appeared first on My Assignment Online.

Expert Help With This Assignment — On Your Terms