Apriori算法的改进及其在电子商务中的应用

刘彬+程晓荣

摘要：Apriori算法是关联模型中的经典算法，但是当数据库很大时Apriori算法的复杂度将会指数上升，因此该文对Apriori算法扫描数据库的方式进行了改进，改进后的算法有效地降低了算法的复杂度。并将Apriori算法粗浅的应用于在电子商务中的推荐环节。

关键词：Apriori算法；关联规则；算法改良；电商平台

中图分类号： TP393 文献标识码： A 文章编号：1009-3044（2017）27-0274-02

随着我国经济的迅速发展，互联网得到了极大的普及。电子商务作为一种新的销售方式，迅速地占据了我国零售业很大的比重。电子商务开辟了新的市场，新的购物方式。近年来我国的电子商务交易量迅速增长，其运营模式的创新日益增加，电子商务呈现出多层次、多元化的发展趋势[1]。其中淘宝、京东、唯品会等平台占领了90%的市场份额。而且随着互联网的发展，怎样让用户消费行为更加简洁，怎样吸引更多的用户成为了各大电商平台关注的焦点。

Apriori算法是一种基于关联规则的算法，根据关联规则可以推荐给用户想要的商品，从而节省了用户的购物时间，使用户购物更为方便快捷，从而可以吸引更多的用户，然而传统的Apriori算法在处理海量的数据时，复杂度较高，必须对Apriori算法进行改良使之能够适用于现在大数据的时代，本文对Apriori算法进行了简单的介绍，并提出了一种改良的方法。并简单的验证了改良后的算法。

1 Apriori算法

1.1 Apriori算法简介

Apriori算法是关联规则模型中的经典算法，它是R.Agrawal等人于1994年在AIS算法基础上提出的改进算法，是數据挖掘问题中的一个重要研究内容。Apriori算法在发现关联规则问题方面有非常的大的影响力[2]。

Apriori算法是一种挖掘关联规则的频繁项集的宽度优先的算法，这个算法的核心思想是通过扫描数据库，生成候选集和逐级的监测来发现数据库的频繁项集。通过对数据库的多次扫描来发现所有的频繁项目集，在每一次扫描中只考虑具有同一长度的所有候选集[3]。

1.2 基本概念

对于事件A和B：

①支持度：P（A∩B），A事件和B事件同时发生的概率。

②置信度：P（B|A），在事件A已经发生的条件下事件B发生的概率。也可以记为P（AB）/P（A）。

例如购物车记录分析：泳衣和泳镜。

支持度1%：只有1%的用户同时购买了泳衣和泳镜。

置信度60%：购买了泳衣的用户有60%也同时购买了泳镜。

1.3 算法的实现

Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法Apriori使用一种称作逐层搜索的迭代方法，“K-1项集”用于搜索“K项集”[4]

首先，需要找到数据库的频繁“1项集”的集合，这个集合记为L1。L1用来寻找频繁“2项集”的集合L2，而L2则用来寻找L3。依次类推循环下去，直到不能找到“K项集”。在这个过程中，每寻找到一个LK，都需要完整的扫描一次数据库。

核心步骤：连接步和剪枝步。连接步是自连接（LK和Lk连接），连接的规则是保证每一项的前k-2项是相同的。依次按字典序连接。剪枝步，是使任一频繁项集的所有非空子集也必须是频繁的。反之，如果某个候选的非空子集不是频繁的，那么该候选集肯定不是频繁的，从而可以将其从Ck中删除，产生Lk。[5]

简单地讲，发现频繁项集过程可以归结为：①扫描；②计数；③比较；④产生频繁项集；⑤连接、剪枝，产生候选项集。

重复步骤①-⑤直到不能发现更大的频集。

例如有如下数据库：

经过三次扫描三次比较找到数据库的3项集，Apriori算法求解得出ABE三项关联度最高。

但是Apriori算法的缺点也显而易见：每找出一个频繁项集Lk，需要完整地扫描一次数据库；而且这样产生的候选项集也非常庞大。当数据库结构较为简单时，Apriori算法可以较好的工作，但是当数据库较为庞大时，Apriori算法复杂度就会很高。例如长度为500的频繁集{X1，X2，X3，……，X500}，将会 产生10000个候选项集[6]。因此我们必须对Apriori算法进行改进。

2 April算法的改进

Apriori算法在现如今大数据时代存在的缺陷极为明显，大数据时代，数据以PB为起步，在这么大的数据库中运用Apriori算法来寻求关联度，其复杂度不可想象的。

根据Apriori算法的特性，改进主要可以由以下两方面来进行：

① 自连接和剪枝步骤采用更优的策略。

② 简化数据库本身来减少Apriori算法的复杂度。

本文主要讨论从数据库方面来进行优化，Apriori算法每筛选一次候选集都需要对数据库进行一次扫描，因此我们队数据库进行优化，在每次计算Ck支持度的过程中，将CK中没有的所有事物都标记出来，并且在以后的扫描中不考虑这些已经被标记的事物，由此在实际计算候选集支持度所涉及的数据库将小于真实数据库，并且随着k值的增大，这一差值也不断增大，因此可以有效地降低扫描时间，减小候选集的计算速度，提升了整个算法的效率。

改进后的算法步骤：

① 选取最小的支持度，对初始数据库进行扫描，计算出各个1项集的度，得到1-项集L1。

② 连接剪枝（与原算法相同）。

③ 将Ck中没有的元素标记，删除被标记的元素得到新的数据库DK，再重扫扫描DK，计算Ck+1各元素的支持度。

④ 将Ck中不满足最小支持度的项集删掉，并形成Lk；②-④，直到不能产生新的频繁项目集时终止。endprint

用实例数据来进行比较：

由图2和图3可以看出来，在筛选C3时，数据库简化变为D1，商品由10项减少为9项，而在下一步中，数据库D2减少为7项，因此节省了扫描数据库的时间，而当数据库越大，这种改进方法节省的时间将越多，因此这样的改进是可行的，但是由于改进算法又增加了新的数据库，生成新的数据库也将会占用一定的时间，所以该算法的改进还有待进一步提升。

3 改进Apriori算法在电商中的应用

随着时代的发展，电子商务在整体商务中占到的比重越来越大，面对纷繁复杂的商品，电商平台如何推荐给用户想要的商品，如何吸引更多的用户，这都是店商平台在考虑的问题。

Apriori根据关联规则计算关联度较高的方法，电商平台可以根据用户的消费行为，以及各种商品的关联度，来推荐给用户想要的商品，從而节省了用户搜索商品的时间，给用户更好的购物体验，从而吸引更多的用户。

4 结束语

Apriori算法是一种基于关联规则的推荐算法，但是随着时代的发展，大数据环境下数据库越来越大，Apriori算法的缺陷也越来越明显，本文对算法进行了改良，使其适用范围更广，可以应用到电商平台，给以用户推荐可能的商品，但是这样的改进还有很多缺陷，下一步的工作将会对算法继续进行改进，使之能够在大数据时代有用武之地。

参考文献：

[1] 聂林海. “互联网+”时代的电子商务[J]. 中国流通经济，2015，29（06）：53-57. [2017-08-10]. DOI：10.14089/j.cnki.cn11-3664/f.2015.06.008

[2] 罗可，黄园芳，郭锋. 用Visual Foxpro实现Apriori算法的研究[J]. 长沙电力学院学报：自然科学版，2001，（4）：16-19. [2017-08-10].

[3] 罗可，贺才望. 基于Apriori算法改进的关联规则提取算法[J]. 计算机与数字工程，2006，（04）：48-51+55. [2017-08-10].

[4] 郅芬香，王留芳. 基于关联规则的Apriori算法改进研究[J]. 信息与电脑：理论版，2014，（09）：169-170. [2017-08-10].

[5] 佘为，谢会娟. 改进的Apriori算法在高校选修课系统和应对气候变化相关统计工作中的应用[J]. 信息与电脑：理论版，2015，（11）：179-181. [2017-08-10].

[6] 麦丞程. 基于Apriori算法的关联规则挖掘系统设计与实现[J]. 电脑编程技巧与维护，2015，（11）：33-35. [2017-08-10]. DOI：10.16184/j.cnki.comprg.2015.11.014endprint