云環(huán)境下基于二進(jìn)制編碼的Apriori改進(jìn)算法

(鄭州華信學(xué)院，河南 新鄭 451100)

Apriori算法[1]改進(jìn)一直是數(shù)據(jù)挖掘的一個(gè)重要研究方向，近年來(lái)，許多學(xué)者相繼提出了基于向量積[2]、布爾向量[3]、最大頻繁項(xiàng)集[4]等方法的改進(jìn)算法。但是，面對(duì)海量數(shù)據(jù)時(shí)，這些算法就需要大量時(shí)間來(lái)掃描數(shù)據(jù)庫(kù)，不利于頻繁項(xiàng)集的快速尋找。本文將在云計(jì)算環(huán)境中，將Apriori算法與MapReduce模型結(jié)合，對(duì)海量數(shù)據(jù)進(jìn)行分布式并行處理，最終產(chǎn)生符合要求的頻繁項(xiàng)集，從而提高了數(shù)據(jù)挖掘效率[5-9]。

1 相關(guān)知識(shí)

1.1 Apriori算法

Apriori算法通過多次掃描事務(wù)數(shù)據(jù)庫(kù)來(lái)計(jì)算各項(xiàng)集的支持度，利用候選項(xiàng)集來(lái)尋找n項(xiàng)頻繁項(xiàng)集。該算法具有以下性質(zhì)：

性質(zhì)1 若L為頻繁項(xiàng)集，則L的任何非空子集均為頻繁項(xiàng)集[4]。

性質(zhì)2 若L為非頻繁項(xiàng)集，則L的任何超集均為非頻繁項(xiàng)集[4]。

1.2 冪集與二進(jìn)制編碼

定義1 對(duì)任意集合A={I1,I2,…,In}，將A中所有子集的全體稱為A的冪集，將A的冪集中所有元素個(gè)數(shù)為k的子集的全體稱為A的k-冪集。

例如，對(duì)于集合A={I1,I2,I3}，則A的冪集為{Φ,{I1},{I2},{I3},{I1,I2},{I1,I3},{I2,I3},{I1,I2,I3}}，A的冪集中元素個(gè)數(shù)為2的子集為{I1,I2}，{I1,I3}，{I2,I3}，則其2-冪集可表示為{{I1,I2},{I1,I3},{I2,I3}}。

為了算法需要，后面約定冪集中不含空集。結(jié)合已有的二進(jìn)制編碼方法[10]，下面給出本文的二進(jìn)制編碼定義。

定義2 對(duì)任意集合A={I1,I2,…,In}，P?A，規(guī)定P的二進(jìn)制編碼為n位，且若Ii∈P，則編碼的第i位用1表示，否則用0表示。

例如，對(duì)于集合A={I1,I2,I3}，若P={I1,I3}，則其二進(jìn)制編碼為101。

1.3 MapReduce模型

MapReduce模型是Google公司提出的、用于并行處理海量數(shù)據(jù)集的編程模型。該編程模型將待處理的事務(wù)數(shù)據(jù)庫(kù)分割成若干子數(shù)據(jù)庫(kù)，并分配給不同的節(jié)點(diǎn)進(jìn)行處理。在每個(gè)節(jié)點(diǎn)中，該模型對(duì)接受到的數(shù)據(jù)進(jìn)行解析，并以鍵值對(duì)的形式表示數(shù)據(jù)，利用Map函數(shù)對(duì)這些鍵值對(duì)進(jìn)行處理，產(chǎn)生待合并的中間結(jié)果，再利用Reduce函數(shù)合并相同性質(zhì)的中間結(jié)果，最終形成符合要求的結(jié)果。

2 云環(huán)境下基于二進(jìn)制編碼的Apriori改進(jìn)算法

為了更好地處理海量數(shù)據(jù)，本文首先改造Map和Reduce函數(shù)，并對(duì)事務(wù)數(shù)據(jù)庫(kù)進(jìn)行處理，產(chǎn)生符合要求的結(jié)果，然后在云環(huán)境下將二進(jìn)制編碼思想應(yīng)用于Apriori算法改進(jìn)中，最終實(shí)現(xiàn)快速高效地尋找頻繁項(xiàng)集的目的。

2.1 Map函數(shù)和Reduce函數(shù)的改造

2.1.1 Map函數(shù)的改造

輸入：某個(gè)事務(wù)標(biāo)識(shí)符First_key，該事務(wù)中項(xiàng)集的二進(jìn)制編碼First_value。

輸出：，，…， // First_value1～ First_valuen為該事務(wù)中項(xiàng)集的k-冪集的二進(jìn)制編碼。

fori=1 ton

{

getisubset;//獲取該事務(wù)中項(xiàng)集的k-冪集的第i個(gè)子集

get a binary encoding of this subset as First_valuei;//該子集用二進(jìn)制編碼First_valuei表示

output();//第i個(gè)子集的輸出形式為

2.1.2 Reduce函數(shù)的改造

輸入：某事務(wù)的k-冪集的//First_valuei中“1”的個(gè)數(shù)為k。

輸出：//di用來(lái)記錄該事務(wù)中所有值為First_valuei的中間結(jié)果個(gè)數(shù)。

intdi=1

forj=1 tom//m為所有中間結(jié)果個(gè)數(shù)

{if(First_valueiΛFirst_valuej==k)di=di+1;//通過“與”運(yùn)算，尋找計(jì)算結(jié)果為k的中間結(jié)果，并用變量di記錄}

output()//合并后的輸出形式為

2.2 云環(huán)境下基于二進(jìn)制編碼的Apriori改進(jìn)算法

為了更加高效地尋找頻繁項(xiàng)集，本文將運(yùn)用MapReduce模型對(duì)Apriori算法加以改進(jìn)，具體算法可描述為：

Step1 將事務(wù)數(shù)據(jù)庫(kù)D分解為大小相等或接近相等的子數(shù)據(jù)庫(kù)，并分配給不同的節(jié)點(diǎn)；

Step2 對(duì)于每個(gè)節(jié)點(diǎn)，使用Map函數(shù)將事務(wù)的項(xiàng)集映射成k-冪集的對(duì)，產(chǎn)生該節(jié)點(diǎn)的候選k-項(xiàng)集；

Step3 對(duì)于所有節(jié)點(diǎn)，使用Reduce函數(shù)將候選k-項(xiàng)集合并，形成候選頻繁k-項(xiàng)集，并將其支持度與最小支持度min_support進(jìn)行比較，確定頻繁k-項(xiàng)集。

通過上述算法改進(jìn)，在尋找頻繁項(xiàng)集時(shí)，通過分解事務(wù)數(shù)據(jù)庫(kù)，利用Map函數(shù)和Reduce函數(shù)實(shí)現(xiàn)了數(shù)據(jù)的并行分布處理，大大提高了算法的效率。

3 實(shí)例分析

以事務(wù)數(shù)據(jù)庫(kù)D=(TID, Itemset)為例 (如表1所示)，利用云環(huán)境下基于二進(jìn)制編碼的Apriori改進(jìn)算法來(lái)尋找頻繁2-項(xiàng)集[1]。在表1中，TID是事務(wù)標(biāo)識(shí)符，Itemset是事務(wù)中的項(xiàng)集，設(shè)最小支持度min_support為2。由文獻(xiàn)[1]可知，頻繁1-項(xiàng)集為{I1，I2，I3，I4，I5}。

表1 事務(wù)數(shù)據(jù)庫(kù)D

(1)將事務(wù)數(shù)據(jù)庫(kù)D分解為3個(gè)子數(shù)據(jù)庫(kù)D1、D2、D3，其中D1為{{101，{I1，I2，I5}}，{102，{I2，I4}}，{103，{I2，I3}}}，D2為{{104，{I1，I2，I4}}，{105，{I1，I3}}，{106，{I2，I3}}}，D3為{{107，{I1，I3}}，{108，{I1，I2，I3，I5}}，{109，{I1，I2，I3}}}，并將子數(shù)據(jù)庫(kù)D1、D2、D3分別發(fā)送到節(jié)點(diǎn)R1、R2、R3(這3個(gè)節(jié)點(diǎn)主要用來(lái)并發(fā)處理3個(gè)子數(shù)據(jù)庫(kù)的數(shù)據(jù))。

在每個(gè)節(jié)點(diǎn)中，將子數(shù)據(jù)庫(kù)的數(shù)據(jù)解析成形如的鍵值對(duì)，其中：

節(jié)點(diǎn)R1的鍵值對(duì)為：<101，{I1，I2，I5}>、<102，{I2，I4}>、<103，{I2，I3}>;

節(jié)點(diǎn)R2的鍵值對(duì)為：<104，{I1，I2，I4}>、<105，{I1，I3}>、<106，{I2，I3}>;

節(jié)點(diǎn)R3的鍵值對(duì)為<107，{I1，I3}>、<108、{I1，I2，I3，I5}>、<109，{I1，I2，I3}>。

(2)對(duì)不同的節(jié)點(diǎn)，使用Map函數(shù)將事務(wù)的項(xiàng)集映射成2-冪集的二進(jìn)制編碼形式。

在節(jié)點(diǎn)R1中，利用經(jīng)過改造的Map函數(shù)對(duì)3個(gè)事務(wù)101～103中的項(xiàng)集進(jìn)行處理，產(chǎn)生形如的中間結(jié)果：

Map(<101，{I1，I2，I5}>)={<11000，1>，<10001，1>，<01001，1>}；

Map(<102，{I2，I4}>)={<01010，1>}；

Map(<103，{I2，I3}>)={<01100，1>}。

在節(jié)點(diǎn)R2中，利用經(jīng)過改造的Map函數(shù)對(duì)3個(gè)事務(wù)104～106中的項(xiàng)集進(jìn)行處理，產(chǎn)生形如的中間結(jié)果：

Map(<104，{I1，I2，I4}>)={<11000，1>，<10010，1>，<01010，1>}；

Map(<105，{I1，I3}>)={<10100，1>}；

Map(<106，{I2，I3}>)={<01100，1>}。

在節(jié)點(diǎn)R3中，利用經(jīng)過改造的Map函數(shù)對(duì)3個(gè)事務(wù)107～109中的項(xiàng)集進(jìn)行處理，產(chǎn)生形如的中間結(jié)果。

Map(<107，{I1，I3}>)={<10100，1>}；

Map(<108，{I1，I2，I3，I5}>)={<11000，1>，<10100，1>，<10001，1>，<01100，1>，<01001，1>，<00101，1>}；

Map(<109，{I1，I2，I3}>)={<11000，1>，<10100，1>，<01100，1>}。

(3)對(duì)于3個(gè)節(jié)點(diǎn)R1、R2、R3，使用Reduce函數(shù)將First_value值相同的中間結(jié)果進(jìn)行合并，形成形如的候選頻繁2-項(xiàng)集[10]：

Reduce(<11000，1>)=<11000，4>；

Reduce(<10001，1>)=<10001，2>；

Reduce(<01001，1>)=<01001，2>；

Reduce(<01010，1>)=<01010，2>；

Reduce(<01100，1>)=<01100，3>；

Reduce(<10010，1>)=<10010，1>；

Reduce(<10100，1>)=<10100，3>；

Reduce(<00101，1>)=<00101，1>。

再將候選頻繁2-項(xiàng)集的支持度d和最小支持度min_support=2進(jìn)行比較，得到頻繁2-項(xiàng)集為：

{<11000，4>，<10001，2>，<01001，2>，<01010，2>，<01100，3>，<10100，3>}。

最后，將頻繁2-項(xiàng)集的二進(jìn)制形式轉(zhuǎn)換為項(xiàng)集形式，可得：

{{I1，I2}，{I1，I5}，{I2，I5}，{I2，I4}，{I2，I3}，{I1，I3}}。

同樣地，當(dāng)k為其他值時(shí)，也可按此過程求頻繁k-項(xiàng)集。

4 結(jié) 語(yǔ)

通過分析Apriori算法的不足，本文引入MapReduce模型，改造了Map和Reduce函數(shù)，結(jié)合冪集的二進(jìn)制編碼方法，提出了云環(huán)境下基于二進(jìn)制編碼的Apriori改進(jìn)算法，一定程度上提高了海量數(shù)據(jù)的頻繁項(xiàng)集挖掘效率，為關(guān)聯(lián)規(guī)則挖掘提供了新的研究方向。

參考文獻(xiàn)：

[1] Han Jiawei, Micheline Kanber.數(shù)據(jù)挖掘概念與技術(shù)[M].范明,孟小峰,譯.北京:機(jī)械工業(yè)出版社,2001.

[2] 劉以安,羊斌.關(guān)聯(lián)規(guī)則挖掘中對(duì)Aprior算法的一種改進(jìn)研究[J].計(jì)算機(jī)應(yīng)用,2007,27(2): 418-420.

[3] 李志林,戴娟,劉以安.基于布爾向量運(yùn)算的Apriori算法[J].江南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2010,9(3):270-273.

[4] 吉根林,楊明,宋余慶，等.最大頻繁項(xiàng)目集的快速更新[J].計(jì)算機(jī)學(xué)報(bào),2005,28(1): 128-135.

[5] 張圣.一種基于云計(jì)算的關(guān)聯(lián)規(guī)則Apriori算法[J].通信技術(shù),2011,44(6):141-143.

[6] 張愷,鄭晶.一種基于云計(jì)算的新的關(guān)聯(lián)規(guī)則Apriori算法[J].甘肅聯(lián)合大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,26(6):61-64.

[7] 吳琪.基于云計(jì)算的Apriori挖掘算法[J].計(jì)算機(jī)測(cè)量與控制,2012,20(6):1653-1655.

[8] 謝宗毅.關(guān)聯(lián)規(guī)則挖掘Apriori算法的研究與改進(jìn)[J].杭州電子科技大學(xué)學(xué)報(bào),2006, 26(3):78-82.

[9] 曾舸,劉先鋒.關(guān)聯(lián)規(guī)則挖掘中Apriori改進(jìn)算法的研究[J].計(jì)算機(jī)與現(xiàn)代化,2007(1):46-48.

[10] 葉曉波.一種基于二進(jìn)制編碼的頻繁項(xiàng)集查找算法[J].楚雄師范學(xué)院學(xué)報(bào),2009,24(3): 13-19.