论文部分内容阅读
[摘 要]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。
2.2 算法思想
Apriori算法将关联规则的发现过程分成了两个步骤：
（1）找出所有支持度高于用户设定的最小支持度的项集，即发现所有的频繁项集。
（2）通过发现的频繁项集构造出满足用户最小置信度的规则。[9]
但是在执行过程中Apriori算法需要频繁地扫描数据库，这一行为会造成过重的I/O负担[10]，改进算法将通过减少数据库扫描次数的方式来减轻I/O负担。
2.3 实例分析
依据上述改进的算法，以一个实例对该算法进行分析。表1为事务数据库，设最小支持度为20%，则最小支持度计数等于2。
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.
[8]刘兴涛，石冰，解英文.挖掘关联规则中Apriori算法的一种改进[J].山东大学学报：理学版，2008，43（11）：67-71.
[9]熊平.数据挖掘算法与Clementine实践[M].北京：清华大学出版社，2011.
[10]周超发，王志坚，叶枫，等.关联规则挖掘算法Apriori的研究改进[J].计算机科学与探索，2015，9（9）：105-108.
[关键词]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。
2.2 算法思想
Apriori算法将关联规则的发现过程分成了两个步骤：
（1）找出所有支持度高于用户设定的最小支持度的项集，即发现所有的频繁项集。
（2）通过发现的频繁项集构造出满足用户最小置信度的规则。[9]
但是在执行过程中Apriori算法需要频繁地扫描数据库，这一行为会造成过重的I/O负担[10]，改进算法将通过减少数据库扫描次数的方式来减轻I/O负担。
2.3 实例分析
依据上述改进的算法，以一个实例对该算法进行分析。表1为事务数据库，设最小支持度为20%，则最小支持度计数等于2。
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.
[8]刘兴涛，石冰，解英文.挖掘关联规则中Apriori算法的一种改进[J].山东大学学报：理学版，2008，43（11）：67-71.
[9]熊平.数据挖掘算法与Clementine实践[M].北京：清华大学出版社，2011.
[10]周超发，王志坚，叶枫，等.关联规则挖掘算法Apriori的研究改进[J].计算机科学与探索，2015，9（9）：105-108.