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

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

中圖分類號：TP311

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

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

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

1.1 AprioriAll算法

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

1.2 算法概述

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

1.3 改進(jìn)點(diǎn)分析

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

2 實驗評測

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

圖1 實驗結(jié)果

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

3 結(jié)束語

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

參考文獻(xiàn)：

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

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

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

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

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

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

作者單位：同濟(jì)大學(xué) 軟件學(xué)院，上海 201804