大數(shù)據(jù)下Apriori算法的改進(jìn)研究

謝胡林

（紹興職業(yè)技術(shù)學(xué)院，紹興312000）

0 引言

在數(shù)據(jù)挖掘領(lǐng)域中，關(guān)聯(lián)規(guī)則旨在找出數(shù)據(jù)集中項(xiàng)與項(xiàng)之間未知的關(guān)系，進(jìn)而可以從挖掘出的數(shù)據(jù)對(duì)象信息中得到我們需要的信息。Apriori算法可以利用它挖掘數(shù)據(jù)集中數(shù)據(jù)項(xiàng)間的潛在關(guān)系。

Apriori算法其核心思想是通過候選集生成和情節(jié)的向下封閉檢測(cè)兩個(gè)階段來挖掘頻繁項(xiàng)集，而且算法已經(jīng)被廣泛的應(yīng)用到商業(yè)、網(wǎng)絡(luò)安全等各個(gè)領(lǐng)域。典型的例子有沃爾瑪超市的尿布與啤酒、超市的牛奶與面包、百度文庫推薦相關(guān)文檔、淘寶推薦相關(guān)書籍等，這些都是商務(wù)智能和關(guān)聯(lián)規(guī)則在實(shí)際生活中的運(yùn)用。

但是Apriori算法缺點(diǎn)很明顯，使用該算法的時(shí)候需要多次對(duì)數(shù)據(jù)庫進(jìn)行掃描，這樣會(huì)增加算法花費(fèi)在讀寫操作上的時(shí)間，導(dǎo)致挖掘算法的時(shí)間成本上升，這種成本是隨著數(shù)據(jù)庫存儲(chǔ)數(shù)據(jù)的增加而呈幾何級(jí)數(shù)上升的；其次，使用該算法則會(huì)產(chǎn)生大量的候選頻繁集，每一步產(chǎn)生的候選頻繁集有時(shí)候是非常巨大的，導(dǎo)致算法在廣度和深度上的適應(yīng)性很差。

Apriori算法是最經(jīng)典、最具影響力的挖掘頻繁項(xiàng)目集的算法，該算法在關(guān)聯(lián)規(guī)則研究中具有里程碑作用，但是在實(shí)際應(yīng)用過程中，Apriori算法有兩個(gè)致命的性能瓶頸：其一是多次掃描事物數(shù)據(jù)庫，需要更大的I/O負(fù)載，其二是可能產(chǎn)生龐大的候選集，許多專家學(xué)者提出了一些基于Apriori算法的改進(jìn)算法以提高Apriori算法的效率，如散列（Hash）技術(shù)、劃分（Partition）技術(shù)、采樣（Sampling）方法等。但是這些改進(jìn)的算法又或多或少的存在一些問題，如采樣方法，它最大的問題就是如何選取樣本數(shù)據(jù)，即便選取了樣本數(shù)據(jù)且提高了算法的效率卻降低了算法的精度。

本文以Apriori算法分析為依托，改進(jìn)算法的四個(gè)方面，從而有效地提升算法的挖掘性能，將高職院校就業(yè)情況當(dāng)成是研究對(duì)象，在比較后其挖掘成效突出。

1 Apriori算法的優(yōu)化

1.1 增加數(shù)據(jù)庫

文中以Apriori算法為依托，結(jié)合形成的頻繁項(xiàng)集Lk-1(k=1,2,…k-1)將數(shù)據(jù)庫Dk加入進(jìn)來，在Dk里將k-頻繁項(xiàng)集和它的事務(wù)集合進(jìn)行保存，假設(shè)事務(wù)集合是Ei，Ei={t1,t2,…，tm,…，tq}，所以，Lk-1在自連接時(shí)使得k-候選項(xiàng)集Ck得以形成，計(jì)算Ck的支持度的過程中，不必掃描原始數(shù)據(jù)，僅對(duì)Ck子集事務(wù)Ei進(jìn)行掃描即可，之后將不同子集事務(wù)Ei的交集計(jì)算出來，在上述集合中事務(wù)的數(shù)量，也就是這一候選項(xiàng)集的支持?jǐn)?shù)，之后刪除低于支持度的一些候選項(xiàng)集，從而可以使訪問效率提升，這一算法優(yōu)化后的偽碼見下。

輸入：原始數(shù)據(jù)庫將m個(gè)事務(wù)包括在內(nèi)

輸出：D里涉及的頻繁項(xiàng)集

1.2 挖掘頻繁1-項(xiàng)集

首先，分類數(shù)據(jù)塊。把數(shù)據(jù)庫結(jié)合相應(yīng)的規(guī)定進(jìn)行劃分，使其數(shù)據(jù)塊大小一致，向計(jì)算節(jié)點(diǎn)進(jìn)行傳送，將Map模型有效地執(zhí)行。

其次，初始化數(shù)據(jù)化。在不同計(jì)算節(jié)點(diǎn)里把全部數(shù)據(jù)向這樣的健值對(duì)形式進(jìn)行轉(zhuǎn)化，在這之中，item代表的是不同事務(wù)項(xiàng)目，Tid代表的是標(biāo)識(shí)符。

之后，Map函數(shù)。局部掃描其中的健值，再將健值對(duì)計(jì)算出來，在這之中，sum代表的是支持度計(jì)數(shù)。

再次，Reduce函數(shù)。將Map函數(shù)的輸出結(jié)果進(jìn)行接收，同時(shí)進(jìn)行合并，使局部候選1-項(xiàng)集得以形成，這樣能夠使全局候選集得以形成。

最后，結(jié)合支持度，使頻繁1項(xiàng)集L1得以形成。倘若L1不成功，那么算法結(jié)束。這一算法優(yōu)化后的偽碼見下。

1.3 挖掘頻繁2-項(xiàng)集

首先，將數(shù)據(jù)塊以及頻繁1項(xiàng)集L1輸入。初始化數(shù)據(jù)塊。在不同計(jì)算節(jié)點(diǎn)，把數(shù)據(jù)向對(duì)進(jìn)行轉(zhuǎn)化，它的形式是。

之后連接。通過不同節(jié)點(diǎn)中的L1使C2得以形成。

接著使用Map函數(shù)局部掃描數(shù)據(jù)庫，從而將C2的sum進(jìn)行獲取。之后Reduce函數(shù)。自獲取Map函數(shù)的輸出結(jié)果，將其與局部候選2項(xiàng)集重組，這樣使得全局候選2項(xiàng)集得以形成。

最后，生成結(jié)果。自既定的最小支持度，使頻繁2項(xiàng)集L2得以形成，倘若生成不成功，那么把L1當(dāng)成是結(jié)果輸出，算法完成。這一算法優(yōu)化后的偽碼見下。

1.4 加入動(dòng)態(tài)存儲(chǔ)空間

通過Apriori算法可以看出，全部的2-頻繁項(xiàng)集中全部元素均以1-頻繁項(xiàng)集密切相關(guān)，相同地，超出2的頻繁項(xiàng)集里，全部元素均與2-頻繁項(xiàng)集密切相關(guān)，結(jié)合這一現(xiàn)象，文中將動(dòng)態(tài)存儲(chǔ)空間進(jìn)行應(yīng)用，對(duì)這一算法進(jìn)行優(yōu)化，從而快速提取數(shù)據(jù)庫。

建立以(k-1)-頻項(xiàng)集為依托的動(dòng)態(tài)存儲(chǔ)空間，以這一算法為基礎(chǔ)，使k-頻繁項(xiàng)集形成，在(k>2)過程中，以(k-1)-頻項(xiàng)集為依托，將鏈掊作進(jìn)行實(shí)施，使k-頻繁集的提取速度提升，這樣能夠使掃描次數(shù)下降，使運(yùn)算速度提升。

2 實(shí)驗(yàn)仿真

想要使算法的挖掘成果體現(xiàn)出來，將以Hadoop為基礎(chǔ)的大數(shù)據(jù)平臺(tái)進(jìn)行應(yīng)用，將Linux系統(tǒng)廣泛推廣，以Vmware虛擬機(jī)為依托，對(duì)其進(jìn)行建立，軟件方面將64位Windows系統(tǒng)應(yīng)用，硬件方面將酷睿i5作為CPU，6G內(nèi)存，將主節(jié)點(diǎn)1個(gè)，從節(jié)點(diǎn)2個(gè)進(jìn)行建立，將不同數(shù)據(jù)容量進(jìn)行設(shè)置，將與學(xué)生就業(yè)評(píng)價(jià)相關(guān)的數(shù)據(jù)記錄進(jìn)行選取，共計(jì)一千條。把評(píng)價(jià)質(zhì)量項(xiàng)目進(jìn)行劃分，共六個(gè)方面，企業(yè)對(duì)學(xué)生的技術(shù)能力、社會(huì)能力、工作能力以及自主能力等進(jìn)行評(píng)價(jià)。

表1 數(shù)據(jù)集屬性

所以，對(duì)輸入項(xiàng)目來說，其數(shù)量是5個(gè)，最小支持度是1，挖掘分析數(shù)據(jù)中的六個(gè)方面內(nèi)容，其項(xiàng)目集是Item={{I1},{I2},{I3},{I4},{I5},{I6}}，使得數(shù)據(jù)表得以形成，具體見表2-表3。

通過圖1可以看出，這一算法評(píng)價(jià)指標(biāo)具體的成效，同時(shí)能夠看出，在不同記錄的情況下，這一指標(biāo)的結(jié)果是有著很大的不同之處的，從某種程度來看，這意味著這一就業(yè)評(píng)價(jià)指標(biāo)是十分典型的。通過圖可以看出，這一算法和以SVM為依托的樣本分類進(jìn)行比較，其成效是不同的。可以看出，這一算法的樣本分類，與SVM分類進(jìn)行比較，前者要好一些，這是由于將數(shù)據(jù)庫加入進(jìn)來，同時(shí)將頻繁1-項(xiàng)集進(jìn)行優(yōu)化，將頻繁2-項(xiàng)集進(jìn)行優(yōu)化，同時(shí)將動(dòng)態(tài)存儲(chǔ)空間加入進(jìn)來，從而使得Apriori算法的性能發(fā)生了很大的變化，從而有效地提升了這一算法的挖掘成效。

表2 數(shù)據(jù)項(xiàng)對(duì)應(yīng)集

表3 候選集集合

圖1 算法評(píng)價(jià)成效

3 結(jié)語

本文結(jié)合Apriori算法自身的問題，有效地優(yōu)化Apriori算法，優(yōu)化的這一算法，其性能發(fā)生了很大的改變，在評(píng)價(jià)分析高職院校就業(yè)指導(dǎo)后，得出結(jié)論這一算法的挖掘成效是十分顯著的。