算法类论文例文 跟关联规则挖掘Apriori算法的一种改进相关毕业论文提纲范文

本论文是一篇免费优秀的关于算法论文范文资料,可用于相关论文写作参考。

关联规则挖掘Apriori算法的一种改进

屈鑫乙,等:关联规则挖掘Apriori算法的一种改进

关联规则挖掘Apriori算法的一种改进

屈鑫乙,王迪,刘滏

(成都理工大学管理科学学院,四川成都610059)

[摘 要]Apriori算法是关联规则挖掘中的经典算法,但在算法执行中,会多次扫描数据库并产生大量的候选集,导致算法效率降低.在分析Apriori算法的基础上,利用任何一个频繁k+1项集一定可以表示成一个频繁k项集与一个频繁1项集的交集这一性质,产生频繁项集,并减少扫描数据库的次数,提高算法的效率,实验结果也表明,改进算法比Apriori算法有更好的性能.

[关键词]Apriori算法;关联规则;数据挖掘

[DOI]1013939/jcnkizgsc201636086

1引言

随着计算机技术与数据库技术的迅猛发展,如何从海量的数据中寻找出有效的信息成为了数据挖掘问题中的一项重要研究内容.数据挖掘是从大量的数据中挖掘出隐含的、未知的、用户可能感兴趣的和对决策有潜在价值的知识和规则.[1]挖掘关联规则问题可以分解为以下两个子问题:[2]①找出所有频繁项集.这些项集出现的频繁性至少和预定义的最小支持计数一样.②根据定义,由频繁项集产生强关联规则必须满足最小支持度和最小置信度.

RAgrawal于1994年首先提出了挖掘关联规则的Apriori算法[3],其基本思想是重复扫描数据库,根据频繁项集的超集才可能是频繁项集这一原理,由长度为k的频繁项集进行迭代计算产生长度为k+1的候选集,再对数据库进行扫描判断其是否为频繁项集.

很多文献基于Apriori算法提出改进算法,杨志刚[4]等人提出了基于压缩事务矩阵相乘的改进算法,焦学磊[5]等人提出了基于矩阵的频繁项集发现算法,将数据库信息全部以矩阵表示,该方法仅需要对数据库进行一次扫描,有效地减少了算法执行的时间,Najadat[6]等人对Apriori算法的不足之处进行了讨论,并优化了Apriori算法在剪枝过程中计算量大的问题,崔贯勋[7]等人提出对数据库进行一定的处理,使其成为水平结构再进行计算,但该方法需要占用大量的空间,也使得该方法的提高程度受到了限制.

2改进的Apriori算法

21算法的相关概念

频繁项集具有如下几个性质:[8]

性质1频繁项集的所有非空子集都是频繁项集,非频繁项集的超集都是非频繁项集.

性质2如果频繁k项集还能产生频繁k+1项集,则频繁k项集中的项数必须大于k.

定义1设D等于{d1,d2,…,dn}是事务的集合.设I等于{i1,i2,…,in)是属性的集合.集合中元素ik等于{dk|dk∈ik},表示具有属性ik的事务dk的集合.

定义2k项集Lk等于{l1,l2,…, ln},其中lk表示在集合I中取k个元素的交集,其数学定义为lk等于ia∪ib∪…∪iz,而其中元素数量大于最小支持度的集合用mk表示,其集合为{m1, m2, …, mn},即频繁k项集.

22算法思想

Apriori算法将关联规则的发现过程分成了两个步骤:

(1)找出所有支持度高于用户设定的最小支持度的项集,即发现所有的频繁项集.

(2)通过发现的频繁项集构造出满足用户最小置信度的规则.[9]

但是在执行过程中Apriori算法需要频繁地扫描数据库,这一行为会造成过重的I/O负担[10],改进算法将通过减少数据库扫描次数的方式来减轻I/O负担.

改进算法的思想就是利用频繁k+1项集中的任一元素,一定可以表示成频繁k项集中某一元素与频繁1项集中某一元素的交集这一性质来产生频繁集,从而减少扫描数据库的次数.

改进算法先对事务数据库进行扫描,得到1项集L1等于{l1,l2,…,ln},再对1项集L1进行剪枝,得到频繁1项集M1等于{l|cardl≥sup且l∈L1},并由频繁1项集M1中元素求得2项集L2等于{l|l等于li∪lj, li∈M1且i≠j},并对L2进行剪枝得到频繁2项集M2等于{l|cardl≥sup且l∈L2},并由M2中元素M1与中元素产生3项集L3,并通过剪枝得到频繁3项集M3,以此类推,可求得频繁k项集Mk,直到频繁k项集中项数小于k,则由性质2可知,频繁k项集Mk无法产生频繁k+1项集,迭代停止.

23实例分析

依据上述改进的算法,以一个实例对该算法进行分析.表1为事务数据库,设最小支持度为20%,则最小支持度计数等于2.

对2项集进行剪枝,可得到频繁2项集M2等于{l12,l13,l15,l23,l24,l25}.

利用频繁2项集M2 与频繁1项集M1,可以得到频繁3项集合M3等于{l123, l125}根据频繁项集的性质2,频繁项集M3中项数为2,其无法产生频繁4项集,因此迭代停止.

24算法实验与分析

为了验证本文改进算法的有效性,将其与Apriori经典算法进行实验对比,测试的数据库选用本校对高校教师的一次调查问卷,数据库有1681条记录,数据库中部分记录如表3所示.因为在本次调查中,教师只需要在24个选项中,选出最符合自己意愿的某几个选项,因此数据的存储采用简单二维表进行记录,用以节省存储空间.

采用的实验环境:CPU为Intel Core I7 260GHz,内存8GB,操作系统为WIN10 专业版,数据库采用SQL2014,算法采用C#语言编写并在VS2012环境下编译,下图是改进算法与Apriori经典算法在不同支持度下执行时间对比.

不同支持度下两种算法的执行时间对比

改进算法在效率上优于Apriori算法,并且在最小支持度较小时,改进算法的执行时间相对于Apriori算法具有明显优势,但是随着最小支持度的增加,两种算法的执行时间均大幅减少,Apriori算法与改进算法的执行时间开销非常接近,这是因为随着最小支持度的增加,迭代次数减少,运算过程中产生的频繁项集的数量均大幅度减少,使得算法的执行时间减少.

3结论与思考

本文提出的算法与Apriori算法相比减少了I/O次数,在改进算法中,是以项集中包含元素的数量与最小支持度计数对比判断其是否为频繁项集,不需要对数据库进行多次扫描,而Apriori算法在每次进行剪枝时,需要对数据库进行扫描才能判断生成的项集是否为频繁项集,改进算法是从这一点出发,进行改进从而提高算法的执行效率,减少算法的执行时间.虽然改进算法虽然减少了I/O次数,提高了算法的执行效率,但是算法在执行过程中,需要保存大量的数据,因而需要占用较多的内存空间,因此如何对数据量较大的数据库执行本算法,还有待进一步的研究与改进.

参考文献:

[1]刘华婷,郭仁祥,姜浩关联规则挖掘Apriori算法的研究与改进[J].计算机应用与软件,2009,26(1):146-149

[2]Han J W,Kamber MData Mining:Concepts and Techniques,数据挖掘:概念与技术[M].范明,孟小峰,等,译北京:机械工业出版社,2001

[3]Pang-Ning Tan,Michael Steinbach,Vipin Kumar数据挖掘导论[M].北京:人民邮电出版社,2006

[4]杨志刚,何顺月基于压缩事务矩阵相乘的Apriori改进算法[J].中国新技术新产品,2010,30(6):57-58

[5]焦学磊,王新庄基于矩阵的频繁项集发现算法[J].江汉大学学报:自然科学版,2007,35(1):43-46

[6]Najadat HM,Al-Maolegi M,Arkok BAn Improved Apriori Algorithm for Association Rules[J].International Research Journal of Computer Science and Application,2013,(1):1-8

[7]崔贯勋,李梁,王柯柯,等关联规则挖掘中Apriori算法的研究与改进[J].计算机应用2010,30(11):2952-2955(下转P121)

[8]刘兴涛,石冰,解英文挖掘关联规则中Apriori算法的一种改进[J].山东大学学报:理学版,2008,43(11):67-71

[9]熊平数据挖掘算法与Clementine实践[M].北京:清华大学出版社,2011

[10]周超发,王志坚,叶枫,等关联规则挖掘算法Apriori的研究改进[J].计算机科学与探索,2015,9(9):105-108

算法论文范文结:

关于对不知道怎么写算法论文范文课题研究的大学硕士、相关本科毕业论文算法论文开题报告范文和文献综述及职称论文的作为参考文献资料下载。