一種改進(jìn)的Apriori算法

趙軍民,張向娟,高 蔚

(河南城建學(xué)院,河南平頂山467036)

1 關(guān)聯(lián)規(guī)則簡(jiǎn)述

項(xiàng)集I={i1,i2,…,im}是m個(gè)不同項(xiàng)目的集合,項(xiàng)目ik(k=1,2,…,m)稱為數(shù)據(jù)項(xiàng),m為數(shù)據(jù)項(xiàng)集的長度,長度為k的數(shù)據(jù)項(xiàng)集稱為k-項(xiàng)集。一個(gè)事務(wù)T(Transaction)是數(shù)據(jù)項(xiàng)集中的一組項(xiàng)目的集合,即I的一個(gè)子集T?I。每個(gè)事務(wù)賦予一個(gè)唯一的標(biāo)志符TID,所有事務(wù)的全體就構(gòu)成一個(gè)事務(wù)數(shù)據(jù)庫D。一個(gè)關(guān)聯(lián)規(guī)則是形如X?Y的蘊(yùn)涵式,其中各項(xiàng)滿足X?I,Y?I且X∩Y=Φ。

定義1： 規(guī)則X?Y在事務(wù)數(shù)據(jù)庫D中的支持度(support)是指如果D中有s%的事務(wù)同時(shí)包含X和Y,那么稱關(guān)聯(lián)規(guī)則X?Y的支持度為s%,實(shí)際上支持度就是一個(gè)概率值,記為support(X?Y)=P(X∪Y)。

定義2： 規(guī)則X?Y在事務(wù)數(shù)據(jù)庫D中的信任度(confident)是指同時(shí)包含X和Y的事務(wù)數(shù)與包含X的事務(wù)數(shù)之比,即若項(xiàng)集X的支持度記為support(X),規(guī)則的信任度就為support(X∪Y)/support(X),用概率表示為confident(X?Y)=P(Y|X)。挖掘關(guān)聯(lián)規(guī)則的問題就是如何產(chǎn)生支持度和信任度分別大于用戶給定的最小支持度(minsupp)和最小信任度(minconf)的關(guān)聯(lián)規(guī)則。發(fā)現(xiàn)關(guān)聯(lián)規(guī)則需要經(jīng)過以下兩個(gè)步驟：1.找出所有頻繁項(xiàng)集;2.由頻繁項(xiàng)集生成滿足最小信任度的規(guī)則[1]。

2 Apriori算法簡(jiǎn)介

Apriori算法的核心是使用候選頻繁項(xiàng)集找頻繁項(xiàng)集即通過k-項(xiàng)集搜索(k+1)-項(xiàng)集。為了提高頻繁項(xiàng)集逐層產(chǎn)生的效率,Apriori算法定義了兩個(gè)性質(zhì)用于壓縮空間。

性質(zhì)1：頻繁項(xiàng)集的所有非空子集都必為頻繁項(xiàng)集。

性質(zhì)2：非頻繁項(xiàng)集的超集一定是非頻繁項(xiàng)集。此性質(zhì)用于找頻繁項(xiàng)集的兩個(gè)過程：連接和剪枝。(1)連接：通過Lk-1與自己連接產(chǎn)生候選k-項(xiàng)集的集合。該候選項(xiàng)集的集合記作Ck。(2)剪枝：Ck的成員可以是也可以不是頻繁項(xiàng)集,但所有的頻繁k-項(xiàng)集包含在Ck中,掃描數(shù)據(jù)庫,確定Ck中每個(gè)候選項(xiàng)集的計(jì)數(shù),計(jì)數(shù)值不小于最小支持度的所有候選項(xiàng)集是頻繁項(xiàng)集,從而確定Ck,為了壓縮空間,可以反用Apriori性質(zhì),任何非頻繁的(k-1)-項(xiàng)集都不可能是頻繁k-項(xiàng)集的子集。因此,如果一個(gè)候選k-項(xiàng)集的(k-1)-子集不在Ck-1中,則該候選項(xiàng)集也不可能是頻繁的。Apriori算法產(chǎn)生候選項(xiàng)集的開銷極大,特別是產(chǎn)生的候選2-項(xiàng)集對(duì)剪枝操作不但不起任何作用還需要占用大量的存儲(chǔ)空間[2]。

3 改進(jìn)算法的思想及其描述

本文提出的改進(jìn)算法思想是：根據(jù)第一次掃描數(shù)據(jù)庫的結(jié)果和以往經(jīng)驗(yàn)確定候選頻繁項(xiàng)集的項(xiàng)數(shù);同時(shí)以事務(wù)長度|TID|為標(biāo)準(zhǔn)將數(shù)據(jù)庫劃分為若干個(gè)子數(shù)據(jù)庫,避免對(duì)整個(gè)數(shù)據(jù)庫的重復(fù)掃描和產(chǎn)生大量的候選項(xiàng)集,提高了算法的效率。

定義3：事務(wù)長度：每個(gè)事務(wù)中所含項(xiàng)的個(gè)數(shù),記為|TID|,若某個(gè)事務(wù)中含有K項(xiàng),稱這個(gè)事務(wù)的長度為：|TID|=K.

性質(zhì)3：候選k-項(xiàng)集的長度k,滿足條件k≤|TID|max最大事務(wù)的長度,也就是說,候選項(xiàng)集都包含于某個(gè)事務(wù)之中。算法描述：

⑴掃描整個(gè)事務(wù)數(shù)據(jù)庫D,計(jì)算給定項(xiàng)集I中各個(gè)屬性項(xiàng)出現(xiàn)的概率P1,P2,…,Pm;同時(shí)計(jì)算不同長度|TID|出現(xiàn)的概率P1,P2,…,Pk,并以不同的|TID|為標(biāo)準(zhǔn)將數(shù)據(jù)庫劃分為若干個(gè)子數(shù)據(jù)庫。

a.定義數(shù)組I[m],初值設(shè)為0。掃描事務(wù)數(shù)據(jù)庫,求出各個(gè)屬性項(xiàng)i1,i2,…,im的獨(dú)立出現(xiàn)概率P1,P2,…,Pm與支持度;數(shù)組I中的每個(gè)數(shù)組元素I[1],I[2],…,I[m]記錄事務(wù)數(shù)據(jù)庫中各個(gè)屬性項(xiàng)i1,i2,…,im的獨(dú)立出現(xiàn)概率P1,P2,…,Pm的值。設(shè)定一個(gè)最小概率s,得到m個(gè)頻繁項(xiàng)集。

b.定義數(shù)組TID[n],初值設(shè)為0。掃描事務(wù)數(shù)據(jù)庫,求出各個(gè)事務(wù)長度|TID|(1,2,…,k)的獨(dú)立出現(xiàn)概率P1,P2,…,Pk。

⑵給定最小支持度,再次掃描整個(gè)事務(wù)數(shù)據(jù)庫D,將小于最小支持度的各個(gè)屬性項(xiàng)從事務(wù)記錄中刪除,同時(shí)再次計(jì)算不同長度的|TID|出現(xiàn)的概率P1,P2,…,Pk,并以不同的|TID|為標(biāo)準(zhǔn)重新將數(shù)據(jù)庫劃分為若干個(gè)子數(shù)據(jù)庫。比較刪除前后|TID|的概率,以概率最大的|TID|結(jié)合以往挖掘的經(jīng)驗(yàn),確定適合的候選項(xiàng)集的項(xiàng)數(shù)k。

⑶生成所有候選項(xiàng)集Ck,掃描|TID|≥k的子數(shù)據(jù)庫,由候選頻繁項(xiàng)集的支持度求出頻繁項(xiàng)集,如果生成的頻繁項(xiàng)集不理想,則重復(fù)步驟⑵、⑶,直到生成滿意的頻繁項(xiàng)集為止[3][4][5]。

4 算法模擬與對(duì)比

有一事務(wù)數(shù)據(jù)庫D,其中有10個(gè)事務(wù)記錄,預(yù)定義最小支持度為20%,生成其最大頻繁項(xiàng)集。

用原Apriori算法進(jìn)行挖掘,首先掃描事務(wù)數(shù)據(jù)庫D,計(jì)算候選1-項(xiàng)集的支持度,將支持度大于或等于20%的候選1-項(xiàng)項(xiàng)集作為頻繁1-項(xiàng)項(xiàng)集,頻繁1-項(xiàng)集與自身連接生成候選2-項(xiàng)集。再次掃描事務(wù)數(shù)據(jù)庫D計(jì)算候選2-項(xiàng)集的支持度,利用剪枝將不滿足最小支持度的候選2項(xiàng)集刪除,生成頻繁2-項(xiàng)集,頻繁2-項(xiàng)集再次與自身連接,生成候選3-項(xiàng)集。再一次掃描數(shù)據(jù)庫,使用相同的方法生成頻繁3-項(xiàng)集。頻繁3-項(xiàng)集再次與自身連接生成候選4-項(xiàng)集,第四次掃描數(shù)據(jù)庫計(jì)算候選4-項(xiàng)集的支持度,發(fā)現(xiàn)候選4-項(xiàng)集不滿足最小支持度的要求,從而得知最大頻繁項(xiàng)集為頻繁3-項(xiàng)集{abc}、{abd}、{abe}。原Apriori算法生成頻繁項(xiàng)集的過程如圖1所示。

圖1 Apriori算法生成頻繁項(xiàng)集過程

用改進(jìn)算法產(chǎn)生頻繁項(xiàng)集的過程如下：掃描事務(wù)數(shù)據(jù)庫,計(jì)算候選1-項(xiàng)集的支持度,將支持度大于或等于20%的候選1-項(xiàng)集作為頻繁1-項(xiàng)集,根據(jù)統(tǒng)計(jì)的事務(wù)長度的數(shù)字1、2、3、4出現(xiàn)的概率分別為0%,10%,70%,20%可知事務(wù)長度為3的事務(wù)占了70%,參考以前的挖掘經(jīng)驗(yàn),為了不使某些規(guī)則遺漏我們把候選項(xiàng)集的項(xiàng)數(shù)暫定為4,生成所有的候選4-項(xiàng)集,根據(jù)不同|TID|劃分的子數(shù)據(jù)庫計(jì)算各個(gè)候選項(xiàng)集的支持度,結(jié)果都不滿足最小支持度的條件,把候選項(xiàng)集的項(xiàng)數(shù)定為3重復(fù)以上過程,得出滿足最小支持度的頻繁3-項(xiàng)集{abc},{abd},{abe}。改進(jìn)算法生成頻繁項(xiàng)集的過程如圖2所示。

圖2 改進(jìn)算法生成頻繁項(xiàng)集過程

從以上的挖掘過程來看,Apriori算法要重復(fù)地對(duì)事務(wù)數(shù)據(jù)庫進(jìn)行掃描,每生成一個(gè)更長的候選項(xiàng)集就需要掃描數(shù)據(jù)庫一次,而且數(shù)據(jù)庫的長度沒有任何變化,這對(duì)海量數(shù)據(jù)來說將會(huì)造成時(shí)間的浪費(fèi)。在連接步過程中,生成了大量對(duì)以后無用的小項(xiàng)頻繁項(xiàng)集,造成了存儲(chǔ)空間的浪費(fèi)。特別是在生成小項(xiàng)候選集時(shí),數(shù)量是海量的。這些是Apriori算法存在的問題。改進(jìn)的算法在這些方面作了一些改進(jìn)：在頻繁項(xiàng)集的生成過程中,根據(jù)事務(wù)長度|TID|出現(xiàn)的概率及以往的經(jīng)驗(yàn)確定最終頻繁集的預(yù)計(jì)長度,只需要生成頻繁1-項(xiàng)集和待生成頻繁項(xiàng)集,避免生成海量小項(xiàng)集,節(jié)省了存儲(chǔ)空間并且減少了掃描數(shù)據(jù)庫的次數(shù)。以事務(wù)長度|TID|為標(biāo)準(zhǔn)將數(shù)據(jù)庫劃分為若干個(gè)子數(shù)據(jù)庫,避免了對(duì)整個(gè)數(shù)據(jù)庫的掃描,只需掃描子數(shù)據(jù)庫。與Apriori算法相比,改進(jìn)算法在時(shí)間和空間上效率都有所提高。

5 結(jié)束語

這種算法適合挖掘海量數(shù)據(jù)集的大項(xiàng)頻繁項(xiàng)集的關(guān)聯(lián)規(guī)則。但是算法中最終頻繁項(xiàng)集的設(shè)定是依據(jù)|TID|值的概率、以往的挖掘經(jīng)驗(yàn)及人們的購買習(xí)慣,因此有一定的主觀性。如果頻繁項(xiàng)集項(xiàng)數(shù)設(shè)定不合適,有可能會(huì)遺漏一些用戶感興趣的關(guān)聯(lián)規(guī)則,目前的解決方法是：根據(jù)人們的購買習(xí)慣、|TID|值及以往挖掘的經(jīng)驗(yàn)共同確定待挖掘頻繁項(xiàng)集的項(xiàng)數(shù),為了確保不遺漏一些用戶感興趣的關(guān)聯(lián)規(guī)則,可以在首次挖掘時(shí)設(shè)定較大的頻繁項(xiàng)集項(xiàng)數(shù)。

[1] 王小虎.關(guān)聯(lián)規(guī)則挖掘綜述[J].計(jì)算機(jī)工程與應(yīng)用,2003(33)：190-193.

[2] 李雄飛,李軍.數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)[M].北京：高等教育出版社,2003.

[3] 徐章艷,劉美玲,張師超,等.Apriori算法的三種優(yōu)化方法[J].計(jì)算機(jī)工程與應(yīng)用,2004(36)：190-192.

[4] 黃進(jìn),尹治本.關(guān)聯(lián)規(guī)則挖掘的Apriori算法的改進(jìn)[J].電子科技大學(xué)學(xué)報(bào),2003,32(1)：76-79.

[5] 劉巍,蔣華.挖掘關(guān)聯(lián)規(guī)則中Apriori算法的改進(jìn)與優(yōu)化[J].計(jì)算機(jī)與現(xiàn)代化,2006(11)：113-115.