石正喜 葛科奇 曹財耀

（寧波城市職業(yè)技術(shù)學(xué)院信息學(xué)院浙江寧波315100）

1 引言

隨著海量數(shù)據(jù)的積累，及時快速的從這些龐大的數(shù)據(jù)中抽取出決策者所需的信息，為企業(yè)獲得更高的經(jīng)濟(jì)效益使得數(shù)據(jù)挖掘的應(yīng)用越來越受到企業(yè)界的重視。在數(shù)據(jù)挖掘技術(shù)中，APriori 算法是關(guān)聯(lián)規(guī)則挖掘的經(jīng)典算法，該算法存在明顯的不足，因?yàn)樗J(rèn)的前提是事務(wù)數(shù)據(jù)庫中的所有數(shù)據(jù)項(xiàng)在挖掘過程中是等價值的，實(shí)際上，不同的數(shù)據(jù)項(xiàng)往往重要性是不同的，也就是說不同的商品給商家?guī)淼睦麧櫜灰粯?。因此在分析APriori 算法的基礎(chǔ)上，提出改進(jìn)的新算法十分必要。

2 Apriori 算法

從本質(zhì)上來講，Apriori 是一種寬度優(yōu)先算法，它的本質(zhì)是多次對數(shù)據(jù)庫D 進(jìn)行掃描進(jìn)而發(fā)現(xiàn)所有的頻繁項(xiàng)目集，在每一次的掃描中只是單一的考慮擁有同一長度k（也就是項(xiàng)目集中所涵蓋的項(xiàng)目的個數(shù)）的所有k- 項(xiàng)目集。在第一趟掃描當(dāng)中，Apriori 算法首先計算出數(shù)據(jù)庫D 中所有的單個項(xiàng)目的支持度，進(jìn)而生成所有長度為L 的頻繁項(xiàng)目集（記為L1），然后利用L1 來挖掘L2，也就是頻繁2- 項(xiàng)集；如此連續(xù)不斷的循環(huán)下去，直至不能夠找到頻繁k- 項(xiàng)集為止，其中在發(fā)現(xiàn)每一個Lk 的過程當(dāng)中都需要對整個事務(wù)數(shù)據(jù)庫掃描一遍。

總之，Apriori 算法比較適用于處理小數(shù)據(jù)量的數(shù)據(jù)庫，對于大型的數(shù)據(jù)庫和數(shù)據(jù)倉庫，執(zhí)行效率會很低。從當(dāng)今的發(fā)展形勢來看，數(shù)據(jù)庫中的數(shù)據(jù)量正在以指數(shù)級上升，Apriori 算法很難被廣泛運(yùn)用于實(shí)際生活中，因此對于Apriori 算法的改進(jìn)也就很有必要[1、2]。

3 對Apriori 算法的改進(jìn)

3.1 算法的改進(jìn)思路

Apriori 算法的最本質(zhì)的思想就是需要多次掃描數(shù)據(jù)庫，但是這樣的做法會帶來不小的弊端，因?yàn)楫?dāng)數(shù)據(jù)庫或者數(shù)據(jù)倉庫的容量很大時，掃描數(shù)據(jù)庫所花費(fèi)的時間代價以及I/O代價都很大，這會降低算法的性能，也會降低數(shù)據(jù)挖掘的效率。由此提出了如下的改進(jìn)思路：

①盡量減少需要掃描的事務(wù)集以及交易的個數(shù)：它的原理是當(dāng)一個事務(wù)不包含長度為M 的大項(xiàng)集，那么它必然也不會包含長度為M+1 的大項(xiàng)集。就此可以將這些事務(wù)移除，在下一次掃描中就可以縮減需要掃描的事務(wù)集的個數(shù)；

②基于劃分的方法：這個算法的核心思想是把數(shù)據(jù)庫從邏輯上劃分為一些互相沒有聯(lián)系的塊，每一次只考慮單獨(dú)一個分塊，并且對它生成所有的頻繁項(xiàng)目集，隨后合并這些頻繁項(xiàng)目集，用來生成所有可能的頻繁項(xiàng)目集。最后是計算這些頻繁項(xiàng)目集的支持度。對于這些分塊來講，它們要滿足一定的大小限制，也就是它們的大小至少要保證每一個分塊可以單獨(dú)的放入主存當(dāng)中，這樣確實(shí)大大地提高了I/O 的效率，因?yàn)槊總€階段只需要被掃描一次。

由于引入了權(quán)值的概念，因此，有必要對加權(quán)關(guān)聯(lián)規(guī)則的支持度做一番改進(jìn)，把項(xiàng)目的加權(quán)值考慮進(jìn)去。定義：關(guān)聯(lián)規(guī)則形如X=>Y 的加權(quán)支持為：

其中，Count (X i) 是時間間隔ti 中包含項(xiàng)目集X 的交易數(shù)，N 為加權(quán)后的總交易數(shù)：

其中，N i 是時間間隔ti 中的總交易數(shù)。

因此可以說，對于一個項(xiàng)目集X，如果X 的加權(quán)支持度不小于m insup，就稱X 為頻繁項(xiàng)目集，如果規(guī)則X=>Y 的加權(quán)支持度和置信度分別大于或等于m insup 和m inconf，則稱X=>Y 為興趣規(guī)則。

3.2 改進(jìn)的新算法

改進(jìn)的新算法是以2 臺計算機(jī)并行執(zhí)行為例進(jìn)行描述、說明的。算法中部分參數(shù)含義：①W：項(xiàng)目權(quán)值的集合；②Lk：頻繁k- 項(xiàng)目的集合；③CK：由k- 項(xiàng)目集組成的候選集合；④MC(x)：項(xiàng)目集X 的支持?jǐn)?shù)；⑤w_m insup：最小加權(quán)支持度閾值[3-5]。

改進(jìn)的新算法的偽代碼如下所述：

輸入：一個事務(wù)數(shù)據(jù)庫D，D 中的每一個數(shù)據(jù)項(xiàng)ij 有它對應(yīng)的權(quán)值w j；最小支持度；最小置信度。

輸出：一個帶權(quán)值的關(guān)聯(lián)規(guī)則集。

計算機(jī)1 用于產(chǎn)生所有長度為奇數(shù)的頻繁項(xiàng)目集。首先生成C1，在進(jìn)行檢查、剪枝后形成L1，然后反復(fù)遍歷數(shù)據(jù)庫D，執(zhí)行For(k=3;k≤size;k=k+2)的循環(huán)過程，直到?jīng)]有新的候選產(chǎn)生為止。計算機(jī)1 的并行算法如下：

計算機(jī)2 的算法與計算機(jī)1 相似，計算機(jī)2 主要用于產(chǎn)生所有長度為偶數(shù)的頻繁項(xiàng)目集。首先生成C2，在進(jìn)行檢查、剪枝后形成L2，然后反復(fù)遍歷數(shù)據(jù)庫D，執(zhí)行For(k=2;k ≤size;k=k+2)的循環(huán)過程，直到?jīng)]有新的候選產(chǎn)生為止。計算機(jī)2 的并行算法如下：

當(dāng)計算機(jī)1、計算機(jī)2 各自完成計算后，由計算機(jī)1 處理全部結(jié)果，并從L=L∪Lk 中生成關(guān)聯(lián)規(guī)則。說明：①Choice(MC，w)被用來計算每一個1- 項(xiàng)集的加權(quán)支持度，如果大于等于w_m insup，就將其放到L1 當(dāng)中；反之則將其取消掉；②Count(D,W)用于生成C1；PW_prune_check(Ck，D)用于生成Lk；③PW_Join(Ck- 1,m insup)在算法當(dāng)中依據(jù)Ck- 1 生成Ck的鏈接方法與Apriori_Gen 函數(shù)相同；④Rules_Gen(L)根據(jù)L中的頻繁項(xiàng)目集生成最低信任閾值的關(guān)聯(lián)規(guī)則；⑤SCAN(D)以交易數(shù)據(jù)倉庫D 為處理對象，發(fā)現(xiàn)其中頻繁項(xiàng)目集的最大可能長度，并返回該數(shù)值[6]。

為驗(yàn)證改進(jìn)的Apriori 算法的性能，在VC++、SQL Server 2005 數(shù)據(jù)庫的環(huán)境下，對改進(jìn)的Apriori 算法及經(jīng)典的Apriori 算法進(jìn)行了對比驗(yàn)證。測試數(shù)據(jù)分別為600、800、1000 條記 錄 ， 最 小 支 持 度 分 別 為0.01，0.02，0.03，0.04，0.05，0.06，0.07，0.08，0.09，0.10。實(shí)驗(yàn)結(jié)果表明：當(dāng)最小支持度增大時，改進(jìn)算法的運(yùn)行速度比Apriori算法快；在頻繁k- 項(xiàng)集的數(shù)量固定的情況下，改進(jìn)算法的執(zhí)行效率也遠(yuǎn)遠(yuǎn)地高于Apriori 算法；另外，隨著數(shù)據(jù)庫中數(shù)據(jù)量的增大，改進(jìn)的Apriori 算法的執(zhí)行效率也明顯高于Apriori算法。

4 結(jié)束語

基于權(quán)值和并行的概念，提出了加權(quán)關(guān)聯(lián)規(guī)則的并行挖掘算法，通過對新算法與Apriori 算法進(jìn)行測算，可以發(fā)現(xiàn)在設(shè)定不同支持度時，新算法在每個階段的運(yùn)行時間均要少于Apriori 算法；而固定了頻繁k- 項(xiàng)集的數(shù)量的情況下，Apriori算法的執(zhí)行效率也遠(yuǎn)遠(yuǎn)地低于新算法。新算法的提出為將來進(jìn)行海量數(shù)據(jù)處理提供了一種有效的處理模式。

[1]Sankar K.Pal,Sanghamitra Bandyopadhyay,Shubhra Sankar Ray.Evolutionary Computation in Association Rules:A Review[J].IEEE Transactions on Systems,Man,And Cybernetics- Part C:Applications And Reviews,2006,36(5):601- 615.

[2]Kay C.W iese,Edward Glen.An association rules based genetic algorithm for RNA secondary structure prediction[J].Soft Computing Systems:Design,Management and Application.2002,4(1):173- 182.

[3]劉琦.基于關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法研究[C.杭州：浙江大學(xué)，2008.

[4]譚光明，馮圣中，孫凝暉．一種基于新型的數(shù)據(jù)挖掘算法研究[J]．軟件學(xué)報，2006，17(7)：1501- 1509．

[5]Alain Deschenes,Kay C.W iese.Using different algorithms for improving the Accuracy of Data M ining Algorithm[J].Evolutionary Computation,2004(2):598- 606.

[6]張玉林．一種無冗余的關(guān)聯(lián)規(guī)則算法[J]．計算機(jī)工程與應(yīng)用，2007，43(3)：26- 29.