【PPT】大数据经典算法APRIORI讲解-APRIORI ALGORITHM.ppt

* * * Apriori Algorithm 小组成员 吴国泉、唐思远、赵清伟、张波 * 购物篮分析：引发性例子 Questions 关联 分析 Solutions 1：经常同时购买的商品可以摆近一点，以便进一步刺激这些商品一起销售。 2：规划哪些附属商品可以降价销售，以便刺激主体商品的捆绑销售。 哪组商品顾客可能会在一次购物时同时购买？ 关联分析的基本概念 关联规则是形如 的蕴含式， （支持度）规则 在事务集D中成立，支持度S是事务包含 的百分比。 Support（ ）= P（ ） （置信度）置信度C是D中同时包含A的事务同时也包含B的百分比。 Confidence（ ）= P（ ）/P（A） （k项集）包含k个项的项集称为k项集，频繁k项集的集合记作 ，候选k项集的集合记作 。 * 由频繁项集产生强关联规则 （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）同时满足最小支持度阀值和最小置信度阀值的规则称为强规则。 * Apriori算法说明 在Apriori算法中,寻找最大项目集的基本思想是: 算法需要对数据集进行多步处理.第一步,简单统计所有含一个元素项目集出现的频率,并找出那些不小于最小支持度的项目集, 即一维最大项目集L1. 从第二步开始循环处理直到再没有最大项目集生成. 循环过程是: 第k步中, 根据第k-1步生成的(k-1)维最大项目集产生k维侯选项目集CK, 然后对数据库进行有哪些信誉好的足球投注网站, 得到侯选项目集的项集支持度, 与最小支持度比较, 从而找到k维频繁项目集LK. * 连接步 为找出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]}。 * 剪枝步 CK是LK的超集，也就是说，CK的成员可能是也可能不是频繁的。通过扫描所有的事务（交易），确定CK中每个候选的计数，判断是否小于最小支持度计数，如果不是，则认为该候选是频繁的。为了压缩Ck,可以利用Apriori性质：任一频繁项集的所有非空子集也必须是频繁的，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK中删除。 * Apriori算法实例 * * * 频繁项集产生关联规则 * Apriori算法 如果存在I1，I2，I4. 和 I1，I3，I4两组的时候，我们要不要连接？ 我认为是不用的。 首先，不用连接的后果，唯一可能造成的后果就是将I1，I2，I3，I4项集遗漏。 我们观察是否会将I1，I2，I3，I4项集遗漏。 * Apriori算法 假设I1，I2，I3，I4项集满足条件，是存在的。 那么候选集中必然存在I1，I2，I3;和I1，,I2，I4 和 I1，I3, I4， 和 I2，I3，I4. 而不会仅仅是I1，I2，I4. 和 I1，I3，I4。 通过I1，I2，I3和I1，I2，I4的组合，就可以得到I1，I2，I3，I4.所以不会遗漏。 * Apriori算法的缺陷 （1）在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素; （2）每次计算项集的支持度时，都对数据库D中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。 因此人们开始寻求一种能减少这种系统1/O开销的更为快捷的算法。 *