集群系统中基于MPI的关联规则快速挖掘算法

安立奎 钱伟懿 韩丽艳

(1.渤海大学数学系,辽宁锦州 121003;2.渤海大学公共计算机教研部,辽宁锦州 121003)

集群系统(cluster)也称机群系统指“利用高速通用网络将一组高性能工作站或高档PC机,按某种结构连接起来,在并行程序设计及可视化人机交互集成开发环境支持下,统一调度,协调处理,实现高效并行处理的系统”(王鼎兴,董春雷.可扩展并行机群系统.From CCW,1997-04),由于其具有开发周期短,性能高,投资风险小,可扩展性好等优点,已经成为并行计算中的热点.MPI提供了基于消息传递方式的并行程序设计,是目前发展较快,使用面广的一个公共消息传递库.关联规则是数据挖掘的一个重要研究领域,它能发现不同商品之间的联系,发现顾客购买行为方式,有利于有效设计商品货架,对用户分类等.关联规则的挖掘算法主要有[1]Agrawal等提出的基于Apriori算法的频集方法.为了提高关联规则的挖掘效率,研究人员又提出了并行挖掘算法,主要包括:[2-5]Agrawal等人提出的CD算法,Park等人提出的PDM算法,Chueng等人提出了FDM和DMA算法.这些算法虽然具有速度快、容易实现等优点,但也存在着可扩性较差、候选项集大、规则合成难度高等缺点.

本文参照了文献[6]的算法,给出了一种在集群系统中用MPI实现的基于二进制的关联规则算法,该算法具有实用性强,并行可扩展性好,实现难度低和高效率等优点.

1 基本概念

1.1 关联规则并行挖掘问题描述

设I={i1,i2,…,im}是项的集合,事务T是I的子集.设事务数据库DB是由事务组成的集合,数量为D.DB={DB1,DB2,…,DBn},数量分别为D={D1,D2,…Dn}.项集X⊂I,X在第j个结点的支持度为X.sup(j),在局部数据库DBj中,对于给定的支持度0≤δ≤1,X是局部频繁的,如果满足X.sup(j)≥δDi,X的全局支持度,如果X.sup≥δD,则称X是频繁项集.在第j个数据库生成的k项目候选集用CLk(j)表示,在第j个数据库生成的k项目频繁项集为局部频繁项目集,用LLk(j)表示,在全局数据库D中生成的k项频繁项集为全局项集,用GLk(D)表示,发送到第j个结点上的全局k项集用GLk(j)表示.

MPI拥有一个上百个函数构成的函数库.用MPI构建一个并行计算环境主要用到六个函数.函数名分别为:MPI-Init,MPI-Comm-Size,MPI-comm-Rank,MPI-Send,MPI-Recv,MPI-Finalize.MPI-Init和MPI-Finalize实现MPI环境的初始化和结束;MPI-COMM-WORLD通信因子是在MPI环境初始化过程中创建的,MPI-Commm-Size获取缺省组(Group)的大小;MPI-Comm-Rank获取本进程在缺省组中的逻辑号(从0开始);MPI-Send和MPI-Recv实现消息的传递[7].MPI主要处理点对点和集合两种通信.本文的算法采用的是主从式并行I/O调控策略.在集群中有一个结点为主结点(通常是0结点)其他为从结点,它们之间通过高速网络进行连接,各从结点与主结点交互数据,不用彼此交换数据,减少了通信量,有较好的扩展性.

1.2 数据的二进制表示及其性质

定义1[6]事务(项集)-二进制数关系.给定I={i1,i2,…,im},称f:T×(X×I)→b1b2…bm-1bm为事务(项集)-二进制数关系,并称b=b1b2…bm-1bm为事务T(项目集X)所对应的二进制数,记为Bt(Bx),其中bj∈{0,1},且如果项ij∈T(ij∈X),则bj=1,否则,bj=0,j=1,2,…,m.对项目集X⊆I,Bx中1的个数成为X的长度,记为length(X).例如:X={I1,I4,I5},Bx=10011,length(Bx)=3.

性质1[6]对于Xp,Xq⊆I,Xp,Xq有且只有k-2个元素相同的充要条件是length(BxporB xq)=k.

由Apriori算法和性质 1有,如果Xp,Xq∈LLk-1(j),length(BxporBxq)=k,则,可以组成结点j上的局部候选k项集Xp∪Xq.以下用m位二进制数p代表项集Xp,m位二进制数q代表项集Xq.

性质2[6]对于m位二进制数p和q,如果porq=p,则Xq⊆Xp.

2 改进算法

2.1 算法思想

主结点首先把事务数据库DB利用定义1进行预处理,把得到的新的事务数据库均匀地分发到从结点i上[7],i=1,2,…,n,每个从结点有自己的事务数据库DBi.(1)在结点j中利用GLk-1(j)产生局部候选k(2≤k≤m)项集CLk(j),CLk(j)=Apriori_gen(GLk-1(j)).(2)在结点j利用Apriori性质对CLk(j)进行剪枝,得到局部频繁k项集LLk(j).(3)将LLk(j)发往中心主结点.(4)中心主结点计算全局支持数GLk(D),并且将GLk(D)重新划分,把GLk(Di)发送到各个结点.(5)重复(1)～(4)直到没有新的局部频繁项集产生.

2.2 中心主结点的算法描述

输入:从结点i的局部候选k项集LLk(i)i=1,2,…,n.输出:全局频繁候选k项集GLk(D).

k=1;GGk(D)=Φ;all=0;

for(i=1;i＜=n;i++)

{GGk(D)=GGk(D)∪LLk(i);

if(LLk(i)==Φ)all++;

if(all==n)exit(0);//没有新的局部频繁项集产生

for eachp∈GGk(D)//计算GGk(D)中所有项集p的全局支持度

for eachq∈LLk(D)

if(pxorq==0)//p与q相同

p.sup+=q.sup;

}

for eachp∈GGk(D)

if(p.sup ＜δD)GGk(D)=GGk(D)-p;

2.3 从结点的局部频繁项目集的生成与支持度计算

(1)局部频繁项目集的生成算法

输入:分发到结点i的k-1项全局频繁项目集GLk-1(i).

输出:局部频繁k项集LLk(i)

Apriori_gen()

{LLk(i)=Φ;

for eachp∈GLk-1(i)

for eachq∈GLk-1(i)//q≠p

{pq=porq;//生成新的k序列

npq=pq;

for(i=1,count=0;i＜=m&&npq！ =0;i++)//统计npq中1的个数

if(npqand 0x01)

{count++;

npq=npq＞＞1;//逻辑右移1位

}

if(count==k)//p,q可以合并生成候选k项集

{for(i=1,b=0x01;i＜=m;i++)

n=pq xor b;//n是pq的k-1项子集

ifnGLk-1(i)//n不是频繁k-1项集

break;

}

if(i==m)//pq的所有k-1项子集都是频繁k-1项集

LLk(i)=LLk(i)∪pq

}

returnLLk(i);

}

(2)项集的局部支持度计算方法

输入:局部频繁k项集LLk(i)

输出:局部频繁k项集LLk(i)每一项的支持度

Support_caculate()

{for each t∈DBi//DBi是局部事务数据库,由主结点分发

for eachp∈LLk(i)

if(port==t)

p.sup++;

}

3 算法理论分析

(1)算法的并行性能分析

假设每个结点的DBi具有D/n个事务,n为并行计算结点的数量,假设需要挖掘的项目集I的大小为k,则最多有2k个项集,每次对数据库的扫描时间为ta,则串行时间为2kta,串行的时间复杂度Ts=O(2k).每个分结点的并行运行时间为2kta/n,主结点的运行时间为tb,最坏情况下并行运行的计算时间为tb+n*2kta/n,在阶的意义下并行代价等于最坏情况下串行的代价,具有代价最佳的并行性.

(2)算法的加速比分析

并行运行的时间tp由两部分组成:计算部分tcomp和通信部分

上述算法中,如果项集X在结点i是局部频繁的,则其通信量的复杂度为wtdata),tstartup是消息时延,tdata是发送单位数据的时间,w是数据量的大小.由阿尔达姆定律加速系数期中f是不能分解成并发任务的计算部分所占的比例,.算法的加速比当m→∞时,S(p)→n,所以该算法具有较好的加速比.

4 结 语

集群系统中基于MPI的二进制关联规则算法充分利用了集群系统的低成本、高性能和容易扩展等特点,使系统很容易建立和管理,具有较好的并行性和线性加速比,使用了局部剪枝和全局剪枝的技术,具有较强的实用性和可操作性,采用了二进制进行数据的存储和计算,对事务数据库进行了预处理,充分利用了C语言的位运算,减少了数据的传输量,提高了计算机的运行.用MPI建立并行环境,采用C语言编程,降低了算法实现的难度,该算法是有效可行的.

[1]Agrawal R,Imielinski T,Swami A.Mining Association Rules Between Sets of Items in Large Databases[C].In:Proc ACM SIGM OD Int Conf M anagement of Date,Washington D C,1993:207-216.

[2]Agrawal R,Shafer J C.Parallel Mining of Association Rules[J].IEEE Transactions on Knowledge and Data Engineering,1996,86:962-969.

[3]Park J S,Chen M S,Yu P S.Efficient Parallel Data Mining for Association Rules[C].In:Proceedings of the 4th International Conference on Information and Knowledge M anagement,Baltimore,Maryland,1995:31-36.

[4]Cheung D W,Han J W,Ng V T,et al.A Fast Distributed Algorithm for Mining Association Rules[C].In:Proceedings of IEEE 4th International Conference Parallel and Distributed Information Systems,Miami Beach,Florida,1996:31-44.

[5]Cheung David W,Ng Vincent T,Fu Ada W.Efficient Mining of Association Rules in Distributed Databases[J].IEEE Transactions On Knowledge And Data Engineering,1996,8(6):911-922.

[6]陈 耿,倪巍伟等.基于分布数据库的快速关联规则挖掘算法[J].计算机工程与应用,2006(4):165-167.

[7]蒋廷耀.基于Cluster结构的多维动态数据分布方法[J].三峡大学学报:自然科学版,2004,26(2):67-69.