• 1. Apriori算法 2012年11月15日
  • 2. 讲述顺序数据挖掘Apriori 算法关联规则
  • 3. Apriori算法数据挖掘关联规则挖掘三者关系
  • 4. 了解数据挖掘算法所处位置
  • 5. 数据挖掘算法功能根据所挖掘知识的类型不同: 为了反映同类事物共同性质的 为了反映事物各方面特征的 为了反映不同事物之间属性差别的 为了反映事物之间依赖或关联的 根据历史的和当前的数据推测未来数据 揭示事物偏离常规的异常现象为了反映事物之间依赖或关联的
  • 6. 典型案例---啤酒与尿布
  • 7. 更多举例e.g: 在购买铁锤的顾客当中,有70%的人同时购买了铁钉。
  • 8. 更多举例e.g: 年龄在40 岁以上,工作在A区的投保人当中,有45%的人曾经向保险公司索赔过。
  • 9. 关联规则挖掘关联规则(Association Rule)挖掘是从事务数据库、关系数据库和其它信息存储中的大量数据项集之间发现有趣的、频繁出现的模式、关联和相关性。
  • 10. 关联规则挖掘步骤一般分为2个步骤: 依据支持度找出所有的频繁项集。 (频度) 依据置信度产生关联规则。 (强度)性能瓶颈!先验算法
  • 11. 基本概念项项集频繁项集事务关联规则置信度支持度由此我们引出之后需要的几个概念:
  • 12. 关联规则挖掘举例最简单的关联规则挖掘 单维、单层、布尔关联规则挖掘交易ID购买项集2000ABC1000AC4000AD5000BEF频繁项集支持度{A}75%{B}50%{C}50%{AC}50%Minsup=50%,Mincon=50%满足频繁项集如表,只有{AC}关联分析有意义 Support(A=>C)=50% Confidence(A=>) P(C/A)=66.7% 找出频繁项集 在频繁项集中找出满足置信度的项集
  • 13. Apriori(先验)算法 先验释义:由原因推结果
  • 14. Apriori算法 Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法。按照所处理的值类型不同进行关联规则分类: 布尔关联规则,如事务向量(001101100)对每种商品可以用一个布尔量来表示该种商品是否被购买,则每个购物篮可以用一个布尔向量来表示 量化关联规则,如Age{X,”30--39”} ∩income{X,”40k—48k”}=〉buys{X,”computer”}
  • 15. Apriori 使用一种称作逐层搜索的迭代方法,“K-1项集”用于探索“K项集”。 首先,找出频繁“1项集”的集合。该集合记作L1。L1用于找频繁“2项集”的集合L2,而L2用于找L3, 如此下去,直到不能找到“K项集”。找每个LK需要一次数据库扫描。 Apriori算法
  • 16. Apriori算法目的意义Apriori算法主要为了提高数据访问效率,提升发现频繁项集的速度
  • 17. 核心:连接步和剪枝步连接步 自连接 原则:前k-2项相同 字典顺序连接 剪枝步 利用Apriori性质:任一频繁项集的所有非空子集也必须是频繁的,反之,如果某个候选的非空子集不是频繁的,那么该候选肯定不是频繁的。过滤候选项集。减少工作量。
  • 18. 步骤1:发现频繁项集频繁项集发现过程: (1)扫描 (2)计数 (3)比较 (4)产生频繁项集 (5)连接、剪枝,产生候选项集 重复步骤(1)~(5)直到不能发现更大频集
  • 19. 步骤2:产生关联规则根据前面提到的置信度的定义,关联规则的产生如下: (1)对于每个频繁项集L,产生L的所有非空子集; (2)对于L的每个非空子集S,如果 则输出规则“S → L-S”。 注:L-S表示在项集L中除去S子集的项集。
  • 20. 举 例
  • 21. Apriori算法伪代码 (1) L 1 = find_frequent_1_itemsets(D);   (2) for (k=2;L k-1 ≠Φ ;k++) {   (3) C k = apriori_gen(L k-1 );   (4) for each transaction t ∈ D {//scan D for counts   (5) C t = subset(C k,t);//get the subsets of t that are candidates   (6) for each candidate c ∈ C t   (7) c.count++;   (8) }   (9) L k ={c ∈ Ck|c.count≥min_sup}   (10) }   (11) return L= ∪ k L k;  
  • 22. 连接步和剪枝步第1 步:连接(join) Procedure apriori_gen(L k -1:frequent(k- 1) itemset) 1) for each itemset l 1∈L k-1 2) for each itemset l 2∈L k-1 3) if ((l 1[1]=l 2[1])∧…∧(l 1[k-2]=l 2[k-2])∧ (l1[k-1] <l 2[k-1])then { 4) c=l1⋈l2;//连接, 产生候选集 5) if has_infrequent_subset(c,L k-1 ) then 6) delete c;//修剪, 去掉无用的候选项 7) else add c to C k; 8) } 9) return C k;
  • 23. 连接步和剪枝步第2 步: 剪枝(prune) procedure has_infrequent_subset(c: candidate k itemset;L k-1 : frequent(k- 1)itemset); //使用先验知识 1) for each (k- 1)subset s of c 2) if s∉L k-1 then 3) return true; 4) return false;
  • 24. 可能产生大量的候选集 可能需要重复扫描数据库Apriori算法局限性
  • 25. 谢 谢!