论文部分内容阅读
摘要: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;②-④,直到不能产生新的频繁项目集时终止。 用实例数据来进行比较:
由图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.014
关键词: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;②-④,直到不能产生新的频繁项目集时终止。 用实例数据来进行比较:
由图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.014