人工智能与数据挖掘教学课件lect-4-13

1、2020/10/7,BUPT-AI 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;,2020/10/7,BUPT-AI&DM,16,Example 2:,TIDList of

2、 item-IDs - T100I1, I2, I5 T200I2, I4 T300I2, I3 T400I1, I2, I4 T500I1, I3 T600I2, I3 T700I1, I3 T800I1, I2, I3, I5 T900I1, I2, I3,Min-support = 20% Min-confidence =70%,2020/10/7,BUPT-AI&DM,17,3. Mining Association Rules: Example 3,2020/10/7,BUPT-AI&DM,18,Min support = 4,2020/10/7,BUPT-AI&DM,19,Freq

3、uent Three-item Sets: Watch Promotion =No & Life Insurance Promotion = No & Credit Card Insurance =No 4,2020/10/7,BUPT-AI&DM,20,4. Confidence of Association Rules,For each frequent itemset l, generate all nonempty subsets of s. Confidence test: s is nonempty subset of l For s (l-s) confidence=Suppor

4、t-count(l) / support-count(s) ab cd l is abcd. s is ab, then l-s is cd. confidence = support(abcd) / support(ab),2020/10/7,BUPT-AI&DM,21,Two Possible Two-Item Set Rules,IF Magazine Promotion =Yes THEN Life Insurance Promotion =Yes (5/7) IF Life Insurance Promotion =Yes THEN Magazine Promotion =Yes (

5、5/5) ( What if “Min confidence = 80%” ?),2020/10/7,BUPT-AI&DM,22,Three-Item Set Rules,IF Watch Promotion =No & Life Insurance Promotion = No THEN Credit Card Insurance =No (4/4) IF Watch Promotion =No THEN Life Insurance Promotion = No & Credit Card Insurance = No (4/6),2020/10/7,BUPT-AI&DM,23,5. Ge

6、neral Considerations (1),Association rules are particularly popular because of their ability to find relationships in large databases without having the restriction of choosing a single dependent variable. We are interested in association rules that show a lift in product sales where the lift is the

7、 result of the products association with one or more other products. We are also interested in association rules that show a lower than expected confidence for a particular association. A good scenario is to specify an initially high value for the item set coverage criterion. If more rules are desir

8、ed, the coverage criterion can be lowered and the entire process repeated.,2020/10/7,BUPT-AI&DM,24,5. General Considerations (2) Performance Bottlenecks,The core of the Apriori algorithm: Use frequent (k 1)-itemsets to generate candidate frequent k-itemsets Use database scan and pattern matching to

9、collect counts for the candidate itemsets The bottleneck of Apriori: candidate generation Huge candidate sets: 104 frequent 1-itemset will generate 107 candidate 2-itemsets To discover a frequent pattern of size 100, e.g., a1, a2, , a100, one needs to generate 2100 1030 candidates. Multiple scans of

10、 database: Needs (n +1 ) scans, n is the length of the longest pattern,2020/10/7,BUPT-AI&DM,25,Homework,A database has 4 transactions. Let min-support =60%, min_confidence=80%. Find the longest frequent itemset(s). List all association rules that satisfy the above requirement, with supports and confidence.,TID Dateitems_bought - T10010/15/99 K, A, D, B T20010/15/99D, A, C, E, B T30010/19/99C, A, B, E T40010/22/99B, A, D,2020/10/7,BUPT-AI&DM,26,关联与分类的使用,从数据挖掘角度看，主要是选择那些置信度和支持度都比较高的准则；从业务角度看，主要是对数据挖掘挑选出的准则进行评估，从而挑选出正确的和有价值的一些交叉销售准则。 在挑选完以后，那些满足条件但没有出现“结果”的客