第八讲 挖掘频繁模式、关联和相关教材课程.ppt

厦门大学软件学院 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 使用垂直数据格式挖掘频繁项集（自学） Vertical format: t(AB) = {T11, T25, …} tid-list: list of trans.-ids containing an itemset Deriving closed patterns based on vertical intersections t(X) = t(Y): X and Y always happen together t(X) ? t(Y): transaction having X always has Y Using diffset to accelerate mining Only keep track of differences of tids t(X) = {T1, T2, T3}, t(XY) = {T1, T3} Diffset (XY, X) = {T2} Closed Patterns and Max-Patterns A long pattern contains a combinatorial number of sub-patterns, e.g., {a1, …, a100} contains (1001) + (1002) + … + (110000) = 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 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? !! 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 Mining Frequent Closed Patterns: CLOSE