文档介绍：Apriori Algorithm
小组成员
吴国泉、唐思远、赵清伟、张波
2
购物篮分析:引发性例子
Questions
关联分析
Solutions
1:经常同时购买的商品可以摆近一点,以便进一步刺激这些商品一起销售。
2:规划哪些附属商品可以降价销售,以便刺激主体商品的捆绑销售。
哪组商品顾客可能会在一次购物时同时购买?
关联分析的基本概念
关联规则是形如的蕴含式,
(支持度)规则在事务集D中成立,支持度S是事务包含的百分比。
Support( )= P( )
(置信度)置信度C是D中同时包含A的事务同时也包含B的百分比。
Confidence( )= P( )/P(A)
(k项集)包含k个项的项集称为k项集,频繁k项集的集合记作,候选k项集的集合记作。
3
由频繁项集产生强关联规则
(1)K维数据项集LK是频繁项集的必要条件是它所有K-1维子项集也为频繁项集,记为LK-1
(2)如果K维数据项集LK的任意一个K-1维子集LK-1,不是频繁项集,则K维数据项集LK本身也不是最大数据项集。
(3)LK是K维频繁项集,如果所有K-1维频繁项集集合LK-1中包含LK的K-1维子项集的个数小于K,则LK不可能是K维最大频繁数据项集。
(4)同时满足最小支持度阀值和最小置信度阀值的规则称为强规则。
4
Apriori算法说明
在Apriori算法中,寻找最大项目集的基本思想是: ,简单统计所有含一个元素项目集出现的频率,并找出那些不小于最小支持度的项目集, 即一维最大项目集L1. 从第二步开始循环处理直到再没有最大项目集生成.
循环过程是: 第k步中, 根据第k-1步生成的(k-1)维最大项目集产生k维侯选项目集CK, 然后对数据库进行搜索, 得到侯选项目集的项集支持度, 与最小支持度比较, 从而找到k维频繁项目集LK.
5
连接步
为找出Lk,通过将Lk-1与自身连接产生候选k项集的集合Ck。设l1和l2是Lk-1中的成员。记li[j]表示li中的第j项。假设Apriori算法对事务集中的项按字典次序排序,即对于(k-1)项集li,li[1]<li[2]<…<li[k-1] 。将Lk-1与自身连接,如果(l1[1]=l2[1])&&( l1[2]=l2[2])&&…….. && (l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1]),那认为l1和l2是可连接。连接l1和l2 产生的结果是{l1[1],l1[2],……,l1[k-1],l2[k-1]}。
6
剪枝步
CK是LK的超集,也就是说,CK的成员可能是也可能不是频繁的。通过扫描所有的事务(交易),确定CK中每个候选的计数,判断是否小于最小支持度计数,如果不是,则认为该候选是频繁的。为了压缩Ck,可以利用Apriori性质:任一频繁项集的所有非空子集也必须是频繁的,如果某个候选的非空子集不是频繁的,那么该候选肯定不是频繁的,从而可以将其从CK中删除。
7
Apriori算法实例
8
9
10