一種新的關聯規則挖掘算法

摘要：對關聯規則算法進行了研究和分析，基于候選集的Apriori-like算法需要反復掃描數據庫，并產生大量的候選集，在挖掘低支持度、長模式的規則時效率低下。針對算法的缺陷，該文提出了一種PS算法，優化了關聯規則的挖掘。實驗結果證明了該算法的有效性。

關鍵詞： 數據挖掘；關聯規則

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)17-20ppp-0c

A New Association Rules Mining Algorithm

LIU Zhi-yi, CHANG Rui

(Changzhou Institute of Technology,Changzhou 213002,china)

Abstract:After analyzing and studying data mining algorithms, there are great flaws in Apriori-like algorithm based on candidate sets, the algorithm needs multiple scanning, produces lots of candidate sets, and has low efficiency when mining low support threshold, long rules. This paper introduces a new algorithm PS which optimizes association rules mining. Experimental results show the algorithm is effective.

Key words:data mining;association rules

Apriori算法[1-3]是關聯規則中最常被使用的方法，但其有些缺點：1)尋找頻繁項目集時，會產生大量侯選項目集2)需要多次掃描數據庫3)當最小支持度改變時，需要重新挖掘。以后雖有許多研究針對此點做改進，但大都沒有跳出Apriori算法的整體框架，包括前面提出的AprioriMend算法。在此提出一個新的挖掘算法PS（Power Set），它將完全脫離Apriori算法的框架結構。

PS算法是一個執行效率快而且平穩的關聯規則挖掘算法，它含有以下特性：只需要掃描數據庫一次，從而可以大大降低I/O存取的時間；算法結構簡單清晰；可以實現先發現各個項目集合，然后用戶在輸入最小支持度，增加挖掘的彈性，即用戶可以任意改變最小支持度，而無須重新掃描整個數據庫；執行效率平穩，不會隨著支持度的變動，而影響其執行效率；可以運用在增量式挖掘；不需要進行數據庫的前期處理。

1 幾個相關概念

定義1：冪集合PS（A）：對于任意一個非空集合A，它的冪集合PS（A）就是由A的全部子集組成的集合。例如非空集合A={a,b,c}，則它的冪集合PS（A）={{φ}，{a},,{c},{a,b},{a,c},{b,c},{a,b,c}}。

定義2：對任意事務數據庫D，I={i1,i2……im}，liuzy01.tif ，則D中包含X的事務數量稱為X在D中的頻度，簡稱為X的頻度。

定義3：對于任意集合A={u1,u2,u3,……，ui}，其中所含元素的個數稱之為該集合的長度，記作Length(A)。

2 PS算法描述

PS算法主要的運作規則相當快速簡單，主要步驟：在讀取事務數據庫D中的每一條交易記錄時，直接以該筆記錄的商品項目本身拆解，也就是直接求出該交易記錄所對應的集合的所有子集（除空集外），例如，ABC為此筆交易記錄，可以拆解出ABC、AB、AC、BC、A、B、C七個子集，接著將這些子集依據集合長度存放在不同的結果表中并做計數動作，如果此集合已經存在于對應的結果表中，則將該集合的計數值加1；如果不存在，則將該集合加入其中，并設置初始值為1。完成以上動作后，此筆交易記錄的拆解才算結束。所以當掃描事務數據庫D一次以后，即表示所有的交易記錄都拆解完成。最后，只需等待使用者輸入最小支持度和最小置信度，就可以產生頻繁項目集和關聯規則，算法偽代碼如下：

PS算法

輸入：事務數據庫D

輸出：所有項目集

（1） scan D;

（2） Result_Table RT; //RT的個數由D中的所有項目總數確定

（3） Forall transaction t contains D do begin

（4） AnalysisElements(transcaton t);//求出一條交易記錄的所有子集

（5） Forall item i do// i代表某交易記錄的某個子集

（6） m =length(i)

（7） If ( i contains RTm)

（8） i.count++;

（9） Else

（10） Add i to RTm;

（11） i.count=1;

（12） End

（13） End

3 PS算法中交易記錄拆解過程

為了便于后面分析，在此先描述一下相關概念。

定義4：事務數據庫中所有項目組成的集合稱為數據庫的項目集，記為大寫字母I，則I={i1,i2……,im}，│I│=m,其中m為事務數據庫中所含項目的總數。

定義5：事務數據庫D：所有事務的集合，相當于事務數據庫中的記錄集合，每個事務T由I中的若干項組成，是I的子集，用唯一的TID來標識。

規定1：對于集合I={i1,i2……im}，規定一個m位的二進制串L（p1,p2,……,pn）與之對應，該位串第一位p1 對應i1, 該位串第二位p2 對應i2，依次類推。

規定2：m位的二進制串l（p1,p2,……,pn）是集合X在I中的對應二進制串，X I，如果pk=1,則ik∈I是其集合X中的元素，反之，如果pk=0,則ik不是集合X中的元素。

定理1：對于任意一個非空集合A={a1，a2，……，an}，則由其可產生的所有子集（空集除外）個數為2n-1。例如非空集合A={a,b,c}，則它的所有子集個數為23-1=7。它們分別為{a},,{c},{a,b},{a,c},{b,c},{a,b,c}。

下面說明PS算法中交易記錄的拆解過程。設有如下一條交易記錄t={A，B，C}，它所生成的子集為{a},,{c},{a,b},{a,c},{b,c},{a,b,c}。根據規定1和規定2來重新描述t和它所生成的子集，見表1。

表1 t和它所生成的子集對應二進制和十進制描述表

從上述表格中,可以看到一個由三個元素組成的集合，它的所有子集共有7個（23-1=7）這些子集如果用二進制串所對應的十進制數表示的話，依次為1、2、3、4、5、6、7，即分別為1到7之間的整數值。依據上述發現，可以使用如下方法快速生成一個集合的所有子集。假如有一條交易記錄t={B，C}，依次讀入t中的每一個元素，并將其存入臨時一維數組M中，等到t讀入完畢之后，就可以得到t的長度和數組M（其中M[1]=B，M[2]=C），從而進一步得知t所產生的所有子集個數為3（22-1=3），這些子集如果用二進制串所對應的十進制數表示的話，依次為1，2，3。然后將1、2、3分別轉換為兩位二進制（因為t的長度為2），分別為01、10、11。先取出某一子集所對應的二進制串“01”，找出“1”在“01”所處的位置，結果發現只有2號位，于是用從數組M中取出相應的數組元素M[2]中的值代表該子集，即C。接下來取出“10”，找出“1”在“10”所處的位置，結果發現只有1號位，于是用從數組M中取出相應的數組元素M[1]中的值代表該子集，即B。最后取出“11”，找出“1”在“11”所處的位置，結果發現有1號位和2號位，于是用從數組M中取出相應的數組元素M[1]和M[2]中的值代表該子集，即BC。

4 PS算法完整實例說明

第一步：載入數據庫中的交易記錄，如表2，其中TID是顧客交易編號，Itemset為顧客購買商品項目的交易記錄代碼明細，D中所含項目總數為4，交易記錄總數為5，最長交易記錄長度為3。

表2 交易數據庫D

第二步：讀入第一條交易記錄，內容為B和C，此筆交易記錄長度為2，申請一個大小為2的臨時數組M，將記錄中的B、C依次存儲在一維數組M中。隨即根據3中的方法產生{B}、{C}、{B，C}項目集組合，將{B}、{C}、{B，C}依據長度不同存儲于不同的RT（Result Table）中,見圖1，此時第一條交易記錄處理完畢，此刻釋放臨時數組M所占用的內存空間。

圖1 T1拆解結果圖

第三步：判斷出數據庫D中尚有記錄，讀取下一條記錄，內容為 A、B和C，此條交易記錄長度為3，隨即產生{A}、{B}、{C}，{A，B}、{A，C}、{B，C}、{A，B，C}。同理將它們存入不同的RT表，結果見圖2。

圖2 T2拆解結果圖

第四步：判斷出數據庫D中尚有記錄，讀取下一條記錄，內容為 A和C，此條交易記錄長度為2，隨即產生{A}、{C}和{A，C}。同理將它們存入不同的RT表。

第五步：判斷出數據庫D中尚有記錄，讀取下一條記錄，內容為D，此條交易記錄長度為1，隨即產生{D}，同理將它存入RT1表中。

第六步：判斷出數據庫D中尚有記錄，讀取下一條記錄，內容為A和D，此條交易記錄長度為2，隨即產生{A}、{D}、{A，D}，同理將它們依次存入RT表中。

圖3 所有記錄拆解完成后的結果示意圖

第七步：判斷沒有任何交易記錄，此時最終的RT表形成，見圖3，等待用戶輸入最小支持度。

第八步：假如此刻用戶輸入最小支持度為40%（5*40%=2）和最小置信度為80%，然后根據使用者所設定的最小支持度產生頻繁項目集，見表3。

表3 生成的頻繁項集統計表

第九步：利用頻繁項目集以及使用者設定的最小置信度80%，來產生符合使用者需求的關聯規則，見表4。

表4 生成的關聯規則表

5 PS算法與Apriori算法比較

PS算法與Apriori算法最主要的不同點如下：對于交易記錄的處理，是直接由數據庫中的第一條記錄開始依次往下處理到最后一條記錄，將交易數據的出現次數直接求和，支持度和置信度的計算由整個數據庫記錄數和項目集個別計算，不需要反復掃描數據庫以求得各個階層項目集的相關信息。

對于新增的記錄而言，也不需要重新掃描整個數據庫，僅需要對新增的記錄加以處理，然后連接之前處理過的記錄資料，即可對所有的項集進行計算支持度。假設數據庫中的交易有N條記錄，而所有交易的記錄中全部有L個項目，新增的交易有m條記錄，N遠大于m；一般以Apriori算法為主的算法必須在每次新增記錄的時候，重新掃描包含新增記錄的全部數據庫記錄，而PS算法則僅僅只對新增記錄做處理，再連接原來的資料即可。假如計算一般算法的時間復雜度的公式表示為Ω（L2（N+m）），則對PS算法的時間復雜度而言，就可以表示為θ（N+m）。從這兩個公式可看出，類似Apriori的各個算法在數據庫中記錄數量越多時，其花費的時間復雜度會隨著數據量L的大小做指數的增加，而由于PS算法處理記錄的方式為單條記錄處理，所以時間復雜度不會隨著整體記錄量的變化而有所變動，且PS算法的處理時間在記錄增加時即時處理，也無須花費一段額外的數據預處理時間，圖4為Apriori算法和PS算法對于每次新增記錄時的處理所耗費時間的比較示意圖，虛線部分為節省掃描數據庫的時間成本，從中可明顯看出PS算法在新增記錄時比Apriori算法節省許多重復搜索記錄的時間，但是PS算法在存儲的空間上，卻會花費比Apriori算法大上數倍的存儲空間，所以PS算法是一種以存儲空間換取挖掘時間的方式。

圖4 Apriori和PS新增記錄時處理所耗費時間比較示意圖

6 算法的實現與比較

為了驗證PS算法的可行性和執行效率，進行了一系列對比實驗。實驗環境為windows Server 2003，硬件為Intel Pentium Processor 1.70GHz和256MB內存，PS算法用Microsoft VB6.0實現，用來實驗的數據庫是由IBM generator產生。

表5PS算法與Apriori算法在不同支持度下的效率比較（單位：秒）

由表5可看出當最小支持度越高，商品出現在交易中的次數需要越大，所以找出的頻繁項目集就相對的減少；而當支持度變低時，商品出現在交易中的次數則需要越少，故挖掘出的頻繁項目集就會增多，當然需要花費的時間也增加。Apriori算法在支持度遞增的情況下，對于測試數據庫所花費的運行時間就相應變少。PS算法是在先不輸入最小支持度的前提下進行挖掘，等到挖掘結束后再根據使用者確定的最小支持度找出頻繁項目集，所以PS算法不會隨著支持度大小的改變，影響整體執行效率。因此PS算法在各種支持度下，整體執行效率優于Apriori算法。

7 PS算法的限制

PS算法的主要操作是拆解每條交易記錄以生成對應的項目集組合，故隨著交易記錄長度的增加，拆解時間會急劇增加，所以PS算法適用于挖掘那些最長記錄長度較小，記錄數適量的中小規模數據庫。

參考文獻

[1]Jiawei Han,Micheline Kamber.Data Mining Concepts and Techniques[M].Morgan Kaufmann Publishers,2000.

[2]David J Hand,Heikki Mannila,Padhraic Smyth.Principles of Data Mining (Adaptive Computation and Machine Learning)[M].MIT Press,2001.

[3]T Hastie,R Tibshirani,J H Friedma.The Elements of Statistical Learning[M].Springer Verlag,2001.

[4]Ian H Eibe Frank.Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations[M].Morgan Kaufmann,1999.

[5]http://www.kdnuggets.com[Eb/OL].

收稿日期：2008-03-26

作者簡介：劉芝怡（1977-），女，講師，碩士，研究方向：數據挖掘、數據倉庫技術、網絡開發。