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

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

2、逐漸引起了專家、學(xué)者的重視。關(guān)聯(lián)規(guī)則挖掘問題可以分為：發(fā)現(xiàn)頻繁項(xiàng)目集和生成關(guān)聯(lián)規(guī)則兩個(gè)子問題，其中發(fā)現(xiàn)所有的頻繁項(xiàng)目集是生成關(guān)聯(lián)規(guī)則的基礎(chǔ)。近年來，發(fā)現(xiàn)頻繁項(xiàng)目集成為了關(guān)聯(lián)規(guī)則挖掘算法研究的重點(diǎn)，在經(jīng)典的Apriori算法的基礎(chǔ)上提出里大量的改進(jìn)算法。Savasere等2設(shè)計(jì)了基于劃分(partition)的算法，該算法可以高度并行計(jì)算，但是進(jìn)程之間的通信是算法執(zhí)行時(shí)間的主要瓶頸；Park等3通過實(shí)驗(yàn)發(fā)現(xiàn)尋找頻集主要的計(jì)算是在生成頻繁2-項(xiàng)集上，利用這個(gè)性質(zhì)Park等引入雜湊（Hash）技術(shù)來改進(jìn)產(chǎn)生頻繁2-項(xiàng)集的方法，該算法顯著的提高了頻繁2-項(xiàng)集的發(fā)現(xiàn)效率；Mannila等4提出：基于前一

3、遍掃描得到的信息，對(duì)此仔細(xì)地作組合分析，可以得到一個(gè)改進(jìn)的算法了。針對(duì)Mannila的思想Toivonen5進(jìn)一步提出：先使用從數(shù)據(jù)庫(kù)中抽取出來的采樣得到一些在整個(gè)數(shù)據(jù)庫(kù)中可能成立的規(guī)則，然后對(duì)數(shù)據(jù)庫(kù)的剩余部分驗(yàn)證這個(gè)結(jié)果。Toivonen的算法相當(dāng)簡(jiǎn)單并顯著地減少了I/O代價(jià)，但是一個(gè)很大的缺點(diǎn)就是產(chǎn)生的結(jié)果不精確，存在數(shù)據(jù)扭曲(data skew)。 上述針對(duì)經(jīng)典Apriori算法的改進(jìn)算法在生成頻繁項(xiàng)目集時(shí)都需要多次掃描數(shù)據(jù)庫(kù)，沒有顯著的減少I/O的代價(jià)。本文在分析了經(jīng)典的Apriori算法的基礎(chǔ)上，給出了一種改進(jìn)的方法，該方法采用轉(zhuǎn)置矩陣的策略，只掃描一次數(shù)據(jù)庫(kù)即完成頻繁項(xiàng)目集的發(fā)現(xiàn)，

4、在項(xiàng)目集長(zhǎng)度較大時(shí)，性能明顯提高。2 Apriori算法2.1 基本概念 設(shè)I=i1, i2, im是二進(jìn)制文字的集合，其中的元素稱為項(xiàng)(item)。定義交易(transaction)T為項(xiàng)的集合，并且TI，定義D為交易T的集合。設(shè)X是I中若干項(xiàng)的集合，如果XT，那么稱交易T包含X。項(xiàng)目集中包含項(xiàng)的個(gè)數(shù)成為項(xiàng)目集長(zhǎng)度。 關(guān)聯(lián)規(guī)則是形如XY的蘊(yùn)涵式，這里XI, YI，并且XY=F。 規(guī)則XY在交易數(shù)據(jù)庫(kù)D中的支持度（support）是交易集合中包含X和Y的交易數(shù)與所有交易數(shù)之比，記為support(XY)，即support(XY)=|T:XYT，TD|/|D|。 規(guī)則XY在交易集中的置信度（co

5、nfidence）是指包含X和Y的交易數(shù)與包含X的交易數(shù)之比，記為confidence(XY)，即confidence(XY)=|T: XYT，TD|/|T:XT，TD|。給定一個(gè)交易集D，挖掘關(guān)聯(lián)規(guī)則就是找出支持度和置信度分別大于用戶給定的最小支持度(minsup)和最小置信度(minconf)的關(guān)聯(lián)規(guī)則。2.2 基本思想 1994年Agrawal等人在項(xiàng)目集格空間理論的基礎(chǔ)上提出了用于發(fā)現(xiàn)頻繁項(xiàng)目集的Apriori算法。該算法采用“逐層搜索”的迭代方法，用k-項(xiàng)集生成(k+1)-項(xiàng)集。首先，掃描數(shù)據(jù)庫(kù)計(jì)算出頻繁1-項(xiàng)集的集合（記為：L1）；然后，執(zhí)行下面的迭代過程計(jì)算頻繁k-項(xiàng)集，直到生成

6、頻繁k-項(xiàng)集的集合（記為：Lk）為空： 連接：Lk-1進(jìn)行自連接運(yùn)算,生成候選k-項(xiàng)集的集合（記為：C k）。所有的頻繁k-項(xiàng)集都包含在C k集合中。 剪枝：生成的C k是Lk的超集，掃描數(shù)據(jù)庫(kù)計(jì)算C k中每個(gè)候選項(xiàng)目集的支持度，支持度大于用戶給定最小支持度的候選k-項(xiàng)目集就是頻繁k-項(xiàng)目集。 通過上述的迭代過程，可以發(fā)現(xiàn)項(xiàng)目集I在給定數(shù)據(jù)庫(kù)D中滿足最小支持度的所有頻繁項(xiàng)目集。2.3 算法分析 Apriori算法在執(zhí)行“連接-剪枝”的迭代過程中，需要多次掃描數(shù)據(jù)庫(kù)，如果生成的頻繁項(xiàng)目集中含有10-項(xiàng)集，則需要掃描10遍數(shù)據(jù)庫(kù)，增大了I/O負(fù)載。并且在迭代過程中，候選項(xiàng)目集合Ck是以指數(shù)速度增長(zhǎng)

7、的，Lk-1自連接會(huì)產(chǎn)生大量的候選k-項(xiàng)目集，例如有104個(gè)1-項(xiàng)集，自連接后就可以產(chǎn)生大約107個(gè)候選2-項(xiàng)集。這些都嚴(yán)重影響了Apriori算法的效率。3 改進(jìn)的Apriori算法3.1 改進(jìn)思想 Apriori算法在迭代過程中多次掃描數(shù)據(jù)庫(kù)和產(chǎn)生大量的候選項(xiàng)目集形成了算法的性能瓶頸。為了提高算法的效率本文進(jìn)行如下改進(jìn)： 數(shù)據(jù)庫(kù)D中每個(gè)交易T都有一個(gè)唯一的編號(hào)TID。定義K-項(xiàng)集Rk=，其中Xk=(ij1, ij2, , ijk)，ij1, ij2, , ijk I，j1j2 jk，TIDS(Xk)是數(shù)據(jù)庫(kù)中所有包含Xk的交易T的編號(hào)TID的集合，即為：TIDS(Xk)=TID : XkT

8、， D。根據(jù)上面的定義k-項(xiàng)目集Rk的支持度可以表示為：support(Rk)=|TIDS(Xk)|/|D|=|TID : XkT， D| / |D|。Rk的支持?jǐn)?shù)supNum(Rk)=support(Rk)*|D|=|TIDS(Xk)|。Lk表示k-項(xiàng)集的集合。 改進(jìn)的Apriori算法依然采用“逐層搜索”的迭代方法，迭代過程的“連接-剪枝”運(yùn)算定義如下： 連接：設(shè)兩個(gè)(k-1)-項(xiàng)集：L k-1 (i)= Lk-1，L k-1 (j)= Lk-1，ij。如果Xk-1和Yk-1的前k-2項(xiàng)相等，即：Xk-1k-2 Yk-1k-2，則(k-1)-項(xiàng)集連接：L k-1 (i)L k-1 (j)=

9、 = =Rk Lk；否則，不進(jìn)行連接運(yùn)算，因?yàn)楫a(chǎn)生的結(jié)果不是重復(fù)，就是非頻繁項(xiàng)目集，這樣可減少計(jì)算量。 剪枝：計(jì)算k-項(xiàng)集的支持?jǐn)?shù)，根據(jù)上面的定義supNum(Rk)=|TIDS(Xk)|，該計(jì)算過程不需要再掃描數(shù)據(jù)庫(kù)，避免了I/O操作，提高了算法的效率。如果supNum(Rk)minSupNum，則 L；否則，從集合Lk中刪除Rk。3.2 改進(jìn)的算法描述 輸入：數(shù)據(jù)庫(kù)D，最小支持?jǐn)?shù)minSupNum 輸出：D中的頻繁項(xiàng)目集L 算法描述： L1 = findFrequentOneItemSets(D); /掃描數(shù)據(jù)庫(kù)D生成1-項(xiàng)集的集合L1。 for each OneItemSet L1 /生

10、成頻繁1-項(xiàng)集的集合 if (|TIDS(X1)| minSupNum) L = L ; else L1 = L1 - ; for (k=2; Lk-1; k+) Lk = Lk-1Lk-1; For each k_ItemSet Lk if (|TIDS(Xk)| minSupNum) L = L ; else Lk = Lk - ; return L;3.3 例舉 設(shè)數(shù)據(jù)庫(kù)D表1所示，最小支持?jǐn)?shù)minSupNum=4，運(yùn)行改進(jìn)的算法的過程如圖所示：4 總結(jié) 改進(jìn)的Apriori算法，只是在生成L1時(shí)進(jìn)行了一次數(shù)據(jù)庫(kù)掃描，在之后的迭代過程中不需要掃描數(shù)據(jù)庫(kù)。與文獻(xiàn)2，3，4，5中提出的改進(jìn)算

11、法相比，使用本文提出的算法大大降低了I/O負(fù)載，使得頻繁項(xiàng)目集的發(fā)現(xiàn)速度大大提高，尤其是在項(xiàng)目集長(zhǎng)度較大的情況下。算法的迭代過程不需要復(fù)雜的計(jì)算，項(xiàng)目集連接僅僅使用集合的并、交運(yùn)算即可完成，使得該算法易于實(shí)現(xiàn)，相信該算法具有一定的理論與實(shí)用價(jià)值。 但是該算法也有不足：為了減少I/O負(fù)載，要求在第一次掃描時(shí)把所有的信息裝入內(nèi)存，雖然本算法對(duì)數(shù)據(jù)庫(kù)進(jìn)行編碼，以二元組的形式存儲(chǔ)項(xiàng)集，但是數(shù)據(jù)挖掘都是基于海量數(shù)據(jù)的，因此，算法運(yùn)行時(shí)需要大量?jī)?nèi)存，對(duì)此將在今后的研究中進(jìn)行改進(jìn)。參考文獻(xiàn)1 R. Agrawal, T. Imielinski, and A. Swami. Mining associatio

12、n rules between sets of items in large databases. Proceedings of the ACM SIGMOD Conference on Management of data, pp. 207-216, 19932 A. Savasere, E. Omiecinski, and S. Navathe. An efficient algorithm for mining association rules in large databases. Proceedings of the 21st International Conference on Very large Database, 19953 J. S. Park, M. S. Chen, and P. S. Yu. An effective hash-based algorithm for mining association rules. Proceed