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

摘要：针对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算法中，计算量主要由于候选项目集多，因此在生成候选项目集时将不可能成为频繁项集的元素提前删除，以减少计算量。即在第一次遍历之后就不用数据库Di来计算支持度，而用集合Fi（k）来计算，并且利用Li（k-1）对Fi（k）进行筛选，将不符合最小支持度的元素从Fi（k）中删除，并同时将项数小于或等于k-1的事务删除，以缩小Fi（k）。各局部处理器，利用改进的Apriori算法进行剪枝处理，生成局部频繁项目集。并传回主处理器，循环至找到全局频繁项目集。

5、结语

本文提出一种高效的基于集群的并行关联规则算法APPAA（Advanced　Pruning　Parallel　Apriori　Algorithm），该算法在生成候选项目集时将不可能成为频繁项集的元素提前删除，以减少计算量，同时由于APPAA算法采用并行挖掘，效率明显高于Apriori算法。此外，APPAA算法具有良好的并行性和可扩展性，适用于专利数据库的个性检索，读者推荐的项目，缩短了读者的检索时间，同时提高了文献的利用率。

参考文献

[1]刘晶.基于数据仓库的高校图书馆管理的设计与实现.图书情报工作，2009.

[2]刘晶等.一种基于单处理机的并行关联规则算法及其在数字图书馆中的应用.图书情报工作，2011.