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

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

1 相關知識

1.1 Apriori算法

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

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

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

1.2 冪集與二進制編碼

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

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

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

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

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

1.3 MapReduce模型

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

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

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

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

2.1.1 Map函數(shù)的改造

輸入：某個事務標識符First_key，該事務中項集的二進制編碼First_value。

輸出：，，…， // First_value1～ First_valuen為該事務中項集的k-冪集的二進制編碼。

fori=1 ton

{

getisubset;//獲取該事務中項集的k-冪集的第i個子集

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

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

2.1.2 Reduce函數(shù)的改造

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

輸出：//di用來記錄該事務中所有值為First_valuei的中間結果個數(shù)。

intdi=1

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

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

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

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

為了更加高效地尋找頻繁項集，本文將運用MapReduce模型對Apriori算法加以改進，具體算法可描述為：

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

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

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

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

3 實例分析

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

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

(1)將事務數(shù)據(jù)庫D分解為3個子數(shù)據(jù)庫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ù)庫D1、D2、D3分別發(fā)送到節(jié)點R1、R2、R3(這3個節(jié)點主要用來并發(fā)處理3個子數(shù)據(jù)庫的數(shù)據(jù))。

在每個節(jié)點中，將子數(shù)據(jù)庫的數(shù)據(jù)解析成形如的鍵值對，其中：

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

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

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

(2)對不同的節(jié)點，使用Map函數(shù)將事務的項集映射成2-冪集的二進制編碼形式。

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

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

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

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

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

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

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

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

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

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)對于3個節(jié)點R1、R2、R3，使用Reduce函數(shù)將First_value值相同的中間結果進行合并，形成形如的候選頻繁2-項集[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-項集的支持度d和最小支持度min_support=2進行比較，得到頻繁2-項集為：

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

最后，將頻繁2-項集的二進制形式轉換為項集形式，可得：

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

同樣地，當k為其他值時，也可按此過程求頻繁k-項集。

4 結 語

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

參考文獻：

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

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

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

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

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

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

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

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

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

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