關(guān)聯(lián)規(guī)則的增量更新算法研究

1、關(guān)聯(lián)規(guī)則的增量更新算法研究 08-05-01 09:23:00 作者：孫寶友1 姜合2 編輯：studa0714摘 要 隨著數(shù)據(jù)庫的不斷變化，關(guān)聯(lián)規(guī)則的增量更新變得尤為重要。為了更好的對關(guān)聯(lián)規(guī)則進(jìn)行有效的更新，本文對已經(jīng)提出的經(jīng)典的關(guān)聯(lián)規(guī)則更新算法FUP和IUA算法進(jìn)行分析，指出其優(yōu)缺點；最后對另外的改進(jìn)算法，做一個簡單的敘述。 關(guān)鍵詞 數(shù)據(jù)庫；關(guān)聯(lián)規(guī)則；增量更新 關(guān)聯(lián)規(guī)則反映了數(shù)據(jù)庫中數(shù)據(jù)項目之間有趣的關(guān)聯(lián)關(guān)系，而其中發(fā)現(xiàn)頻繁項目集是關(guān)聯(lián)規(guī)則挖掘應(yīng)用中的關(guān)鍵技術(shù)和步驟。關(guān)于頻繁項目集的挖掘算法研究，人們對此進(jìn)行了大量的工作，其中以R. Agrawal 等人提出的Apriori 、Aprior

2、iTid 等算法最具有影響力和代表性。而這些算法的提出都是在挖掘數(shù)據(jù)庫和最小支持度不變的條件下進(jìn)行的。但實際中，遇到的情況可能是：隨著時間的推移，挖掘數(shù)據(jù)庫的規(guī)?？赡懿粩嗯蛎浕蛐枰獎h除一部分記錄，或者需要對最小支持度進(jìn)行調(diào)整從而逐步聚集到我們感興趣的頻繁項目集上。因而如何從數(shù)據(jù)發(fā)生變動后的數(shù)據(jù)庫中高效地對已經(jīng)推導(dǎo)出的關(guān)聯(lián)規(guī)則進(jìn)行更新，具有非常重要的應(yīng)用價值，這就是所謂的增量式挖掘關(guān)聯(lián)規(guī)則的問題。1 關(guān)聯(lián)規(guī)則 問題描述： 設(shè)I=i1，i2，.，im是m個不同項目的集合，給定一個事務(wù)數(shù)據(jù)庫D，其中D每一個事務(wù)T是I中一組項目的集合，即TI，T有一個惟一的標(biāo)志符TID。如果對于I中的一個子集X，有X

3、T，我們就說一個事務(wù)T包含X。一條關(guān)聯(lián)規(guī)則(association rule)就是一個形如X =Y的蘊涵式，其中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)生強規(guī)則的問題。 關(guān)聯(lián)規(guī)則的挖掘問題可以分解為以下兩個問題： (1) 找出事務(wù)數(shù)據(jù)庫中所有具有用戶最小支持度的項目集。具有用戶指定最小支持度的項目集稱為頻繁項目集，反之稱為非頻繁項目集。一個項

4、目中所含項目的個數(shù)稱為該項目的長度。 (2) 利用頻繁項目集生成關(guān)聯(lián)規(guī)則。對于每一個頻繁項目集A，若BA，B，且support(A)/support(B)minconf，則有關(guān)聯(lián)規(guī)則B= (A-B)。目前大多數(shù)的研究主要集中在第一個問題上面。2 Apriori核心算法1 Agrawal等人于1994年提出了一個挖掘顧客交易數(shù)據(jù)庫中項集間的關(guān)聯(lián)規(guī)則的重要方法Apriori算法，其核心是基于兩個階段頻繁項集思想的遞推算法。算法的基本思想是首先找出所有的頻集，這些項集出現(xiàn)的頻繁性至少和預(yù)定義的最小支持度一樣。然后由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則，這些規(guī)則必須滿足最小支持度和最小可信度。Apriori核心算法

5、思想簡要描述如下：該算法中有兩個關(guān)鍵步驟連接步和剪枝步。 (1) 連接步：為找出Lk(頻繁k一項集)，通過Lk-1與自身連接，產(chǎn)生候選k-項集，該候選項集記作Ck；其中Lk-1的元素是可連接的。 (2) 剪枝步：Ck是Lk的超集，即它的成員可以是也可以不是頻繁的，但所有的頻繁一項集都包含在Ck中。掃描數(shù)據(jù)庫，確定Ck中每一個候選的計數(shù)，從而確定Lk(計數(shù)值不小于最小支持度計數(shù)的所有候選是頻繁的，從而屬于Lk)。然而，Ck可能很大，這樣所涉及的計算量就很大。為壓縮Ck，使用Apriori性質(zhì)：任何非頻繁的(k-1)-項集都不可能是頻繁k-項集的子集。因此，如果一個候選k-項集的(k-1)項集不在

6、Lk中，則該候選項也不可能是頻繁的，從而可以由Ck中刪除。這種子集測試可以使用所有頻繁項集的散列樹快速完成。 這個方法要求多次掃描可能很大的交易數(shù)據(jù)庫，即如果頻集最多包含10個項，那么就需要掃描交易數(shù)據(jù)庫10遍，這需要很大的I/O負(fù)載?？赡墚a(chǎn)生大量的候選集，以及可能需要重復(fù)掃描數(shù)據(jù)庫，是Apriori算法的兩大缺點。3 關(guān)聯(lián)規(guī)則增量更新 關(guān)聯(lián)規(guī)則反映了數(shù)據(jù)庫中數(shù)據(jù)項目之間有趣的關(guān)聯(lián)關(guān)系，而其中發(fā)現(xiàn)頻繁項目集是關(guān)聯(lián)規(guī)則挖掘應(yīng)用中的關(guān)鍵技術(shù)和步驟。關(guān)于頻繁項目集的挖掘算法研究，人們對此進(jìn)行了大量的工作，其中以R. Agrawal 等人提出的Apriori、AprioriTid 等算法最具有影響力和

7、代表性。而這些算法的提出都是在挖掘數(shù)據(jù)庫和最小支持度不變的條件下進(jìn)行的。實際中，數(shù)據(jù)庫的規(guī)模隨著時間，可能不斷膨脹或需要刪除一部分記錄，或者需要對最小支持度進(jìn)行調(diào)整從而逐步聚集到我們感興趣的頻繁項目集上。因而如何高效地從更新后的數(shù)據(jù)庫中對已經(jīng)推導(dǎo)出的關(guān)聯(lián)規(guī)則進(jìn)行更新是具有非常重要的價值的，這就是關(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ī)則；在給

8、定的最小支持度和最小置信度下，當(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)缺點。3.1 FU

9、P算法的基本思想 對任意一個k (k1)項集，若其在DB和db中都是頻繁項集，則其一定是頻繁項集；若其在DB和db中都是非頻繁項集，則其一定是非頻繁項集；若其僅在DB(db)中是頻繁項集，則其支持計數(shù)應(yīng)加上其在db(DB)中的支持?jǐn)?shù)以確定它是否為頻繁項集。FUP算法假設(shè)在DB中發(fā)現(xiàn)的頻繁項集(n為L中最大元素的元素個數(shù))已被保存下來。它需要對DB和db進(jìn)行多次掃描，在第一次掃描中，算法先掃描db，將L1中的元素仍為dbDB中的頻繁項集的元素記入L1，并生成候選頻繁1項集C1，C1中的元素為db中的頻繁1項集且不包含在L1中；然后掃描DB以決定C1中的元素是否為dbDB中的頻繁項集，并將是dbD

10、B中的頻繁項集的元素記入L1中。在第k (k1)此掃描前，先對Lk-1用Apriori_Gen函數(shù)生成候選頻繁k項集Ck，并除去Lk中的元素，即Ck=Ck - Lk，對Lk進(jìn)行剪枝，即對于XLk，若存在且Y Lk-1 Lk-1，則X肯定不是dbDB中的頻繁k項集，應(yīng)將其在Lk中刪除；然后掃描db，將Lk中的元素仍為dbDB中的頻繁項集的元素記入Lk，記錄候選頻繁k項集Ck中的元素在db中的支持?jǐn)?shù)；最后掃描DB，記錄Ck中的元素在DB中的支持?jǐn)?shù)，掃描結(jié)束時，將Ck中是dbDB中頻繁項集的元素記入Lk中。算法在Lk和Ck均為空時結(jié)束。 性能分析 FUP算法利用原數(shù)據(jù)庫集DB的挖掘結(jié)果，即頻繁項集L

11、，需要對DB和db進(jìn)行n次掃描(n為L中最大的元素的元素個數(shù))，最后得到DBdb中的頻繁項集L，所以FUP算法的效率比使用Apriori算法和DHP算法重新對dbDB進(jìn)行挖掘的效率要高得多。 不過，F(xiàn)UP算法也存在其缺點，雖然它利用此算法利用了原數(shù)據(jù)庫集DB的挖掘結(jié)果，但是在對新的數(shù)據(jù)庫進(jìn)行更新時，又需要重復(fù)的掃描原數(shù)據(jù)庫DB，對候選集進(jìn)行模式匹配，因為原數(shù)據(jù)庫集DB相對增加的數(shù)據(jù)集db是很大的，所以在利用FUP算法對關(guān)聯(lián)規(guī)則進(jìn)行更新時，會消耗大量時間處理規(guī)模巨大的候選集，浪費了時間。3.2 IUA3算法基本思想 算法IUA采用了一個獨特的候選頻繁項集生成算法iua_gen，在對每一次對數(shù)據(jù)庫

12、DB掃描之前生成較小的候選頻繁項集，從而提高了算法的效率。它也要求上一次對數(shù)據(jù)庫DB進(jìn)行采掘時發(fā)現(xiàn)的頻繁項集(n為L中最大元素的元素個數(shù))在本次挖掘時是可使用的。因為人們在發(fā)現(xiàn)關(guān)聯(lián)規(guī)則時， 常常需要不斷地調(diào)整最小支持度和最小可信度來聚集到那些真正令其感興趣的關(guān)聯(lián)規(guī)則上， 因而該算法具有很重要的意義。IUA 算法的基本框架也和Apriori 算法一致， 也需要對交易數(shù)據(jù)庫DB 進(jìn)行多趟掃描. 因為有s s， 所以原來所有的頻繁k 項目集(L k ) 在新的最小支持度下仍然是頻繁k 項目集， 因此在每一趟中掃描交易數(shù)據(jù)庫D 計算候選k 項目集的支持度計數(shù)時， 我們就沒有必要再考慮一遍Lk 對應(yīng)的候

13、選k 項目集。如果更進(jìn)一步希望避免又重新生成一遍Lk對應(yīng)的候選k 項目集， 我們可以考慮采取以空間換時間的策略， 只要在Apriori 算法中的每一趟k， 保存相應(yīng)的(Ck -L k ) 即可。 在第1趟掃描中，IUA 算法只對原來不在L1中的單個項目進(jìn)行支持度計算，并確定出所有新的頻繁1 項目集L1，然后通過L1L1 得到L1。利用一個頻繁項目集的任意一個子集必定是頻繁項目集這一性質(zhì)，頻繁k項集c的每一單個項目i所對應(yīng)的頻繁1項集i或者從L1中取，或者從L1中取。根據(jù)這一特點，IUA算法將具有新支持度s的所有頻繁k(k2)項目集分成3類： 對于其中的每一個頻繁k 項目集c= i1， i2，.

14、 . .，ik， Pj (1j k )，必有ijL 1； 對于其中的每一個頻繁k 項目集c= i1， i2，. . .ik， Pj (1j k )，必有ijL1； 對于其中的每一個頻繁k 項目集c= i1， i2，. . . ik， 必有兩個非空子集c1 和c2， 使得c1c2= c， c1c2= ， 而且c1 L1， c2 L1。 我們將所有第類頻繁k 項目集構(gòu)成的集合記為L1k， 第類記為L2k， 第類記為L3k. 同時與之相對應(yīng)的候選k 項目集構(gòu)成的集合分別記為C1k， C2k， C3k.對于C1k， C2k直接利用Apriori算法分析：算法中的apriori-gen函數(shù)生成；對于C3

15、k通過Lj1和Lk-22拼接修剪而成，j從1迭代到k-1。IUA也是采用Apriori框架。IUA 在自底向上的搜索過程中， 依據(jù)第k 層頻繁項目集來生成第k+ 1 層所有候選頻繁項目集， 然后對各候選頻繁項目集進(jìn)行支持度計算， 從而獲得第k + 1 層所有頻繁項目集， 直到某層候選項目集為空為止。 性能分析： (1)IUA算法與Apriori算法一樣，主要是利用了“一個頻繁項目集的任一非空子集必定也是頻繁項目集”這一性質(zhì)。根據(jù)這一性質(zhì)可知，對于任一項目i，如果i不是任一j(jk)項目集的元素，則i一定不是k-項目集的元素，而在IUA算法的6-8步的循環(huán)中7，每調(diào)用一次iua_gen函數(shù)，通過該函數(shù)的拼接將會使一些已明顯不是頻繁k-項目集的k-項目集成為候選k-項目集C3k中的元素，從而給iua_gen函數(shù)中的修剪增加運算量，增加了算法的時間復(fù)雜性。 (2)IUA算法在關(guān)聯(lián)規(guī)則更新時，對k-項目集的開采，只是注意到利用已存在的頻繁k-項目集的集合Lk，沒有注意到基于“一個頻繁項目集的任一非空子集必定也是頻繁項目集”性質(zhì)的在本次更新時，對新產(chǎn)生的頻繁(k-1)-項目集的集合Lk-1加以利用。 由于IUA 充分利用已挖掘的結(jié)果及采用有效的候選頻繁項