關(guān)聯(lián)規(guī)則挖掘算法研究.doc

關(guān)聯(lián)規(guī)則挖掘算法的研究摘 要：Apriori算法是發(fā)現(xiàn)頻繁項(xiàng)目集的經(jīng)典算法，但是該算法需反復(fù)掃描數(shù)據(jù)庫，因此效率較低。本文介紹了Apriori算法的思想，同時對已經(jīng)提出的經(jīng)典的關(guān)聯(lián)規(guī)則更新算法FUP和IUA算法進(jìn)行分析，指出其優(yōu)缺點(diǎn)；最后對另外的改進(jìn)算法，做一個簡單的敘述。 關(guān)鍵詞 數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；Apriori算法Keywords：data mining；relation rule；Apriori algorithm 關(guān)聯(lián)規(guī)則反映了數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)目之間有趣的關(guān)聯(lián)關(guān)系，而其中發(fā)現(xiàn)頻繁項(xiàng)目集是關(guān)聯(lián)規(guī)則挖掘應(yīng)用中的關(guān)鍵技術(shù)和步驟。關(guān)于頻繁項(xiàng)目集的挖掘算法研究，人們對此進(jìn)行了大量的工作，其中以R. Agrawal 等人提出的Apriori 、AprioriTid 等算法最具有影響力和代表性。而這些算法的提出都是在挖掘數(shù)據(jù)庫和最小支持度不變的條件下進(jìn)行的。但實(shí)際中，遇到的情況可能是：隨著時間的推移，挖掘數(shù)據(jù)庫的規(guī)模可能不斷膨脹或需要刪除一部分記錄，或者需要對最小支持度進(jìn)行調(diào)整從而逐步聚集到我們感興趣的頻繁項(xiàng)目集上。因而如何從數(shù)據(jù)發(fā)生變動后的數(shù)據(jù)庫中高效地對已經(jīng)推導(dǎo)出的關(guān)聯(lián)規(guī)則進(jìn)行更新，具有非常重要的應(yīng)用價(jià)值，這就是所謂的增量式挖掘關(guān)聯(lián)規(guī)則的問題。1 關(guān)聯(lián)規(guī)則問題描述： 設(shè)I=i1，i2，.，im是m個不同項(xiàng)目的集合，給定一個事務(wù)數(shù)據(jù)庫D，其中D每一個事務(wù)T是I中一組項(xiàng)目的集合，即TI，T有一個惟一的標(biāo)志符TID。如果對于I中的一個子集X，有XT，我們就說一個事務(wù)T包含X。一條關(guān)聯(lián)規(guī)則(association rule)就是一個形如X =Y的蘊(yùn)涵式，其中X，YT，而XY=。關(guān)聯(lián)規(guī)則成立的條件是：它具有最小支持度s，即事務(wù)數(shù)據(jù)庫D中至少有s%的事務(wù)包含XY；它具有最小可信度c，即在事務(wù)數(shù)據(jù)庫D中包含X的事務(wù)中至少有c%同時也包含Y。給定一個事務(wù)集D，挖掘關(guān)聯(lián)規(guī)則問題就是產(chǎn)生支持度和可信度分別大于用戶給定的最小支持度和最小可信度的關(guān)聯(lián)規(guī)則，也就是產(chǎn)生強(qiáng)規(guī)則的問題。關(guān)聯(lián)規(guī)則的挖掘問題可以分解為以下兩個問題： (1) 找出事務(wù)數(shù)據(jù)庫中所有具有用戶最小支持度的項(xiàng)目集。具有用戶指定最小支持度的項(xiàng)目集稱為頻繁項(xiàng)目集，反之稱為非頻繁項(xiàng)目集。一個項(xiàng)目中所含項(xiàng)目的個數(shù)稱為該項(xiàng)目的長度。 (2) 利用頻繁項(xiàng)目集生成關(guān)聯(lián)規(guī)則。對于每一個頻繁項(xiàng)目集A，若BA，B，且support(A)/support(B)minconf，則有關(guān)聯(lián)規(guī)則B= (A-B)。目前大多數(shù)的研究主要集中在第一個問題上面。2 Apriori核心算法 Agrawal等人于1994年提出了一個挖掘顧客交易數(shù)據(jù)庫中項(xiàng)集間的關(guān)聯(lián)規(guī)則的重要方法Apriori算法，其核心是基于兩個階段頻繁項(xiàng)集思想的遞推算法。算法的基本思想是首先找出所有的頻集，這些項(xiàng)集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣。然后由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度。Apriori核心算法思想簡要描述如下：該算法中有兩個關(guān)鍵步驟連接步和剪枝步。 (1) 連接步：為找出Lk(頻繁k一項(xiàng)集)，通過Lk-1與自身連接，產(chǎn)生候選k-項(xiàng)集，該候選項(xiàng)集記作Ck；其中Lk-1的元素是可連接的。 (2) 剪枝步：Ck是Lk的超集，即它的成員可以是也可以不是頻繁的，但所有的頻繁一項(xiàng)集都包含在Ck中。掃描數(shù)據(jù)庫，確定Ck中每一個候選的計(jì)數(shù)，從而確定Lk(計(jì)數(shù)值不小于最小支持度計(jì)數(shù)的所有候選是頻繁的，從而屬于Lk)。然而，Ck可能很大，這樣所涉及的計(jì)算量就很大。為壓縮Ck，使用Apriori性質(zhì)：任何非頻繁的(k-1)-項(xiàng)集都不可能是頻繁k-項(xiàng)集的子集。因此，如果一個候選k-項(xiàng)集的(k-1)項(xiàng)集不在Lk中，則該候選項(xiàng)也不可能是頻繁的，從而可以由Ck中刪除。這種子集測試可以使用所有頻繁項(xiàng)集的散列樹快速完成。 這個方法要求多次掃描可能很大的交易數(shù)據(jù)庫，即如果頻集最多包含10個項(xiàng)，那么就需要掃描交易數(shù)據(jù)庫10遍，這需要很大的I/O負(fù)載?？赡墚a(chǎn)生大量的候選集，以及可能需要重復(fù)掃描數(shù)據(jù)庫，是Apriori算法的兩大缺點(diǎn)。3 關(guān)聯(lián)規(guī)則增量更新 關(guān)聯(lián)規(guī)則反映了數(shù)據(jù)庫中數(shù)據(jù)項(xiàng)目之間有趣的關(guān)聯(lián)關(guān)系，而其中發(fā)現(xiàn)頻繁項(xiàng)目集是關(guān)聯(lián)規(guī)則挖掘應(yīng)用中的關(guān)鍵技術(shù)和步驟。關(guān)于頻繁項(xiàng)目集的挖掘算法研究，人們對此進(jìn)行了大量的工作，其中以R. Agrawal 等人提出的Apriori、AprioriTid 等算法最具有影響力和代表性。而這些算法的提出都是在挖掘數(shù)據(jù)庫和最小支持度不變的條件下進(jìn)行的。實(shí)際中，數(shù)據(jù)庫的規(guī)模隨著時間，可能不斷膨脹或需要刪除一部分記錄，或者需要對最小支持度進(jìn)行調(diào)整從而逐步聚集到我們感興趣的頻繁項(xiàng)目集上。因而如何高效地從更新后的數(shù)據(jù)庫中對已經(jīng)推導(dǎo)出的關(guān)聯(lián)規(guī)則進(jìn)行更新是具有非常重要的價(jià)值的，這就是關(guān)聯(lián)規(guī)則增量更新問題。 廣義上的關(guān)聯(lián)規(guī)則的更新問題就是，在原有數(shù)據(jù)庫DB的基礎(chǔ)上，對其加上(或減去)數(shù)據(jù)庫db，在新的數(shù)據(jù)庫DB上挖掘新關(guān)聯(lián)規(guī)則的問題。關(guān)聯(lián)規(guī)則的增量式更新問題主要有三個：在給定的最小支持度和最小置信度下，當(dāng)一個新的數(shù)據(jù)集db添加到舊的數(shù)據(jù)庫DB中時，如何生成dbDB中的關(guān)聯(lián)規(guī)則；在給定的最小支持度和最小置信度下，當(dāng)從舊的數(shù)據(jù)庫DB中刪除數(shù)據(jù)集db時，如何生成DB-db中的關(guān)聯(lián)規(guī)則；給定數(shù)據(jù)庫DB，在最小支持度和最小置信度發(fā)生變化時，如何生成數(shù)據(jù)庫DB中的關(guān)聯(lián)規(guī)則。文獻(xiàn)2中Agrawal R，和Srikant R 提出的FUP算法是一個與Apriori算法相一致的針對第一個問題的更新算法。文獻(xiàn)3中，Brin S， Motwani R， 和Silverstein C提出的 FUP2算法是一個同時考慮第一個問題與第二個問題的算法。第三類問題則有馮玉才、馮劍琳提出的算法IUA和PIUA7。 下面給出兩個比較經(jīng)典算法：FUP和IUA算法的基本思想，并分析了各自的優(yōu)缺點(diǎn)。(1) FUP算法的基本思想 對任意一個k (k1)項(xiàng)集，若其在DB和db中都是頻繁項(xiàng)集，則其一定是頻繁項(xiàng)集；若其在DB和db中都是非頻繁項(xiàng)集，則其一定是非頻繁項(xiàng)集；若其僅在DB(db)中是頻繁項(xiàng)集，則其支持計(jì)數(shù)應(yīng)加上其在db(DB)中的支持?jǐn)?shù)以確定它是否為頻繁項(xiàng)集。FUP算法假設(shè)在DB中發(fā)現(xiàn)的頻繁項(xiàng)集 (n為L中最大元素的元素個數(shù))已被保存下來。它需要對DB和db進(jìn)行多次掃描，在第一次掃描中，算法先掃描db，將L1中的元素仍為dbDB中的頻繁項(xiàng)集的元素記入L1，并生成候選頻繁1項(xiàng)集C1，C1中的元素為db中的頻繁1項(xiàng)集且不包含在L1中；然后掃描DB以決定C1中的元素是否為dbDB中的頻繁項(xiàng)集，并將是dbDB中的頻繁項(xiàng)集的元素記入L1中。在第k (k1)此掃描前，先對Lk-1用Apriori_Gen函數(shù)生成候選頻繁k項(xiàng)集Ck，并除去Lk中的元素，即Ck=Ck - Lk，對Lk進(jìn)行剪枝，即對于XLk，若存在且Y Lk-1 Lk-1，則X肯定不是dbDB中的頻繁k項(xiàng)集，應(yīng)將其在Lk中刪除；然后掃描db，將Lk中的元素仍為dbDB中的頻繁項(xiàng)集的元素記入Lk，記錄候選頻繁k項(xiàng)集Ck中的元素在db中的支持?jǐn)?shù)；最后掃描DB，記錄Ck中的元素在DB中的支持?jǐn)?shù)，掃描結(jié)束時，將Ck中是dbDB中頻繁項(xiàng)集的元素記入Lk中。算法在Lk和Ck均為空時結(jié)束。 性能分析：FUP算法利用原數(shù)據(jù)庫集DB的挖掘結(jié)果，即頻繁項(xiàng)集L，需要對DB和db進(jìn)行n次掃描(n為L中最大的元素的元素個數(shù))，最后得到DBdb中的頻繁項(xiàng)集L，所以FUP算法的效率比使用Apriori算法和DHP算法重新對dbDB進(jìn)行挖掘的效率要高得多。 不過，F(xiàn)UP算法也存在其缺點(diǎn)，雖然它利用此算法利用了原數(shù)據(jù)庫集DB的挖掘結(jié)果，但是在對新的數(shù)據(jù)庫進(jìn)行更新時，又需要重復(fù)的掃描原數(shù)據(jù)庫DB，對候選集進(jìn)行模式匹配，因?yàn)樵瓟?shù)據(jù)庫集DB相對增加的數(shù)據(jù)集db是很大的，所以在利用FUP算法對關(guān)聯(lián)規(guī)則進(jìn)行更新時，會消耗大量時間處理規(guī)模巨大的候選集，浪費(fèi)了時間。(2) IUA3算法基本思想 算法IUA采用了一個獨(dú)特的候選頻繁項(xiàng)集生成算法iua_gen，在對每一次對數(shù)據(jù)庫DB掃描之前生成較小的候選頻繁項(xiàng)集，從而提高了算法的效率。它也要求上一次對數(shù)據(jù)庫DB進(jìn)行采掘時發(fā)現(xiàn)的頻繁項(xiàng)集 (n為L中最大元素的元素個數(shù))在本次挖掘時是可使用的。因?yàn)槿藗冊诎l(fā)現(xiàn)關(guān)聯(lián)規(guī)則時， 常常需要不斷地調(diào)整最小支持度和最小可信度來聚集到那些真正令其感興趣的關(guān)聯(lián)規(guī)則上， 因而該算法具有很重要的意義。IUA 算法的基本框架也和Apriori 算法一致， 也需要對交易數(shù)據(jù)庫DB 進(jìn)行多趟掃描. 因?yàn)橛衧 s， 所以原來所有的頻繁k 項(xiàng)目集(L k ) 在新的最小支持度下仍然是頻繁k 項(xiàng)目集， 因此在每一趟中掃描交易數(shù)據(jù)庫D 計(jì)算候選k 項(xiàng)目集的支持度計(jì)數(shù)時， 我們就沒有必要再考慮一遍Lk 對應(yīng)的候選k 項(xiàng)目集。如果更進(jìn)一步希望避免又重新生成一遍Lk對應(yīng)的候選k 項(xiàng)目集， 我們可以考慮采取以空間換時間的策略， 只要在Apriori 算法中的每一趟k， 保存相應(yīng)的(Ck -L k ) 即可。 在第1趟掃描中，IUA 算法只對原來不在L1中的單個項(xiàng)目進(jìn)行支持度計(jì)算，并確定出所有新的頻繁1 項(xiàng)目集L1，然后通過L1L1 得到L1。利用一個頻繁項(xiàng)目集的任意一個子集必定是頻繁項(xiàng)目集這一性質(zhì)，頻繁k項(xiàng)集c的每一單個項(xiàng)目i所對應(yīng)的頻繁1項(xiàng)集i或者從L1中取，或者從L1中取。根據(jù)這一特點(diǎn)，IUA算法將具有新支持度s的所有頻繁k(k2)項(xiàng)目集分成3類： 對于其中的每一個頻繁k 項(xiàng)目集c= i1， i2，. . .，ik， Pj (1j k )，必有ijL 1； 對于其中的每一個頻繁k 項(xiàng)目集c= i1， i2，. . ., ik， Pj (1j k )，必有ijL1； 對于其中的每一個頻繁k 項(xiàng)目集c= i1， i2，. . ., ik， 必有兩個非空子集c1 和c2， 使得c1c2= c， c1c2= ， 而且c1 L1， c2 L1。 我們將所有第類頻繁k 項(xiàng)目集構(gòu)成的集合記為L1k， 第類記為L2k， 第類記為L3k. 同時與之相對應(yīng)的候選k 項(xiàng)目集構(gòu)成的集合分別記為C1k， C2k， C3k.對于C1k， C2k直接利用Apriori算法分析：算法中的apriori-gen函數(shù)生成；對于C3k通過Lj1和Lk-22拼接修剪而成，j從1迭代到k-1。IUA也是采用Apriori框架。IUA 在自底向上的搜索過程中， 依據(jù)第k 層頻繁項(xiàng)目集來生成第k+ 1 層所有候選頻繁項(xiàng)目集， 然后對各候選頻繁項(xiàng)目集進(jìn)行支持度計(jì)算， 從而獲得第k + 1 層所有頻繁項(xiàng)目集， 直到某層候選項(xiàng)目集為空為止。 性能分析： (1)IUA算法與Apriori算法一樣，主要是利用了“一個頻繁項(xiàng)目集的任一非空子集必定也是頻繁項(xiàng)目集”這一性質(zhì)。根據(jù)這一性質(zhì)可知，對于任一項(xiàng)目i，如果i不是任一j(jk)項(xiàng)目集的元素，則i一定不是k-項(xiàng)目集的元素，而在IUA算法的6-8步的循環(huán)中7，每調(diào)用一次iua_gen函數(shù)，通過該函數(shù)的拼接將會使一些已明顯不是頻繁k-項(xiàng)目集的k-項(xiàng)目集成為候選k-項(xiàng)目集C3k中的元素，從而給iua_gen函數(shù)中的修剪增加運(yùn)算量，增加了算法的時間復(fù)雜性。 (2)IUA算法在關(guān)聯(lián)規(guī)則更新時，對k-項(xiàng)目集的開采，只是注意到利用已存在的頻繁k-項(xiàng)目集的集合Lk，沒有注意到基于“一個頻繁項(xiàng)目集的任一非空子集必定也是頻繁項(xiàng)目集”性質(zhì)的在本次更新時，對新產(chǎn)生的頻繁(k-1)-項(xiàng)目集的集合Lk-1加以利用。 由于IUA 充分利用已挖掘的結(jié)果及采用有效的候選頻繁項(xiàng)目集生成方法，并且采取以空間換時間的策略，這樣以來就顯著地減少了各層候選頻繁項(xiàng)目集數(shù)目， 有效地提高了關(guān)聯(lián)規(guī)則的更新效率.但I(xiàn)UA 受Apriori 框架的局限， 主要存在著以下不足： 多遍掃描數(shù)據(jù)庫， 掃描次數(shù)取決于新增最大頻繁項(xiàng)目集的長度； 需產(chǎn)生大量的候選項(xiàng)目集。(3) 其它算法 還有一些關(guān)聯(lián)規(guī)則更新算法，也都以IUA算法或者以FUP算法為基礎(chǔ)，在此算法的基礎(chǔ)上進(jìn)行分析，在某一方面進(jìn)行改進(jìn)，從而提出了一些效率相對更高改造方法，以IUA算法為基礎(chǔ)的，例如：宋海生的UA算法10，皋軍等提出的My_IUA算法11，周海巖提出的NEWIUA算法等；還有以FUP算法為基礎(chǔ)的，例如李寶東，宋翰濤的EFUP算法8，朱全玉，汪曉剛的NEWFUP算法9等。下面簡單介紹兩種。 1) NEWIUA算法 NEWIUA算法的基本框架與IUA算法和Apriori算法一致，對k=1，2，m，采用某種策略生成候選k-項(xiàng)目集Ck，然后掃描數(shù)據(jù)庫來確定Ck中那些k-項(xiàng)目集是頻繁項(xiàng)目集。NEWIUA算法與傳統(tǒng)的增量式更新算法不同之處主要體現(xiàn)在以下兩點(diǎn)： 因?yàn)橛衧s，所以，原來所有在舊的最小支持度s下的頻繁k-項(xiàng)目集在新的最小支持度s下仍是頻繁k-項(xiàng)目集。因此在每一趟掃描數(shù)據(jù)庫D計(jì)算候選k-項(xiàng)目集的支持?jǐn)?shù)時，就沒有必要對Lk中的項(xiàng)目重新再計(jì)算一次。因此NEWIUA算法在生成候選k-項(xiàng)目集的集合Ck時不含Lk中的項(xiàng)目集。 NEWIUA算法在生成候選k-項(xiàng)目集Ck時，不但利用了已經(jīng)存在的頻繁k-項(xiàng)目集的集合Lk，而且注意到，基于對本次更新時新產(chǎn)生的頻繁k-1-項(xiàng)目集Lk-1加以充分利用。與IUA算法相比，NEWIUA算法很好地利用了apriori-gen 函數(shù)，不過重復(fù)對原來Lk-1的處理，所以算法NEWIUA與重新運(yùn)行Apriori 算法相比，效率上只是有限地提高。 2) EFUP算法 EFUP算法的基本思想與FUP算法類似，區(qū)別是：FUP算法利用原數(shù)據(jù)庫集DB的挖掘結(jié)果，即頻繁項(xiàng)集L，需要對DB和db進(jìn)行n次掃描(n為L中最大的元素的元素個數(shù))，最后得到DBdb中的頻繁項(xiàng)集L；而EFUP算法只需對DB進(jìn)行一次掃描，對db同樣進(jìn)行n次掃描。因?yàn)镈B一般遠(yuǎn)大于db因此對于大數(shù)據(jù)集，EFUP算法可以通過較少對DB的I/O操作來提高效率。對db采用類似于Apriori的算法，一方面驗(yàn)證L中的元素是否為dbDB中的頻繁項(xiàng)集，另一方面生成其中的頻繁項(xiàng)集Ldb，然后對DB 進(jìn)行一次掃描，驗(yàn)證Ldb中的元素是否為dbDB中的頻繁項(xiàng)集。但EFUP算法的前提是已知元數(shù)據(jù)庫DB中的頻繁項(xiàng)集和其中元素的支持?jǐn)?shù)。(4) 負(fù)關(guān)聯(lián)規(guī)則的增量式更新傳統(tǒng)的關(guān)聯(lián)規(guī)則用于