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

1、基于MapReduce和AprioriAll的分布式序列挖掘算法摘 要：序列挖掘技術(shù)，可以從大量雜亂的數(shù)據(jù)中挖掘出用戶的潛在訪問(wèn)形式。然而，傳統(tǒng)的挖掘技術(shù)，由于其性能和擴(kuò)展性的諸多限制，并不適宜現(xiàn)今大數(shù)據(jù)下的挖掘任務(wù)。本文基于傳統(tǒng)的挖掘算法AprioriAll，在結(jié)合國(guó)內(nèi)外研究進(jìn)展的根底上引入分布式概念格模型，提出了分布式序列挖掘算法PAHDP。通過(guò)在分布式系統(tǒng)上構(gòu)建算法原型，并加以評(píng)估，本文證明了該算法的正確性和有效性，具有一定的應(yīng)用價(jià)值。關(guān)鍵詞：數(shù)據(jù)挖掘；分布式計(jì)算；概念格；Hadoop中圖分類號(hào)：TP311分布式計(jì)算的思想，可以將僅僅由單個(gè)計(jì)算機(jī)難以計(jì)算和維護(hù)的計(jì)算任務(wù)分為很多小的、互相

2、獨(dú)立的部分，然后把這些局部分配給很多臺(tái)計(jì)算機(jī)進(jìn)展處理。在這個(gè)根底上，利用分布式系統(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é)果綜合。本文在此根底上，對(duì)傳統(tǒng)的數(shù)據(jù)挖掘算法AprioriAll進(jìn)展了分布式探究，并針對(duì)影響性能的多個(gè)因素進(jìn)展了分析與改良。1 基于AprioriAll的分布式挖掘算法設(shè)計(jì)與實(shí)現(xiàn)1.1 AprioriA

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

4、HDP算法進(jìn)展了比擬購(gòu)置商品數(shù)目分別固定為8與2.5。結(jié)果如以下列圖所示：圖1 實(shí)驗(yàn)結(jié)果通過(guò)比照那么隨之從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%。從比照實(shí)驗(yàn)可以看出，傳統(tǒng)的AprioriAll算法在顧客數(shù)目小于商品數(shù)目的時(shí)候，其計(jì)算時(shí)間的增長(zhǎng)比顧客數(shù)目大于商品數(shù)目的情況下更為緩慢，因此該算法對(duì)于數(shù)據(jù)的內(nèi)在構(gòu)造是敏感的。而對(duì)于PAHDP算法來(lái)說(shuō)，那么在三種情況下的運(yùn)行速度差異不大，因此其對(duì)于數(shù)據(jù)是不敏感的。3 完畢語(yǔ)本文深化分析了AprioriAll算法的實(shí)現(xiàn)流程和相關(guā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)：2呂峰等.4種序列形式挖掘算法的特性研究J.武漢理工大學(xué)學(xué)報(bào)，2022，282：57-603周嘉偉等.新多維序列挖掘算法：對(duì)Apriori