基于關聯規則的利潤加權并行算法

石正喜 葛科奇 曹財耀

（寧波城市職業技術學院信息學院浙江寧波315100）

1 引言

隨著海量數據的積累，及時快速的從這些龐大的數據中抽取出決策者所需的信息，為企業獲得更高的經濟效益使得數據挖掘的應用越來越受到企業界的重視。在數據挖掘技術中，APriori 算法是關聯規則挖掘的經典算法，該算法存在明顯的不足，因為它默認的前提是事務數據庫中的所有數據項在挖掘過程中是等價值的，實際上，不同的數據項往往重要性是不同的，也就是說不同的商品給商家帶來的利潤不一樣。因此在分析APriori 算法的基礎上，提出改進的新算法十分必要。

2 Apriori 算法

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

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

3 對Apriori 算法的改進

3.1 算法的改進思路

Apriori 算法的最本質的思想就是需要多次掃描數據庫，但是這樣的做法會帶來不小的弊端，因為當數據庫或者數據倉庫的容量很大時，掃描數據庫所花費的時間代價以及I/O代價都很大，這會降低算法的性能，也會降低數據挖掘的效率。由此提出了如下的改進思路：

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

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

由于引入了權值的概念，因此，有必要對加權關聯規則的支持度做一番改進，把項目的加權值考慮進去。定義：關聯規則形如X=>Y 的加權支持為：

其中，Count (X i) 是時間間隔ti 中包含項目集X 的交易數，N 為加權后的總交易數：

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

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

3.2 改進的新算法

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

改進的新算法的偽代碼如下所述：

輸入：一個事務數據庫D，D 中的每一個數據項ij 有它對應的權值w j；最小支持度；最小置信度。

輸出：一個帶權值的關聯規則集。

計算機1 用于產生所有長度為奇數的頻繁項目集。首先生成C1，在進行檢查、剪枝后形成L1，然后反復遍歷數據庫D，執行For(k=3;k≤size;k=k+2)的循環過程，直到沒有新的候選產生為止。計算機1 的并行算法如下：

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

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

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

4 結束語

基于權值和并行的概念，提出了加權關聯規則的并行挖掘算法，通過對新算法與Apriori 算法進行測算，可以發現在設定不同支持度時，新算法在每個階段的運行時間均要少于Apriori 算法；而固定了頻繁k- 項集的數量的情況下，Apriori算法的執行效率也遠遠地低于新算法。新算法的提出為將來進行海量數據處理提供了一種有效的處理模式。

[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]劉琦.基于關聯規則的數據挖掘算法研究[C.杭州：浙江大學，2008.

[4]譚光明，馮圣中，孫凝暉．一種基于新型的數據挖掘算法研究[J]．軟件學報，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]張玉林．一種無冗余的關聯規則算法[J]．計算機工程與應用，2007，43(3)：26- 29.