Microsoft PowerPoint - ch6_association_rule [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - ch6_association_rule [兼容模式]"

蛟巩柏
7 years ago
Views:

1 第三章关联规则挖掘 Association Rule Mining

2 10 Data Mining Tasks Data Tid Refund Marital Status Taxable Income 1 Yes Single 125K No 2 No Married 100K No 3 No Single 70K No 4 Yes Married 120K No Cheat 5 No Divorced 95K Yes 6 No Married 60K No 7 Yes Divorced 220K No 8 No Single 85K Yes 9 No Married 75K No 10 No Single 90K Yes 11 No Married 60K No 12 Yes Divorced 220K No 13 No Single 85K Yes 14 No Married 75K No 15 No Single 90K Yes Milk Tan,Steinbach, Kumar Introduction to Data Mining 4/18/2004 # 2

3 背景简介 (Motivation) 超市购物 : 商场经理可能想了解顾客的购物习惯例如 : 顾客多半会在一次购物时买哪些商品? 分析的结果可用于市场规划广告策划和分类设计文本分类 : 个性化新闻推荐系统希望对新闻进行分类, 推荐用户感兴趣类别的新闻内容给用户系统可以通过挖掘哪些关键词与某个类别经常联系在一起, 找出文档的分类标准信息推荐 : 电子商务网站推荐用户所需的信息如 : 下载某种类型音乐的用户通常具有什么样的特点解决这些问题的种有效途径就是 A i ti R l 解决这些问题的一种有效途径就是 Association Rule Mining ( 关联规则挖掘 )

4 Association Rule Mining Given a set of transactions, find rules that will predict the occurrence of an item based on the occurrences of other items in the transaction Market-Basket transactions TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke Example of Association Rules {Diaper} {Beer}, {Milk, Bread} {Eggs,Coke}, {Beer, Bread} {Milk}, Implication means co-occurrence, occurrence not causality!

5 Definition: Frequent Itemset Itemset A collection of one or more items Example: {Milk, Bread, Diaper} k-itemset An itemset that contains k items Support count (σ) Frequency of occurrence of an itemset E.g. σ({milk, Bread,Diaper}) = 2 Support Fraction of transactions that contain an itemset E.g. s({milk, Bread, Diaper}) = 2/5 Frequent Itemset An itemset whose support is greater than or equal to a minsup threshold TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke

6 Definition: Association Rule Association Rule An implication expression of the form X Y, where X and Y are itemsets Example: {Milk, Diaper} {Beer} Rule Evaluation Metrics Support (s) Fraction of transactions that contain both X and Y Confidence (c) TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke Example: { Milk, Diaper} (Milk, Diaper, Beer) s = σ T 2 = = 5 Measures how often items in Y appear in transactions that 5 contain X Beer 0.4 σ (Milk,Diaper,Beer) 2 c = = = 0.67 σ (Milk, Diaper) 3 支持度是全局角度, 置信度只关注于该规则自身 3

7 Association Rule Mining Task Given a set of transactions T, the goal of association rule mining is to find all rules having support minsup threshold confidence minconf threshold Brute-force approach: List all possible association rules Compute the support and confidence for each rule Prune rules that fail the minsup and minconf thresholds Computationally prohibitive!

8 Mining Association Rules TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke Example of Rules: {Milk,Diaper} {Beer} (s=0.4, c=0.67) {Milk,Beer} {Diaper} (s=0.4, c=1.0) {Diaper,Beer} {Milk} (s=0.4, c=0.67) {Beer} {Milk,Diaper} (s=0.4, c=0.67) {Diaper} {Milk,Beer} (s=0.4, c=0.5) {Milk} {Diaper,Beer} (s=0.4, c=0.5) Observations: All the above rules are binary partitions of the same itemset: {Milk, Diaper, Beer} Rules originating from the same itemset have identical support but can have different confidence Thus, we may decouple the support and confidence requirements

9 Mining Association Rules Two-step approach: 1. Frequent Itemset Generation Generate all itemsets whose support minsup 2. Rule Generation Generate high confidence rules from each frequent itemset, where each rule is a binary partitioning of a frequent itemset Frequent itemset generation is still computationally ti expensive

10 Frequent Itemset Generation null A B C D E AB AC AD AE BC BD BE CD CE DE ABC ABD ABE ACD ACE ADE BCD BCE BDE CDE ABCD ABCE ABDE ACDE BCDE ABCDE Given d items, there are 2 d possible candidate itemsets t

11 Frequent Itemset Generation Brute-force approach: Each itemset in the lattice is a candidate frequent itemset Count the support of each candidate by scanning the database Transactions TID Items 1 Bread, Milk 2 Bread, Diaper, Beer, Eggs 3 Milk, Diaper, Beer, Coke 4 Bread, Milk, Diaper, Beer 5 Bread, Milk, Diaper, Coke Match each transaction against every candidate Complexity ~ O(NMw) => Expensive since M = 2 d!!!

12 Computational Complexity Given d unique items: Total number of itemsets = 2 d Total number of itemsets 2 Total number of possible association rules: = = = d k k d j j k d k d R = d + d j k If d=6, R = 602 rules

13 Frequent Itemset Generation Strategies Reduce the number of candidates (M) Complete search: M=2 d Use pruning techniques to reduce M Reduce the number of transactions (N) Reduce size of N as the size of itemset increases Used by DHP and vertical-based mining algorithms Reduce the number of comparisons (NM) Use efficient data structures to store the candidates or transactions No need to match every candidate against every transaction

14 Reducing Number of Candidates Apriori principle: If an itemset is frequent, then all of its subsets must also be frequent Apriori principle holds due to the following property of fthe support measure: X, Y : ( X Y ) s ( X ) s ( Y Support of an itemset never exceeds the support of its subsets This is known as the anti-monotone property p of support )

15 Illustrating Apriori Principle Found to be Infrequent Pruned supersets

16 Illustrating Apriori Principle Item Count Bread 4 Coke 2 Milk 4 Beer 3 Diaper 4 Eggs 1 Minimum Support = 3 Items (1-itemsets) Itemset Count {Bread,Milk} 3 {Bread,Beer} 2 {Bread,Diaper} 3 {Milk,Beer} 2 {Milk,Diaper} 3 {Beer,Diaper} 3 Pairs (2-itemsets) (No need to generate candidates involving Coke or Eggs) Triplets (3-itemsets) If every subset is considered, 6 C C C 3 = 41 With support-based pruning, = 13 Item set Count {B read,m ilk,d iaper} 3

17 Apriori Algorithm Method: Let k=1 Generate frequent itemsets t of length 1 Repeat until no new frequent itemsets are identified Generate length (k+1) candidate itemsets from length k frequent itemsets Prune candidate itemsets containing subsets of length k that are infrequent Count the support of each candidate by scanning the DB Eliminate candidates that are infrequent, leaving only those that are frequent

18 Apriori i Algorithm L 1 = {frequent 1-itemset}; for (k=2; L k-1 ; k++) do begin C k = apriori-gen(l k-1 1 ); // 生成大小为 k 的候选项集合 C k 为大小 k 的候选项集构成的集合 for all transactions t DD do begin C t = subset(c k,t); // 事务数据 t 中包含的候选项集 for all candidates c C t do c.count ++; end L k = {c C k c.count count minsup} end Answer = L k-1

19 生成候选项集合 Apriori i 算法是根据有关频繁项集性质的先验知识 Apriori i Principal 命名的该算法使用一种逐层搜索的迭代方法, 利用 k- 项集产生 (k+1)- 项集具体做法 : 首先找出频繁 1- 项集的集合, 记为 L 1 ; 再用 L 1 找频繁 2- 项集的集合 L 2 ; 再用 L 2 找 L 3 如此下去, 直到不能找到频繁 k- 项集为止找每个 L k 需要一次数据库扫描

20 生成候选项集合整个过程由连接和剪枝两步组成, 即 : (1) 连接步为找 L k k,, 可通过 L k-1 与自己连接, 产生一个候连接步产生候选项集剪枝步确定频繁项集选 k- 项集的集合, 该候选项集的集合记作 C k

21 生成候选项集合设 l 1 和 l 2 是 L k-1 中的项集, 记号 l i [j] 表示 l i 的第 j 项为方便计, 假定事务或项集中的项按字典次序排序 L k-1 L k-1 执行连接, 其中 L k-1 的元素是可连接的, 如果它们前 (k-2) 个项相同

22 生成候选项集合即,LL k-1 的元素 l 1 和 l 2 是可连接的, 若 : ( l 1 [1] = l 2 [1] l 1 [2] = l 2 [2] l 1 [k-2] = l 2 [k- 2] l 1 [k-1] < l 2 [k-1] ) 而条件 (l 1 [k-1] < l 2 [k-1]) 可确保不产生重复的项 1 2 集

23 生成候选项集合 (2) 剪枝步 C k 是 L k 的超集, 即它的成员不一定都是频繁项集, 但所有的频繁 k- 项集都包含在 C k 中扫描数据库, 确定 C k 中每个候选项集的计数, 从而确定 L k 然而, C k 可能很大, 这样所涉及的计算量就很大

24 生成候选项集合为了压缩 C k, 可利用 Apriori 性质 : 任何非频繁的 (k-1)- 项集都不可能是频繁 k- 项集的子集因此, 若一个候选 k- 项集的 (k-1)- 项子集不在 L k-1 中, 则该候选也不可能是频繁的, 从而可以从 C k 中删除

25 生成候选项集合例一个 Apriori i 的具体例子, 该例基于右图某商店的事务 DB DB 中有 9 个事务, Apriori 假定事务中的项按字典次序存放 TID T100 T200 T300 T400 T500 T600 T700 项 ID 的列表 I1,I2,I5 I2,I4 I2,I3 I1,I2,I4 I1,I3 I2,I3 I1,I3 T800 I1,I2,I3,I5I2 I3 I5 T900 I1,I2,I3

26 (1) 在算法的第一次迭代, 每个项都是候选 1- 项集的集合 C 1 的成员算法简单地扫描所有的事务, 对每个项的出现次数计数 C 1 扫描 D, 对每个候选计数项集支持度计数 {I1} 6 {I2} 7 {I3} {3} 6 {I4} 2 {I5} 2

27 (2) 设最小支持计数为 2, 可以确定频繁 1- 项集的集合 L 1 它由具有最小支持度的候选 1- 项集组成 L 1 项集支持度计数 {I1} 6 比较候选支持度计数 {I2} 7 与最小支持度计数 {I3} 6 {I4} 2 {I5} 2

28 (3) 为发现频繁 2- 项集的集合 L 2, 算法 L 1 L 1 2 使用产生候选 2- 项集集合 C 2 由 L 1 产生候选 C 2 C 2 项集 {I1,I2} {I1,I3} {I1,I4} {I1,I5} {I2,I3} {I2,I4} {I2,I5} {I3,I4} {I3,I5} {I4,I5}

29 (4) 扫描 D 中事务, 计算 C 2 中每个候选项 C 2 集的支持计数 C 2 项集支持度计数 {I1,I2} 4 {I1,I3} 4 扫描 D D, 对每 {I1,I4} I4 1 个候选计数 {I1,I5} 2 {I2,I3} I3} 4 {I2,I4} 2 {I2,I5} I5} 2 {I3,I4} 0 {I3,I5} I5} 1 {I4,I5} 0

30 (5) 确定频繁 2- 项集的集合 L 2, 它由具有最小支持度的 C 2 中的候选 2- 项集组成 L 2 项集支持度计数比较候选支持度计数 {I1,I2} 4 {I1,I3} 4 与最小支持度计数 {I1,I5} I5} 2 {I2,I3} 4 {I2,I4} 2 {I2,I5} I5} 2

31 (6) 候选 3- 项集的集合 C 3 的产生如下 : 1 连接 : C 3 = L 2 L 2 = {{I1, I2},{I1, I3},{I1, I5},{I2, I3},{I2, I4},{I2, I5}} {{I1, I2},{I1, I3},{I1, I5},{I2, I3},{I2, I4},{I2,I5}} } = {{I1, I2, I3},{I1, I2, I5},{I1, I3, I5},{I2, I3, I4},{I2, I3, I5},{I2, I4, I5}}

32 2 利用 Apriori 性质剪枝 : 频繁项集的所有子集必须是频繁的存在候选项集, 判断其子集是否频繁 {I1,I2,I3} 的 2- 项子集是 {I1,I2},{I1,I3} { } 和 {I2,I3}, 它们都是 L 2 的元素因此保留 {I1,I2,I3} 在 C 3 中 {I1,I2,I5} 的 2- 项子集是 {I1,I2},{I1,I5} 和 {I2,I5}, 它们都是 L 2 的元素因此保留 {I1,I2,I5} 在 C 3 中 {I1,I3,I5} 的 2- 项子集是 {I1,I3},{I1,I5} 和 {I3,I5}, {I3,I5} 不是 L 2 的元素, 因而不是频繁的, 由 C 3 中删除 {I1,I3,I5}

33 {I2,I3,I4} 的 2- 项子集是 {I2,I3},{I2,I4} 和 {I3,I4}, 其中 {I3,I4} I4} 不是 L 2 的元素, 因而不是频繁的, 由 C 3 中删除 {I2,I3,I4} {I2I3I5} {I2,I3,I5} 的 2- 项子集是 {I2,I3},{I2,I5} I3} I5} 和 {I3,I5}, I5} 其中 {I3,I5} 不是 L 2 的元素, 因而不是频繁的, 由 C 3 中删除 {I2,I3,I5} {I2,I4,I5} 的 2- 项子集是 {I2,I4},{I2,I5} 和 {I4,I5}, 其中 {I4,I5} 不是 L 2 的元素, 因而不是频繁的, 由 C 3 中删除 {I2,I4,I5}

34 3 这样, 剪枝后 C 3 = {{I1,I2,I3},{I1,I2,I5}} (7) 扫描 D 中事务, 以确定 L 3, 它由 C 3 中具有最小支持度的的候选 3- 项集组成由 L 2 产生候选 C 3 项集 {I1,I2,I3} {I1,I2,I5} C3 扫描 D, 对每个候选计数项集 C3 支持度计数 {I1,I2,I3} 2 {I1,I2,I5} 2

35 L 3 L 3 (8) 算法使用产生候选 4- 项集的集合 C 4 尽管连接产生结果 {{I1I2I3I5}} {{I1,I2,I3,I5}}, 这个项集被剪去, 因为它的子集 {I2,I3,I5} 不是频繁的则 C 4 = ψ, 因此算法终止, 找出了所有的频繁项集 L 3 比较候选支持度计数与最小支持度计数项集支持度计数 {I1,I2,I3} 2 {I1,I2,I5} I2 I5} 2

36 候选项目集的生成函数 apriori-gen 以 Lk-1 作为输入, 输出全部频繁 k- 项目集的一个超集该函数包含两个操作, 连接 (join) 与修剪 (prune) 连接操作将 Lk- 1 中的频繁项目集按如下方式进行拼接 : insert into Ck select p.item1, p.item2,, p.itemk-1, q. itemk-1 from Lk-1 p, Lk-1 q where p. item1=q. item1,, p. itemk-2=q. itemk-2, p. itemk-1 <q q. itemk-1;

37 修剪操作对 Ck 中任一候选项集 c, 若 c 的某个大小为 k-1 1 的子集不属于 Lk-1, 则将其从 Ck 中删除 forall itemsets c Ck do forall (k-1)-subsets s of c do if (s Lk-1) then delete c from Ck ;

38 例子假设集合 L3={{1 2 3},{1 2 4},{1 3 4},{1 3 5},{2 34}} 4}}, 通过连接得到 C4 ={{ },{ }} 由于项集 {1 4 5} 不在 L3 中, 所以修剪操作将 { } 从 C4 中删除

39 例子 ( 设 min_sup = 50%) )

ch3_association_rule副本

ch3_association_rule副本第三章关联规则挖掘 Association Rule Mining 背景简介 (Motivation) 超市购物 : 商场经理可能想了解顾客的购物习惯例如 : 顾客多半会在一次购物时买哪些商品? 分析的结果可用于市场规划广告策划和分类设计文本分类 : 个性化新闻推荐系统希望对新闻进行分类, 推进用户感兴趣类别的新闻内容给用户系统可以通过挖掘哪些关键词与某个类别经常联系在一起, 找出