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

2、iTid 等算法最具有影響力和代表性。而這些算法的提出都是在挖掘數據庫和最小支持度不變的條件下進行的。但實際中，遇到的情況可能是：隨著時間的推移，挖掘數據庫的規模可能不斷膨脹或需要刪除一部分記錄，或者需要對最小支持度進行調整從而逐步聚集到我們感興趣的頻繁項目集上。因而如何從數據發生變動后的數據庫中高效地對已經推導出的關聯規則進行更新，具有非常重要的應用價值，這就是所謂的增量式挖掘關聯規則的問題。1 關聯規則 問題描述： 設I=i1，i2，.，im是m個不同項目的集合，給定一個事務數據庫D，其中D每一個事務T是I中一組項目的集合，即TI，T有一個惟一的標志符TID。如果對于I中的一個子集X，有X

3、T，我們就說一個事務T包含X。一條關聯規則(association rule)就是一個形如X =Y的蘊涵式，其中X，YT，而XY=。關聯規則成立的條件是：它具有最小支持度s，即事務數據庫D中至少有s%的事務包含XY；它具有最小可信度c，即在事務數據庫D中包含X的事務中至少有c%同時也包含Y。給定一個事務集D，挖掘關聯規則問題就是產生支持度和可信度分別大于用戶給定的最小支持度和最小可信度的關聯規則，也就是產生強規則的問題。 關聯規則的挖掘問題可以分解為以下兩個問題： (1) 找出事務數據庫中所有具有用戶最小支持度的項目集。具有用戶指定最小支持度的項目集稱為頻繁項目集，反之稱為非頻繁項目集。一個項

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

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

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

7、代表性。而這些算法的提出都是在挖掘數據庫和最小支持度不變的條件下進行的。實際中，數據庫的規模隨著時間，可能不斷膨脹或需要刪除一部分記錄，或者需要對最小支持度進行調整從而逐步聚集到我們感興趣的頻繁項目集上。因而如何高效地從更新后的數據庫中對已經推導出的關聯規則進行更新是具有非常重要的價值的，這就是關聯規則增量更新問題。 廣義上的關聯規則的更新問題就是，在原有數據庫DB的基礎上，對其加上(或減去)數據庫db，在新的數據庫DB+上挖掘新關聯規則的問題。關聯規則的增量式更新問題主要有三個：在給定的最小支持度和最小置信度下，當一個新的數據集db添加到舊的數據庫DB中時，如何生成dbDB中的關聯規則；在給

8、定的最小支持度和最小置信度下，當從舊的數據庫DB中刪除數據集db時，如何生成DB-db中的關聯規則；給定數據庫DB，在最小支持度和最小置信度發生變化時，如何生成數據庫DB中的關聯規則。文獻2中Agrawal R，和Srikant R 提出的FUP算法是一個與Apriori算法相一致的針對第一個問題的更新算法。文獻3中，Brin S， Motwani R， 和Silverstein C提出的 FUP2算法是一個同時考慮第一個問題與第二個問題的算法。第三類問題則有馮玉才、馮劍琳提出的算法IUA和PIUA7。 下面給出兩個比較經典算法：FUP和IUA算法的基本思想，并分析了各自的優缺點。3.1 FU

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

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

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

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

13、選k 項目集。如果更進一步希望避免又重新生成一遍Lk對應的候選k 項目集， 我們可以考慮采取以空間換時間的策略， 只要在Apriori 算法中的每一趟k， 保存相應的(Ck -L k ) 即可。 在第1趟掃描中，IUA 算法只對原來不在L1中的單個項目進行支持度計算，并確定出所有新的頻繁1 項目集L1，然后通過L1L1 得到L1。利用一個頻繁項目集的任意一個子集必定是頻繁項目集這一性質，頻繁k項集c的每一單個項目i所對應的頻繁1項集i或者從L1中取，或者從L1中取。根據這一特點，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 項目集構成的集合記為L1k， 第類記為L2k， 第類記為L3k. 同時與之相對應的候選k 項目集構成的集合分別記為C1k， C2k， C3k.對于C1k， C2k直接利用Apriori算法分析：算法中的apriori-gen函數生成；對于C3

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