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

1、關(guān)聯(lián)規(guī)矩的增量更新算法研究摘要隨著數(shù)據(jù)庫的不竭變革，關(guān)聯(lián)規(guī)矩的增量更新變得尤為緊張。為了更好的對關(guān)聯(lián)規(guī)矩舉行有效的更新，本文對已經(jīng)提出的經(jīng)典的關(guān)聯(lián)規(guī)矩更新算法FUP和IUA算法舉行闡發(fā)，指出其優(yōu)缺點；末了對別的的革新算法，做一個簡樸的表達。關(guān)鍵詞數(shù)據(jù)庫；關(guān)聯(lián)規(guī)矩；增量更新關(guān)聯(lián)規(guī)矩反響了數(shù)據(jù)庫中數(shù)據(jù)工程之間幽默的關(guān)聯(lián)干系，而此中創(chuàng)造頻仍工程集是關(guān)聯(lián)規(guī)矩開掘應(yīng)用中的關(guān)鍵技能和步調(diào)。關(guān)于頻仍工程集的開掘算法研究，人們對此舉行了大量的事變，此中以R.Agraal等人提出的Apriri、ApririTid等算法最具有影響力和代表性。而這些算法的提出都是在開掘數(shù)據(jù)庫和最小支持度穩(wěn)定的條件下舉行的。但現(xiàn)實中

2、，碰到的環(huán)境大概是：隨著時間的推移，開掘數(shù)據(jù)庫的范圍大概不竭膨脹或必要刪除一局部記載，大概必要對最小支持度舉行調(diào)解從而漸漸聚攏到我們感愛好的頻仍工程集上。因此怎樣從數(shù)據(jù)產(chǎn)生變更后的數(shù)據(jù)庫中高效地對已經(jīng)推導(dǎo)出的關(guān)聯(lián)規(guī)矩舉行更新，具有非常緊張的應(yīng)用代價，這就是所謂的增量式開掘關(guān)聯(lián)規(guī)矩的題目。題目形貌：設(shè)I=i1，i2，.，i是個差異工程標(biāo)聚攏，給定一個事件數(shù)據(jù)庫D，此中D每一個事件T是I中一組工程標(biāo)聚攏，即TI，T有一個惟一的標(biāo)記符TID。假設(shè)對付I中的一個子集X，有XT，我們就說一個事件T包羅X。一條關(guān)聯(lián)規(guī)矩(assiatinrule)就是一個形如X=Y的蘊涵式，此中X，YT，而XY=。關(guān)聯(lián)規(guī)矩

3、建立的條件是：它具有最小支持度s，即事件數(shù)據(jù)庫D中至少有s%的事件包羅XY；它具有最小可信度，即在事件數(shù)據(jù)庫D中包羅X的事件中至少有%同時也包羅Y。給定一個事件集D，開掘關(guān)聯(lián)規(guī)矩題目就是產(chǎn)生支持度和可信度別離大于用戶給定的最小支持度和最小可信度的關(guān)聯(lián)規(guī)矩，也就是產(chǎn)生強規(guī)矩的題目。關(guān)聯(lián)規(guī)矩的開掘題目可以剖析為以下兩個題目：(1)尋失事件數(shù)據(jù)庫中全部具有效戶最小支持度的工程集。具有效戶指定最小支持度的工程集稱為頻仍工程集，反之稱為非頻仍工程集。一個工程中所含工程標(biāo)個數(shù)稱為該工程標(biāo)長度。(2)利用頻仍工程集天生關(guān)聯(lián)規(guī)矩。對付每一個頻仍工程集A，假設(shè)BA，B，且supprt(A)/supprt(B)i

4、nnf，那么有關(guān)聯(lián)規(guī)矩B=(A-B)。如今大多數(shù)的研究重要會合在第一個題目上面。Agraal等人于1994年提出了一個開掘主顧生意業(yè)務(wù)數(shù)據(jù)庫中項集間的關(guān)聯(lián)規(guī)矩的緊張要領(lǐng)Apriri算法，其焦點是基于兩個階段頻仍項集頭腦的遞推算法。算法的根本頭腦是起首尋出全部的頻集，這些項集出現(xiàn)的頻仍性至少和預(yù)界說的最小支持度一樣。然后由頻仍項集產(chǎn)生強關(guān)聯(lián)規(guī)矩，這些規(guī)矩必需滿意最小支持度和最小可信度。Apriri焦點算法頭腦扼要形貌如下：該算法中有兩個關(guān)鍵步調(diào)毗連步和剪枝步。(1)毗連步：為尋出Lk(頻仍k一項集)，通過Lk-1與自身毗連，產(chǎn)生候選k-項集，該候選項集記作k；此中Lk-1的元素是可毗連的。(2)

5、剪枝步：k是Lk的超集，即它的成員可以是也可以不是頻仍的，但全部的頻仍一項集都包羅在k中。掃描數(shù)據(jù)庫，確定k中每一個候選的計數(shù)，從而確定Lk(計數(shù)值不小于最小支持度計數(shù)的全部候選是頻仍的，從而屬于Lk)。然而，k大概很大，如許所涉及的盤算量就很大。為壓縮k，利用Apriri性子：任何非頻仍的(k-1)-項集都不成能是頻仍k-項集的子集。因此，假設(shè)一個候選k-項集的(k-1)項集不在Lk中，那么該候選項也不成能是頻仍的，從而可以由k中刪除。這種子集測試可以利用全部頻仍項集的散列樹快速完成。這個要領(lǐng)要求屢次掃描大概很大的生意業(yè)務(wù)數(shù)據(jù)庫，即假設(shè)頻集最多包羅10個項，那么就必要掃描生意業(yè)務(wù)數(shù)據(jù)庫10遍

6、，這必要很大的I/負載。大概產(chǎn)生大量的候選集，以及大概必要重復(fù)掃描數(shù)據(jù)庫，是Apriri算法的兩大缺點。關(guān)聯(lián)規(guī)矩反響了數(shù)據(jù)庫中數(shù)據(jù)工程之間幽默的關(guān)聯(lián)干系，而此中創(chuàng)造頻仍工程集是關(guān)聯(lián)規(guī)矩開掘應(yīng)用中的關(guān)鍵技能和步調(diào)。關(guān)于頻仍工程集的開掘算法研究，人們對此舉行了大量的事變，此中以R.Agraal等人提出的Apriri、ApririTid等算法最具有影響力和代表性。而這些算法的提出都是在開掘數(shù)據(jù)庫和最小支持度穩(wěn)定的條件下舉行的?，F(xiàn)實中，數(shù)據(jù)庫的范圍隨著時間，大概不竭膨脹或必要刪除一局部記載，大概必要對最小支持度舉行調(diào)解從而漸漸聚攏到我們感愛好的頻仍工程集上。因此怎樣高效地從更新后的數(shù)據(jù)庫中對已經(jīng)推導(dǎo)出

7、的關(guān)聯(lián)規(guī)矩舉行更新是具有非常緊張的代價的，這就是關(guān)聯(lián)規(guī)矩增量更新題目。廣義上的關(guān)聯(lián)規(guī)矩的更新題目就是，在原有數(shù)據(jù)庫DB的底子上，對其加上(或減去)數(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ī)矩；給定命據(jù)庫DB，在最小支持度和最小置信度產(chǎn)生變革時，怎樣天生數(shù)據(jù)庫DB中的關(guān)聯(lián)規(guī)矩。文獻2中AgraalR，和SrikantR提出的FUP算法是一個與

8、Apriri算法一樣等的針對第一個題目的更新算法。文獻3中，BrinS，taniR，和SilverstEin提出的FUP2算法是一個同時思量第一個題目與第二個題目的算法。第三類題目那么有馮玉才、馮劍琳提出的算法IUA和PIUA7。下面給出兩個比力經(jīng)典算法：FUP和IUA算法的根本頭腦，并闡發(fā)了各自的優(yōu)缺點。3.1FUP算法的根本頭腦對恣意一個k(k1)項集，假設(shè)其在DB和db中都是頻仍項集，那么其必然是頻仍項集；假設(shè)其在DB和db中都黑白頻仍項集，那么其必然黑白頻仍項集；假設(shè)其僅在DB(db)中是頻仍項集，那么其支持計數(shù)應(yīng)加上其在db(DB)中的支持數(shù)以確定它是否為頻仍項集。FUP算法假設(shè)在D

9、B中創(chuàng)造的頻仍項集(n為L中最大元素的元素個數(shù))已被保存下來。它必要對DB和db舉行屢次掃描，在第一次掃描中，算法先掃描db，將L1中的元素仍為dbDB中的頻仍項集的元素記入L1，并天生候選頻仍1項集1，1中的元素為db中的頻仍1項集且不包羅在L1中；然后掃描DB以決定1中的元素是否為dbDB中的頻仍項集，并將是dbDB中的頻仍項集的元素記入L1中。在第k(k1)此掃描前，先對Lk-1用Apriri_Gen函數(shù)天生候選頻仍k項集k，并撤除Lk中的元素，即k=k-Lk，對Lk舉行剪枝，即對付XLk，假設(shè)存在且YLk-1Lk-1，那么X肯定不是dbDB中的頻仍k項集，應(yīng)將其在Lk中刪除；然后掃描d

10、b，將Lk中的元素仍為dbDB中的頻仍項集的元素記入Lk，記載候選頻仍k項集k中的元素在db中的支持數(shù)；末了掃描DB，記載k中的元素在DB中的支持數(shù)，掃描竣事時，將k中是dbDB中頻仍項集的元素記入Lk中。算法在Lk和k均為空時竣事。性能闡發(fā)FUP算法利用原數(shù)據(jù)庫集DB的開掘效果，即頻仍項集L，必要對DB和db舉行n次掃描(n為L中最大的元素的元素個數(shù))，末了得到DBdb中的頻仍項集L，以是FUP算法的服從比利用Apriri算法和DHP算法重新對dbDB舉行開掘的服從要高得多。不外，F(xiàn)UP算法也存在其缺點，固然它利用此算法利用了原數(shù)據(jù)庫集DB的開掘效果，但是在對新的數(shù)據(jù)庫舉行更新時，又必要重復(fù)

11、的掃描原數(shù)據(jù)庫DB，對候選集舉行形式匹配，由于原數(shù)據(jù)庫集DB相對增長的數(shù)據(jù)集db是很大的，以是在利用FUP算法對關(guān)聯(lián)規(guī)矩舉行更新時，會斲喪大量時間處置懲罰范圍宏大的候選集，白費了時間。3.2IUA3算法根本頭腦算法IUA接納了一個奇特的候選頻仍項集天生算法iua_gen，在對每一次對數(shù)據(jù)庫DB掃描之宿世成較小的候選頻仍項集，從而進步了算法的服從。它也要求上一次對數(shù)據(jù)庫DB舉行采掘時創(chuàng)造的頻仍項集(n為L中最大元素的元素個數(shù))在本次開掘時是可利用的。由于人們在創(chuàng)造關(guān)聯(lián)規(guī)矩時，經(jīng)常必要不竭地調(diào)解最小支持度和最小可信度來聚攏到那些真正令其感愛好的關(guān)聯(lián)規(guī)矩上，因此該算法具有很緊張的意義。IUA算法的根

12、本框架也和Apriri算法同等，也必要對生意業(yè)務(wù)數(shù)據(jù)庫DB舉行多趟掃描.由于有ss，以是本來全部的頻仍k工程集(Lk)在新的最小支持度下仍舊是頻仍k工程集，因此在每一趟中掃描生意業(yè)務(wù)數(shù)據(jù)庫D盤算候選k工程集的支持度計數(shù)時，我們就沒有需要再思量一遍Lk對應(yīng)的候選k工程集。假設(shè)更進一步盼望制止又重新天生一遍Lk對應(yīng)的候選k工程集，我們可以思量接納以空間換時間的計謀，只要在Apriri算法中的每一趟k，保存相應(yīng)的(k-Lk)即可。在第1趟掃描中，IUA算法只對本來不在L1中的單個工程舉行支持度盤算，并確定出全部新的頻仍1工程集L1，然后通過L1L1得到L1。利用一個頻仍工程集的恣意一個子集肯定是頻仍

13、工程集這一性子，頻仍k項集的每一單個工程i所對應(yīng)的頻仍1項集i大概從L1中取，大概從L1中齲按照這一特點，IUA算法將具有新支持度s的全部頻仍k(k2)工程集分成3類：對付此中的每一個頻仍k工程集=i1，i2，.，ik，Pj(1jk)，必有ijL1；對付此中的每一個頻仍k工程集=i1，i2，.ik，Pj(1jk)，必有ijL1；對付此中的每一個頻仍k工程集=i1，i2，.ik，必有兩個非空子集1和2，使得12=，12=，而且1L1，2L1。我們將全部第類頻仍k工程集組成的聚攏記為L1k，第類記為L2k，第類記為L3k.同時與之相對應(yīng)的候選k工程集組成的聚攏別離記為1k，2k，3k.對付1k，2

14、k直接利用Apriri算法闡發(fā)：算法中的apriri-gen函數(shù)天生；對付3k通過Lj1和Lk-22拼接修剪而成，j從1迭代到k-1。IUA也是接納Apriri框架。IUA在自底向上的搜刮歷程中，根據(jù)第k層頻仍工程集來天生第k+1層全部候選頻仍工程集，然后對各候選頻仍工程集舉行支持度盤算，從而得到第k+1層全部頻仍工程集，直到某層候選工程集為空為止。性能闡發(fā)：(1)IUA算法與Apriri算法一樣，重要是利用了“一個頻仍工程集的任一非空子集肯定也是頻仍工程集這一性子。按照這一性子可知，對付任一工程i，假設(shè)i不是任一j(jk)工程集的元素，那么i必然不是k-工程集的元素，而在IUA算法的6-8步

15、的循環(huán)中7，每調(diào)用一次iua_gen函數(shù)，通過該函數(shù)的拼接將會使一些已顯著不是頻仍k-工程集的k-工程集成為候選k-工程集3k中的元素，從而給iua_gen函數(shù)中的修剪增長運算量，增長了算法的時間龐大性。(2)IUA算法在關(guān)聯(lián)規(guī)矩更新時，對k-工程集的開采，只是留意到利用已存在的頻仍k-工程集的聚攏Lk，沒有留意到基于“一個頻仍工程集的任一非空子集肯定也是頻仍工程集性子的在本次更新時，對新產(chǎn)生的頻仍(k-1)-工程集的聚攏Lk-1加以利用。由于IUA充實利用已開掘的效果及接納有效的候選頻仍工程集天生要領(lǐng)，而且接納以空間換時間的計謀，如許以來就明顯地淘汰了各層候選頻仍工程集數(shù)量，有效地進步了關(guān)聯(lián)

16、規(guī)矩的更新服從.但IUA受Apriri框架的范圍，重要存在著以下不敷：多遍掃描數(shù)據(jù)庫，掃描次數(shù)取決于新增最大頻仍工程集的長度；需產(chǎn)生大量的候選工程集。3.3別的算法另有一些關(guān)聯(lián)規(guī)矩更新算法，也都以IUA算法大概以FUP算法為底子，在此算法的底子上舉行闡發(fā)，在某一方面舉行革新，從而提出了一些服從相對更高改革要領(lǐng)，以IUA算法為底子的，比方：宋海生的UA算法10，皋軍等提出的y_IUA算法11，周海巖提出的NEIUA算法等；另有以FUP算法為底子的，比方李寶東，宋翰濤的EFUP算法8，朱全玉，汪曉剛的NEFUP算法9等。下面簡樸先容兩種。1)NEIUA算法NEIUA算法的根本框架與IUA算法和Ap

17、riri算法同等，對k=1，2，接納某種計謀天生候選k-工程集k，然后掃描數(shù)據(jù)庫來確定k中那些k-工程集是頻仍工程集。NEIUA算法與傳統(tǒng)的增量式更新算法差異之處重要表如今以下兩點：由于有ss，以是，本來全部在舊的最小支持度s下的頻仍k-工程集在新的最小支持度s下還是頻仍k-工程集。因此在每一趟掃描數(shù)據(jù)庫D盤算候選k-工程集的支持數(shù)時，就沒有需要對Lk中的工程重新再盤算一次。因此NEIUA算法在天生候選k-工程集的聚攏k時不含Lk中的工程集。NEIUA算法在天生候選k-工程集k時，不單利用了已經(jīng)存在的頻仍k-工程集的聚攏Lk，而且留意到，基于對本次更新時新產(chǎn)生的頻仍k-1-工程集Lk-1加以充

18、實利用。與IUA算法比擬，NEIUA算法很好地利用了apriri-gen函數(shù)，不外重復(fù)對本來Lk-1的處置懲罰，以是算法NEIUA與重新運行Apriri算法比擬，服從上只是有限地進步。2)EFUP算法EFUP算法的根本頭腦與FUP算法雷同，區(qū)別是：FUP算法利用原數(shù)據(jù)庫集DB的開掘效果，即頻仍項集L，必要對DB和db舉行n次掃描(n為L中最大的元素的元素個數(shù))，末了得到DBdb中的頻仍項集L；而EFUP算法只需對DB舉行一次掃描，對db同樣舉行n次掃描。由于DB一樣平常宏大于db因此對付大數(shù)據(jù)集，EFUP算法可以通過較少對DB的I/操縱來進步服從。對db接納雷同于Apriri的算法，一方面驗證

19、L中的元素是否為dbDB中的頻仍項集，另一方面天生此中的頻仍項集Ldb，然后對DB舉行一次掃描，驗證Ldb中的元素是否為dbDB中的頻仍項集。但EFUP算法的條件是元數(shù)據(jù)庫DB中的頻仍項集和此中元素的支持數(shù)?？偨Y(jié)：如今一些算法有的存在頻仍項集的遺漏題目，有的產(chǎn)生較多的候選項集，有的占用較大的空間，比方文獻81213。在文獻8中所提到的算法大概會造成頻仍項集的遺漏題目。在文獻12中所提到的算法大概會造成在掃描db時侯選頻仍項集的增長而低落開掘的服從。在文獻13中所提到的算法固然簡樸，但是卻沒有充實利用LDB中可以確定為非頻仍項集的項集，在Apriri算法對db舉行掃描產(chǎn)生侯選集Ldb的歷程中舉行

20、更有效的剪枝；而且假設(shè)新增的數(shù)據(jù)庫db所產(chǎn)生的局部頻仍項集與原頻仍都較大且大局部是雷同集時，整個歷程中空間的白費也較大。因此提出高效的更新算法是當(dāng)務(wù)之急。3.4負關(guān)聯(lián)規(guī)矩的增量式更新傳統(tǒng)的關(guān)聯(lián)規(guī)矩用于開掘主顧事件數(shù)據(jù)庫中項集間的關(guān)聯(lián)干系，而傳統(tǒng)的關(guān)聯(lián)規(guī)矩開掘算法僅能用來創(chuàng)造強形式，即那些具有高頻率和強相干的顯式?，F(xiàn)實上數(shù)據(jù)庫中還存在著很多接納如今開掘技能所不克不及創(chuàng)造的隱式形式，這些緊張的隱士形式之一便是負關(guān)聯(lián)規(guī)矩，即兩件事變很少同時出現(xiàn)，但卻具有較高的相干度，它具有低頻率、強相干的性子，表示了數(shù)據(jù)工程集間的不輕易直接不雅察到的強相干性子，這些隱式規(guī)矩報告我們哪些數(shù)據(jù)工程較少的一起產(chǎn)生，但它們

21、卻包羅了非常有代價的信息，因此創(chuàng)造負關(guān)聯(lián)規(guī)矩具有非常緊張的意義。險些大局部的關(guān)聯(lián)規(guī)矩開掘及其算法都只是涉及到項集間的關(guān)聯(lián)規(guī)矩，即正關(guān)聯(lián)規(guī)矩，比方“買了尿布的主顧也大概買啤酒如許的規(guī)矩。但是形如“買了牛奶的主顧大概不買咖啡如許的負關(guān)聯(lián)規(guī)矩，在現(xiàn)實中可以和正關(guān)聯(lián)規(guī)矩一樣提供有代價的信息。比方，負關(guān)聯(lián)規(guī)矩可以幫助市場監(jiān)視局部在浩繁的非公正生意業(yè)務(wù)的警報信號中斷定哪些是可以忽略的；企業(yè)可以通過綜合思量正、負關(guān)聯(lián)規(guī)矩從而捉住更多的商機。現(xiàn)實上，負關(guān)聯(lián)規(guī)矩的增量更新與關(guān)聯(lián)規(guī)矩的增量更新雷同，都是在更新后的數(shù)據(jù)庫中開掘負關(guān)聯(lián)規(guī)矩。但如今對負關(guān)聯(lián)規(guī)矩增量更新的研究還處于初始階段，在以后的學(xué)習(xí)與研究中，將重點研

22、究負關(guān)聯(lián)規(guī)矩的增量更新這方面的知識。本文起首提出了關(guān)聯(lián)規(guī)矩的經(jīng)典Apriri算法，并闡發(fā)了該算法的長處以及存在的不敷，接著引入了關(guān)聯(lián)規(guī)矩的相干知識，并側(cè)重討論關(guān)聯(lián)規(guī)矩的更新算法，重點對FUP與IUA算法舉行闡發(fā)與總結(jié)，末了又簡樸先容了兩種好的革新算法，盼望以后對負關(guān)聯(lián)規(guī)矩的增量式更新的研究有所幫助。1AgraalR，IielinskiT，SaIA.iningassiatinrulesbeteensetsfitesinlargedatabaseA.Preedingfthe1993ASIGDInternatinalnferenenanageentfData.NeYrk：APress，1993.207-2162AgraalR，SrikantR.Fastalgrithsfrinin