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

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

0 引 言

數(shù)據(jù)挖掘是從有噪音的、不完整的、不清晰的、隨機(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)性或許能滿足人們對其中一些屬性同時(shí)出現(xiàn)在一個(gè)事務(wù)上的規(guī)律和方式的探尋，以提升經(jīng)濟(jì)、管理等方面的效益。

Agrawal等在1994年通過候選項(xiàng)集的連接和剪枝得到頻繁項(xiàng)集，首次提出了關(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ùn)算等，通過類似的優(yōu)化手段改進(jìn)Apriori算法。改進(jìn)后的關(guān)聯(lián)規(guī)則可以用于醫(yī)療領(lǐng)域中的病癥規(guī)律研究、消費(fèi)領(lǐng)域的經(jīng)濟(jì)發(fā)展研究、教育信息化研究等。然而實(shí)際應(yīng)用時(shí)，數(shù)據(jù)庫經(jīng)常處于不斷變化狀態(tài)，數(shù)據(jù)經(jīng)常性增加或更新，因此關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的規(guī)則具有時(shí)效性，僅反映數(shù)據(jù)庫某一時(shí)刻的狀態(tài)。為了使發(fā)現(xiàn)的規(guī)則穩(wěn)定可靠，應(yīng)在相當(dāng)長的一段時(shí)間內(nèi)收集大量數(shù)據(jù)。如果要更新規(guī)則，就不得不重新使用算法對數(shù)據(jù)庫進(jìn)行挖掘，這樣做除了效率低下，還浪費(fèi)了大量已經(jīng)挖掘出的信息資源。

在此背景下，對于動(dò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)。該算法對歷史頻繁項(xiàng)集以及新產(chǎn)生的候選項(xiàng)集進(jìn)行篩選來得到新的頻繁項(xiàng)集。該算法計(jì)算支持度的方式仍然沿用Apriori算法的思想，需要多次掃描數(shù)據(jù)庫。陳勁松等對小增量下的情況進(jìn)行了研究。李寶東等和黃德才等則是著重對數(shù)據(jù)集的掃描次數(shù)減少問題進(jìn)行優(yōu)化，以此提高算法的效率。Hong等將增量更新算法思想應(yīng)用到FP-growth算法中。王誠等與朱曉峰等則對算法進(jìn)行了并行化改進(jìn)，以此來提高數(shù)據(jù)處理效率。

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

1 相關(guān)知識

1.1 Apriori算法

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

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

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

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

1.2 CBE-Apriori算法

Apriori算法的痛點(diǎn)在于每一次迭代中生成頻繁

k

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

k

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

a

,

b

,

c

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

a

,

b

,

c

)，(

a

,

c

)，(

a

,

b

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

a

,

b

,

c

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

n

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

a

,

b

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

a

&

b

=

a

，說明

a

是

b

的子集，若

a

&

b

!=

a

，則說明

a

不是

b

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

a

，

b

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

表1 CBE-Apriori算法的支持度計(jì)算過程

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

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

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

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

(4)通過位運(yùn)算計(jì)算支持度，得到頻繁2-項(xiàng)集。

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

(6)通過位運(yùn)算計(jì)算支持度，得到頻繁3-項(xiàng)集。

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

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

O

(

k

log

k

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

O

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

2 CBEF-Apriori算法

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

k

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

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

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

L

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

s

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

D

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

L

，其支持計(jì)數(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

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

s

*(

D

+

d

)時(shí)，原始的頻繁1-項(xiàng)集

L

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

s

*

d

時(shí)，不是原頻繁1-項(xiàng)集

L

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

k

-項(xiàng)集(其中

k

>1)。

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

k

-項(xiàng)集

L

中的

k

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

s

*(

D

+

d

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

k

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

k

-項(xiàng)集

L

中的

k

-項(xiàng)集{Item，…，Item}，只有在{Item，…，Item}.support≥

s

*

d

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

k

-項(xiàng)集。

2.2 算法流程

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

C

，每個(gè)Item∈db但不在原頻繁1-項(xiàng)集

L

中的大小為1的項(xiàng)集被加入

C

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

C

且Item.support<

s

*

d

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

C

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

s

*

d

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

圖1 CBEF-Apriori算法新1-項(xiàng)集生成流程

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

C

時(shí)將排除原

L

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

C

中的項(xiàng)目集?；谛再|(zhì)4，所有被篩除的集合在DB∪db中不可能頻繁。對于所有Item∈

C

，如果Item.support<

s

*

d

，則從

C

中刪除。

圖2 CBEF-Apriori算法新k-項(xiàng)集生成流程

在

k

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

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-項(xiàng)集進(jìn)行第一次考驗(yàn)

if

k

==2 then

C

={item∈(apriori-gen1(

L

-1)-

L

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

else

C

={item∈(apriori-gen2(

L

-1)-

L

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

k

項(xiàng)集進(jìn)行第一次考驗(yàn)

end

(7)answer=∪

L

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

INSERT INTO

C

SELECT p.item,q.item

from Lp, Lq

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

k

-項(xiàng)集(

k

>2)INSERT INTO

C

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

from Lp, Lq

where p^q∈L

3 性能評估

3.1 實(shí)驗(yàn)環(huán)境

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

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

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

T

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

I

表示頻繁項(xiàng)集的平均長度，

D

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

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

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

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

3.3 實(shí)驗(yàn)分析

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

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

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

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

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

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

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

表4 不同增量與支持度下的運(yùn)行時(shí)間 s

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

10%增量下與40%增量下的CBEF算法在運(yùn)行效率上都有著顯著的提升，在10%增量下的提升尤為明顯。在最小支持度閾值設(shè)置為0.02，0.01，0.007 5時(shí)，算法相比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-項(xiàng)集只增加3項(xiàng)，且只有1次迭代過程，即只有頻繁1-項(xiàng)集的產(chǎn)生。因此產(chǎn)生的候選項(xiàng)集個(gè)數(shù)相比于重新計(jì)算過程大大減少，這正是增量更新算法最大的優(yōu)勢所在，即若增量數(shù)據(jù)對關(guān)聯(lián)規(guī)則產(chǎn)生的影響較小，此算法可以節(jié)約大量時(shí)間快速給出新的結(jié)果。而在60%增量下CBEF算法的優(yōu)勢已經(jīng)不再明顯，雖然在0.01以上支持度上仍然優(yōu)于其他兩種算法，但是在0.007 5支持度閾值以及80%增量的條件下，由于候選項(xiàng)集的個(gè)數(shù)顯著增多，候選項(xiàng)集的編碼開銷基本已經(jīng)超過了Apriori算法。

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

4 結(jié)束語

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