基于矩陣的并行化頻繁項集挖掘算法 精靈論文

1、基于矩陣的并行化頻繁項集挖掘算法陳曉云，趙娟（蘭州大學信息科學與工程學院，蘭州 730000）摘要：在分析并行頻繁項集挖掘算法的基礎上，提出了一種新的基于矩陣的并行化頻繁項集5挖掘算法，該并行算法采用主從節(jié)點處理模式，利用矩陣存儲頻繁項集信息。將主節(jié)點處理 后生成的矩陣分發(fā)到從節(jié)點上并行的生成頻繁 k 項集。通過實驗驗證了算法的可行性和有效 性。關鍵詞：并行化；頻繁項集挖掘；并行中圖分類號：TP301.610Paralleled Frequent Itemset Mining Algorithm BasedMatrixChen Xiaoyun, Zhao Juan(School of Info

2、rmation Science & Engineering ,Lanzhou University, LanZhou 730000)15Abstract: Based on the analysis of the parallel frequent itemset mining algorithm, a new paralleled frequent itemset mining algorithm based matrix is introduced in this paper. The parallel algorithmadopts a master-slave node pro

3、cessing mode，using matrix to storage itemset to reduce memoryspending. Distributed the matrix which is processed by the master node to the slave node ,then the slave node generated the frequent k itemset paralleled. The results of the experiments show that our20algorithm has good effectiveness and f

4、easibility.Keywords:parallel; frequent itemset mining; parallel0引言數(shù)據(jù)挖掘是通過一定的方法從數(shù)據(jù)庫中將大量隱藏的信息展示出來。隨著人類的發(fā)展科25技的進步，人類以往存儲的信息變得越來越龐大，怎樣將這些龐大的信息利用簡單的方法提 取出來，并且將這些看似無關的信息通過某種方式關聯(lián)起來就成為數(shù)據(jù)挖掘最重要的研究內(nèi) 容1。為了發(fā)現(xiàn)關系數(shù)據(jù)庫中各個項目之間內(nèi)在的關聯(lián)，很多研究工作者提出了關聯(lián)規(guī)則的概 念。關聯(lián)規(guī)則挖掘是通過置信度尋找出所有的強關聯(lián)規(guī)則，而這些強關聯(lián)規(guī)則被成為頻繁項30集。因此關聯(lián)規(guī)則挖掘中最重要的問題就是頻繁項集挖掘。頻繁

5、項集挖掘已經(jīng)成為數(shù)據(jù)挖掘 領域的重要研究方向，并且在相關性分析、入侵檢測等領域已經(jīng)有了廣泛的應用。研究工作 者也提出了很多高效率的頻繁項集挖掘算法。但是隨著數(shù)據(jù)量的增長串行的頻繁項集挖掘算 法已經(jīng)不能快速的進行挖掘工作，因此提出一種有效地并行頻繁項集挖掘算法成為當今社會 研究的重點。本文在研究當前已有的并行化頻繁項集挖掘算法的基礎上提出了一種新的基于35矩陣的并行頻繁項集挖掘算法MPHP-Miner。通過實驗證明了 MPHP-Miner 算法的有效性和可行性，并且能夠有效的降低內(nèi)存使用率 和運行時間，是一個很好的并行化頻繁項集挖掘算法。1并行頻繁項集挖掘綜述頻繁模式挖掘的搜索空間可以被模擬成類

6、似格的結構，其中由模式的大小來決定它處于基金項目：甘肅省科技支撐項目（2009GS00858）；廣東省教育部產(chǎn)學研項目（00367851220327032）作者簡介：陳曉云，（1956-），女，教授，數(shù)據(jù)倉庫與挖掘通信聯(lián)系人：趙娟，（1985-），女，碩士研究生，視頻處理與應用. E-mail: zj855810163 40格中的哪一層，每一層又以某種順序進行排列。模式格的維數(shù)決定了問題的指數(shù)級別2。例 如，對于一個有著 n 個不同項的事務數(shù)據(jù)庫，可能的模式就會有 2n。也就是說，如果一個 事務數(shù)據(jù)庫有 100 個不同的項，搜索空間就達到 2100 1030。巨大的搜索空間使得在大型數(shù) 據(jù)庫上

7、的頻繁模式的挖掘成為一個計算密集型問題。然而傳統(tǒng)的頻繁模式挖掘算法被單一處 理器和有限的內(nèi)存空間所限制，不適用于大型數(shù)據(jù)庫。因此，利用高性能并行計算來改善現(xiàn)45有頻繁模式挖掘算法的瓶頸，使其適用于大規(guī)模數(shù)據(jù)庫是非常必要的。在 Apriori 算法的基礎上，R.Agrawal 等人提出了并行算法 Count Distribution，DataDistribution 和 Candidate Distribution Methods4。1.1Candidate Distribution 算法DD 算法和 CD 算法都需要處理器同步的再每一遍的最后分別交換計數(shù)或者是頻繁項集504。這樣花費的時間代價

8、比較大。CaD 算法綜合了 DD 和 CD 算法,以彌補它們各自的不足。 CaD 算法在前 L 步采用 DD 算法或 CD 算法;到第 L 步(其中 L 由啟發(fā)而定),為了減少各節(jié)點 之間的數(shù)據(jù)依賴,算法對大項集 Ll-1 進行分配,同時也對數(shù)據(jù)進行重新分配,使 Pi 能獨立于其 他節(jié)點生成 Cik(k>l,CikCjk= ,ij)。為了減少節(jié)點對候選項集的依賴,CaD 算法不再等待從 其他節(jié)點傳來的完整的剪枝信息,而是盡可能快地剪枝,將滯后到達的剪枝信息留在下一次剪55枝時使用。對于所有的 k<1，采用 DD 算法或者 CD 算法。 對于所有的 k=1，CaD 算法的具體步驟如下

9、：1N 個處理器中的 Lk 1 ，Lk 1 是平衡的。記錄在 Lk 1 中的每一個頻繁項集，哪一個處 理器被分配來處理這個頻繁項集。這個分割在每一個處理器上都是并行的。602處理器 Pi 生成C i ，邏輯上僅僅使用 L分割來完成它。注意到 Pi 仍然接近完成kk 1k 1kL，因此可以使用標準剪枝操作，在這個過程中生成C i 。k3Pi 產(chǎn)生全局計數(shù)在C i 中產(chǎn)生候選。同時數(shù)據(jù)庫被重新分配到 DRi 。4當 Pi 處理完所有的本地數(shù)據(jù)以及從其他全部處理器接收的數(shù)據(jù)，它布置 N-1 異步接收緩沖來接收 Lj 從所有其他處理器。這些 Lj 需要剪枝C j，在產(chǎn)生候選項集的k65剪枝步。kk +

10、15處理器 Pi 利用C i 計算 Li ，異步發(fā)送它到其他的 N-1 個處理器使用 N-1 異步發(fā)送。kk對于所有的 k>1，CaD 算法的具體步驟如下：1處理器 Pi 收集所有的頻繁項集發(fā)送給其他處理器。這些頻繁項集被用在產(chǎn)生候選 項集的剪枝步，而不是添加步。從處理器 j 得到的項集，長度可以是 k-1，或者小70于 k-1（比較慢的處理器）或者是大于 k-1（比較快的處理器）。Pi 保持跟蹤每個處 理器 pj 產(chǎn)生最大長度的頻繁項集。接收頻繁項集的緩沖區(qū)在處理完后重新后置處 理。iij2處理器 Pi 利用本地 Lk 1 來計算Ck 。Pi 沒有從其他處理器收到 Lk 1 ，所以 P

11、i 在剪枝時應該注意。它需要區(qū)分一個項集（一個長度為 k-1 的候選項集的子集）并不存在jj75于一個項集的任何 Lk 1 ，而是存在于一些 Lk 1 。但是這個集合還沒有被 Pi 接收到。它這么做通過探索 Lj 1 （重新分配發(fā)生在第 l 遍）使用在問題中長度為 l-1 的項集k 1的前綴，發(fā)現(xiàn)處理器對它是可靠的，并且檢查 Lj 是否被處理器接收。Pi 通過 DRi 執(zhí)行一遍并且計算C i 。然后利用C i 計算 Li 并且異步的傳播 Li 到每一個其kkkk他處理器使用 N-1 異步發(fā)送。801.2 PFP-tree 算法8590951001051102004 年 Javed 和 Khok

12、har 等人提出了類 FP-Growth 的基于分布式內(nèi)存環(huán)境下的并行頻繁 項集挖掘算法 PFP-Tree5。該算法將整個數(shù)據(jù)庫分割為 p 個不重合的塊，其中 p 是處理節(jié)點 的數(shù)量。然后將不同的任務 i 分配給每一個處理節(jié)點 pi，其中 0 i < p 。PFP-tree 算法的具體 步驟如下：1各節(jié)點 p 掃描被分配的數(shù)據(jù)塊并且計算本地數(shù)據(jù)庫塊中的頻繁項的支持度。2所有處理節(jié)點做同步得到總體的頻繁項支持度計數(shù)。3各節(jié)點依據(jù)總的支持度來排序頻繁項，并刪除非頻繁項。4各節(jié)點第二次掃描本地數(shù)據(jù)庫塊并建立本地 FP-tree。5頭表被分成 p 個互不相交的子集，每個處理節(jié)點為被分配到的項的集

13、合并行挖掘頻 繁模式。6由于第 5 步中的劃分是靜態(tài)的，每個處理節(jié)點必須通過其他的節(jié)點來確認本地樹上 的信息。在第 4 步被分配到一個節(jié)點上的單頻繁前綴分支構成了挖掘步的完整信 息。利用一次自底向上的掃描來進行確認信息。7第 6 步中確認的信息利用一個遞歸的歸并樹結構在各節(jié)點上將需要進行l(wèi)og p 次通 訊。在每一次通訊的最后，一個節(jié)點需要解包收到的信息到本地的 FP-tree 樹上， 然后為下一次歸并準備新的信息。8每個處理節(jié)點挖掘被分配的頻繁項集。 為了挖掘頻繁項集，它的條件模式基需要依附一個主處理器。頻繁 1-項集的條件模式基和前綴路徑一起構成每一個本地 FP-Tree 的所有事件元素的

14、根。與此同時為了得到本地所 需的數(shù)據(jù)分塊，PFP-tree 算法需要各節(jié)點交換基于每個頻繁 1-項集的條件模式基，因此整個 算法的通訊還是比較多的，降低了并行的效率。2基于矩陣的并行化頻繁項集挖掘算法為了減少內(nèi)存使用率以及減少算法的通訊量，我們提出了一個新的基于矩陣的并行化頻 繁項集挖掘算法 MPFP-Miner，該算法采用矩陣這種簡單的數(shù)據(jù)存儲結構，通過一次掃描數(shù) 據(jù)庫之后，將每個項目的支持度等信息存儲在矩陣中，之后再無需掃描數(shù)據(jù)庫，直接通過矩 陣行列之間的簡單運算就可計算出頻繁 k 項集的支持度。采用主從式并行計算的方式，由主 計算節(jié)點將矩陣行列之間的運算分配到各個分計算節(jié)點，在各個分計算

15、節(jié)點并行的處理后， 將結果返回給主節(jié)點。在主從節(jié)點通訊方面，采用讀取共享內(nèi)存的方式節(jié)約主從節(jié)點通訊的 時間，我們在內(nèi)存中開辟一塊大小為的內(nèi)存塊，采用互斥的方式讀寫內(nèi)存塊。MPFP-Miner 算法主要包含三個步驟，第一個步驟是矩陣的構造，這一部是本算法最重 要的一個步驟。第二個步驟是主節(jié)點處理算法，第三個方面是從節(jié)點處理步驟。下面我們就 每個步驟進行詳細的介紹。2.1 矩陣的構造由于樹結構在內(nèi)存中存儲時占用存儲空間比較大，而且遍歷樹花費的時間代價也比較115120125130高，因此我們本算法中采用 0-1 矩陣（所謂 0-1 矩陣是指矩陣中的每個元素的值或者是 0 或 者是 1）這種存儲形式

16、，這種存儲格式的優(yōu)點是只需計算每一行 1 的個數(shù)就可以計算出頻繁 K 項集的支持度3 6 7。給定的事務數(shù)據(jù)庫 D，事務個數(shù)為 m，項目格式為 n，我們構造一個 m 行 n 列的矩陣 M， 矩陣 M 的定義如圖所示，如果項目 I 屬于事務 T，則對應的 R 值就為 1，否則為 0。圖 1 矩陣 M Fig. 1 Matrix M給矩陣 M 加入一列 sum，我們構建 m 行 n+1 列的矩陣 M*，sum 值表示每一個項目 I的支持度，sum 的值由 I 行每一列的 R 值相加得到。剛開始時每一行的 sum 值初始為 0。圖 2 在矩陣 M 中加入一列 sumFig. 2 Add a col

17、name sum in Matrix M2.2 主節(jié)點處理算法這一節(jié)我們主要介紹 MPFP-Miner 算法的主節(jié)點處理算法。下面我們以事務數(shù)據(jù)庫 D 為例，規(guī)定最小支持度閾值 min_sup=2，以此為例來具體說明 我們的算法。135140表 1 事務數(shù)據(jù)庫 D Tab. 1 database D145150主節(jié)點構造首先矩陣，并且計算出每一個項目 I 的 sum 值，如圖所示。如果某個項目的TIDTransactionsT1a,b,eT2b, dT3b, cT4a,b, dT5a,cT6b, cT7a,cT8a, b, c, eT9a, b, csum 值小于定義的最小支持度閾值 min_

18、sup 的話，就把這個項目所在的一行刪除。通過構造 的矩陣 M*我們看出每個項目的支持度都大于等于 min_sup 因此這一步不需做處理。圖 3 主節(jié)點構造好的矩陣 M 以及矩陣 M* Fig. 3 M and M*然后主節(jié)點項目兩兩組合分成 4 組，第一組a,b、a,c、a,d、a,e，第二組b,c、b,d、b,e，第三組c,d、c,e，第四組d,e。表現(xiàn)在矩陣中就是將這些組合的行進行與 運算。將 4 組數(shù)據(jù)分別發(fā)送給 4 個從節(jié)點讓其進行與運算處理，從節(jié)點處理好后將得到的結 果矩陣發(fā)送給主節(jié)點，主節(jié)點將 4 個從節(jié)點返回的結果矩陣進行合并得到矩陣 M1(即頻繁 2 項集矩陣)，新的到的矩陣

19、 M1 將覆蓋矩陣 M，以減少存儲空間。新矩陣如圖所示。155160165圖 4 頻繁 2 項集矩陣 M1Fig. 4 Matrix M1同樣的方法主節(jié)點將得到的頻繁 2 項集矩陣的項目分成 5 組。將這 5 組發(fā)送到 5 個從 節(jié)點進行相同的運算，分節(jié)點將計算結果返回給主節(jié)點，主節(jié)點將結果矩陣進行合并得到矩 陣 M2(即頻繁 3 項集矩陣)，新的到的矩陣 M將覆蓋矩陣 M，以減少存儲空間。新矩陣如 圖所示。圖 5 頻繁 3 項集矩陣 M2Fig. 5 Matrix M2算法如下圖所示：170圖 6 主節(jié)點處理算法Fig. 6 master algorithm1751802.3 從節(jié)點處理算法

20、這一節(jié)我們主要介紹 MPFP-Miner 算法的從節(jié)點處理算法。上一節(jié)主節(jié)點將數(shù)據(jù)分成 4 組，我們?nèi)〉谝唤M為例來說明從節(jié)點的主要工作。第一組 數(shù)據(jù)運行在從節(jié)點 1 上，從節(jié)點 1 得到主節(jié)點發(fā)送過來的數(shù)據(jù)，將其進行與運算，并行將結 果中小于最小支持度閾值 min_sup 的行刪除，然后將得到的矩陣發(fā)送給主節(jié)點。第一組運算 后得到的結果矩陣以及刪除非頻繁項后的頻繁 2 項集矩陣 M2*如圖所示。圖 7 結果矩陣以及頻繁 2 項集矩陣 M2*Fig. 7 M2*第二次主節(jié)點將數(shù)據(jù)分成 5 組，同樣我們以第一組數(shù)據(jù)為例，如圖所示。185圖 8 結果矩陣以及頻繁 3 項集矩陣 M2*Fig. 8 M

21、2*算法如下圖所示：190圖 8 從節(jié)點處理算法Fig. 8 slaver algorithm1953實驗結果與分析實驗環(huán)境：由 5 臺 2.8 GHz Intel Core CPU，2GB 內(nèi)存的 PC 機搭建 X10 環(huán)境，機子之 間的通信采用千兆路由器實現(xiàn)，操作系統(tǒng)為 Windows XP。所有程序均用 X10 編譯實現(xiàn)。實 驗數(shù)據(jù)我們采用標準數(shù)據(jù)集：BMS-POS、BMS-WebView-1。對比算法我們使用 F-Miner 算 法和 FP-Growth*算法。200205210圖 9 BMS-POS 數(shù)據(jù)集Fig. 9 BMS-POS dataset圖 10 BMS-WebView-

22、1 數(shù)據(jù)集Fig. 10 BMS-View-1 dataset通過實驗結果可以看出，MPFP-Miner 算法是一種很好的并行頻繁項集挖掘算法。4結論本文在研究當前已有的并行化頻繁項集挖掘算法的基礎上提出了一種新的基于矩陣的 并行頻繁項集挖掘算法MPHP-Miner。該算法采用矩陣這種簡單的數(shù)據(jù)存儲結構，通過一 次掃描數(shù)據(jù)庫之后，將每個項目的支持度等信息存儲在矩陣中，之后再無需掃描數(shù)據(jù)庫，直 接通過矩陣行列之間的簡單運算就可計算出頻繁 k 項集的支持度。并且采用主從式并行計算 的方式，由主計算節(jié)點將矩陣行列之間的運算分配到各個分計算節(jié)點，在各個分計算節(jié)點并 行的處理后，將結果返回給主節(jié)點。在主從節(jié)點通訊方面，采用讀取共享內(nèi)存的方式節(jié)約主 從節(jié)點通訊的時間，我們在內(nèi)