一種有效的并行頻繁項集挖掘算法
2008-12-31 00:00:00王丹陽田衛東胡學鋼
計算機應用研究 2008年11期
(合肥工業大學 計算機與信息學院， 合肥 230009)
摘要：傳統的挖掘頻繁項集的并行算法存在各節點間負載不均衡、同步開銷過大、通信量大等問題。針對這些問題，提出了一種多次傳送重新分配數據的并行算法(MRPD)。MRPD算法在第l步時將數據庫重新劃分成若干組，并根據各節點的需要多次傳送分組；各節點獲得完整分組后異步地計算頻繁項集；所有節點計算完成后，得到全部頻繁項集。理論分析和實驗結果表明MRPD算法是有效的。
關鍵詞：數據挖掘; 并行算法; 頻繁項集
中圖分類號：TP182;TP301.6文獻標志碼：A
文章編號：1001-3695(2008)11-3332-03
Effective parallel algorithm for mining frequent itemsets
WANG Dan-yang， TIAN Wei-dong， HU Xue-gang
(School of Computer Information， Hefei University of Technology， Hefei 230009， China)
Abstract:There were problems in traditional parallel algorithms for mining frequent itemsets， such as load imbalance， frequent synchronization， large scale communication and so on. Aiming at solving these problems， this paper proposed a parallel algorithm with multi-transmitting redistributed data (MRPD). In MRPD， data was redistributed into some groups at step l， and all the groups were multi-transmitted according to the request of computer nodes. Each node would compute frequent itemsets asynchronously after having received one full group. Finally， resulted the integrated frequent itemsets. Theoretical analysis and experimental results suggest that MRPD is effective.
Key words：data mining; parallel algorithm; frequent itemsets
數據挖掘又稱做知識發現(knowledge discovery of database，KDD)，是繼網絡之后的又一大技術熱點。關聯規則挖掘是數據挖掘的重要功能之一，用于發現大量數據中項集之間有趣的關聯和相關關系。挖掘關聯規則的核心是發現頻繁項集[1]，現已有多種發現頻繁項集的串行算法，如Apriori[2]、PARTITION[3]、FP-growth[4]及抽樣算法等。但是，現在用于頻繁項集挖掘的數據庫往往很大（按GB 乃至TB 計），采用傳統的串行算法所需的時間和空間開銷大，效率較低。為了提高挖掘頻繁項集的效率，研究人員提出了多種并行挖掘算法，主要有CD（count distribution）、DD（data distribution）、CaD（candidate distribution）[5]、FDM[6]和FMAGF[7]等。這些并行挖掘算法各有優點，但仍然存在通信量大、同步開銷較多和各節點負載不均衡等問題。針對這些問題，本文在深入分析了CD和CaD優缺點的基礎上，提出了一種多次重新分割數據的并行關聯規則挖掘算法（MRPD）。
1相關定義和Apriori性質
11并行挖掘頻繁項集的問題描述
全局事務數據庫為D，總的事務條數為d。設P1，P2，…，Pn為n臺基于無共享體系結構的計算機節點（簡稱節點），即它們之間除了通過網絡傳遞信息外，其他資源（如硬盤、內存等）全部都是獨立的；Di（i = 1，2，…，n）是D經過分割存儲于節點Pi上的分事務數據庫，其中的事務有di條，則D=∪ni=1Di，d=∑ni=1di。并行挖掘頻繁項集問題就是指如何通過n臺節點同時工作，節點Pi（i = 1，2，…，n）只處理自己的私有數據Di（i=1，2，…，n），各臺節點間僅通過網絡傳遞有限的信息，最終在整個事務數據庫D中挖掘出頻繁項集。
12本文中符號的定義
Lk：由頻繁k-項集構成的集合，集合的每個成員有兩個域，即項目集和支持數。
Ck：由候選k-項集構成的集合，集合的每個成員有兩個域，即項目集和支持數。
Pi：ID號為i的處理器。
Di：分配到Pi的數據集。
DRj：劃分數據庫后得到的數據庫分組，ID號為j。
Cjk：k=l步時，表示劃分后得到的候選項集分組，ID號為j；k＞l時，表示由劃分后的分組經連接剪枝產生的候選k-項集集合。
Ljk：ID號為j的分組產生的頻繁k-項集集合。
13Apriori性質
性質1設X是頻繁項集，Z是項集，如果ZX，則Z也是頻繁項集。
性質2設X是不頻繁項集，Z是項集，如果XZ，則Z也是不頻繁項集。
性質3如果X、Z是項集，且ZX，則support(Z)≥support(X)。
2現有的并行算法CD和CaD
Agrawal等人[5]提出了三種并行算法CD、DD和CaD。其中，CD是Apriori的一個簡單并行化算法，它是通過分割數據庫來完成并行化的，可描述如下：如果有N個處理器節點，則各節點獲得數據庫的1/N，然后分別在各數據庫子集上完成類似于Apriori的算法。DD算法為了更好地利用系統的內存，每個節點互相獨立地計算不同的候選集的支持度。由于DD算法需要每個節點在每一步都將本地數據給所有其他的節點，DD算法需要很高的通信帶寬。現有條件下DD算法通信消費過大，無法取得好的時間性能，本文只對CD和CaD算法進行重點討論。CaD算法綜合了DD和CD算法，以彌補它們各自的不足。CaD算法在前l步采用DD算法或CD算法；到第l步(其中l由啟發而定)，為了減少各節點之間的數據依賴，算法對大項集Ll-1進行分配，同時也對數據進行重新分配，使Pi能獨立于其他節點生成Cik(k＞l，Cik∩Cjk=，i≠j)。為了減少節點對候選集的依賴，CaD算法不等待從其他節點傳來完整的剪枝信息，它盡可能快地剪枝，而滯后到達的剪枝信息在下一次剪枝時使用。
經過實驗運行CD和CaD兩種算法，發現采用重新分配數據庫方案的異步的CaD算法反而不如思路簡單的同步的CD算法。通過進一步分析發現，對不同l的選取大大影響著CaD算法的并行效率。對l的選取過大，由于候選的項集數量很大，CaD算法優勢無法抵消分配數據造成的時間消耗；對l的選取過小，由于CaD算法采取Ll-1的前l-2項前綴進行頻繁項集和數據的重新分配，那么得到的前l-2項前綴過短，導致數據分配不平衡，會影響并行算法的負載平衡性。問題是如何選擇l，CaD算法往往得不到理想的l。另一方面，CD算法的代價相對而言較小，但是當數據分布不夠均勻或者節點的運算能力相差很大(如不同的內存大小、不同的處理器速度、不同的I/O帶寬)的情況下，同步的代價將會非常大。
3多次傳送重新分配數據的并行算法(MRPD)
31算法思路
為了改進CaD算法找不到合適的l，導致負載不平衡的缺點，設計了一種多次傳送重新分割數據的并行算法——MRPD。MRPD算法設定固定的l值，通常選取較小的l值；但所產生的頻繁l-1項集的分組應遠大于處理器節點的個數，這一條件是很容易滿足的。由于大型事務型數據庫往往有很多個不同的項，會產生大量的頻繁1-項集，其個數通常遠多于處理器節點的個數；由頻繁1-項集連接和剪枝后生成的頻繁2-項集的個數達到頻繁1-項集個數的平方數量級，因此若取l最小值3，根據前l-1前綴產生的候選l-項集的分組應遠多于處理器節點的個數。
有了確定的l值，MRPD算法在到達l步后，各節點將候選1-項集分組，并按照該分組對局部數據進行預分割，預分割即只在各節點的內部分割，而不再按照分組傳送和合并各節點的局部數據。所有節點都完成預分割后，各節點傳送按字典序排列在一起的n個數據分組，使每個節點都得到某一完整的數據分組。然后，每個節點按照類似CaD算法的方法計算頻繁項集。當出現空閑節點時，該節點向其他節點發送請求，從其他節點獲得一個完整的數據分組，并計算由該分組產生的頻繁項集。如此，直到所有分組都完成生成頻繁項集的計算和所產生頻繁項集的傳送，每個節點就會得到完整的頻繁項集。
MRPD算法采用空閑節點申請計算任務的方式，有效地解決了CaD算法各節點間負載不平衡的缺點，以及CD算法當數據分布不夠均勻或節點的運算能力相差很大的情況下，同步的代價非常大的缺點。
32算法步驟
算法描述如下：
a)第k步(k＜l)，應用CD或者DD算法。
b)第k步(k=l)，
(a)在n個節點根據完整的Lk-1生成完整的Ck。
(b)各Pi根據Ck的前k-1前綴劃分Ck，得到分組Cjk，將前k-1前綴作為分組的ID號。這個劃分過程是由每個節點并行地完成，每個Pi都得到同樣的Cjk分組。
(c）各Pi根據Cjk中的候選項集能夠在本地計數，將數據庫重新劃分為DRj。這個劃分過程也是由每個節點并行地完成。
(d）根據ID號選擇n個Cjk，對被選中Cjk添加記號，并將它們對應的DRj傳送到相應的Pi。
(e）當Pi處理完所有本地數據以及接收完其他節點發送的數據時，它產生n-1個異步接收緩沖區，以從其他節點接收Ljk。在產生候選集Cj+1k的剪枝步驟時，需要其他節點的Ljk作為剪枝信息。
(f）節點Pi根據Cjk計算Ljk，利用n-1步異步廣播將其廣播到其他n-1個節點。
c)第k步（k＞l)，若Pi沒有收到其他節點的請求，則執行(a）~(d）;若收到請求則立刻執行(e）。
(a）Pi收集由其他所有處理器發送過來的頻繁項集。在產生候選集的剪枝步驟中將用到這些信息，但在連接時無須這樣的信息。Pi保存其他Pi發送的頻繁項集的分組ID號和最大長度，頻繁項集的接收緩沖區在每次處理后重新設置。
(b）Pi根據本地的Ljk-1產生Cjk。但是Pi可能沒有從其他的處理器接收到Ljk-1，所以處理器Pi在剪枝步驟時應當小心。它必須能區分一個候選項目集的k-1長度的子集是在所有Ljk-1都沒有出現，還是在某一個Ljk-1中出現了，但是這個Ljk-1處理器Pi沒有收到。Pi利用有疑問的項目集的l-1前綴找到這個項目集應在的分組。根據分組標記確定所在節點，從而判斷Ljk-1是否已經從該處理器接收到。
(c）Pi掃描一遍DRj，并且計數Cjk，然后根據Cjk計算Ljk，并且利用n-1步異步地向其他n-1個處理器發送Ljk。
（d）若Ljk為空，向其他Pi發送請求。
(e）若還有未添加標記的DRj，Pi接到請求立刻記錄當前執行的步驟信息，并根據字典序傳送某個未添加標記的DRj到發送請求的節點，為其添加標記。令發送請求的節點的k=l+1。Pi傳送完本地的DRj，則讀取被記錄的步驟信息，恢復原來的步驟。
3．3算法的完備性證明
為了進行完備性證明，先對算法的兩個設計細節作了說明，并給出了以下兩個定義：
a)事務數據的分組。假定ID號是有序的，如果某一事務滿足多個ID號，則只會被分配到排在最前面的ID號所表示的Cjk中。為了解決這個問題，MRPD算法允許事務被分配多次，事務將會被分配到它所包含的所有ID號所表示的Cjk中。因此，對于候選項集可以在數據重新分配后的局部數據中獲得它的完備的支持度計數。
b)利用Ljk-1生成Cjk。該規則是每個節點保存所有根據Apriori性質的剪枝步所需要的候選k-1項集，并認為那些候選k-1項集是頻繁的，直到得到某一節點傳來的剪枝信息(剪枝信息是指某候選項集或其子項集是頻繁的這一信息)，才將該節點所保存的候選k-1項集中符合剪枝信息的定為頻繁的，不符合剪枝信息的定為不頻繁的，并進行相應的剪枝。剪枝是指對目前候選項集中包含的子項集是不頻繁的直接不對其計數，直接定為不頻繁的。
當k=l時，顯然所有Cjk是Ck的一個劃分。為了方便，將這種情況稱做Ck是完美的。將任一候選k-項集在所有Cjk中可以找到而且只找到一次的，稱Ck是完備的。得到以下定義：若Ck=∪Cjk且Cik∩Cjk=，i≠j，則稱Ck是完美的；若Ck∪Cjk且Cik∩Cjk=，i≠j，則稱Ck是完備的。顯然，Ck是完備的，不一定是完美的；而Ck是完美的，則肯定是完備的。
證明MRPD算法所得到的頻繁項集包含所有頻繁項集且只包含頻繁項集。
先證MRPD算法所得到的頻繁項集只包含頻繁項集。由于所有得出的頻繁項集均滿足最小支持度計數，必然為頻繁項集。證明MRPD算法所得到的頻繁項集包含所有頻繁項集，可轉換為MRPD算法可得到整個數據集能夠得到的所有候選項集，即所有Ck都是完備的。當k≤l時，算法生成Ck的方法應用同步算法CD或DD，因此這些Ck都是完美的。因此，只需證明k＞l時，若Ck-1是完備的，則其后生成的Ck也是完備的。證明過程如下：
由于各Pi根據得到的DRj和Cjl分組經若干次連接剪枝生成的Cjk中，只包含各分組獨有的l-1前綴的候選k-項集，那么由各分組生成的候選k-項集均與其他分組生成的候選k-項集不同，則一個候選k-項集最多只能出現在一個Cjk中一次。現在證明若Ck-1是完備的，則其后生成的Ck中的任一候選k-項集均可在某一Cjk中找到。先考慮最壞的情況，所有其他分組的k-1項集的剪枝信息都沒有到達，這時該分組所在節點認為所有該分組以外的候選k-1項集都是頻繁的，并以此進行Ljk-1中的頻繁項集的連接操作生成該分組的候選k-項集。因為Ck-1是完備的，根據前面證明可知 Lk-1是完美的，那么各Ljk-1是Lk-1的一個劃分，Ljk-1就包含了所有具有該ID號前綴的頻繁k-1項集。這些頻繁項集連接后產生的候選項集的集合Cjk也包含具有該ID號前綴的候選k-項集的全部；又由Apriori性質1可知，Ck中的候選k項集的l-1前綴必為某一分組的ID號，因此Ck是完備的。現在考慮剪枝的情況。由于剪枝是將該處理器所計數的所有候選的Ck-1項集中符合剪枝信息的定為頻繁的，不符合剪枝信息的定為不頻繁的，并對目前候選項集中包含的子項集是不頻繁的直接不對其計數，直接定為不頻繁的。根據Apriori性質2，剪枝并沒有打破Ck的完備性。故而得證。
4算法分析與性能測試
為了測試算法的性能，將MRPD算法與經典的挖掘頻繁項集的并行算法CD、CaD算法進行性能比較。測試環境為8個計算節點的集群系統，帶寬為100 Mbps，各節點配置均為Dual Xeon 3.16 GHz，內存 2GB，集群系統采用Linux操作系統，并使用OSCAR 4.2集群管理軟件；測試數據集使用Gen工具生成的數據集 (http://www.almaden.ibm.com/ cs/quest/)；測試程序的編程語言為VC++6.0，消息傳遞庫為標準MPI。測試對MRPD算法l值取3，對CaD算法l值分別取3和5以及CD算法作了比較，且在MRPD算法和CaD算法的前l-1步均采用CD算法。測試結果如圖1和2所示。其中，圖1(a)是采用水平等間距投影方法分別在8個節點生成測試數據庫的測試結果，每個節點為5 000 條數據；(b)是對數據分布不夠均勻的數據庫的測試結果。其中一個節點為20 000 條數據，其他7個節點為5 000條數據。圖2則顯示了數據分布不均勻的情況下，CD、CaD(l=3)、CaD(l=5)和MRPD的每個節點的計算時間、通信時間、同步等待時間和處理器空閑時間所占全部時間的比例。
由圖1可知，對于數據分布均勻的數據庫，CD算法還有不太明顯的優勢；對于數據不均勻分布的數據庫，MRPD算法和CaD算法體現了重新分配數據庫的優勢。在這兩種情況下，MRPD算法比CaD算法在執行時間上都有所降低。通過圖2和進一步分析，可得到如下結論：a）CD算法對于數據分布不均勻的數據庫同步耗時過大，嚴重影響了算法的效率；進一步可知，如果節點的運算能力相差很大，CD算法同步的代價將會很大。b）CaD算法中對于取不同的l值，時間性能將會顯著變化，且l值越大，CaD算法的性能越接近CD算法的性能。c）MRPD算法比CD算法節省了大量用于同步的時間開銷；MRPD算法與 CaD算法取相同l值時，MRPD算法的空閑處理器節點請求任務的方式有效減少了處理器的空閑時間，表現了較好的負載平衡性；當CaD算法所取l值大于MRPD算法時，MRPD算法體現了其對比CD算法時的優勢。
5結束語
MRPD算法采用固定的l值和空閑節點申請計算任務的方式，克服了CaD算法找不到合適的l值而引起的各節點間負載不平衡的缺點；也克服了當數據分布不夠均勻或者節點的運算能力相差很大的情況下，CD算法的同步代價非常大的缺點。MRPD算法采用較小的固定l值，并在l步后是一種異步算法，降低了節點間的依賴。通過理論分析和實驗測試可知，MRPD算法是一種應用廣泛的有效算法。
參考文獻：
［1］AGRAWAL R， IMIELINSKI T， SWAMI A. Mining association rules between sets of items in large databases[C]//Proc of ACM SIGMOD International Conference on Management of Data. New York:ACM Press， 1993:207-216.
[2]AGRAWAL R， SRKANT R. Fast algorithms for mining association rules[C]//Proc of the 20th International Conference on Very Large Databa-ses. San Francisco:Morgan Kaufmann Publishers， 1994:487-499.
[3]SAVASERE A， OMIECINSKI E， NACATHE S. An efficient algorithm for mining association rules in large database[C]//Proc of the 21st International Conference on Very Large Databases.San Francisco:Morgan Kaufmann Publishers，1995:432-444.
[4]HAN Jia-wei， PEI Jian， YIN Yi-wen. Mining frequent patterns without candidate generation[C]//Proc of ACM SIGMOD International Conference on Management of Data. New York: ACM Press， 2000:1-12.
[5]AGRAWAL R， SHARFER J. Parallel mining of association rules[J]. IEEE Trans on Knowledge and Data Engineering， 1996，8(6):962-969.
[6]CHEUNG W L， VINCENT N， FU W C， et al. Efficient mining of association rules in distributed database[J]. IEEE Trans on Know-ledge and Data Engineering，1996，8(1):911-922.
[7]楊明，孫志揮，吉根林．快速挖掘全局頻繁項目集[J].計算機研究與發展，2003，40(4)：620-626.
