关联规则中的Apriori算法的研究与改进
近十几年来,人们利用信息技术生产和搜集数据的能力大幅度提高,数据资料的规模急速膨胀。于是,人们希望有新一代的技术和工具能够智能地自动地帮助人们分析已经消耗大量财力和物力所收集与整理的海量数据,以发现有用的知识,达到为决策服务的目的。因此,面对“人们被数据淹没,人们却饥饿于知识”的挑战,数据挖掘技术应运而生,并得以蓬勃发展。数据挖掘是当今人工智能和数据库研究方面最富活力的领域。数据挖掘是指从大量的数据中发现潜在的、有用的知识的过程。关联规则挖掘是数据挖掘的主要研究内容。而频繁项目集的发现是关联规则挖掘的核心问题。 本文详细描述了数据挖掘、关联规则的基本理论以及关联规则挖掘的经典算法Apriori算法,并对经典Apriori算法进行了分析发现其存在着规则冗余度大、效率不高和不能挖掘定量规则等缺陷。本文针对此算法的算法瓶颈问题提出了两种改进方法,如下: 1.针对经典Apriori算法运行效率瓶颈问题,结合位集合占用内存空间少、逻辑运算快的特点,本文提出一种基于项集位逻辑运算的改进算法:B_Apriori算法。该算法通过一次数据库扫描,构建事务集位集合;采用项集位逻辑“与”运算和位统计操作确定频繁项集;改进连接和剪枝策略,采用项集位的逻辑“或”运算,统计运算结果重复出现次数,生成候选项集。实验证明,通过与经典Apriori算法的对比可以发现,B_Apriori算法运行时间明显减少。该算法避免了数据库的重复扫描和繁琐的连接减枝操作,进一步提高了Apriori算法的运行效率。 2.针对经典Apriori算法在统计事务库中的项时要反复扫描事务库,算法开销很大的问题,本章结合数学中矩阵以及向量内积的概念上提出了一种新的Apriori改进算法:Apriori_Matrix算法。Apriori_Matrix算法从三个方面对原有的算法进行了改进,减少了产生的候选频繁项集Ck中项集的数据,也减少了剪枝过程中的运算次数,在统计支持度阶段减少了需要扫描的数据库中的事务数。而且计算机进行向量运算和位运算速度更快,程序也会更容易实现。实验证明,新算法在系统的开销和时间效率上都有很大的提高。
数据挖掘;关联规则;Apriori算法;位集合;垂直向量
中国海洋大学
硕士
通信与信息系统
丁香乾
2012
中文
TP311.131;TP301.6
59
2012-12-27（万方平台首次上网日期，不代表论文的发表时间）