一种混合型的增量数据关联规则挖掘技术分析

　摘要：在数据库中增加数据且调整最小支持度时，数据库中关联规则会发生变化，为从数据量和最小支持度同时发生变化的数据库中快速获取频繁项集，发现变化后的关联规则，通过对FIM和AIUA算法进行分析，提出一种结合两种算法优点的增量数据关联规则挖掘My_FIM_AIUA算法，该算法能减少数据库扫描次数，减少候选项集数量。通过实验表明My_FIM_AIUA算法能在数据量和最小支持度同时变化时快速找到频繁项集，提高挖掘增量数据关联规则的速度。
　　关键词：关联规则；增量数据；支持度变化
　　中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）31-7237-04
　　Abstract： There will be some changes of association rules when adding data and adjusting the minimum support in the database. In order to obtain the frequent item sets quickly from the database when changes of the data size and minimum support happened at the same time， and to find out the changed association rule， the My_FIM_AIUA mining algorithm for incremental data association rule that combined the advantages of FIM and AIUA will be proposed by means of the analysis of FIM and AIUA algorithm. This algorithm can reduce the times of database scanning and decrease the numbers of candidate items. Thus， an experiment will be taken to show that the My_FIM_AIUA algorithm can search the frequent item sets quickly when changes of data size and minimum support happened at the same time， and it can improve the speed of mining the incremental data association rule.
　　Key words： association rule； incremental data； support changes
　　1 概述
　　关联规则挖掘是指从海量数据中寻找频繁在一起出现的事务及规律，经典的算法有Apriori算法和FP增长算法，但这两种算法都是面向数据量不变且最小支持度不变，但My_IUA算法在数据量增加且支持度变大时存在频繁项集遗漏以及数据量增加且支持度变小的时候存在频繁项集发现错误的情况；IFU算法是在FUP和IUA算法的基础上提出并改进。为此，在总结FIM和AIUA算法优点的基础上，提出My_FIM_AIUA算法，在数据量增加和最小支持度变大时改进FIM算法快速找到频繁项集，相对FIM算法减少扫描新增数据的次数；在数据量增加和最小支持度变小时拓展AIUA算法找到相关频繁项集，修正My_IUA算法的错误，减少候选项集的数量。My_FIM_AIUA算法在FIM和AIUA基础上提出，执行速度相比IFU算法要更快。
　　2 FIM和AIUA算法
　　2.1 FIM算法基本思想
　　FIM算法是最小支持度不变、数据量变化时的一种关联规则挖掘算法，它的基本思想是如果一个项集要是最终的频繁项集，要么是原数据库DB中的频繁项集，要么是新增数据库db中的频繁项集。该算法假设DB中的现有频繁项集[LDBk]都已保存，首先扫描新增数据得到db的频繁项集[Ldbk]，将[LDBk]和[Ldbk]中相同的频繁项集加入到最终频繁项集[L'k]并将其从[LDBk]和[Ldbk]中删除；接着扫描db对[LDBk]剩余的频繁项集更新支持度计数并将满足最小支持度计数的加入[L'k]；最后扫描DB对[Ldbk]中剩余的频繁项集更新支持度计数并将满足最小支持度的加入[L'k]。
　　2.2 AIUA算法基本思想
　　从实验结果可知，My_FIM_AIUA算法的运行时间均比Apriori和IFU算法要少，说明My_FIM_AIUA算法执行速度快。虽然3个算法扫描数据库的次数一致，但My_FIM_AIUA算法大大减少了候选项集的数量，所以在扫描数据库时对候选项集支持度计数所花时间变少。从挖掘得到的频繁项集个数看，My_FIM_AIUA算法与Apriori算法挖掘结果基本一致，说明My_FIM_AIUA算法的正确性。
My_FIM_AIUA算法的缺点是需要保存[Lk]中频繁项集的支持度计数，若[Lk]非常大超过运行时内存的可使用空间将成为本算法的瓶颈，而且该算法在支持度变小时与其他算法类似，依然需要多次扫描DB来获得频繁项集。
　　5 结束语
　　在信息量暴增和急需数据背后知识指导工作的信息时代，如何快速发现增量数据和最小支持度变化的关联规则是企事业单位信息管理系统必须要解决的问题。该文提出的My_FIM_AIUA算法在一定程度上提高了数据量和最小支持度同时变化时频繁项集的挖掘效率，但该算法需要较大的内存空间以及多次扫描数据库，如何能减少扫描数据库的次数或减少候选项集的数量将能进一步提高算法的执行效率，这是以后进一步研究待解决的问题。
　　参考文献：
　　[1] 刘凯.彭国志.关联规则挖掘方法研究[J].电脑知识与技术，2010，6（5）：1029-1031.
　　[2] 涂明，张公让，程业媛.一种高效的关联规则增量式更新算法[J].微电子学与计算机，2010，27（9）：56-60.
　　.Proceedings of the 12th international conference on Data Engineering， 1996：212-223.
　　[4] ， ， and ， "An efficient technique for incremental updating of association rules. " International Journal of Hybrid Intelligent Systems，pages 45-53，May 2008.
　　[5] 冯玉才，冯剑琳.关联规则的增量式更新算法[J].软件学报，1998，9（4）：301-306.
　　[6] 杨学兵，安红梅.一种高效的关联规则增量式更新算法[J].计算机技术与发展，2007，17（1）：108-110+113.
　　[7] 皋军，王建东.关联规则挖掘算法更新与拓展[J].计算机工程与应用，2003，35：178-179+202.
　　[8] 唐璐，江红，上官秋子. 一种改进的关联规则的增量式更新算法[J].计算机应用与软件，2012，29（4）：246-248.