一种正交链表存储的改进Apriori算法  

An Improved Apriori Algorithm Based on Orthogonal List Storage

作　　者：赵学健[1] 孙知信[1] 袁源[2] 陈勇 

机构地区：[1]南京邮电大学江苏省通信与网络技术工程研究中心,南京210003 [2]江苏省邮电规划设计院有限责任公司,南京210000 [3]南京龙渊微电子科技有限公司,南京210000

出　　处：《小型微型计算机系统》2016年第10期2291-2295,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61373135;61401225;61502252)资助;江苏省基础研究计划(自然科学基金)项目(BK20140883;BK20131377;BK20140894)资助;中国博士后科学基金项目(2015M581844)资助;江苏省博士后科研计划项目(1501125B)资助;南京邮电大学校级科研基金项目(NY214101;NY215147)资助

摘　　要：随着数据量的逐渐增大,关联规则挖掘算法的时间效率亟待提升,因此提出一种基于正交链表的改进Apriori算法.该算法首先将带扫描数据库转化为关系矩阵,并使用正交链表对该矩阵进行存储,从而可以通过对链表节点集合进行操作实现频繁项目集的挖掘,克服了Apriori算法需要多次扫描数据库的缺点,只需扫描数据库一遍,减少了频繁进行I/O操作的时间;此外,该算法对Apriori算法复杂的自连接和剪枝过程进行了优化,简化了频繁项目集的生成过程,提高了Apriori算法的时间效率.With the gradual increase of data quantity, the time efficiency of association rule mining algorithms needs to be improved badly. Consequently, an improved Apriori association rule mining algorithm based on orthogonal list is proposed. In this algorithm, the database is transformed into a relational matrix first, and the matrix is stored by orthogonal list. The mining of frequent item sets can be realized by operating orthogonal list nodes. The algorithm overcomes the shortcoming of the Apriori that need to scan the database many times. It only needs to scan the database once which reduces the time consumed by the frequent I/O operation. Furthermore, the algorithm optimizes the complex self-connection and pruning process in the Apriori algorithm and simplifies the process of generating frequent item sets. As a result,it improves the time efficiency.

关 键 词：关联规则 正交链表 APRIORI 事务数据库 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]