大数据经典算法Apriori讲解

大数据十大经典算法讲解PPT

Apriori Algorithm

小组成员 吴国泉、唐思远、赵清伟、张波

大数据十大经典算法讲解PPT

购物篮分析：引发性例子Questions哪组商品顾客可能会在一次购物时同时购买？

关联 分析 Solutions1:经常同时购买的商品可以摆近一点，以便进一 步刺激这些商品一起销售。 2:规划哪些附属商品可以降价销售，以便刺激主 体商品的捆绑销售。2

大数据十大经典算法讲解PPT

关联分析的基本概念A 关联规则是形如 A B 的蕴含式， I , B I , 且A B , (支持度)规则 A B 在事务集D中成立，支持度S 是事务包含 A B 的百分比。 Support(A B )= P(A B) (置信度)置信度C是D中同时包含A的事务同时也包 含B的百分比。 A Confidence( B)= P(A B)/P(A) (k项集)包含k个项的项集称为k项集，频繁k项集的 集合记作 L k ,候选k项集的集合记作 C k 。

大数据十大经典算法讲解PPT

由频繁项集产生强关联规则(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)同时满足最小支持度阀值和最小置信度阀值的 规则称为强规则。

大数据十大经典算法讲解PPT

Apriori算法说明在Apriori算法中,寻找最大项目集的基本思 想是: 算法需要对数据集进行多步处理.第一步, 简单统计所有含一个元素项目集出现的频率, 并找出那些不小于最小支持度的项目集, 即一 维最大项目集L1. 从第二步开始循环处理直到 再没有最大项目集生成. 循环过程是: 第k步中, 根据第k-1步生成的 (k-1)维最大项目集产生k维侯选项目集CK, 然后 对数据库进行搜索, 得到侯选项目集的项集支 持度, 与最小支持度比较, 从而找到k维频繁项 目集LK.

大数据十大经典算法讲解PPT

连接步为找出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[k1],l2[k-1]}。

大数据十大经典算法讲解PPT

剪枝步CK是LK的超集，也就是说，CK的成员可能是也可 能不是频繁的。通过扫描所有的事务(交易),确 定CK中每个候选的计数，判断是否小于最小支持度 计数，如果不是，则认为该候选是频繁的。为了压 缩Ck,可以利用Apriori性质：任一频繁项集的所有非 空子集也必须是频繁的，如果某个候选的非空子集 不是频繁的，那么

该候选肯定不是频繁的，从而可 以将其从CK中删除。

大数据十大经典算法讲解PPT

Apriori算法实例

大数据十大经典算法讲解PPT

大数据十大经典算法讲解PPT

大数据十大经典算法讲解PPT

频繁项集产生关联规则

大数据十大经典算法讲解PPT

如果存在I1,I2,I4. 和 I1,I3,I4两组的时 候，我们要不要连接？ 我认为是不用的。 首先，不用连接的后果，唯一可能造成的后 Apriori算法 果就是将I1,I2,I3,I4项集遗漏。 我们观察是否会将I1,I2,I3,I4项集遗漏。

大数据十大经典算法讲解PPT

假设I1,I2,I3,I4项集满足条件，是存在的。 那么候选集中必然存在I1,I2,I3;和I1,,I2, I4 和 I1,I3, I4, 和 I2,I3,I4. 而不会仅仅是I1,I2,I4. 和 I1,I3,I4。 Apriori算法 通过I1,I2,I3和I1,I2,I4的组合，就可以 得到I1,I2,I3,I4.所以不会遗漏。

大数据十大经典算法讲解PPT

Apriori算法的缺陷(1)在每一步产生侯选项目集时循环产生的 组合过多，没有排除不应该参与组合的元素; (2)每次计算项集的支持度时，都对数据库D 中的全部记录进行了一遍扫描比较，如果是一 个大型的数据库的话，这种扫描比较会大大增 加计算机系统的I/O开销。而这种代价是随着数 据库的记录的增加呈现出几何级数的增加。 因此人们开始寻求一种能减少这种系统1/O开 销的更为快捷的算法。

大数据十大经典算法讲解PPT

Apriori算法的优化思路在逐层搜索循环过程的第k步中，根据k-1步生 成的k-1维频繁项目集来产生k维候选项目集，由于 在产生k-1维频繁项目集时，我们可以实现对该集 中出现元素的个数进行计数处理，因此对某元素而 言，若它的计数个数不到k-1的话，可以事先删除 该元素，从而排除由该元素将引起的大规格所有组 合。 这是因为对某一个元素要成为K维项目集的一 元素的话，该元素在k-1阶频繁项目集中的计数次 数必须达到K-1个，否则不可能生成K维项目集(性质 3)。

大数据十大经典算法讲解PPT

根据以上思路得到了这个候选项目集后，可以 对数据库D的每一个事务进行扫描，若该事务中至 少含有候选项目集CK中的一员则保留该项事务，否 则把该事物记录与数据库末端没有作删除标记的事 务记录对换，并对移到数据库末端的事务记录作删 除标一记，整个数据库扫描完毕后为新的事务数据 库D’ 中。 因此随着K 的增大，D’中事务记录量大大地减 少，对于下一次事务扫描可以大大节约I/0 开销。由 于顾客一般可能一次只购买几件商品，因此这种虚 拟删除的方法可以实现大量的交易记录在以后的挖 掘中被剔除出来，在所剩余的不多的记录中再作更 高维的数据挖掘是可以大大地节约时间的。