Apriori算法是常用于挖掘出数据关联规则的算法,能够发现事物数据库中频繁出现的数据集,这些联系构成的规则可帮助用户找出某些行为特征,以便进行企业决策。例如,某食品商店希望发现顾客的购买行为,通过购物篮分析得到大部分顾客会在一次购物中同时购买面包和牛奶,那么该商店便可以通过降价促销面包的同时提高面包和牛奶的销量。了解Apriori算法推导之前,我们先介绍一些基本概念。
关联规则的挖掘目标是找出所有的频繁项集和根据频繁项集产生强关联规则。对于Apriori算法来说,其目标是找出所有的频繁项集,因此对于数据集合中的频繁数据集,我们需要自定义评估标准来找出频繁项集,常用的评估标准就是用上述介绍的支持度。
Apriori算法是经典生成关联规则的频繁项集挖掘算法,其目标是找到最多的K项频繁集。那么什么是最多的K项频繁集呢?例如当我们找到符合支持度的频繁集AB和ABE,我们会选择3项频繁集ABE。下面我们介绍Apriori算法选择频繁K项集过程。
Apriori算法采用迭代的方法,先搜索出候选1项集以及对应的支持度,剪枝去掉低于支持度的候选1项集,得到频繁1项集。然后对剩下的频繁1项集进行连接,得到候选2项集,筛选去掉低于支持度的候选2项集,得到频繁2项集。如此迭代下去,直到无法找到频繁k+1集为止,对应的频繁k项集的集合便是算法的输出结果。我们可以通过下面例子来看到具体迭代过程。
数据集包含4条记录{'134','235','1235','25'},我们利用Apriori算法来寻找频繁k项集,最小支持度设置为50%。首先生成候选1项集,共包含五个数据{'1','2','3','4','5'},计算5个数据的支持度,然后对低于支持度的数据进行剪枝。其中数据{4}支持度为25%,低于最小支持度,进行剪枝处理,最终频繁1项集为{'1','2','3','5'}。根据频繁1项集连接得到候选2项集{'12','13','15','23','25','35'},其中数据{'12','15'}低于最低支持度,进行剪枝处理,得到频繁2项集为{'13','23','25','35'}。如此迭代下去,最终能够得到频繁3项集{'235'},由于数据无法再进行连接,算法至此结束。
从Apriori算法原理中我们能够总结如下算法流程,其中输入数据为数据集合D和最小支持度α,输出数据为最大的频繁k项集。
参考
刘建平Pinard-Apriori算法原理总结
你看到的这篇文章来自于公众号「谓之小一」,欢迎关注我阅读更多文章。