摘要 Apriori算法在关联规则领域有很大的影响力，然而由于需要过于频繁的扫描数据库及较大的空间消耗，仍然有需要改进的地方。通过对Apriori算法进行深入研究，本文提出了基于临时表的Apriori改进算法，通过比较分析，获得了较好的效率和性能。关键词 关联规则 Apriori算法 频繁项集 临时表 0 引言数据挖掘（Data Mining)是数据库知识发现KDD(Knowledge Discovery in Database)的核心,是指从数据库中提取潜在的、有用的、最终可理解的知识的过程。关联规则算法则是数据挖掘的一个重要研究方向,其侧重于确定数据库中不同领域间的联系,找出满足给定支持度和可信度的多个域之间的相互关系[4]。简单的说，关联规则就是给定一组项目Item和一个记录集合，通过分析记录集合，推导出 Item 间的相关性。1 Apriori算法介绍1.1 Apriori算法基本思想Apriori算法是发现关联规则领域的经典算法。该算法将发现关联规则的过程分为两个步骤： 论文检测天使-免费论文检测软件http://www.jiancetianshi.com
第一步通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集；第二步利用频繁项集构造出满足用户最小信任度的规则[5]。具体做法就是：首先找出频繁1-项集，记为L1；然后利用L1来产生候选项集C2，对C2中的项进行判定挖掘出L2，即频繁2-项集；不断如此循环下去直到无法发现更多的频繁k-项集为止。每挖掘一层Lk就需要扫描整个数据库一遍。1.2 Apriori算法描述Apriori利用层次循环发现频繁项集，算法如下：输入：交易数据库D，最小支持阈值min-sup输出：D中的频繁项集L
然后利用 Apriori性质删除那些子集为非频繁项集的候选项集，一旦产生所有候选，就要扫描数据库，对于数据库中的每个交易利用subset 函数来帮助发现该交易记录的所有（已成为候选项集）的子集，由此累计每个候选项集的支持频度。最终满足最小支持频度的候选项集组成了频繁项集 L。然而,像这样产生候选集的开销极大,特别是频繁集很长或最小支持度非常小时。例如,当有104个频繁1-项集时,Apriori算法就会产生多于107个的候选2-项集。针对Apriori算法的瓶颈，本文提出了一种基于临时表的改进算法。2 基于临时表的Apriori改进算法2.1 基本思想基于临时表的Apriori改进算法利用了以下两个事实：(1) 对于已知规模的事务数据库D，任意一个项集I的出现频繁度与规模小于|I|的事务无关。所以在第|I|次扫描数据库D时，可以删除规模小于|I|的事务记录。(2) k-候选项集中不包含任何(k-1)-项集的项集一定不是频繁项集，因此k次扫描时可以将这样的事务记录立即删除，从而减少了下次需要扫描的记录数。用临时表来完成频繁项集的选择。首先把(k-1)-项集中的 论文检测天使-免费论文检测软件http://www.jiancetianshi.com
第一个项集添加进临时表中；然后把最后一项不同的其它项集添加进临时表，生成k-项集，计算其频繁度，若频繁度大于最小频繁度，则生成该频繁项并保存，否则删除。依此循环，直至生成所有的频繁项。2.2 改进算法的描述输入：事务数据库D；最小支持度阈值min_sup输出：D的频繁项集L变量说明： Ck：k-候选项集 Lk：k-频繁项集 Dk：第k次扫描后的数据库L1 = {large 1-itemsets}; //D中的1-项集 
[8]电大学习网.免费论文网[EB/OL]. /d/file/p/2024/0424/fontbr />
| TID | 项的列表 |
| T100 | I1,I2,I5 |
| T200 | I2,I4 |
| T300 | I2,I3 |
| T400 | I1,I2,I4 |
| T500 | I1,I3 |
| T600 | I2,I3 |
| T700 | I1,I3 |
| T800 | I1,I2,I3,I5 |
| T900 | I1,I2,I3 |
第一次扫描数据库，确定1-项集及各元素的覆盖频度。如图1所示：
(2) 利用L1⊕L1来产生候选2-项集C2，由C2确定频繁2-项集。如图2所示： 
(3) 利用L2⊕L2进行连接操作，获得候选3-项集C3，为{(I1,I2,I3),(I1,I2,I5),(I1,I3,I5),(I2,I3,I5),(I2,I4,I5)}。根据Apriori“一个频繁项集的所有子集也是频繁的”的性质，可以确定后四个项集不可能是频繁的，因此可以删除它们，从而减少了扫描次数。结果如图3所示：
图3(4) 利用L3⊕L3进行连接操作得到C4，根据Apriori性质可知C4=Φ。算法至此结束。由此可见，Apriori算法每次扫描都要彻底扫描整个数据库D，而改进后的算法及时的将不符合要求的项集删除，从而减少了下次扫描数据库的记录数；Apriori算法进行连接操作时需生成完整的项集，而使用临时表则只需将最后一个不同的项进行连接，从而节省了大量的存储空间。算法比较结果如下表所示：
表2说明：表2中数据库规模是指数据库中的记录数，空间耗费是指生成的候选项集所占的空间。从表2可以看到，在扫描规模上，Apriori每次需要对所有的事务数据库进行扫描，而基于临时表的改进算法在第二趟数据扫描后，数据中二元组 T200，T300，T500，T600，T700被删除，第三次的扫描量减至4。在空间耗费上， 论文检测天使-免费论文检测软件http://www.jiancetianshi.com第一次对 5 个单项进行判断每一个单项占一位空间，需要的空间耗费为 5。第二次进行 JOIN 运算时，需要（C14+C13+C12+C11）×2=10×2=20 个单元空间，第三次进行 JOIN 运算，需要（C13+C12+C11）×3=18个单元空间。临时表压缩算法采用了逐个动态生成频繁项，依次所需空间均为 1。 4.结束语 本文在对Apriori挖掘算法的深入研究基础上，提出了基于临时表的改进算法。通过分析比较，在减少扫描数据库中记录数量和进行连接操作所需空间耗费上，取得了较好的效果。与 Apriori相比，基于临时表的改进算法在数据规模及空间耗费上均占有优势，随数据规模的增大，这种优势将更加明显。 参考文献：1 R Agrawal,R Wrikant. Fast Algorithms for Mining Association Rules in Large Databases. Proc,20th int’l Conf.Very large databases.1994：478~4992 Margarent H.Dunham. Data Mining Introductory and Advanced Topics. Southern Mehodist University.20033 Brin S, Motwani R. Dynamic Itemset Counting and Implication Rules for Market Basket Data. In: Proc. Of the 1997 ACM_SIGMOD Int’1 Conf, On the Management of Data. New York: ACM Press, 19974 陈江平,傅仲良,徐志红.一种Apriori的改进算法.武汉大学学报(信息科学版),2003,2.5 李雄飞，李军.数据挖掘与知识发现.北京：高等教育出版社，2003.6 韩家炜.数据挖掘概念与技术.北京:机械工业出版社,20017 Savasere A,Ong B, Mitbander B. An efficient algorithm for mining association rules in large databases[A]. In Proc 1995, Int Conf Very Large Databases(VLDB’95)[C].19958 Bayardo R J, Agrawal R. Mining the Most Interesting Rules[c]. Processing of the 5th International Conference on knowledge Discovery and Data Mining. San Diego: ACMPress, 1999:145-154
[8]电大学习网.免费论文网[EB/OL]. /d/file/p/2024/0424/fontbr />
相关文章：
时政热点：习总关于建设健康中国的重要论述04-26
【关注】教育部、科技部发文要求规范高校SCI论文相关04-26
健全毕业论文抽检体系保障人才培养基本质量04-26
安全是发展的保障 发展是安全的目的04-26