基于线性链表存储结构的apriori改进算法

《基于线性链表存储结构的apriori改进算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于线性链表存储结构的Apriori改进算法赵明茹郭键孙媛（北京物资学院信息学院，北京市，101149）摘要：^priori是故有影响的挖掘关联规则频繁项集的算法。但是Apiori由于需要多次对数据库进行扫描,所以运行效率比较低。在Apriori算法的基础上,本文提出了一种基丁线性链表的频繁项集挖掘算法,实验证明该算法能够有效提高执行效率。关键词：数据挖掘；关联规则；Apriori算法；线性链表中图分类号：TO11文献标志码：AAnImprovedAlgorithmofAprioriBasedonLinerListZhaoMingru,GuoJian,SunYua

2、n(SchoolofInformation・BeijingXVuZiUniversity.Beijing101149.China)Abstract:Aprioriisthemostinfluentialfrequentpatternminingalgorithm.However,becausetheApriorialgorithmscansthedatabasemanytimes,sotheefficiencyofAprioriisrelativelylow.Inthispaper,anewApriorialgorithmbasedonlinerlistwaspr

3、oposed,thenewApriorialgorithmcanimprovedtheefficiencyofApriorialgorithmbyexperiments・Keywords:DataMining;AssociationRules;thealgorithmofApriori;linerlist引言数据挖掘是从数据库中抽取隐含的、以前未知的、具冇潜在应用价值的信息过程。关联规则挖掘发现大量数据中项集Z间有趣的关联或相关关系，关联规则在数据库挖掘屮占有非常重要的地位。Apriori是关联规则挖掘的经典算法。它是一种挖掘单维、单层、布尔关联规则的算法,由Ra

4、keshAgrawalRama和krishnanSkrikant于1993年提出的，Apriori算法采丿IJ两阶段挖掘的思想：笫阶段挖掘频繁项集，第二阶段挖掘频繁关联规则。笫二步较为简单，如果得到频繁项集，可以直接推出关联规则。挖掘的重点主要集中在如何快速、高效发现频繁项集。Apriori算法的主要不足之处是，生成了大量的候选频繁项集以及为了验证候选频繁项集是否是频繁项集，需要反复扫描事务数据库，所以Apriori算法效率较低，不能满足人规模数据库的实时挖掘要求［1］。为了减少扫描数据库的次数，提高算法的效率，本文研究并实现了一种Apriori的改进算法，将事物

5、数据库屮的信息用线性链表表示，节约了存储设备"0时间，把对数据库的扔描转化为対内存中线性链表的扫描。实验证明，该算法能显箸地捉髙执行效率。1Apriori算法简介及其局限性1.1Apriori算法简介Apriori算法的基木原理是使用一种称作逐层搜索的迭代方法，即用k-项集去探索（k+1）-项集。通过对事务数据库的多次扫描來发现所有的频繁项集，在每一次扫描中只考虑具有同一长度（即项集中所含项目的个数）的所冇项集。首先，Apriori算法计算事务数据库中所有单个项目的支持度，得到所有长度为1的频繁项集，称为1-频繁项集L1。在后续工作中，首先以k-1次扫描所牛成的频

6、繁项集为阜础产生新的候选项集Ck。然后计算这些候选项集的支持度，生成k-频繁项集Lk。重复上述过程氏到再也发现不了新的频繁项集为止［2］。1.1Apriori算法的不足Aprirori一直作为经典的关联规则挖掘算法被使用，Apriori算法采用了逐层搜索的迭代方法，算法简单明了，没有复朵的理论推导，也易于实现。但是，它冇一些难以克服的不足：（1）对数据库的扫描次数过多。在反复扌「I描数据库的过程小，数据库D的大小将影响算法的性能，并且系统的I/O负载相当大。（2）Apriori算法会产生人量的屮间项集。由频繁k-1项集进行连接生成的候选k项集数量巨大。由Lk-l产

7、生候选k项集Ck是指数级增长的。候选集的规模巨大，验证候选集是不是频繁项集需耍占用算法很多时间⑶。2Apriori算法的改进为了使算法减少扫描数据库的次数，节省存储设备的T/0时间。木文把事物数据库中的信息用链表表示，把对数据库的扫描转变为对内存屮链表的扌「I描。2.1事务数据库的链表表示方法本文屮利用线性链表表示事务数据库信息。规定事务中的项按字典顺序组织，将事务数据库的信息用链农表示。链农由两部分组成：事务标识头表与链表中间节点。其屮，每个事务标识节点包含三个域：事务序号和两个指针。两个指针分别指向下一个事务标识节点和指向该事务的第一个项。链表小间节点有三个域

8、组成：如图