基于MapReduce和AprioriAll的分布式序列挖掘算法

摘 要：序列挖掘技術，能夠從大量雜亂的數(shù)據(jù)中挖掘出用戶的潛在訪問模式。然而，傳統(tǒng)的挖掘技術，由于其性能和擴展性的諸多限制，并不適合現(xiàn)今大數(shù)據(jù)下的挖掘任務。本文基于傳統(tǒng)的挖掘算法AprioriAll，在結合國內(nèi)外研究進展的基礎上引入分布式概念格模型，提出了分布式序列挖掘算法PAHDP。通過在分布式系統(tǒng)上構建算法原型，并加以評估，本文證明了該算法的正確性和有效性，具有一定的應用價值。

關鍵詞：數(shù)據(jù)挖掘；分布式計算；概念格；Hadoop

中圖分類號：TP311

分布式計算的思想，可以將僅僅由單個計算機難以計算和維護的計算任務分為很多小的、相互獨立的部分，然后把這些部分分配給很多臺計算機進行處理。在這個基礎上，利用分布式系統(tǒng)架構MapReduce，用戶可以在不了解分布式底層細節(jié)的情況下，充分利用其框架下集群的高傳輸率與容錯率的優(yōu)點進行計算與存儲。

正是在這種背景下，采用分布式計算以實現(xiàn)龐大數(shù)據(jù)集的數(shù)據(jù)挖掘，成為了目前國內(nèi)外的研究熱點。利用分布式計算，人們可以把龐大的數(shù)據(jù)集分為小的、相對獨立的部分，并部署于集群的計算機中進行計算，最后將結果綜合。本文在此基礎上，對傳統(tǒng)的數(shù)據(jù)挖掘算法AprioriAll進行了分布式探索，并針對影響性能的多個因素進行了分析與改進。

1 基于AprioriAll的分布式挖掘算法設計與實現(xiàn)

1.1 AprioriAll算法

AprioriAll算法是由R.Agrawal等人提出的，該算法采用迭代增長的思想，首先在數(shù)據(jù)庫中找出所有頻繁項集，并在每一次迭代過程中，將上一次得到的序列相互鏈接以生成新序列。接著，在掃描數(shù)據(jù)庫的同時去掉不滿足最小支持度閾值的序列，并將結果作為下一次迭代的候選，直到無法再產(chǎn)生更長的新序列為止。最后，掃描生成的頻繁序列，去除包含于其它序列的子序列，留下來的就是最終的結果。該算法結構簡單，然而面臨著重復掃描哦數(shù)據(jù)庫、難以并行化等問題，需要進行優(yōu)化。

1.2 算法概述

分布式序列模式挖掘的基本思想是將數(shù)據(jù)劃分為一個個數(shù)據(jù)分片，再將每個獨立的數(shù)據(jù)分片上進行數(shù)據(jù)挖掘，最后將所得的數(shù)據(jù)合并。結合這樣的思路，本算法的基本流程則為：（1）數(shù)據(jù)轉(zhuǎn)換與有機分割。本算法的第一步，就是完成數(shù)據(jù)源到形式背景的轉(zhuǎn)換。由于輸入數(shù)據(jù)為大量的交易記錄，因此此步操作可以在集群系統(tǒng)上完成。對于每一個集群節(jié)點，其輸入的數(shù)據(jù)則為交易數(shù)據(jù)庫的一部分，接著，集群節(jié)點保存輸入的交易信息，并記錄其中出現(xiàn)的交易（對象）與商品（屬性）。待所有節(jié)點完成輸入與處理，將每一個形式背景分片合并，即可得到由原數(shù)據(jù)庫轉(zhuǎn)化而得到的形式背景。（2）分布式建格。待數(shù)據(jù)轉(zhuǎn)化和分割完成之后，各節(jié)點即可根據(jù)輸入的子全概念和其對應的形式背景構造子全格。本算法采用了Bordat算法作為建格算法，其實現(xiàn)簡單，且效率較高。（3）頻繁1-序列生成。待節(jié)點建立好了子全格之后，即可進行頻繁1-序列的生成。由于在第1步實現(xiàn)了數(shù)據(jù)的相對獨立分割，因此，此處僅需執(zhí)行本地操作，無需與外界通信。由于概念格的每一個節(jié)點與概念一一對應，而概念則反映了項集（商品集）與其購買記錄之間的聯(lián)系。因此，僅需遍歷概念格，對每一個節(jié)點計算其外延的支持度，并收集支持度大于最小閾值的概念，其內(nèi)涵即為頻繁項集，也就是頻繁1-序列。（4）數(shù)據(jù)再分配與頻繁序列挖掘。待所有節(jié)點完成計算，將所有頻繁1-序列進行合并，即可得到所有的頻繁1-序列，這就是頻繁序列挖掘的基礎。對于挖掘出的頻繁序列集來說，可以按照序列的首元素進行分組，對每一個節(jié)點設定其目標序列，所有節(jié)點僅需挖掘以目標序列開頭的頻繁序列。待所有節(jié)點對頻繁序列的挖掘完畢，即可進行合并，并將最終結果輸出。

1.3 改進點分析

針對傳統(tǒng)的AprioriAll算法，這個算法做出的改進在于：（1）將傳統(tǒng)的串行算法并行化，利用了集群計算的優(yōu)勢提高計算效率。通過將算法部署于MapReduce框架，實現(xiàn)了分布式計算任務的自動部署和負載管理；（2）引入了分布式概念格的思想，避免了AprioriAll算法對數(shù)據(jù)庫的頻繁訪問，通過對數(shù)據(jù)的一次訪問，即可建立起數(shù)據(jù)之間的內(nèi)在聯(lián)系，為之后的序列挖掘提供了所有的必需信息，從而減少了節(jié)點之間的通信；（3）在序列生成上，將傳統(tǒng)的挖掘任務分離，通過采用目標序列的辦法實現(xiàn)了分布式挖掘，在提高效率的同時減少了冗余數(shù)據(jù)的出現(xiàn)。

2 實驗評測

實驗時，共對三種情況下的序列模式挖掘（AprioriAll算法，偽分布式環(huán)境下的PAHDP算法與分布式環(huán)境下的PAHDP算法）進行了比較與測試。實驗設置8組交易數(shù)據(jù)，其中顧客數(shù)目與商品數(shù)目相等，并從20增長到2000。顧客平均交易數(shù)目與平均每次購買商品數(shù)目分別固定為8與2.5。結果如下圖所示：

圖1 實驗結果

通過對比可以發(fā)現(xiàn)，當顧客數(shù)目與商品數(shù)目相等，且交易數(shù)據(jù)小于9000時，PAHDP算法執(zhí)行時間遠遠大于AprioriAll的單機算法。而當數(shù)據(jù)量繼續(xù)提升時，AprioriAll的執(zhí)行時間則隨之從53.385秒增加到了405.418秒（記錄數(shù)為18906），并超過了PAHDP算法。當數(shù)據(jù)量繼續(xù)增長時，AprioriAll算法內(nèi)存溢出而無法計算，而PAHDP算法增速較緩（偽分布式節(jié)點的計算時間僅從116秒增長到了153秒，增長率為31.9%）。從對比實驗可以看出，傳統(tǒng)的AprioriAll算法在顧客數(shù)目小于商品數(shù)目的時候，其計算時間的增長比顧客數(shù)目大于商品數(shù)目的情況下更為緩慢，因此該算法對于數(shù)據(jù)的內(nèi)在結構是敏感的。而對于PAHDP算法來說，則在三種情況下的運行速度差異不大，因此其對于數(shù)據(jù)是不敏感的。

3 結束語

本文深入分析了AprioriAll算法的實現(xiàn)流程和相關局限，從而提出了新算法的改進目標。基于這些改進點，本文提出了分布式挖掘算法PAHDP，并對整個算法的流程和其中的關鍵技術進行了闡述。本文證明了PAHDP算法的有效性，論述了在較大規(guī)模數(shù)據(jù)庫的情況下PAHDP算法所具有的優(yōu)勢。作為集群化序列挖掘的一個有效解決方案，本文設計的算法能夠在大規(guī)模序列挖掘領域具備研究價值。

參考文獻：

[1]王紅俠.基于分布式概念格的序列模式發(fā)現(xiàn)研究[D].合肥：合肥工業(yè)大學.2007

[2]呂峰等.4種序列模式挖掘算法的特性研究[J].武漢理工大學學報，2006，28（2）：57-60

[3]周嘉偉等.新多維序列挖掘算法：對AprioriAll算法的改進[J].科技經(jīng)濟市場，2006，4：26～27

[4]吳漢燕等.基于改進的AprioriAll算法的Web序列模式挖掘研究[J].計算機工程與設計，2010（05）：921-1034

[5]王宇.序列模式挖掘的并行算法研究[D].哈爾濱.哈爾濱理工大學.2007

作者簡介：周游（1990-），男，四川南充人，研究生，研究方向：分布式數(shù)據(jù)挖掘。

作者單位：同濟大學 軟件學院，上海 201804