【正文】 ehavior of this subset ? The rule is accepted only if a statistical test (., Ztest) confirms the inference with high confidence ? Subrule: highlights the extraordinary behavior of a subset of the pop. of the super rule ? ., (Sex = female) ^ (South = yes) = mean wage = $? Two forms of rules ? Categorical = quantitative rules, or Quantitative = quantitative rules ? ., Education in [1418] (yrs) = mean wage = $? Open problem: Efficient methods for LHS containing two or more quantitative attributes 14 Chapter 7 : Advanced Frequent Pattern Mining ? Pattern Mining: A Road Map ? Pattern Mining in MultiLevel, MultiDimensional Space ? Mining MultiLevel Association ? Mining MultiDimensional Association ? Mining Quantitative Association Rules ? Mining Rare Patterns and Negative Patterns ? ConstraintBased Frequent Pattern Mining ? Mining HighDimensional Data and Colossal Patterns ? Mining Compressed or Approximate Patterns ? Pattern Exploration and Application ? Summary 15 Negative and Rare Patterns ? Rare patterns: Very low support but interesting ? ., buying Rolex watches ? Mining: Setting individualbased or special groupbased support threshold for valuable items ? Negative patterns ? Since it is unlikely that one buys Ford Expedition (an SUV car) and Toyota Prius (a hybrid car) together, Ford Expedition and Toyota Prius are likely negatively correlated patterns ? Negatively correlated patterns that are infrequent tend to be more interesting than those that are frequent 16 Defining Negative Correlated Patterns (I) ? Definition 1 (supportbased) ? If itemsets X and Y are both frequent but rarely occur together, ., sup(X U Y) sup (X) * sup(Y) ? Then X and Y are negatively correlated ? Problem: A store sold two needle 100 packages A and B, only one transaction containing both A and B. ? When there are in total 200 transactions, we have s(A U B) = , s(A) * s(B) = , s(A U B) s(A) * s(B) ? When there are 105 transactions, we have s(A U B) = 1/105, s(A) * s(B) = 1/103 * 1/103, s(A U B) s(A) * s(B) ? Where is the problem? —Null transactions, ., the supportbased definition is not nullinvariant! 17 Defining Negative Correlated Patterns (II) ? Definition 2 (negative itemsetbased) ? X is a negative itemset if (1) X = ā U B, where B is a set of positive items, and ā is a set of negative items, |ā|≥ 1, and (2) s(X) ≥ μ ? Itemsets X is negatively correlated, if ? This definition suffers a similar nullinvariant problem ? Definition 3 (Kulzynski measurebased) If itemsets X and Y are frequent, but (P(X|Y) + P(Y|X))/2 ?, where ? is a negative pattern threshold, then X and Y are negatively correlated. ? Ex. For the same needle package problem, when no matter there are 200 or 105 transactions, if ? = , we have (P(A|B) + P(B|A))/2 = ( + )/2 ? 18 Chapter 7 : Advanced Frequent Pattern Mining ? Pattern Mining: A Road Map ? Pattern Mining in MultiLevel, MultiDimensional Space ? ConstraintBased Frequent Pattern Mining ? Mining HighDimensional Data and Colossal Patterns ? Mining Compressed or Approximate Patterns ? Pattern Exploration and Application ? Summary 19 Constraintbased (QueryDirected) 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) ? Constraintbased mining ? User flexibility: provides constraints on what to be mined ? Optimization: explores such constraints for efficient mining — constraintbased mining: constraintpushing, similar to push selection first in DB query processing ? Note: still find all the answers satisfying constraints, not finding some answers in “heuristic search” 20 Constraints in Data Mining ? Knowledge type constraint: ? classification, association, etc. ? Data constraint — using SQLlike queries ? find product pairs sold together in stores in Chicago this year ? 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% MetaRule Guided Mining ? Metarule can be in the rule form with partially instantiated predicates and constants P1(X, Y) ^ P2(X, W) = buys(X, “iPad”) ? The resulting rule derived can be age(X, “1525”) ^ profession(X, “student”) = buys(X, “iPad”) ? In general, it can be in the form of P1 ^ P2 ^ … ^ Pl = Q1 ^ Q2 ^ … ^ Qr ? Method to find metarules ? Find frequent (l+r) predicates (based on minsupport threshold) ? Push constants deeply when possible into the mining process (see the remaining discussions on constraintpush techniques) ? Use confidence, correlation, and other measures when possible 21 22 ConstraintBased Frequent Pattern Mining ? Pattern space pruning constraints ? Antimonotonic: If constraint c is violated, its further mining can be terminated ? Monotonic: If c is satisfied, no need to check c again ? Succinct: c must be satisfied, so one can start with the data sets satisfying c ? Convertible: c is not monotonic nor antimonotonic, but it can be converted into it if items in the transaction can be properly ordered ? Data space pruning constraint ? Data succinct: Data space can be pruned at the initial pattern mining process ? Data antimonotonic: If a transaction t does not satisfy c, t can be pruned from its further mining 23 Pattern Space Pruning with AntiMonotonicity Constraints ? A constraint C is antimonotone if the super pattern satisfies C, all of its subpatterns do so too ? In other words, antimonotonicity: If a