tcss555a 7

Association Rules Mining Part II: 

10/17/2007 TCSS555A Isabelle Bichindaritz 1 Association Rules Mining Part II

Learning Objectives: 

10/17/2007 TCSS555A Isabelle Bichindaritz 2 Learning Objectives Mining multilevel association rules from transactional databases Mining multidimensional association rules from transactional databases and data warehouse

Acknowledgements: 

10/17/2007 TCSS555A Isabelle Bichindaritz 3 Acknowledgements These slides are adapted from Jiawei Han and Micheline Kamber

Slide 4: 

10/17/2007 TCSS555A Isabelle Bichindaritz 4 Association rule mining Mining single-dimensional Boolean association rules from transactional databases Mining multilevel association rules from transactional databases Mining multidimensional association rules from transactional databases and data warehouse

Multiple-Level Association Rules: 

10/17/2007 TCSS555A Isabelle Bichindaritz 5 Multiple-Level Association Rules Items often form hierarchy. Items at the lower level are expected to have lower support. Rules regarding itemsets at appropriate levels could be quite useful. Transaction database can be encoded based on dimensions and levels We can explore shared multi-level mining

Mining Multi-Level Associations: 

10/17/2007 TCSS555A Isabelle Bichindaritz 6 Mining Multi-Level Associations A top_down, progressive deepening approach: First find high-level strong rules: milk ® bread [20%, 60%]. Then find their lower-level “weaker” rules: 2% milk ® wheat bread [6%, 50%]. Variations at mining multiple-level association rules. Level-crossed association rules: 2% milk ® Wonder wheat bread Association rules with multiple, alternative hierarchies: 2% milk ® Wonder bread

Multi-level Association: Uniform Support vs. Reduced Support: 

10/17/2007 TCSS555A Isabelle Bichindaritz 7 Multi-level Association: Uniform Support vs. Reduced Support Uniform Support: the same minimum support for all levels + One minimum support threshold. No need to examine itemsets containing any item whose ancestors do not have minimum support. – Lower level items do not occur as frequently. If support threshold too high  miss low level associations too low  generate too many high level associations Reduced Support: reduced minimum support at lower levels There are 4 search strategies: Level-by-level independent Level-cross filtering by k-itemset Level-cross filtering by single item Controlled level-cross filtering by single item

Uniform Support: 

10/17/2007 TCSS555A Isabelle Bichindaritz 8 Uniform Support Multi-level mining with uniform support Milk [support = 10%] 2% Milk [support = 6%] Skim Milk [support = 4%] Level 1 min_sup = 5% Level 2 min_sup = 5% Back

Reduced Support: 

10/17/2007 TCSS555A Isabelle Bichindaritz 9 Reduced Support Multi-level mining with reduced support 2% Milk [support = 6%] Skim Milk [support = 4%] Level 1 min_sup = 5% Level 2 min_sup = 3% Back Milk [support = 10%]

Multi-level Association: Redundancy Filtering: 

10/17/2007 TCSS555A Isabelle Bichindaritz 10 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.

Multi-Level Mining: Progressive Deepening: 

10/17/2007 TCSS555A Isabelle Bichindaritz 11 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.

Progressive Refinement of Data Mining Quality: 

10/17/2007 TCSS555A Isabelle Bichindaritz 12 Progressive Refinement of Data Mining Quality 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).

Progressive Refinement Mining of Spatial Association Rules: 

10/17/2007 TCSS555A Isabelle Bichindaritz 13 Progressive Refinement Mining of Spatial Association Rules 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)

Slide 14: 

10/17/2007 TCSS555A Isabelle Bichindaritz 14 Association rule mining Mining single-dimensional Boolean association rules from transactional databases Mining multilevel association rules from transactional databases Mining multidimensional association rules from transactional databases and data warehouse

Multi-Dimensional Association: Concepts: 

10/17/2007 TCSS555A Isabelle Bichindaritz 15 Multi-Dimensional Association: Concepts Single-dimensional rules: buys(X, “milk”)  buys(X, “bread”) Multi-dimensional rules:  2 dimensions or predicates Inter-dimension association rules (no repeated predicates) age(X,”19-25”)  occupation(X,“student”)  buys(X,“coke”) hybrid-dimension association 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

Techniques for Mining MD Associations: 

10/17/2007 TCSS555A Isabelle Bichindaritz 16 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.

Static Discretization of Quantitative Attributes: 

10/17/2007 TCSS555A Isabelle Bichindaritz 17 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 cubescan be much faster.

Quantitative Association Rules: 

10/17/2007 TCSS555A Isabelle Bichindaritz 18 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:

ARCS (Association Rule Clustering System): 

10/17/2007 TCSS555A Isabelle Bichindaritz 19 ARCS (Association Rule Clustering System) How does ARCS work? 1. Binning 2. Find frequent predicateset 3. Clustering 4. Optimize

Limitations of ARCS: 

10/17/2007 TCSS555A Isabelle Bichindaritz 20 Limitations of ARCS Only quantitative attributes on LHS of rules. Only 2 attributes on LHS. (2D limitation) An alternative to ARCS Non-grid-based equi-depth binning clustering based on a measure of partial completeness. “Mining Quantitative Association Rules in Large Relational Tables” by R. Srikant and R. Agrawal.

Mining Distance-based Association Rules: 

10/17/2007 TCSS555A Isabelle Bichindaritz 21 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

Clusters and Distance Measurements: 

10/17/2007 TCSS555A Isabelle Bichindaritz 22 S[X] is a set of N tuples t1, t2, …, tN , projected on the attribute set X The diameter of S[X]: distx:distance metric, e.g. Euclidean distance or Manhattan Clusters and Distance Measurements

Clusters and Distance Measurements(Cont.): 

10/17/2007 TCSS555A Isabelle Bichindaritz 23 The diameter, d, assesses the density of a cluster CX , where Finding clusters and distance-based rules the density threshold, d0 , replaces the notion of support modified version of the BIRCH clustering algorithm Clusters and Distance Measurements(Cont.)