白雪峰

摘要：針對Apriori算法存在的缺陷，提出一種改進的關聯規(guī)則算法。該算法對數據庫中的項采用二進制編碼，且只需掃描一次事物數據庫就能找出所有的頻繁項集，減少了掃描數據庫的次數和計算成本，從而大大提高了算法的執(zhí)行效率。

關鍵詞：關聯規(guī)則；Apriori算法；頻繁項集；數據挖掘；數據庫

中圖分類號：TP311.13文獻標識碼：A文章編號：1009-3044(2012)05-1015-04

An Improved Algorithm for Mining Association Rules

BAI Xue-feng

(Chongqing Three Gorges Medical College, Chongqing 404120, China)

Abstract: According to the inefficiency problems about the Apriori algorithm, this thesis proposes a new improved algorithm of association rules. This algorithm uses the binary code to the database item. This algorithm is able to discover all the frequent item sets only by searching the database once. Because this algorithm reduces the number of scanning the database and computational cost, so it has higher efficiency.

Key words: association rule; apriori algorithm; frequent item set; date mining; database

關聯規(guī)則挖掘是研究人員于1993年研究市場購物籃問題時提出的[1]，它是用來從大量的數據中挖掘出數據項間隱藏的相互關聯的有用知識，應用極其廣泛，在數據挖掘中具有重要的地位。

針對關聯規(guī)則的經典算法—Apriori算法存在的不足，本文提出了一種新的關聯規(guī)則挖掘算法—GApriori算法，該算法對數據庫中的項采用二進制編碼，提高了算法的執(zhí)行速度，節(jié)省了大量的時間。同時，該算法只需對數據庫進行一次掃描就能找出所有的頻繁項集，而連接前剪枝有效的減少了挖掘過程中需要進行連接的項集數目，因而對算法效率有了很大提高。

1關聯規(guī)則挖掘

先介紹關聯規(guī)則的幾個基本概念，具體描述如下[2]：

定義1：假設關聯規(guī)則挖掘的事務數據集記為D，其中，D= {t1,t2,…,tk,…,tn}，tk={i1,i2,…,im,…ip}，那么tk（k=1，2，…，n）稱為事務(Transaction)，im（m=1，2，…，p）稱為項目（Item）。

定義2：假設I={i1,i2,…,im }是由D中所有項目組成的集合，則I的每一個子集X就稱為D的項目集（Itemset）。假設X、Y都是項目集，且X?Y=?，則蘊含式X?Y稱為關聯規(guī)則。

定義3：對于關聯規(guī)則X?Y，如果數據集D中擁有項目集X?Y的個數為σ，交易數據集D的事務數為||D，那么，關聯規(guī)則X?Y的支持度就是σ與||D之比。

定義4：如果項目集X的支持度大于等于事先設定的最小支持度minsupport，那么就稱X為頻繁項目集。

關聯規(guī)則的挖掘過程是先查找符合既定條件的頻繁項集，然后利用頻繁項集生成關聯規(guī)則。通過對數據庫使用關聯規(guī)則挖掘，可以得到一些潛在有用的挖掘結果。將這些結果同事先設定的最小支持度minsupport和最小置信度minconfidence進行比較，如果其值不小于事先設定的值，那么就是有趣的規(guī)則。

Apriori算法是通過對數據庫進行反復逐層搜索，來得到頻繁項集。首先，對數據庫進行第一次掃描，得到頻繁1-項集L1；然后，由L1產生C2，并對數據庫進行第二次掃描，得到頻繁2-項集L2；接著利用上述方法，得到頻繁3-項集L3，然后不斷重復上述過程，直到找出所有的頻繁項集。通過研究分析頻繁項集，可以得到用戶感興趣的規(guī)則。

顯然，對于Apriori算法，存在著如下缺陷[3]：

1）Apriori算法在對候選項集進行模式匹配時，需要對數據庫進行多次重復掃描。當數據庫規(guī)模龐大時，大量的時間將消耗在內存與數據庫中的數據的交換上，使得整個掃描過程的時間復雜度很大。

2）算法可能需要產生大量的候選項集。比如說，如果有104個頻繁1-項集，那么，就將獲得多達107個候選2-項集。

2一種改進的關聯規(guī)則算法

本文就Apriori算法存在的缺陷，給出一種改進的關聯規(guī)則算法—GApriori算法。它采用二進制編碼技術，算法執(zhí)行過程中只需掃描一次數據庫，能有效地提高數據挖掘的效率。

2.1算法思想

GApriori算法的基本思想：首先對數據庫D中的每個數據項進行編碼，與此同時，根據每個數據項在數據庫中出現的次數獲得其支持度計數，從而得到頻繁1-項集L1。而由L1得到L2，只需要對L1中項的編碼兩兩進行“與”運算即可。接著由頻繁k-項集得到中間頻繁項集，將頻繁k-項集與中間頻繁項集中項的編碼作“與”運算，得到頻繁(k+1) -項集。重復上述這一步驟，最終得到符合要求的所有頻繁項集。采用這種基于編碼的方法只需要掃描一遍數據庫，且不需要產生候選項集。

由GApriori算法的思想可知，對數據項進行編碼是整個算法的基礎。下面介紹編碼的基本原則：首先要確定編碼的長度，這主要取決于D中的事務數。然后，選擇一種順序，對事務進行排序，任一事務僅對應編碼中的一位。對于D中某數據項，若出現在某一事務中，則把該事務在此項編碼中對應的位取為“1”，相反，取為“0”。比方說，某數據庫D共有15個事務(T 1，T 2, T3，……，T15)，項I1分別在事務T 1、T3、T8和T12中出現，那么，相應地可知項I1的編碼為(101000010001000)。

該算法主要用到了頻繁項集的以下一些性質及推論：

性質1：頻繁項集的所有非空子集也一定是頻繁的[3]。

利用頻繁項集定義，易于得到上述性質，故不再贅述。

由性質1可得到如下性質：如果在數據集D中，X是頻繁k-項集，那么，X的任意（k-1）項子集必定是頻繁（k-1）-項集。

推論1：如果在數據集D中，Xk是頻繁k-項集，那么頻繁（k–1）-項集集合Lk-1中包含Xk的（k-1）項子集的個數一定為k[4]。

該推論由上述性質很容易得到。因為Xk的（k-1）項子集個數為k，而Xk是數據集D的頻繁k-項集，所以這k個（k-1）項子集都是頻繁（k-1）-項集。

推論2：如果在數據集D中，Xk={Xi| 1≤i≤k }是頻繁k-項集，那么，對于其任意元素Xi，它在頻繁（k-1）-項集集合Lk-1的全部（k-1）項集中出現次數都必定不小于k﹣1次[5]。

證明：因為Xk的（k-1）項子集的個數為k，且由上述性質可知，這k個（k-1）項子集都是頻繁（k-1）-項集，因而都包含在Lk-1中。對于Xk的任意元素Xi，它在這k個（k-1）項子集中出現的次數為k-1次。所以，可知結論成立。

2.2算法描述

1）掃描事務數據庫，對所有事務項進行編碼，形成項編碼表，統計項的編碼中“1”的個數，如果“1”的個數小于事先設定的最小支持度計數，刪除該項，得到頻繁1-項集L1。

2）將L1中項的編碼兩兩進行“與”運算，對于新得到的編碼，統計“1”的個數，如果滿足最小支持度計數，那么，這兩項就組成頻繁2-項集。

3）設其中一個頻繁(k-1) -項集為{Ti，Tj，…Tm}，其中(i

①對Lk-1中每個項出現的次數進行統計，如果出現的次數小于k-1，那么，從Lk-1中刪除包含該項的項集，得到Lk-1。同時，由Lk-1中所有項（刪除Lk-1中出現次數小于(k﹣1)的項）得到中間頻繁單項集LM。這里應用了推論2。

②將Lk-1中項集的編碼與LM中項Tn的編碼進行“與”運算，對于新得到的編碼，如果包含“1”的個數不小于最小支持度計數，那么，將k-項集{Ti，Tj，…Tm，Tn}放到頻繁k-項集。否則n=n+1，繼續(xù)執(zhí)行第2）步。

4）重復步驟3），直到不能產生新的頻繁項集。

2.3算法舉例

假設事務數據庫D與表1相同。數據庫中有7個事務，最小支持數為2。下面演示GApriori算法生成頻繁項集的過程。

表1事務數據庫D

第一步：對數據庫D進行掃描，按照前述編碼原則給每個項進行編碼，得到項編碼表，如表2所示。

表2項編碼表

第二步：給每個項目賦一個整數（其中，1對應A，2對應B，依次類推），按照項的編碼計數，對支持數小于2的項目進行刪除，得到頻繁1-項集，如表3所示。

表3頻繁1-項集L1

第三步：將頻繁1-項集中的項的編碼進行兩兩“與”運算，生成頻繁2-項集，如表4所示。

表4頻繁2-項集L2

第四步：連接前剪枝，由L2生成L2′和LM，L2中各項出現的次數如表5所示。

表5 L中各項出現的次數

由上表可知，項6在L2中僅出現了1次，小于2，因此，在LM中不包含項6，同時將{2，6}從L2′中刪除，不再進行后續(xù)連接。第五步：由L2′和LM連接，生成頻繁3-項集L3，如表6所示。

表6頻繁3-項集L3

第六步：連接前剪枝，由L3生成L3′和LM。

顯然，此時L3中每個項出現的次數都小于3，因而L3′為空集。這樣搜索過程終止。

3算法評價和性能測試

3.1算法評價

針對前述Apriori算法的不足，GApriori算法做了多方面的改進，具體改進事項如下：

1）與Apriori算法相比，利用GApriori算法生成頻繁項集，只需要對數據庫掃描一遍，因而效率更高。

2）GApriori算法在生成頻繁k-項集時，不再采用頻繁(k-1) -項集的自連接。與Apriori算法相比，這會大大減少生成頻繁k-項集時所需要連接的項集的數量，同時，生成頻繁項集前，無須生成候選項集。

3.2算法性能測試

為了對GApriori算法與Apriori算法的效率進行比較，下面采用相同的條件進行實驗。

實驗環(huán)境：CPU為Pentium 4 /2.0GHz，內存為1G，操作系統為Windows XP Professional。軟件采用VC++6.0。

實驗數據庫：源于一家大型零售超市的銷售數據庫，共有14580條記錄，包含106項。

實驗結果如圖1所示。

圖1兩種算法所用時間比較

在圖1中，所花費的時間僅僅指算法本身的執(zhí)行時間，不包括數據的輸入輸出時間。就算法本身而言，其執(zhí)行效率與數據的輸入輸出時間無關，因此，我們在實驗中只是對算法本身的執(zhí)行時間進行測試。

從圖1的測試結果中可以得出結論：在支持度相同的情況下，與Apriori算法相比，GApriori算法所用時間更短。并且，支持度越小，GApriori算法的性能越好。

4結束語

本文針對Apriori算法存在的不足，提出了一種新的改進算法—GApriori算法，介紹了該算法的思想和理論依據，并通過具體事例對該算法的執(zhí)行過程進行了詳細說明。最后，對該算法進行了測試，結果表明，該算法具有良好的執(zhí)行效率。

參考文獻：

[1] Agrawal R,Imielinski T,Wami A S.Mining Association Rules Between Sets of Items in Large Databases[C]//Proc. of the ACM SIGMOD Conference on Management of Data,Washington D.C.,1993:207-216.

[2]邵峰晶,于忠清.數據挖掘原理與算法[M].北京:中國水利水電出版社,2003.

[3] Kamber M,Han J.數據挖掘概念與技術[M].范明,孟小峰,譯.北京:機械工業(yè)出版社,2007.

[4]顏雪松,蔡之華.一種基于Apriori的高效關聯規(guī)則挖掘算法的研究[J].計算機工程與應用,2002(10):209-211.

[5]李緒成,王保保.挖掘關聯規(guī)則中Apriori算法的一種改進[J].計算機工程,2006(7):36-38.