基于二進(jìn)制編碼的Apriori增量更新算法研究

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

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

0 引 言

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

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

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

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

1 相關(guān)知識

1.1 Apriori算法

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

其主要有兩條基本性質(zhì)：

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

性質(zhì)2：非頻繁項集的超集一定是非頻繁項集。

1.2 CBE-Apriori算法

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

k

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

k

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

a

,

b

,

c

，事物數(shù)據(jù)庫有三項數(shù)據(jù)(

a

,

b

,

c

)，(

a

,

c

)，(

a

,

b

)。首先根據(jù)頻繁1-項集的個數(shù)對頻繁1-項集進(jìn)行二進(jìn)制編碼，

a

,

b

,

c

分別被編碼位100，010，001，即2，2，2。編碼后的二進(jìn)制數(shù)可能小于

n

，這是由于二進(jìn)制數(shù)前面部分位置若為0代表的項均不存在。然后根據(jù)頻繁1-項集的編碼結(jié)果對事務(wù)數(shù)據(jù)庫進(jìn)行編碼。可知數(shù)據(jù)庫事務(wù)的編碼對應(yīng)111，101，110。對于任意項集例如(

a

,

b

)的支持度計算被轉(zhuǎn)化為了二進(jìn)制的位與運算。若項集的二進(jìn)制編碼與事務(wù)數(shù)據(jù)庫的二進(jìn)制編碼位與的結(jié)果等于項集二進(jìn)制編碼其本身，則證明該項集為該條事務(wù)的子集，即支持度計數(shù)理應(yīng)加1。即若

a

&

b

=

a

，說明

a

是

b

的子集，若

a

&

b

!=

a

，則說明

a

不是

b

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

a

，

b

)的支持度應(yīng)為2。

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

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

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

(2)根據(jù)1-項集的編碼結(jié)果對事務(wù)數(shù)據(jù)庫進(jìn)行編碼。

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

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

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

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

重復(fù)步驟(5)～(6)，直到?jīng)]有新的頻繁項集產(chǎn)生。

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

O

(

k

log

k

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

O

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

2 CBEF-Apriori算法

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

k

次迭代過程中，候選項集的產(chǎn)生大大減少。

2.1 算法的定義和性質(zhì)

假設(shè)DB為原數(shù)據(jù)庫，

L

為原數(shù)據(jù)庫中頻繁項集的集合，

s

為人為設(shè)定的最小支持度閾值，

D

為原數(shù)據(jù)庫中的事務(wù)數(shù)。假定對于每個Item∈

L

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

d

是db中的事務(wù)數(shù)。對于相同的最小支持度

s

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

s

，即Item.support≥

s

*(

D

+

d

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

s

*(

D

+

d

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

L

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

s

*

d

時，不是原頻繁1-項集

L

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

k

-項集(其中

k

>1)。

性質(zhì)6：對于在原頻繁

k

-項集

L

中的

k

-項集{Item，…，Item}，當(dāng)且僅當(dāng){Item，…，Item}.support<

s

*(

D

+

d

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

k

-項集。性質(zhì)7：對于不在原頻繁

k

-項集

L

中的

k

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

s

*

d

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

k

-項集。

2.2 算法流程

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

C

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

L

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

C

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

C

且Item.support<

s

*

d

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

C

中所有在db數(shù)據(jù)庫支持度計數(shù)小于

s

*

d

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

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

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

C

時將排除原

L

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

C

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

C

，如果Item.support<

s

*

d

，則從

C

中刪除。

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

在

k

次迭代中，無需再對數(shù)據(jù)庫進(jìn)行掃描來連接和剪枝候選項集，而是通過二進(jìn)制運算來判斷項集是否為事務(wù)的子集。其偽代碼如下：輸入：增量數(shù)據(jù)db，原數(shù)據(jù)庫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-項集進(jìn)行第一次考驗

if

k

==2 then

C

={item∈(apriori-gen1(

L

-1)-

L

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

else

C

={item∈(apriori-gen2(

L

-1)-

L

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

k

項集進(jìn)行第一次考驗

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，內(nèi)存為16 GB DDR4，操作系統(tǒng)為Windows 10，選用Python 3.6作為開發(fā)語言。模擬實驗對Apriori算法、CBE-Apriori算法以及CBEF-Apriori算法進(jìn)行了對比分析。

3.2 數(shù)據(jù)集介紹

實驗采用的數(shù)據(jù)集為數(shù)據(jù)挖掘?qū)嶒炛谐Ｓ玫臄?shù)據(jù)集，即mushroom數(shù)據(jù)集和T10I4D100K，數(shù)據(jù)集信息如表2所示。mushroom數(shù)據(jù)集為稠密型數(shù)據(jù)，總共包含120種不同的屬性，任意一條事務(wù)的長度均為23，樣本總數(shù)則為8 124，總共包含120個項。T10I4D100K為模擬稀疏數(shù)據(jù)集，其中

T

表示事務(wù)平均長度，

I

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

D

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

表2 數(shù)據(jù)集簡介

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

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

3.3 實驗分析

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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