國(guó)家級(jí)論文發(fā)表推薦期刊《信息與電腦》國(guó)家新聞出版總署批準(zhǔn)，國(guó)內(nèi)外公開(kāi)發(fā)行的計(jì)算機(jī)類優(yōu)秀期刊。1989年創(chuàng)刊，國(guó)內(nèi)統(tǒng)一刊號(hào)：CN11-2697/TP，國(guó)際標(biāo)準(zhǔn)刊號(hào)：ISSN1003-9767，郵發(fā)代號(hào)：82-454。《信息與電腦》雜志在零售流通領(lǐng)域有著廣泛的盛譽(yù)，鑒于“中國(guó)第一本全力推動(dòng)流通領(lǐng)域信息化刊物”權(quán)威性的要求，雜志的主要特點(diǎn)就是匯集流通業(yè)IT業(yè)內(nèi)專家和企業(yè)管理者最新的言論和觀點(diǎn)，以及他們的實(shí)踐經(jīng)驗(yàn)與體會(huì)分享，為流通領(lǐng)域的企業(yè)提供理論指導(dǎo)和實(shí)踐參考。
　　摘 要：序列挖掘技術(shù)，能夠從大量雜亂的數(shù)據(jù)中挖掘出用戶的潛在訪問(wèn)模式。然而，傳統(tǒng)的挖掘技術(shù)，由于其性能和擴(kuò)展性的諸多限制，并不適合現(xiàn)今大數(shù)據(jù)下的挖掘任務(wù)。本文基于傳統(tǒng)的挖掘算法AprioriAll，在結(jié)合國(guó)內(nèi)外研究進(jìn)展的基礎(chǔ)上引入分布式概念格模型，提出了分布式序列挖掘算法PAHDP。通過(guò)在分布式系統(tǒng)上構(gòu)建算法原型，并加以評(píng)估，本文證明了該算法的正確性和有效性，具有一定的應(yīng)用價(jià)值。

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

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

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

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

　　1.1 AprioriAll算法

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

　　1.2 算法概述

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

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

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

　　2 實(shí)驗(yàn)評(píng)測(cè)

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

　　圖1 實(shí)驗(yàn)結(jié)果

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

　　3 結(jié)束語(yǔ)

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

　　參考文獻(xiàn)：

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

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

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

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

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

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

轉(zhuǎn)載請(qǐng)注明來(lái)自：http://www.jinnzone.com/jisuanjiyingyonglw/51136.html