一种基于多叉树的并行Apriori算法  

Parallel Apriori Algorithm Based on Multi-tree

作　　者：郭方方[1] 梁晓[1] 王慧强[1] 钱真[1] 陈江涛[1] 

机构地区：[1]哈尔滨工程大学计算机科学与技术学院,哈尔滨150001

出　　处：《小型微型计算机系统》2015年第6期1176-1180,共5页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61370212)资助;高等学校博士学科点专项科研基金项目(20102304120012;20122304130002)资助

摘　　要：在云计算环境下,如何在大数据中进行关联规则挖掘是目前研究的重点和热点.目前已有的并行Apriori算法访问数据库频繁,时间复杂度高,且存储开销大.据此提出一种基于多叉树的并行Apriori算法.首先,依据垂直分割的思想,将原事务数据库转换为布尔型项目数据库并用二进制形式存储.其次,将记录集分割成n个子集,由多个节点并行计算,并使用多叉树结构存储频繁项.方法用于某网络安全态势感知系统后的结果表明,该算法与现有方法相比减小了对数据存储空间的要求,降低了数据库的访问次数,缩短了算法的运行时间.In cloud computing environment, how to carry on the mining association rules in large data is a research focus and hot spot. The existing parallel Apriori algorithms have access to the database frequently with high time complexity and large storage space. Therefore, this paper presents a parallel Apriori algorithm based on multi-tree. First, an original transaction database is converted to a Boolean project database and stored in binary form, based on thought of vertical division. Second, the database is divided into n subsets for parallel computation, and use multi-tree to store frequent items. The experimental results used in the network security situation awareness show that, compared with the existing methods, the algorithm reduces the requirements of the data storage space, reduces ac- cess to the database, shorten the running time of the algorithm.

关 键 词：数据挖掘 关联规则 并行Apriori算法 多叉树 二进制存储 

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