基于二進制編碼的Apriori增量更新算法研究

羅章銘，唐 杰，黃逸奇，張 錦

(湖南師范大學 信息科學與工程學院，湖南 長沙 410006)

0 引 言

數據挖掘是從有噪音的、不完整的、不清晰的、隨機的數據中提取出有效的、潛在的、有用的知識，在人工智能、醫(yī)學、電子商務、工業(yè)等各領域得到廣泛應用。關聯規(guī)則是目前最為常用，應用領域最為廣泛的數據挖掘技術。作為挖掘重要關聯知識與規(guī)則的分析手段，關聯規(guī)則用于發(fā)現存在于數據庫中的海量數據之間的關聯性，而這些關聯性或許能滿足人們對其中一些屬性同時出現在一個事務上的規(guī)律和方式的探尋，以提升經濟、管理等方面的效益。

Agrawal等在1994年通過候選項集的連接和剪枝得到頻繁項集，首次提出了關聯規(guī)則中最經典也是使用最為頻繁的Apriori算法，2000年Han等在此基礎上提出了頻繁模式增長算法，即FP-growth算法。近三十年來關于關聯規(guī)則的改進算法層出不窮，主要工作集中在解決關聯規(guī)則算法多次迭代中頻繁掃描數據庫這一問題。程遠對剪枝連接函數Apriori_Gen進行優(yōu)化；劉智提出V-Apriori算法，即單次掃描數據庫后，事務數據庫被轉換為布爾矩陣，將事務數據庫的掃描轉化為向量運算等，通過類似的優(yōu)化手段改進Apriori算法。改進后的關聯規(guī)則可以用于醫(yī)療領域中的病癥規(guī)律研究、消費領域的經濟發(fā)展研究、教育信息化研究等。然而實際應用時，數據庫經常處于不斷變化狀態(tài)，數據經常性增加或更新，因此關聯規(guī)則發(fā)現的規(guī)則具有時效性，僅反映數據庫某一時刻的狀態(tài)。為了使發(fā)現的規(guī)則穩(wěn)定可靠，應在相當長的一段時間內收集大量數據。如果要更新規(guī)則，就不得不重新使用算法對數據庫進行挖掘，這樣做除了效率低下，還浪費了大量已經挖掘出的信息資源。

在此背景下，對于動態(tài)數據的增量式關聯規(guī)則挖掘成為新的研究方向，力圖發(fā)現快速地更新已有規(guī)則的算法。在這一研究方向上，Cheung等首次提出了增量更新算法(incremental updating，IU)，通過對增量數據庫與原數據庫歷史結果的關系進行處理，提出了在數據增加這一情況下的關聯規(guī)則增量算法(stands for fast update，FUP)。該算法對歷史頻繁項集以及新產生的候選項集進行篩選來得到新的頻繁項集。該算法計算支持度的方式仍然沿用Apriori算法的思想，需要多次掃描數據庫。陳勁松等對小增量下的情況進行了研究。李寶東等和黃德才等則是著重對數據集的掃描次數減少問題進行優(yōu)化，以此提高算法的效率。Hong等將增量更新算法思想應用到FP-growth算法中。王誠等與朱曉峰等則對算法進行了并行化改進，以此來提高數據處理效率。

該文從項集支持度的計算過程入手，通過二進制編碼位運算在項集支持度計算方面的優(yōu)勢，減少增量更新算法掃描數據庫的次數和時間資源消耗，通過模擬實驗對比分析了不同算法的性能，驗證了所提出算法的有效性。

1 相關知識

1.1 Apriori算法

關聯規(guī)則有多種算法，但大部分都是基于經典Apriori的改進算法。根據支持度閾值設置的不同，挖掘結果也會有所不同。首先需要說明以下概念，包含某項集的事務數在整個數據庫中的比例稱為該項集的支持度，包含的意思指的就是事務的子集是該項集。最小支持度指的就是人為根據經驗設置的最小支持度閾值。從關聯規(guī)則誕生以來，最基本也是使用率最高的算法就是Apriori算法。

其主要有兩條基本性質：

性質1：頻繁項目集的所有非空子集也是頻繁項目集。

性質2：非頻繁項集的超集一定是非頻繁項集。

1.2 CBE-Apriori算法

Apriori算法的痛點在于每一次迭代中生成頻繁

k

-項集時都需要對數據庫進行一次掃描，用以對項集支持度進行計數，直接影響了算法的運行效率。在進行連接操作時，還需判斷項集得前(

k

-1)項是否相等?；谏鲜鯝priori算法存在的問題，近年來研究者從許多方面對此算法進行改進，包括矩陣化處理，引入并行機制等等。而胡世昌、谷鵬分別提出了BE-Apriori(binary encode，BE)和CBE-Apriori (compressed binary encode，CBE)算法，通過對項集和事務二進制編碼進行位運算，將掃描數據庫的過程轉化為內存中的位運算。與經典Apriori需要重復掃描數據庫來計算項集的支持度不同，現假設某數據庫有頻繁1-項集

a

,

b

,

c

，事物數據庫有三項數據(

a

,

b

,

c

)，(

a

,

c

)，(

a

,

b

)。首先根據頻繁1-項集的個數對頻繁1-項集進行二進制編碼，

a

,

b

,

c

分別被編碼位100，010，001，即2，2，2。編碼后的二進制數可能小于

n

，這是由于二進制數前面部分位置若為0代表的項均不存在。然后根據頻繁1-項集的編碼結果對事務數據庫進行編碼?？芍獢祿焓聞盏木幋a對應111，101，110。對于任意項集例如(

a

,

b

)的支持度計算被轉化為了二進制的位與運算。若項集的二進制編碼與事務數據庫的二進制編碼位與的結果等于項集二進制編碼其本身，則證明該項集為該條事務的子集，即支持度計數理應加1。即若

a

&

b

=

a

，說明

a

是

b

的子集，若

a

&

b

!=

a

，則說明

a

不是

b

的子集。如表1所示，上述例子中2-項集(

a

，

b

)的支持度應為2。

表1 CBE-Apriori算法的支持度計算過程

CBE-Apriori算法的主要流程如下：

(1)掃描數據庫獲取頻繁1-項集，對其進行二進制編碼。

(2)根據1-項集的編碼結果對事務數據庫進行編碼。

(3)頻繁1-項集自連接產生候選2-項集。

(4)通過位運算計算支持度，得到頻繁2-項集。

(5)若每一項頻繁2-項集相異或，結果仍是頻繁項集，則求得這兩項頻繁2-項集的并集作為候選3-項集。

(6)通過位運算計算支持度，得到頻繁3-項集。

重復步驟(5)～(6)，直到沒有新的頻繁項集產生。

BE-Apriori、CBE-Apriori算法的優(yōu)勢在于只需掃描兩次數據庫，即可得到全部頻繁項集。原Apriori算法連接和剪枝操作的時間復雜度為

O

(

k

log

k

)。而改進后算法通過編碼后兩個頻繁項集異或結果是否為頻繁2-項集，就可以完成連接和剪枝操作，時間復雜度為

O

(1)，常數時間即可完成。正是因為二進制的基本運算代替了集合之間的運算，因此可以有效提高算法執(zhí)行效率。

2 CBEF-Apriori算法

基于已有研究，該文提出了基于二進制編碼的Apriori增量更新算法CBEF-Apriori(compressed binary encode fast update Apriori)。該算法吸收了二進制編碼算法的優(yōu)點，即只需要通過兩次對數據庫的遍歷，第一次遍歷的目的是為了獲取頻繁1-項集，第二次遍歷則是根據頻繁1-項集的結果對數據庫進行二進制編碼，將結果存入內存中，在內存中計算代替之后的“逐層搜索”過程，能有效避免I/O效率低下的時間消耗。結合算法性質，其主要優(yōu)勢體現在：無需重新對新數據和舊數據一起進行挖掘，根據增量數據和上一次挖掘得到的結果，可以生成新的頻繁項集；在

k

次迭代過程中，候選項集的產生大大減少。

2.1 算法的定義和性質

假設DB為原數據庫，

L

為原數據庫中頻繁項集的集合，

s

為人為設定的最小支持度閾值，

D

為原數據庫中的事務數。假定對于每個Item∈

L

，其支持計數為Item.support(包含Item的原數據庫中的事務支持度)，新事務數據增量db添加到原始數據庫DB中，

d

是db中的事務數。對于相同的最小支持度

s

，如果DB∪db中Item的支持度不小于

s

，即Item.support≥

s

*(

D

+

d

)，則項集Item在更新的數據庫DB∪db中仍頻繁。下文中Item.support代表項集Item在DB∪db中的支持度，即全局支持度；Item.support代表項集Item在原數據庫DB中的支持度；Item.Support代表項集Item在增量數據庫db中的支持度。對于第一次迭代主要有兩條重要性質：性質3：當且僅當Item.Support<

s

*(

D

+

d

)時，原始的頻繁1-項集

L

中的項Item在更新后的數據庫DB∪db中成為失敗者(即不是新的頻繁1-項集)。性質4：僅當Item.Support>

s

*

d

時，不是原頻繁1-項集

L

中的項Item才可能成為更新數據庫DB∪db的贏家(即可能是新的頻繁1-項集)。下列性質則可用于得出更新數據庫后的頻繁

k

-項集(其中

k

>1)。

性質6：對于在原頻繁

k

-項集

L

中的

k

-項集{Item，…，Item}，當且僅當{Item，…，Item}.support<

s

*(

D

+

d

)時，在更新后的數據庫DB∪db中成為失敗者。即不可能是新的頻繁

k

-項集。性質7：對于不在原頻繁

k

-項集

L

中的

k

-項集{Item，…，Item}，只有在{Item，…，Item}.support≥

s

*

d

時，在更新后的數據庫DB∪db才有可能成為贏家，即可能是新的頻繁

k

-項集。

2.2 算法流程

(2)在同一掃描中，創(chuàng)建一個集合

C

，每個Item∈db但不在原頻繁1-項集

L

中的大小為1的項集被加入

C

。這些項成為候選1-項集，它們在db中的支持度可以在掃描中統(tǒng)計得到。更重要的是，根據性質2，如果Item∈

C

且Item.support<

s

*

d

，則Item在DB∪db中永遠不可能頻繁。因此，刪除

C

中所有在db數據庫支持度計數小于

s

*

d

的項。這樣在生成新的頻繁1-項集的過程中，減少了大量不可能在更新數據庫后成為頻繁1-項集的項。

圖1 CBEF-Apriori算法新1-項集生成流程

(2)與第一次迭代類似，此次迭代的第二部分是找到新頻繁2-項集。通過自連接創(chuàng)建

C

時將排除原

L

中的集合。通過二進制運算統(tǒng)計其支持計數來修剪

C

中的項目集。基于性質4，所有被篩除的集合在DB∪db中不可能頻繁。對于所有Item∈

C

，如果Item.support<

s

*

d

，則從

C

中刪除。

圖2 CBEF-Apriori算法新k-項集生成流程

在

k

次迭代中，無需再對數據庫進行掃描來連接和剪枝候選項集，而是通過二進制運算來判斷項集是否為事務的子集。其偽代碼如下：輸入：增量數據db，原數據庫DB，支持度minsup，原頻繁項集

L

,

L

,…,

L

(1)forall transactions

t

∈db do beginforall item∈

t

do begin

db_item.count ++

end

end

(2)forall

t

∈ DB and db do beginforall item∈

t

do begin

DB_and_db_item.count ++

end

end

(3)

C

={item∈db and ?DB|db_item.count≥minsup}//對候選1-項集進行第一次考驗

if

k

==2 then

C

={item∈(apriori-gen1(

L

-1)-

L

)|db_item.count≥minsup}//對候選-2項集進行第一次考驗

else

C

={item∈(apriori-gen2(

L

-1)-

L

-1) | db_item.count≥minsup}//對候選-

k

項集進行第一次考驗

end

(7)answer=∪

L

(8)apriori-gen-1//獲取候選2-項集

INSERT INTO

C

SELECT p.item,q.item

from Lp, Lq

(9)apriori-gen-2//獲取候選

k

-項集(

k

>2)INSERT INTO

C

SELECT p.item,p.item,...,p.item,q.item

from Lp, Lq

where p^q∈L

3 性能評估

3.1 實驗環(huán)境

實驗環(huán)境如下：處理器為3.0 GHz AMD Ryzen5 4600H，內存為16 GB DDR4，操作系統(tǒng)為Windows 10，選用Python 3.6作為開發(fā)語言。模擬實驗對Apriori算法、CBE-Apriori算法以及CBEF-Apriori算法進行了對比分析。

3.2 數據集介紹

實驗采用的數據集為數據挖掘實驗中常用的數據集，即mushroom數據集和T10I4D100K，數據集信息如表2所示。mushroom數據集為稠密型數據，總共包含120種不同的屬性，任意一條事務的長度均為23，樣本總數則為8 124，總共包含120個項。T10I4D100K為模擬稀疏數據集，其中

T

表示事務平均長度，

I

表示頻繁項集的平均長度，

D

表示數據集中的事務總數，意味著該數據集事務平均長度為10，頻繁項集的平均長度為4，事務總數為100 000條。

表2 數據集簡介

對于文中所考慮的增量更新問題，最為直接的辦法就是將Apriori算法與CBE算法重新運行一遍，與文中提出的增量更新算法CBEF進行性能比較。增量從原數據庫中隨機提取。

下文的實驗結果以5次取值的平均值的方式給出，減少實驗的偶然性。

3.3 實驗分析

(1)mushroom數據集。為驗證CBEF算法結果的有效性，實驗中分別比較了三種算法在不同支持度約束下生成的最終頻繁項集數目，如表3所示。從表3中可以看出，CBEF算法在結果上與其他兩種算法無異。

表3 不同增量與支持度下的頻繁選項集個數

圖3和圖4分別給出了在增量為1 125以及2 125時，三個算法各自的運行時間以及候選項集個數。CBEF算法生成的候選項集數均小于原Apriori算法以及CBE算法生成的候選項集數，算法運行時間也明顯少于其他兩種算法。在支持度接近0.5時，三個算法生成的候選項集個數十分接近，其主要原因是在0.5支持度下，篩除掉的必不可能成為頻繁項集的數目變得越來越少，因此候選項集的個數趨向于相等，耗費時間的優(yōu)勢變小?？傮w上，其運行效率與Apriori相比提升達到2.2至3.6倍，與CBE算法相比提升也有1.1至1.4倍。以上研究結果表明，在較小數據規(guī)模數據集上CBEF算法的時間效率較Apriori算法以及CBE算法是有明顯提升的。

圖3 1 125增量下算法時間消耗與候選項集生成數對比

圖4 2 125增量下算法時間消耗與候選項集生成數對比

(2)T10I4D100K數據集。為了探究該算法在較大數據集上的運行情況，使用IBM合成數據產生器生成的T10I4D100K數據集進行實驗分析。并分別提取出10%、40%、60%、80%作為增量數據條件下，模擬CBEF算法數據增量更新過程所需時間。

在表4中可以看出，CBE算法在較大數據量的數據集中已經不再適用。在大量數據集中使用CBE算法，會產生大量的候選項集以及事務的編碼數據，該過程產生的開銷已經超過了在每一次迭代中重新掃描數據庫計算最小支持度的開銷。

表4 不同增量與支持度下的運行時間 s

隨著支持度閾值的增大，各算法的運行時間大大減少。原因是符合條件的候選項集數量在閾值增大后減少，在逐層搜索的迭代過程中，產生的頻繁項集個數也大大減少，在某些參數下沒有迭代過程，只產生頻繁1-項集。

10%增量下與40%增量下的CBEF算法在運行效率上都有著顯著的提升，在10%增量下的提升尤為明顯。在最小支持度閾值設置為0.02，0.01，0.007 5時，算法相比Apriori算法分別有10.41倍，6.02倍，4.08倍提升，相比CBE算法分別有11.54倍，7.17倍，6.65倍提升。

通過分析，在10%增量下提升明顯的原因是，10%的增量對于原數據100 000條來說是較小的數據量，對關聯規(guī)則更新的影響程度也較小，例如在0.02的支持度參數下，頻繁1-項集只增加3項，且只有1次迭代過程，即只有頻繁1-項集的產生。因此產生的候選項集個數相比于重新計算過程大大減少，這正是增量更新算法最大的優(yōu)勢所在，即若增量數據對關聯規(guī)則產生的影響較小，此算法可以節(jié)約大量時間快速給出新的結果。而在60%增量下CBEF算法的優(yōu)勢已經不再明顯，雖然在0.01以上支持度上仍然優(yōu)于其他兩種算法，但是在0.007 5支持度閾值以及80%增量的條件下，由于候選項集的個數顯著增多，候選項集的編碼開銷基本已經超過了Apriori算法。

在數據集較大的情況下，由以上分析結果可以說明：(1)在數據增量較小時，CBEF算法相比于其他兩種算法有明顯的提升，這是因為較小的增量對于規(guī)則的影響不大，與增量前的數據結果出入較小，因此產生的開銷也小。CBEF算法在增量較小的情況下的規(guī)則更新效果優(yōu)勢明顯。(2)在增量到達一定規(guī)模時，例如上文的80%，此時運用增量更新的算法開銷已經接近或者大于使用Apriori或者CBE算法，可以考慮直接使用其他算法重新計算。

4 結束語

針對Apriori算法性能提升需求，通過二進制位運算過程計算項集支持度，結合增量更新思想，該文提出了一種基于二級制編碼的Apriori增量更新算法CBEF-Apriori。通過對算法的分析以及實驗證明，相比經典Apriori算法以及普通的二進制編碼算法CBE-Apriori，該算法不僅可以結合歷史的規(guī)則生成結果來更快地給出新的頻繁項集，并且在計算支持度以及篩除候選項集上都有著明顯的優(yōu)勢，解決了Apriori算法以及CBE算法各自的問題。后續(xù)可以考慮在最小支持度閾值更新的情況下，如何更快生成新的頻繁項集的情況。并且在較大規(guī)模較大增量的情況下通過多進程并行計算等提高算法效率。