大数据经典算法Apriori讲解.ppt

《大数据经典算法Apriori讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、AprioriAlgorithm小组成员吴国泉、唐思远、赵清伟、张波购物篮分析：引发性例子Questions关联分析Solutions1：经常同时购买的商品可以摆近一点，以便进一步刺激这些商品一起销售。2：规划哪些附属商品可以降价销售，以便刺激主体商品的捆绑销售。哪组商品顾客可能会在一次购物时同时购买？2关联分析的基本概念关联规则是形如的蕴含式，（支持度）规则在事务集D中成立，支持度S是事务包含的百分比。Support（）=P（）（置信度）置信度C是D中同时包含A的事务同时也包含B的百分比。Confidence（）=P（）/P（A）（k项集）包含k个项的项集称为k项集，频繁k项集的集合记作

2、，候选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算法中,寻找最大项目集的基本思想是:算法需要对数据集进行多步处理.第一步,简单统计所有含一个元素项目集出现

3、的频率,并找出那些不小于最小支持度的项目集,即一维最大项目集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]

4、1])&&(l1[2]=l2[2])&&……..&&(l1[k-2]=l2[k-2])&&(l1[k-1]

5、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.所以不会遗漏。Aprior

6、i算法的缺陷（1）在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参与组合的元素;（2）每次计算项集的支持度时，都对数据库D中的全部记录进行了一遍扫描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的I/O开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此人们开始寻求一种能减少这种系统1/O开销的更为快捷的算法。Apriori算法的优化思路在逐层搜索循环过程的第k步中，根据k-1步生成的k-1维频繁项目集来产生k维候选项目集，由于在产生k-1维频繁项目集时，我们可以实现对该集中出现元素的个数进行计数处理，因此对某元素而言，若它的计数个数不到k-1

7、的话，可以事先删除该元素，从而排除由该元素将引起的大规格所有组合。这是因为对某一个元素要成为K维项目集的一元素的话，该元素在k-1阶频繁项目集中的计数次数必须达到K-1个，否则不可能生成K维项目集(性质3)。根据以上思路得到了这个候选项目集后，可以对数据库D的每一个事务进行扫描，若该事务中至少含有候选项目集CK中的一员则保留该项事务，否则把该事物记录与数据库末端没有作删除标记的事务记录对换，并对移到数据库末端的事务记录作