海量数据上挖掘关联规则的并行算法  

Parallel mining algorithm of association rules on massive data

作　　者：张兆功[1] 李建中[1] 张艳秋[2] 

机构地区：[1]黑龙江大学计算机技术学院,黑龙江哈尔滨150080 [2]哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨150001

出　　处：《哈尔滨工业大学学报》2004年第5期561-565,共5页Journal of Harbin Institute of Technology

基　　金：国家自然科学基金资助项目(60273082);国家重点基础研究发展规划资助项目 (G1 9990 3 2 70 4);国家高技术研究发展计划资助项目资助项目 (2 0 0 1 -AA-41 5-41 0 );国家教委博士基金资助项目(2 0 0 0 0 2 1 3 0 3 );黑龙江省自然科学基金资助项目(F0 0 -1 1 )

摘　　要：针对目前关联规则挖掘算法中数据库规模很大时算法执行时间太长的问题.指出了并行计算是解决该问题的一个有效方法.利用新提出的可以忽略仅仅在少于1/4的结点机上的局部频繁项集,给出了一种新的并行随机抽样方法,并利用机群并行计算机的自治能力和I/O高度并行的特点,提高了抽样算法对海量数据的处理能力和效率.理论分析和实验数据显示,该算法的加速比接近于处理机的个数p,通信复杂性为处理机的个数p的对数,具有良好的扩展性和海量处理能力,且精确度较高.Some technologies of mining association rules on massive data and study efficient of parallel algorithm are discussed. At present, many association rules mining algorithms have been discussed. As the database scale is big and executed time of algorithms is very long. Parallel computing is an efficient method for this problem; however, existed parallel algorithms all have shortcomings of less scalability and weak dealing with massive data. Ignoring local frequent itemsets only in 1/4 of all node computers emerge, we propose a parallel sampling algorithm. It takes advantage of the ability of cluster computer with self-manage and parallel accessible for disks I/O, to improve the ability and efficiency of sampling algorithm for dealing with massive data. Theoretic analysis and experiential result show that speedup of the algorithm approximates node number p of cluster computer, and the complex of communication is the logarithm of node number p, holds better scalability and ability to deal with massive data, and has also high-precision.

关 键 词：海量数据 关联规则 并行算法 数据挖掘 数据库 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]