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

1、關(guān)聯(lián)規(guī)那么挖掘算法研究摘要apriri算法是發(fā)現(xiàn)頻繁工程集的經(jīng)典算法，但是該算法需反復(fù)掃描數(shù)據(jù)庫，因此效率較低。本文介紹了apriri算法的思想，并分析了該算法的性能瓶頸。在此根底上，針對(duì)apriri算法提出了一種改良方法，該方法采用轉(zhuǎn)置矩陣的策略，只掃描一次數(shù)據(jù)庫即可完成所有頻繁工程集的發(fā)現(xiàn)。與其他經(jīng)典的算法相比，本文提出的算法在工程集長度較大時(shí)，性能明顯進(jìn)步。關(guān)鍵字關(guān)聯(lián)規(guī)那么，支持度，置信度，apriri1引言關(guān)聯(lián)規(guī)那么挖掘就是在海量的數(shù)據(jù)中發(fā)現(xiàn)數(shù)據(jù)項(xiàng)之間的關(guān)系，是數(shù)據(jù)挖掘領(lǐng)域中研究的熱點(diǎn)問題。1993年agraal等人1首先提出了交易數(shù)據(jù)庫中不同商品之間的關(guān)聯(lián)規(guī)那么挖掘，并逐漸引起了專家

2、、學(xué)者的重視。關(guān)聯(lián)規(guī)那么挖掘問題可以分為：發(fā)現(xiàn)頻繁工程集和生成關(guān)聯(lián)規(guī)那么兩個(gè)子問題，其中發(fā)現(xiàn)所有的頻繁工程集是生成關(guān)聯(lián)規(guī)那么的基矗近年來，發(fā)現(xiàn)頻繁工程集成為了關(guān)聯(lián)規(guī)那么挖掘算法研究的重點(diǎn)，在經(jīng)典的apriri算法的根底上提出里大量的改良算法。savasere等2設(shè)計(jì)了基于劃分(partitin)的算法，該算法可以高度并行計(jì)算，但是進(jìn)程之間的通信是算法執(zhí)行時(shí)間的主要瓶頸；park等3通過實(shí)驗(yàn)發(fā)現(xiàn)尋找頻集主要的計(jì)算是在生成頻繁2-項(xiàng)集上，利用這個(gè)性質(zhì)park等引入雜湊hash技術(shù)來改良產(chǎn)生頻繁2-項(xiàng)集的方法，該算法顯著的進(jìn)步了頻繁2-項(xiàng)集的發(fā)現(xiàn)效率；annila等4提出：基于前一遍掃描得到的信息，

3、對(duì)此仔細(xì)地作組合分析，可以得到一個(gè)改良的算法了。針對(duì)annila的思想tivnen5進(jìn)一步提出：先使用從數(shù)據(jù)庫中抽取出來的采樣得到一些在整個(gè)數(shù)據(jù)庫中可能成立的規(guī)那么，然后對(duì)數(shù)據(jù)庫的剩余局部驗(yàn)證這個(gè)結(jié)果。tivnen的算法相當(dāng)簡單并顯著地減少了i/代價(jià)，但是一個(gè)很大的缺點(diǎn)就是產(chǎn)生的結(jié)果不準(zhǔn)確，存在數(shù)據(jù)扭曲(dataske)。上述針對(duì)經(jīng)典apriri算法的改良算法在生成頻繁工程集時(shí)都需要屢次掃描數(shù)據(jù)庫，沒有顯著的減少i/的代價(jià)。本文在分析了經(jīng)典的apriri算法的根底上，給出了一種改良的方法，該方法采用轉(zhuǎn)置矩陣的策略，只掃描一次數(shù)據(jù)庫即完成頻繁工程集的發(fā)現(xiàn)，在工程集長度較大時(shí)，性能明顯進(jìn)步。2ap

4、riri算法2.1根本概念設(shè)i=i1,i2,i是二進(jìn)制文字的集合，其中的元素稱為項(xiàng)(ite)。定義交易(transatin)t為項(xiàng)的集合，并且ti，定義d為交易t的集合。設(shè)x是i中假設(shè)干項(xiàng)的集合，假如xt，那么稱交易t包含x。工程集中包含項(xiàng)的個(gè)數(shù)成為工程集長度。關(guān)聯(lián)規(guī)那么是形如xy的蘊(yùn)涵式，這里xi,yi，并且xy=f。規(guī)那么xy在交易數(shù)據(jù)庫d中的支持度supprt是交易集合中包含x和y的交易數(shù)與所有交易數(shù)之比，記為supprt(xy)，即supprt(xy)=|t:xyt，td|/|d|。規(guī)那么xy在交易集中的置信度nfidene是指包含x和y的交易數(shù)與包含x的交易數(shù)之比，記為nfidene

5、(xy)，即nfidene(xy)=|t:xyt，td|/|t:xt，td|。給定一個(gè)交易集d，挖掘關(guān)聯(lián)規(guī)那么就是找出支持度和置信度分別大于用戶給定的最小支持度(insup)和最小置信度(innf)的關(guān)聯(lián)規(guī)那么。2.2根本思想1994年agraal等人在工程集格空間理論的根底上提出了用于發(fā)現(xiàn)頻繁工程集的apriri算法。該算法采用“逐層搜索的迭代方法，用k-項(xiàng)集生成(k+1)-項(xiàng)集。首先，掃描數(shù)據(jù)庫計(jì)算出頻繁1-項(xiàng)集的集合記為：l1；然后，執(zhí)行下面的迭代過程計(jì)算頻繁k-項(xiàng)集，直到生成頻繁k-項(xiàng)集的集合記為：lk為空：連接：lk-1進(jìn)展自連接運(yùn)算,生成候選k-項(xiàng)集的集合記為：k。所有的頻繁k-項(xiàng)

6、集都包含在k集合中。剪枝：生成的k是lk的超集，掃描數(shù)據(jù)庫計(jì)算k中每個(gè)候選工程集的支持度，支持度大于用戶給定最小支持度的候選k-工程集就是頻繁k-工程集。通過上述的迭代過程，可以發(fā)現(xiàn)工程集i在給定數(shù)據(jù)庫d中滿足最小支持度的所有頻繁工程集。2.3算法分析apriri算法在執(zhí)行“連接-剪枝的迭代過程中，需要屢次掃描數(shù)據(jù)庫，假如生成的頻繁工程集中含有10-項(xiàng)集，那么需要掃描10遍數(shù)據(jù)庫，增大了i/負(fù)載。并且在迭代過程中，候選工程集合k是以指數(shù)速度增長的，lk-1自連接會(huì)產(chǎn)生大量的候選k-工程集，例如有104個(gè)1-項(xiàng)集，自連接后就可以產(chǎn)生大約107個(gè)候選2-項(xiàng)集。這些都嚴(yán)重影響了apriri算法的效率

7、。3改良的apriri算法3.1改良思想apriri算法在迭代過程中屢次掃描數(shù)據(jù)庫和產(chǎn)生大量的候選工程集形成了算法的性能瓶頸。為了進(jìn)步算法的效率本文進(jìn)展如下改良：數(shù)據(jù)庫d中每個(gè)交易t都有一個(gè)唯一的編號(hào)tid。定義k-項(xiàng)集rk=xk，tids(xk)，其中xk=(ij1,ij2,ijk)，ij1,ij2,ijki，j1j2jk，tids(xk)是數(shù)據(jù)庫中所有包含xk的交易t的編號(hào)tid的集合，即為：tids(xk)=tid:xkt，tid,td。根據(jù)上面的定義k-工程集rk的支持度可以表示為：supprt(rk)=|tids(xk)|/|d|=|tid:xkt，tid,td|/|d|。rk的支持

8、數(shù)supnu(rk)=supprt(rk)*|d|=|tids(xk)|。lk表示k-項(xiàng)集的集合。改良的apriri算法仍然采用“逐層搜索的迭代方法，迭代過程的“連接-剪枝運(yùn)算定義如下：連接：設(shè)兩個(gè)(k-1)-項(xiàng)集：lk-1(i)=xk-1，tids(xk-1)lk-1，lk-1(j)=yk-1，tids(yk-1)lk-1，ij。假如xk-1和yk-1的前k-2項(xiàng)相等，即：xk-1k-2yk-1k-2，那么(k-1)-項(xiàng)集連接：lk-1(i)lk-1(j)=xk-1yk-1,tids(xk-1)tids(yk-1)=xk，tids(xk)=rklk；否那么，不進(jìn)展連接運(yùn)算，因?yàn)楫a(chǎn)生的結(jié)果不是

9、重復(fù)，就是非頻繁工程集，這樣可減少計(jì)算量。剪枝：計(jì)算k-項(xiàng)集的支持?jǐn)?shù)，根據(jù)上面的定義supnu(rk)=|tids(xk)|，該計(jì)算過程不需要再掃描數(shù)據(jù)庫，防止了i/操作，進(jìn)步了算法的效率。假如supnu(rk)insupnu，那么xk,|tids(xk)|l；否那么，從集合lk中刪除rk。3.2改良的算法描繪輸入：數(shù)據(jù)庫d，最小支持?jǐn)?shù)insupnu輸出：d中的頻繁工程集l算法描繪：l1=findfrequentneitesets(d);/掃描數(shù)據(jù)庫d生成1-項(xiàng)集的集合l1。freahneitesetx1,tids(x1)l1/生成頻繁1-項(xiàng)集的集合if(|tids(x1)|insupnu)l

10、=lx1,|tids(x1)|;elsel1=l1-x1,tids(x1);fr(k=2;lk-1;k+)lk=lk-1lk-1;freahk_itesetxk,tids(xk)lkif(|tids(xk)|insupnu)l=lxk,|tids(xk)|;elselk=lk-xk,tids(xk);returnl;3.3例舉設(shè)數(shù)據(jù)庫d表1所示，最小支持?jǐn)?shù)insupnu=4，運(yùn)行改良的算法的過程如下圖：4總結(jié)改良的apriri算法，只是在生成l1時(shí)進(jìn)展了一次數(shù)據(jù)庫掃描，在之后的迭代過程中不需要掃描數(shù)據(jù)庫。與文獻(xiàn)2，3，4，5中提出的改良算法相比，使用本文提出的算法大大降低了i/負(fù)載，使得頻繁工

11、程集的發(fā)現(xiàn)速度大大進(jìn)步，尤其是在工程集長度較大的情況下。算法的迭代過程不需要復(fù)雜的計(jì)算，工程集連接僅僅使用集合的并、交運(yùn)算即可完成，使得該算法易于實(shí)現(xiàn)，相信該算法具有一定的理論與實(shí)用價(jià)值。但是該算法也有缺乏：為了減少i/負(fù)載，要求在第一次掃描時(shí)把所有的信息裝入內(nèi)存，雖然本算法對(duì)數(shù)據(jù)庫進(jìn)展編碼，以二元組的形式存儲(chǔ)項(xiàng)集，但是數(shù)據(jù)挖掘都是基于海量數(shù)據(jù)的，因此，算法運(yùn)行時(shí)需要大量內(nèi)存，對(duì)此將在今后的研究中進(jìn)展改良。參考文獻(xiàn)1r.agraal,t.iielinski,anda.sai.iningassiatinrulesbeteensetsfitesinlargedatabases.preedingsf

12、theasigdnferenenanageentfdata,pp.207-216,19932a.savasere,e.ieinski,ands.navathe.aneffiientalgrithfriningassiatinrulesinlargedatabases.preedingsfthe21stinternatinalnferenenverylargedatabase,19953j.s.park,.s.hen,andp.s.yu.aneffetivehash-basedalgrithfriningassiatinrules.preedingsfasigdinternatinalnferenenanageentfdata,pages175-186,sanjse,a,ay19954h.annila,h.tivnen,anda.verka.effiientalgrithfrdisveringassiatinrules.aaairkshpnknledgedisveryindatabases,1994,pp.181-1925h.tivnen.saplinglargedataba