一種新的關(guān)聯(lián)規(guī)則挖掘算法

摘要：對關(guān)聯(lián)規(guī)則算法進(jìn)行了研究和分析，基于候選集的Apriori-like算法需要反復(fù)掃描數(shù)據(jù)庫，并產(chǎn)生大量的候選集，在挖掘低支持度、長模式的規(guī)則時效率低下。針對算法的缺陷，該文提出了一種PS算法，優(yōu)化了關(guān)聯(lián)規(guī)則的挖掘。實(shí)驗(yàn)結(jié)果證明了該算法的有效性。

關(guān)鍵詞： 數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則

中圖分類號：TP311文獻(xiàn)標(biāo)識碼：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]是關(guān)聯(lián)規(guī)則中最常被使用的方法，但其有些缺點(diǎn)：1)尋找頻繁項(xiàng)目集時，會產(chǎn)生大量侯選項(xiàng)目集2)需要多次掃描數(shù)據(jù)庫3)當(dāng)最小支持度改變時，需要重新挖掘。以后雖有許多研究針對此點(diǎn)做改進(jìn)，但大都沒有跳出Apriori算法的整體框架，包括前面提出的AprioriMend算法。在此提出一個新的挖掘算法PS（Power Set），它將完全脫離Apriori算法的框架結(jié)構(gòu)。

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

1 幾個相關(guān)概念

定義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：對任意事務(wù)數(shù)據(jù)庫D，I={i1,i2……im}，liuzy01.tif ，則D中包含X的事務(wù)數(shù)量稱為X在D中的頻度，簡稱為X的頻度。

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

2 PS算法描述

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

PS算法

輸入：事務(wù)數(shù)據(jù)庫D

輸出：所有項(xiàng)目集

（1） scan D;

（2） Result_Table RT; //RT的個數(shù)由D中的所有項(xiàng)目總數(shù)確定

（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算法中交易記錄拆解過程

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

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

定義5：事務(wù)數(shù)據(jù)庫D：所有事務(wù)的集合，相當(dāng)于事務(wù)數(shù)據(jù)庫中的記錄集合，每個事務(wù)T由I中的若干項(xiàng)組成，是I的子集，用唯一的TID來標(biāo)識。

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

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

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

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

表1 t和它所生成的子集對應(yīng)二進(jìn)制和十進(jìn)制描述表

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

4 PS算法完整實(shí)例說明

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

表2 交易數(shù)據(jù)庫D

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

圖1 T1拆解結(jié)果圖

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

圖2 T2拆解結(jié)果圖

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

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

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

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

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

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

表3 生成的頻繁項(xiàng)集統(tǒng)計(jì)表

第九步：利用頻繁項(xiàng)目集以及使用者設(shè)定的最小置信度80%，來產(chǎn)生符合使用者需求的關(guān)聯(lián)規(guī)則，見表4。

表4 生成的關(guān)聯(lián)規(guī)則表

5 PS算法與Apriori算法比較

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

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

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

6 算法的實(shí)現(xiàn)與比較

為了驗(yàn)證PS算法的可行性和執(zhí)行效率，進(jìn)行了一系列對比實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境為windows Server 2003，硬件為Intel Pentium Processor 1.70GHz和256MB內(nèi)存，PS算法用Microsoft VB6.0實(shí)現(xiàn)，用來實(shí)驗(yàn)的數(shù)據(jù)庫是由IBM generator產(chǎn)生。

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

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

7 PS算法的限制

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

參考文獻(xiàn)

[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-），女，講師，碩士，研究方向：數(shù)據(jù)挖掘、數(shù)據(jù)倉庫技術(shù)、網(wǎng)絡(luò)開發(fā)。