基于ＶＯＰＰ并行編程環境的最大頻繁項集生成方法

(1.天津大學 計算機科學與技術學院， 天津 300073； 2. 天津工程師范學院 計算機系， 天津 300222)

摘 要：

頻繁項集挖掘是關聯規則挖掘的核心內容，提出了一種挖掘最大頻繁項集的并行算法CDTR。它對CD (counting distribution)算法進行了改進，根據一種新的分布式共享內存環境下面向視圖并行編程思想，將數據庫劃分成視圖。為了實現動態任務分配，對數據庫進行了預處理。實驗結果顯示CDTR能夠高效地生成最大頻繁項集，大大提高了分布式共享內存系統的效率。

關鍵詞：分布式共享內存系統; 面向視圖并行編程； 關聯規則； 最大頻繁項集

中圖分類號：TP338.6文獻標志碼：A

文章編號：1001-3695(2009)04-1305-03

Algorithm for finding frequent itemsets based on VOPP

ZHENG Xiao-yan1，2， SHI Lian-shuan2， SUN Ji-zhou1

(1.College of Computer Science Technology， Tianjin University， Tianjin 300073， China; 2.Dept. of Computer， Tianjin University of Techno-logy Education， Tianjin 300222， China)

Abstract:

Mining frequent item sets is a crucial issue in data mining applications. This paper proposed a novel and powerful parallel algorithm for mining maximal frequent item sets， called CDTR. CDTR improved the counting distribution algorithm based on VOPP (view-oriented parallel programming)， a novel style for parallel programming on cluster computers. It divided search space into views and preprocessed database to help dynamic tasks allocation. Experiments show that CDTR finds maximal frequent item set efficiently and improves the performance of distribution shared memory system.

Key words：distribution shared memory; view-oriented parallel programming; association rules; maximal frequent itemsets

關聯規則挖掘是數據挖掘領域中一個非常重要的內容，最早在1993年由Agrawal等人[1]提出，受到廣泛的關注，并在實際應用中越來越顯示出它的地位。研究人員針對關聯規則挖掘提出了很多有用的算法，但是隨著數據庫規模和網絡通信能力的不斷提高，數據挖掘所面對的數據量迅速膨脹，加之關聯規則挖掘算法的計算量和I/O量都很大的特點，串行挖掘算法遠遠不能滿足實際需要。所以并行關聯規則挖掘算法成為研究的重要課題，已經提出的并行算法主要有產生候選集和不產生候選集兩類方法，產生候選集的方法主要基于Apriori算法[1]。本文討論基于一種新的面向視圖并行編程（view-oriented parallel programming，VOPP）思想的關聯規則挖掘算法。VOPP是Huang 等人 [2]提出的一種新的分布式共享存儲系統下的編程思想。

目前PC機群上的并行編程模型有兩類，即消息傳遞模型和共享存儲模型。消息傳遞模型的工業標準是消息傳遞接口 (message passing interface，MPI)，有多種具體的實現。運行在PC機群上的共享存儲系統稱為分布式共享存儲系統(distributed shared memory，DSM)，DSM實際上是在消息傳遞分布式系統上，給程序員提供了一個虛擬的共享存儲器的假象，這個環境下的編程很方便，可以省去很多與消息傳遞相關的程序設計。但也正因為如此，DSM程序的執行效率遠不如MPI[3]。在MPI編程中，消息傳遞是程序設計的一部分工作，程序員也必須考慮處理機之間的消息，設計消息的內容、傳遞時機和接發消息的對象等，通過對消息的優化設計減少不必要的消息，從而提高效率。而在DSM中，消息傳遞實際上也是存在的，但不再是程序設計的任務。DSM需要通過傳遞消息進行一致性維護，但是為了給用戶一個共享存儲的假象，無須程序員對消息傳遞進行設計和實現。這簡化了程序員的程序設計任務，使得程序設計更加容易，同時也意味著不能通過程序設計優化消息傳遞。大量的用于內存一致性維護以及換頁的消息傳遞，使得當處理機數量和計算規模增加時，DSM性能會急劇下降。而在方便編程方面，共享存儲模型有著很大的優勢。

CD算法是Agrawal等人在文獻[4]中提出的基于Apriori算法的并行算法，是基于不共享內存結構提出的。算法只需要交換計數，所以CD算法的通信量小，實驗表明在數據庫規模以及頻集尺寸增大時的可擴展性能較好。本文根據VOPP思想的特點，對CD算法改造和優化，提出了帶有事務刪減的counting distribution算法(counting distribution with transaction reduction，CDTR)，并在VOPP環境中實現。

1 新的面向視圖的并行編程環境

1.1 面向視圖的并行編程

為使得在DSM編程中，程序員可以通過優化數據分配等方式參與性能優化，Huang 等人 [2]提出了一種新的PC機群上的面向視圖的并行編程思想，針對其他共享存儲編程環境的缺點，提出了視圖的概念。視圖是在分布式共享存儲系統中用于維護一致性的一個概念。一個視圖由需要作為整體進行一致性維護的數據對象組成，視圖不能互相重疊。視圖是在程序員的頭腦里隱式定義的，但是通過原語顯式地調用。例如acquire_view表示要求獨占地訪問一個視圖，用于寫訪問，release_view表示訪問完成。Acquire_view不能嵌套調用，也就是說，一個處理器同一時刻只能寫訪問一個視圖。對于只讀訪問，VOPP提供了一對原語，即acquired_Rview和release_Rview，可以嵌套地調用這兩個原語同時對多個視圖進行只讀訪問。不管在并行程序中是否存在數據沖突，處理器對一個視圖進行訪問時必須通過調用請求和釋放原語才能得到訪問權。如果一個處理器同時訪問多個視圖，那么其中只能有一個視圖是寫訪問。通過對這些原語的使用，編程的重點就集中在如何對共享對象進行訪問。

例如一個簡單的矩陣加運算：A=B+C。其中A、B、C都是1 000×1 000的矩陣，處理器個數為8，VOPP代碼如下：

acquire_view(proc_id);

acquire_Rview(proc_id+8);

acquire_Rview(proc_id+16);

for(i= proc_id *125; i<(proc_id+1)*125;i++)

for(j=0; j<100;j++)

A[i][j]=B[i][j]+C[i][j];

release_Rview(proc_id+16);

acquire_Rview(proc_id+8);

acquire_view(proc_id);

將共享矩陣A、B、C的數據劃分成視圖。上例中，矩陣A的數據按行被分成8個視圖，view(0)~view(7)，即第0~124行的數據為視圖0，125~249行的數據為視圖1，依此類推；同樣，矩陣B的數據也按行被分成8個視圖view(8)~view(15)；矩陣C的數據分成8個視圖view(16)~view(23)。8個處理器pi(p0~p7)分別執行矩陣A和B的第i×124~(i+1)×124行的相加計算，對矩陣B、C的訪問是只讀的，所以可以使用只讀訪問原語acquire_Rview和release_Rview。

歸納起來，VOPP有如下幾個特點：

a)VOPP編程的重點是如何劃分和分配共享數據，程序員通過合理劃分共享對象、合理使用視圖訪問原語，可以參與程序的性能優化；

b)VOPP將共享對象的劃分通過原語顯式地體現出來，還可以使對數據的使用更加明確，減少編程時出現的錯誤；

c）只在視圖訪問原語acquire_view被調用時，更新被調用視圖中相關的數據對象[5，6]。

1.2 基于視圖的一致性維護

在并行計算應用中，實際上有時并不要求每個處理器都需要知道其他處理器執行的所有內存修改。為了提高DSM系統的性能，可以選擇數據更新的時間、處理器和被更新的數據，即實現時間選擇、處理器選擇和數據選擇。憑借將共享數據劃分為互不重疊的視圖，VOPP實現直接實現了數據選擇。為了使得VOPP達到與MPI同樣的效率，提出了帶有集成diffs的面向視圖更新協議[4](view-oriented update protocol with integrated diff， VOUPID)。這個一致性維護協議使用了與TreadMarks[7]類似的diffs概念。TreadMarks采用復寫協議[8]來實現DSM系統的一致性維護，該協議中起用了一個稱為diff的數據結構，用于記錄對頁面的修改。對每個頁面的任何一次修改都有一個diff記錄，每當被修改過的頁被某個處理器請求使用時，相關的所有diff就被用于該頁中數據對象的一致性維護。多個處理器可以并發地對頁面進行修改，所以與同一頁面相關的diff可能有很多個。這個協議帶來的主要問題是diff的積累問題，即當與一個頁面相關的diff越來越多時，將會占用大量的內存空間和CPU時間。文獻[6]基于diff思想，針對diff積累問題進行優化，提出了VOUPID，即在每次處理器釋放對頁面的訪問權（即調用release_view原語）時，將新產生的diff同原有的diff進行合并。這樣就保證任何時候每個頁面只有一個相關的diff，減少了diff的數量，降低了內存空間的占用和傳遞diff所需的處理器時間。當下一個處理器申請使用一個頁面時，與該頁相關的diff就同頁面一起被傳遞給那個處理器。請參見文獻[6]獲得有關diff合并算法的詳細信息。

2 基于VOPP的關聯規則挖掘算法CDTR

為了實現共享編程環境下的高效關聯規則挖掘，筆者提出了VOPP下帶有事務刪減的CD算法。

CD算法思想簡單，容易編程實現。但是每次掃描都要掃描整個數據庫。實際上，對于事務T，如果T不包含任何k-1頻集，由頻繁項集產生的規則可知，T不可能包含任何k頻集。在第k次掃描中不包含任何k項集的事務，不會再對更高維的頻繁項集有貢獻，無須再對其進行掃描。原有的CD算法為了減少數據通信量，使得每個處理器都獨立工作在自己的局部數據庫上，只采用了靜態任務分配。如果根據頻繁項集產生規則，每次掃描過程中削減無用的事務，可以在一定程度上提高搜索速度。提高的范圍與設定的最小支持度有關。同時，因為每個處理器對局部數據庫的削減速度和程度可能不同，會導致負載不平衡，采用動態任務劃分可以最大程度保證計算資源的利用。VOPP環境下，可以利用視圖的概念方便地實現動態任務劃分。

基于以上考慮，筆者提出了基于視圖的CD算法，算法描述如下：

設系統中存在n個處理器P1~Pn，將數據庫劃分為m個視圖V1~Vm，m≥n，且m為每個處理器可用內存的整數倍。記第k次未被掃描的視圖為V_k，記第k次掃描中沒有貢獻的事務為T_k。

K=1

a) 處理器Pi對一個V_1進行掃描，產生局部候選1項集Ci1；

b) Pi將本次掃描獲得的局部Ci1計入全局C1；

c) Pi掃描下一個V_1，直至所有視圖都被掃描為止；

d) 同步，產生L1。

K>1

a) Pi根據Lk-1生成Ck；

b) Pi對一個V_k中未標記的事務進行掃描，標記出T_k，計算Ck的局部計數；

c) Pi掃描下一個V_k，累加局部Ck，直到沒有未被掃描的視圖為止，將局部Ck計入全局Ck；

d) 同步，計算Lk；

e) 各處理器獨立決定是否終止。

CDTR憑借刪減事務獲得更少的掃描數據庫時間。如果數據庫是勻質的，事務刪減效果不明顯，各個處理器上的事務刪減速度也基本相同，處理器之間可以維持負載平衡;反之則會產生負載不平衡。為了能夠使算法適應所有類型的數據庫，CDTR對數據庫進行預處理，使劃分出來的各個子數據庫的數據分布不均勻，事務刪減就可以起到顯著的作用。數據預處理的方法是將數據庫劃分成n個大小相等的邏輯塊，計算各個分塊中m個項目的支持數，形成n個m維的矢量。采用聚類的方法把這n個矢量聚成h個類，使類與類之間的差別盡量大，每個類中的事務差別盡量小，每個類劃分為一個視圖。當k達到某一個值時，某些視圖可能因為不含有任何大項集而被刪減，或剩余很少的事務，此時，動態任務分配就會有利于效率的提高。從以上算法描述中可以看出，算法對事務的刪減是邏輯刪減，通過標記實現，不會增加額外的磁盤I/O。

3 相關實驗及結果

實驗所用數據庫中所有項均被處理成二值的（是或不是），根據這個特點，在VOPP程序編寫中對算法進行了再一次的優化，在計算過程中削減事務的大小。具體實現方法如下：

對數據進行預處理，將第i個項目(1≤i≤m) 的名稱寫為i，值置為0（不是）或i（是）。每次一個處理器要求訪問一個子數據庫時，首先將該子數據庫中未被標記的事務拷貝到一個本地二維數組中。當統計某個頻繁項目集的支持數時，可以借助項目集中項目的名稱直接訪問對應的數組元素，而不必逐個訪問事務中的所有項目，達到對事務數量和大小進行邏輯刪減的目的。

視圖的劃分會影響程序實現的性能。根據1.2節的描述，VOPP的內存維護是根據與視圖相關的diff實現的，每個視圖有一個對應的diff，這些diff在一致性維護中均作為單獨的消息傳遞。所以劃分的視圖越多，系統中產生的消息越多。根據VOPP的基本思想，一個視圖在整個程序中要作為整體使用，當一個處理器申請使用某個共享數據時，包含該數據的視圖將被傳遞給這個處理器。所以劃分的視圖越大，使用視圖時在系統中引起的數據傳輸越多。本算法中維護的視圖有：

 a）h個子數據庫各成為一個視圖，算法執行中用做只讀視圖。

b）全局候選項目集C，每次掃描結束之后被更新。

c）頻繁項集L，每次掃描結束后更新，下一次掃描開始之前被各處理器讀取。

d）L的支持度S，用于產生規則，同L一起更新。

e）一個整數x∈[1，h]，用來記錄本次掃描中已經被掃描的視圖號，每次掃描開始初始化為0，每個處理器占用一個子數據庫后增1。當x=h時本次掃描結束。

f)一維數組Mx，為每一個子數據庫x維護一個獨立于事務集的一維數組Mx，用來保存在掃描過程中對各個事務的標記信息。每個處理器讀入子數據庫時根據Mx的值選擇性地讀入事務，掃描結束后寫入本次掃描中發現的新的T_k。

實驗所用的集群由16臺運行RedHat Linux 9.0的個人計算機構成，通過100 Mbps交換機連接。每臺計算機帶有650 MHz的處理器和128 MB內存，硬盤16 GB，虛擬頁面大小為4 KB。實驗所用的數據庫是某大型賣場六個月的銷售數據庫，共259 240條事務，所賣商品屬于56個類別，實驗用來發現這些商品類別在銷售中的關系。數據庫總尺寸13.7 MB，設定的最小支持度2%。實驗實現了MPI下的CD算法和VOPP下的CDTR算法；為了對比動態任務分配的影響，還實現了VOPP下靜態任務分配的CD算法，以下簡稱為CD_V。圖1顯示了本實驗中三種算法的加速比曲線。



從圖1中可以看出，處理器數量較少（少于8個）時，VOPP和MPI的加速比相差不大，但隨著處理器數量增加，加速比差距拉大。造成這種差距的原因主要有三個方面，即障礙的使用、數據傳輸延遲和一致性維護。

VOPP程序要使用比MPI更多的障礙。VOPP程序中，有時必須使用障礙來達到處理器之間的同步，而MPI程序幾乎可以不使用障礙。如果在MPI程序中人為地加入一些不必要的障礙，實驗中可以發現，程序的加速比會隨障礙數目的增多大幅下降。可見障礙是導致加速比下降的主要因素。MPI程序中，進程在等待數據時處于阻塞狀態，一旦得到數據就可以立即繼續執行。而VOPP程序中，進程在等待數據時處于障礙點上，需要發送數據的進程向它發送消息才能繼續執行。這中間還需要進行內存的一致性維護，這些消息和內存維護操作需要消耗CPU時間。與MPI相比，VOPP的內存一致性維護完全是額外的代價，也在一定程度上影響了程序效率。

CDTR的加速比較CD-V提高了，原因主要有三個方面：a）動態任務分配有效利用了CPU資源；b)事務數量的刪減減少了磁盤I/O次數；c)CDTR程序實現中優化的結果。

4 結束語

實驗結果說明，CDTR是一個有效利用視圖概念的共享地址空間下并行產生大項集的方法，通過合理劃分視圖和針對性的數據預處理技術，CDTR算法在處理器個數較少時表現非常出色。在VOPP的支持下，能夠很容易地編寫出實現程序。

參考文獻：

[1]AGRAWAL R，IMIELINSKI T，SWAMI A. Mining association rules between sets of items in large database[C]//Proc of ACM SIGMOD International Conference of Management Data. New York: ACM Press， 1993:207-216.

[2]HUANG Zhi-yi， PURVIS M， WERSTEIN P. View-oriented parallel programming on cluster computers[EB/OL].(2004-09).http://www.cs.otago.ac.nz/research/techreports.html.

[3]WERSTEIN P， PETHICK M， HUANG Zhi-yi. A performance comparison of DSM， PVM， and MPI[C]//Proc of the 4th International Conference on Parallel and Distributed Computing， Applications and Technologies. [S.l.]: IEEE Press， 2003:476-482.

[4]AGRAWAL R， SHARFER J. Parallel mining of association rules[J]. IEEE Trans on Knowledge and Data Engineering， 1996， 8(6):962-969.

[5]HUANG Zhi-yi， PURVIS M， WERSTEIN P. View-oriented parallel programming and view-based consistency[C]//Proc of the 5th International Conference on Parallel and Distributed Computing， Applications and Technologies.2004:505-518.

[6]HUANG Z， PURVIS M， WERSTEIN P. View oriented update protocol with integrated diff for view-based consistency[C]//Proc of IEEE/ACM Symposium on Cluster Computing and Grid. Washington DC:IEEE Computer Society， 2005:208-217.

[7]AMZA C， COX A L， DWARKADSA S， et al. TreadMarks: shared memory computing on networks of workstations[J]. IEEE Compu-ter， 1996， 29(2):18-28.

[8]CARTER J B， BENNETT J K， ZWAENEPOEL W. Techniques for reducing consistency-related information in distributed shared memory system[J]. ACM Trans on Computer Systems， 1995， 13(3):205-243.