【文章內容簡介】 ot need to check C in subsequent mining ? Alternatively, monotonicity: If an itemset S satisfies the constraint, so does any of its superset ? Ex. 1. sum() ? v is monotone ? Ex. 2. min() ? v is monotone ? Ex. 3. C: range() ? 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 25 Data Space Pruning with Data Antimonotonicity ? A constraint c is data antimonotone if for a pattern p cannot satisfy a transaction t under c, p’s superset cannot satisfy t under c either ? The key for data antimonotone is recursive data reduction ? Ex. 1. sum() ? v is data antimonotone ? Ex. 2. min() ? v is data antimonotone ? Ex. 3. C: range() ? 25 is data antimonotone ? Itemset {b, c}’s projected DB: ? T10’: {d, f, h}, T20’: {d, f, g, h}, T30’: {d, f, g} ? since C cannot satisfy T10’, T10’ can be pruned TID Transaction 10 a, b, c, d, f, h 20 b, c, d, f, g, h 30 b, c, d, f, g 40 c, e, f, g TDB (min_sup=2) Item Profit a 40 b 0 c 20 d 15 e 30 f 10 g 20 h 5 26 Pattern Space Pruning with Succinctness ? Succinctness: ? Given A1, the set of items satisfying a succinctness constraint C, then any set S satisfying C is based on A1 , ., 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() ? v is succinct ? sum() ? v is not succinct ? Optimization: If C is succinct, C is precounting pushable 27 Na239。ve Algorithm: Apriori + Constraint T ID Ite m s100 1 3 4200 2 3 5300 1 2 3 5400 2 5Database D ite m s e t s u p .{ 1 } 2{ 2 } 3{ 3 } 3{ 4 } 1{ 5 } 3i te m s e t s u p .{ 1 } 2{ 2 } 3{ 3 } 3{ 5 } 3Scan D C1 L1 item set{1 2}{1 3}{1 5}{2 3}{2 5}{3 5}ite m s et s up{ 1 2} 1{ 1 3} 2{ 1 5} 1{ 2 3} 2{ 2 5} 3{ 3 5} 2ite m s e t s u p{ 1 3 } 2{ 2 3 } 2{ 2 5 } 3{ 3 5 } 2L2 C2 C2 Scan D C3 L3 item set{2 3 5}Scan D ite m s e t s u p{ 2 3 5 } 2Constraint: Sum{} 5 28 Constrained Apriori : Push a Succinct Constraint Deep T ID Ite m s100 1 3 4200 2 3 5300 1 2 3 5400 2 5Database D ite m s e t s u p .{ 1 } 2{ 2 } 3{ 3 } 3{ 4 } 1{ 5 } 3i te m s e t s u p .{ 1 } 2{ 2 } 3{ 3 } 3{ 5 } 3Scan D C1 L1 item set{1 2}{1 3}{1 5}{2 3}{2 5}{3 5}ite m s et s up{ 1 2} 1{ 1 3} 2{ 1 5} 1{ 2 3} 2{ 2 5} 3{ 3 5} 2ite m s e t s u p{ 1 3 } 2{ 2 3 } 2{ 2 5 } 3{ 3 5 } 2L2 C2 C2 Scan D C3 L3 item set{2 3 5}Scan D ite m s e t s u p{ 2 3 5 } 2Constraint: min{ } = 1 not immediately to be used 29 Constrained FPGrowth: Push a Succinct Constraint Deep Constraint: min{ } = 1 T ID Ite m s100 1 3 4200 2 3 5300 1 2 3 5400 2 5T ID Ite m s100 1 3200 2 3 5300 1 2 3 5400 2 5Remove infrequent length 1 FPTree T ID Ite m s100 3 4300 2 3 51Projected DB No Need to project on 2, 3, or 5 30 Constrained FPGrowth: Push a Data Antimonotonic Constraint Deep Constraint: min{ } = 1 T ID Ite m s100 1 3 4200 2 3 5300 1 2 3 5400 2 5T ID Ite m s100 1 3300 1 3 FPTree Single branch, we are done Remove from data 31 Constrained FPGrowth: Push a Data Antimonotonic Constraint Deep Constraint: range{ } 25 min_sup = 2 FPTree TID Transaction 10 a, c, d, f, h 20 c, d, f, g, h 30 c, d, f, g BProjected DB B FPTree TID Transaction 10 a, b, c, d, f, h 20 b, c, d, f, g, h 30 b, c, d, f, g 40 a, c, e, f, g TID Transaction 10 a, b, c, d, f, h 20 b, c, d, f, g, h 30 b, c, d, f, g 40 a, c, e, f, g Item Profit a 40 b 0 c 20 d 15 e 30 f 10 g 20 h 5 Recursive Data Pruning Single branch: bcdfg: 2 32 Convertible Constraints: Ordering Data in Transactions ? Convert tough constraints into antimonotone or monotone by properly ordering items ? Examine C: avg() ? 25 ? Order items in valuedescending order ? a, f, g, d, b, h, c, e ? If an itemset afb violates C ? So does afbh, afb* ? It bees antimonotone! 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 33 Strongly Convertible Constraints ? avg(X) ? 25 is convertible antimonotone . item value descending order R: a, f, g, d, b, h, c, e ? 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 . item value ascending order R1: e, c, h, b, d, g, f, a ? 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 34 Can Apriori Handle Convertible Constraints? ? A convertible, not monotone nor antimonotone 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 frequentpattern growth framework! Item Value a 40 b 0 c 20 d 10 e 30 f 30 g 20 h 10 35 Pattern Space Pruning w. Convertible Constraints ? C: avg(X) = 25, min_sup=2 ? List items in every transaction in value descending order R: a, f, g, d, b, h, c, e ? C is convertible antimonotone . R ? Scan TDB once