文档介绍：Apriori算法和FP-。频繁项集是经常出现在一块的物品的集合,关联规则暗示两种物品之间可能存在很强的关系。频繁项集是指那些经常出现在一起的物品的集合,上表的集合{葡萄酒,尿布,豆奶}就是频繁项集的一个例子,从上面的数据集也可以找到诸如尿布——>葡萄酒的关联规则。交易号码商品0豆奶,莴苣1莴苣,尿布,葡萄酒,甜菜2豆奶,尿布,葡萄酒,橙汁3莴苣,豆奶,尿布,葡萄酒4莴苣,豆奶,尿布,橙汁如何定义这些有趣的关系呢?谁来定义什么是有趣的?当寻找频繁项集时,频繁的定义是什么?有许多概念可以解答上述问题,不过其中最重要的是支持度和置信度。一个项集的支持度被定义为数据集中包含该项集的记录所占的比例。从表中可以得到,在5条交易记录中有3条包含{豆奶,尿布},因此{豆奶,尿布}的支持度是3/5。支持度是针对项集来说的,因此可以定义一个最小支持度,而只保留满足最小支持度的项集。置信度或可信度是针对一条诸如{尿布}——>{葡萄酒}的关联规则定义的。这条规则的可信度被定义为“支持度({尿布,葡萄酒})/支持度({尿布})”。从表中可以看到,由于{尿布,葡萄酒}的支持度为3/5,尿布的支持度为4/5,所以“尿布——>葡萄酒”的可信度为3/4=。这意味着对于包含“尿布”的所有记录,我们的规则对其中75%的记录都适用。。,应该如何去做?一个办法是生成一个物品所有可能组合的清单,然后对每一种组合统计它出现的频繁程度,可是当物品成千上万时,上述做法非常非常慢。为了降低所需的计算时间,研究人员发现一种所谓的Apriori原理。Apriori原理是说如果某个项集是频繁的,那么它的所有子集也是频繁的。例如:项集{豆奶,尿布}是频繁的,那么{豆奶}、{尿布}也一定是频繁的,也就是说如果一个项集是非频繁项集,那么它的所有超集也是非频繁的。如已知项集{橙汁}是非频繁的,我们就知道{莴苣,橙汁}、{牛奶,尿布,橙汁}也是非频繁的。使用该原理可以避免项集数目的指数增长,从而在合理的时间内计算出频繁项集。【例3】一个Apriori的具体例子,该例基于右图某商店的事务DB。DB中有9个事务,Apriori假定事务中的项按字典次序存放。11,2,52,422,331,2,441,3562,31,371,2,3,581,2,39(1)在算法的第一次迭代,每个项都是候选1-项集的集合C1的成员。算法简单地扫描所有的事务,对每个项的出现次数计数。C1项集支持度计数{1}6扫描D,对每个候选计数{2}7{3}6{4}2{5}2(2)设最小支持计数为2,可以确定1-频集的集合L1。它由具有最小支持度的候选1-项集组成。L1项集支持度计数{1}6比较候选支持度计数{2}7与最小支持度计数{3}6{4}2{5}2(3)为发现繁-频集的集合L2,算法使用L1 L1产生候选2-项集集合C2。C2项集{1,2}{1,3}{1,4}{1,5}由L1产生候选C2{2,3}{2,4}{2,5}{3,4}{3,5}{4,5}(4)扫描D中事务,计算C2中每个候选项集的支持计数。C2项集支持度计数{1,2}4{1,3}4{1,4}1{1,5}2扫描D,对每个候选计数{2,3}4{2,4}2{2,5}2{3,4}0{3,5}1{4,5}0