1、關(guān)聯(lián)規(guī)則的增量更新算法研究 08-05-01 09:23:00 作者：孫寶友1 姜合2 編輯：studa0714摘 要 隨著數(shù)據(jù)庫(kù)的不斷變化，關(guān)聯(lián)規(guī)則的增量更新變得尤為重要。為了更好的對(duì)關(guān)聯(lián)規(guī)則進(jìn)行有效的更新，本文對(duì)已經(jīng)提出的經(jīng)典的關(guān)聯(lián)規(guī)則更新算法FUP和IUA算法進(jìn)行分析，指出其優(yōu)缺點(diǎn)；最后對(duì)另外的改進(jìn)算法，做一個(gè)簡(jiǎn)單的敘述。 關(guān)鍵詞 數(shù)據(jù)庫(kù)；關(guān)聯(lián)規(guī)則；增量更新 關(guān)聯(lián)規(guī)則反映了數(shù)據(jù)庫(kù)中數(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)目集的挖掘算法研究，人們對(duì)此進(jìn)行了大量的工作，其中以R. Agrawal 等人提出的Apriori 、Aprior

2、iTid 等算法最具有影響力和代表性。而這些算法的提出都是在挖掘數(shù)據(jù)庫(kù)和最小支持度不變的條件下進(jìn)行的。但實(shí)際中，遇到的情況可能是：隨著時(shí)間的推移，挖掘數(shù)據(jù)庫(kù)的規(guī)模可能不斷膨脹或需要?jiǎng)h除一部分記錄，或者需要對(duì)最小支持度進(jìn)行調(diào)整從而逐步聚集到我們感興趣的頻繁項(xiàng)目集上。因而如何從數(shù)據(jù)發(fā)生變動(dòng)后的數(shù)據(jù)庫(kù)中高效地對(duì)已經(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個(gè)不同項(xiàng)目的集合，給定一個(gè)事務(wù)數(shù)據(jù)庫(kù)D，其中D每一個(gè)事務(wù)T是I中一組項(xiàng)目的集合，即TI，T有一個(gè)惟一的標(biāo)志符TID。如果對(duì)于I中的一個(gè)子集X，有X

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

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

5、思想簡(jiǎn)要描述如下：該算法中有兩個(gè)關(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ù)庫(kù)，確定Ck中每一個(gè)候選的計(jì)數(shù)，從而確定Lk(計(jì)數(shù)值不小于最小支持度計(jì)數(shù)的所有候選是頻繁的，從而屬于Lk)。然而，Ck可能很大，這樣所涉及的計(jì)算量就很大。為壓縮Ck，使用Apriori性質(zhì)：任何非頻繁的(k-1)-項(xiàng)集都不可能是頻繁k-項(xiàng)集的子集。因此，如果一個(gè)候選k-項(xiàng)集的(k-1)項(xiàng)集不在

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

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

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

9、P算法的基本思想 對(duì)任意一個(gè)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(zhǎng)中最大元素的元素個(gè)數(shù))已被保存下來。它需要對(duì)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)集，并將是dbD

10、B中的頻繁項(xiàng)集的元素記入L1中。在第k (k1)此掃描前，先對(duì)Lk-1用Apriori_Gen函數(shù)生成候選頻繁k項(xiàng)集Ck，并除去Lk中的元素，即Ck=Ck - Lk，對(duì)Lk進(jìn)行剪枝，即對(duì)于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é)束時(shí)，將Ck中是dbDB中頻繁項(xiàng)集的元素記入Lk中。算法在Lk和Ck均為空時(shí)結(jié)束。 性能分析 FUP算法利用原數(shù)據(jù)庫(kù)集DB的挖掘結(jié)果，即頻繁項(xiàng)集L

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

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

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

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

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