集群系統(tǒng)中基于MPI的關聯(lián)規(guī)則快速挖掘算法

安立奎 錢偉懿 韓麗艷

(1.渤海大學數學系,遼寧錦州 121003;2.渤海大學公共計算機教研部,遼寧錦州 121003)

集群系統(tǒng)(cluster)也稱機群系統(tǒng)指“利用高速通用網絡將一組高性能工作站或高檔PC機,按某種結構連接起來,在并行程序設計及可視化人機交互集成開發(fā)環(huán)境支持下,統(tǒng)一調度,協(xié)調處理,實現(xiàn)高效并行處理的系統(tǒng)”(王鼎興,董春雷.可擴展并行機群系統(tǒng).From CCW,1997-04),由于其具有開發(fā)周期短,性能高,投資風險小,可擴展性好等優(yōu)點,已經成為并行計算中的熱點.MPI提供了基于消息傳遞方式的并行程序設計,是目前發(fā)展較快,使用面廣的一個公共消息傳遞庫.關聯(lián)規(guī)則是數據挖掘的一個重要研究領域,它能發(fā)現(xiàn)不同商品之間的聯(lián)系,發(fā)現(xiàn)顧客購買行為方式,有利于有效設計商品貨架,對用戶分類等.關聯(lián)規(guī)則的挖掘算法主要有[1]Agrawal等提出的基于Apriori算法的頻集方法.為了提高關聯(lián)規(guī)則的挖掘效率,研究人員又提出了并行挖掘算法,主要包括:[2-5]Agrawal等人提出的CD算法,Park等人提出的PDM算法,Chueng等人提出了FDM和DMA算法.這些算法雖然具有速度快、容易實現(xiàn)等優(yōu)點,但也存在著可擴性較差、候選項集大、規(guī)則合成難度高等缺點.

本文參照了文獻[6]的算法,給出了一種在集群系統(tǒng)中用MPI實現(xiàn)的基于二進制的關聯(lián)規(guī)則算法,該算法具有實用性強,并行可擴展性好,實現(xiàn)難度低和高效率等優(yōu)點.

1 基本概念

1.1 關聯(lián)規(guī)則并行挖掘問題描述

設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)表示,發(fā)送到第j個結點上的全局k項集用GLk(j)表示.

MPI擁有一個上百個函數構成的函數庫.用MPI構建一個并行計算環(huán)境主要用到六個函數.函數名分別為:MPI-Init,MPI-Comm-Size,MPI-comm-Rank,MPI-Send,MPI-Recv,MPI-Finalize.MPI-Init和MPI-Finalize實現(xiàn)MPI環(huán)境的初始化和結束;MPI-COMM-WORLD通信因子是在MPI環(huán)境初始化過程中創(chuàng)建的,MPI-Commm-Size獲取缺省組(Group)的大小;MPI-Comm-Rank獲取本進程在缺省組中的邏輯號(從0開始);MPI-Send和MPI-Recv實現(xiàn)消息的傳遞[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進行預處理,把得到的新的事務數據庫均勻地分發(fā)到從結點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)發(fā)往中心主結點.(4)中心主結點計算全局支持數GLk(D),并且將GLk(D)重新劃分,把GLk(Di)發(fā)送到各個結點.(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)局部頻繁項目集的生成算法

輸入:分發(fā)到結點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++)//統(tǒng)計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是局部事務數據庫,由主結點分發(fā)

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是發(fā)送單位數據的時間,w是數據量的大小.由阿爾達姆定律加速系數期中f是不能分解成并發(fā)任務的計算部分所占的比例,.算法的加速比當m→∞時,S(p)→n,所以該算法具有較好的加速比.

4 結 語

集群系統(tǒng)中基于MPI的二進制關聯(lián)規(guī)則算法充分利用了集群系統(tǒng)的低成本、高性能和容易擴展等特點,使系統(tǒng)很容易建立和管理,具有較好的并行性和線性加速比,使用了局部剪枝和全局剪枝的技術,具有較強的實用性和可操作性,采用了二進制進行數據的存儲和計算,對事務數據庫進行了預處理,充分利用了C語言的位運算,減少了數據的傳輸量,提高了計算機的運行.用MPI建立并行環(huán)境,采用C語言編程,降低了算法實現(xiàn)的難度,該算法是有效可行的.

[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]陳 耿,倪巍偉等.基于分布數據庫的快速關聯(lián)規(guī)則挖掘算法[J].計算機工程與應用,2006(4):165-167.

[7]蔣廷耀.基于Cluster結構的多維動態(tài)數據分布方法[J].三峽大學學報:自然科學版,2004,26(2):67-69.