一种高效并行关联规则挖掘算法在专利数据库应用.docVIP

一种高效并行关联规则挖掘算法在专利数据库应用 　　摘要：针对Apriori算法在专利数据库挖掘时因数量巨大而存在的低效问题，提出一种利用集群的并行关联规则挖掘算法APPAA（Advanced　Pruning　Parallel　Apriori　Algorithm）。通过仿真实验表明，APPAA算法比传统的Apriori算法在时间上缩短了85%左右。同时该方法具有良好的并行性和可扩展性，可以有效地提高专利数据库服务水平。 　　关键词：并行计算 专利数据库 数据挖掘 Apriori算法； 　　中图分类号：G250.76；TP391 文献标识码：A 文章编号：1007-9416（2012）11-0134-01 　　1、引言 　　随着专利的迅猛发展，产生了大量的记录和数据，在此情况下，借鉴目前数字图书馆的管理方式，利用数据挖掘对海量信息深层次的开发，以方便读者使用和提高文献使用率，成为提高专利数据库服务水平的一种解决方案。关联规则的Apriori是数据挖掘中效果较好的一种算法。它通过挖掘数据项集之间的潜在关系，从而在大量数据中发现有用的知识，这些知识对于读者分析、专利分类、个性推荐等决策的制定起到了很大的作用。但是，随着专利数据库的不断发展，读者数量激增，传统的Apriori算法需要频繁扫描候选集耗费时间过长。已有很多文献对传统的Apriori算法进行了有效的改进。为了提高挖掘的效率，同时提高系统的扩展性，提出一种高效的并行关联规则算法，以加快专利检索的处理速度，提高了挖掘效率。 　　2、关联规则 　　关联规则挖掘是从大量数据项中发现有趣的关联或相关联系。设I={，，…，}是项的集合，其中的元素称为项（item）。记D为交易T的集合，这里交易T是项的集合，并且。对应每一个交易有唯一的标识，如交易号（TID）。设X是一个I中项的一个集合，如果XT，那么称交易T包含X。 　　一个关联规则是形如XY的蕴涵式，这里XI，YI，并且X∩Y=Φ。规则XY在事物数据库D中的支持度（support）是事物集中包含X和Y的事物数与所有事物数之比，记为support（XY），即 　　规则XY在事物集中的可信度（confidence）是指包含X和Y的事务数与包含X的事物数之比，记为confidence（XY），即： 　　3、并行关联规则 　　并行Apriori算法主要有以下几种： 　　CD（Count　Distribution）算法是Apriori算法最直接的并行方式。每个处理机根据本地数据库划分所有候选项集的局部支持度。在每趟扫描结束时，交换局部支持度来产生全局支持度。由于CD算法不管候选集是否频繁相互之间都传递候选集的信息，对通讯资源的带宽浪费严重，在候选集过多时会造成通迅量的过载。 　　DD（DataDistribution）算法将候选集分成几部分，分别放到不同的处理机上。为了产生全局支持度，各处理机每扫描一趟都要覆盖整个数据库，产生了巨大的数据交换开销。 　　CAD（Candidate　Distribution）算法是分割候选集，采用了有选择复制数据库的方法，使每个处理机相对独立工作。 　　目前并行Apriori算法主要问题是重复访问数据库分区带来的I/O开销和每次迭代过程中候选计数、数据交换的通信开销。因此需要从以上两个方面优化现有并行算法，本文提出一种基于提前剪枝的并行关联规则挖掘算法APPAA（Advanced　Pruning　Parallel　Apriori　Algorithm），实验证明，该算法减少了候选项目集和数据交换开销，加快Apriori算法效率85%左右。 　　4、APPAA算法描述 　　设P1，P2……Pi（i=1，2，……，n）为n台无共享体系结构集群，即它们之间除了通过网络传递信息外，其它资源（处理器、硬盘、内存等）全部是独立的。 　　定理一：设数据集D被分割成分块D1，D2，...，Dn，全局最小支持度为minsupport，对应其最小支持数为min_count。设数据分块Di的局部最小支持数记为min_counti（i=1，2，...，n）那么局部最小支持数 　　min_counti　=min_count*Di/D（i=1，2，...，n） 　　定理二：如果一个数据项目集在D1，D2，...，Dn中均不是频繁项目集，则这个数据项目集在全局数据集D中不可能是频繁项目集。 　　定理三：一个局部的频繁项目集不一定是全局的频繁项目集。 　　根据定理一，定理二和定理三，本文采用总-分-总的处理方法，即主处理器完成生成第一次频繁项目集，并对该频繁项目集进行划分，生成局部项目集。局部项目集分别处理各自的数据后将结果返回主处理器，循环直至结束。 　　在Apriori算法中，计算量主要由于候选