一種改進(jìn)Ａｐｒｉｏｒｉ的個(gè)性化信息推薦算法

摘要：對(duì)現(xiàn)有的Apriori算法進(jìn)行改進(jìn)，用分治策略引入哈希技術(shù)的方法完成了壓縮侯選集，減少頻繁掃描數(shù)據(jù)庫(kù)的次數(shù)，克服了原有關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法生成頻繁集比較大，且需要反復(fù)掃描數(shù)據(jù)庫(kù)的問(wèn)題。

關(guān)鍵詞：Web數(shù)據(jù)挖掘；網(wǎng)站個(gè)性化信息推薦；關(guān)聯(lián)規(guī)則

中圖分類(lèi)號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)24-1265-02

A Personalized Information Recommendation of Improved the Apriori Algorithm

YANG Jie

(Zhejiang Financial Professional College， Hangzhou 310020， China)

Abstract: This paper improved the apriori algorithm， complete the compress reserve by introducing the Hash technoloy， reduce the times of scanning the data base，overcome the problem that the data mining algorithm about association rules produce the big frequency collection and scan the database again and again.

Key words: web data mining; web personalized information recommendation; association rules

1 引言

隨著網(wǎng)絡(luò)信息技術(shù)的快速發(fā)展，網(wǎng)絡(luò)中的信息量越來(lái)越大，Internet出現(xiàn)了“信息爆炸”的現(xiàn)象。在這種背景下，用戶可能在花費(fèi)了大量的時(shí)間后依然無(wú)法獲取自己所需的信息資源，即產(chǎn)生“信息迷航”現(xiàn)象[1-4]。因此，通過(guò)識(shí)別不同用戶的需求特點(diǎn)，以此采用個(gè)性化的服務(wù)策略和方式，將很好解決這個(gè)問(wèn)題。

2 Apriori算法

Apriori等在1993年設(shè)計(jì)了一個(gè)基本算法Apriori[5]，提出了挖掘關(guān)聯(lián)規(guī)則的一個(gè)重要的基于兩階段頻集思想的方法，是最典型的層次算法，是布爾關(guān)聯(lián)規(guī)則采掘算法中最成功的一類(lèi)算法。其核心技術(shù)為其它各類(lèi)布爾關(guān)聯(lián)規(guī)則采掘算法所廣泛采用。算法的思想是：如果說(shuō)S是頻繁項(xiàng)集，對(duì)于S的任意非空子集L，我們就可以通過(guò)計(jì)算可信度，也就是：conf support(S)/support(L)，并通過(guò)conf≥miniconf(最小可信度)來(lái)確定規(guī)則L→(S-L)是否確立(該規(guī)則由于S是頻繁項(xiàng)集故肯定具有最小支持度)。

例如：ABCD是頻繁項(xiàng)集，AB是它子集

如果conf=support(ABCD)/support(AB)≥miniconf(最小可信度)

那么規(guī)則AB→CD是成立的，否則不成立。

具體到頁(yè)面會(huì)話中，S是頻繁項(xiàng)集即S中的頁(yè)面是一次訪問(wèn)中經(jīng)常同時(shí)訪問(wèn)的頁(yè)面，而訪問(wèn)序列中最后的一個(gè)頁(yè)面往往是用戶的訪問(wèn)目的。所以用頻繁項(xiàng)集產(chǎn)生所需的規(guī)則時(shí)，主要導(dǎo)出S的前n-1個(gè)頁(yè)面到最后一個(gè)頁(yè)面的規(guī)則，如果此規(guī)則滿足最小可信度，將此規(guī)則存入模式庫(kù)中。

3 Apriori算法的改進(jìn)

從Apriori算法的思路中可以看出，當(dāng)有相當(dāng)數(shù)量的頻繁1項(xiàng)集，Apriori會(huì)產(chǎn)生大量的候選集，而且可能需要重復(fù)的掃描數(shù)據(jù)庫(kù)，這無(wú)疑降低了算法的效率，本文提出的算法是通過(guò)分治策略引入哈希技術(shù)來(lái)改進(jìn)產(chǎn)生頻繁項(xiàng)目集，并且用數(shù)據(jù)查詢語(yǔ)言實(shí)現(xiàn)關(guān)聯(lián)規(guī)則挖掘算法。要得出用戶的頻繁訪問(wèn)路徑，如果用戶每次訪問(wèn)的最大向前引用都很長(zhǎng)的話，那就需要生成若干的k項(xiàng)集，產(chǎn)生大量的候選項(xiàng)目集，每次需要重復(fù)的多次的掃描同一個(gè)事務(wù)庫(kù)，我們提出一種改進(jìn)策略。為了討論方便，這里對(duì)I中的每個(gè)項(xiàng)目用其項(xiàng)目編號(hào)來(lái)代替。和前面一樣，把所有頻繁k項(xiàng)目集的集合記為L(zhǎng)k，比如L1為所有頻繁1項(xiàng)目集的集合。這里我們假定交易數(shù)據(jù)庫(kù)中的交易以及在算法中出現(xiàn)的任一個(gè)項(xiàng)目集中的項(xiàng)目都是按照項(xiàng)目編號(hào)順序排好的。在后面的算法中，我們?nèi)菀卓吹剑灰ＷC開(kāi)始時(shí)也就是2項(xiàng)目集中的項(xiàng)目是有序的，那么算法的執(zhí)行將自動(dòng)保證任一個(gè)項(xiàng)目集也是有序的。

通過(guò)利用哈希技術(shù)通過(guò)構(gòu)建一個(gè)相當(dāng)小的C2以產(chǎn)生更小的L2來(lái)導(dǎo)出C3。如果C2很龐大，數(shù)據(jù)庫(kù)就不能有效修剪。此步之后，Li的大小隨i值的增大迅速減小，從而導(dǎo)致很小的Li+1，這樣對(duì)應(yīng)的開(kāi)銷(xiāo)就小得多，極大的提高了整個(gè)過(guò)程的執(zhí)行效率。

哈希表的優(yōu)點(diǎn)就是避免反復(fù)查找的過(guò)程，通過(guò)定址的方法直接找到要查找的數(shù)據(jù)，通常通過(guò)設(shè)計(jì)一個(gè)哈希函數(shù)，它是一個(gè)映象，只要使得任何關(guān)鍵字由此所得的哈希函數(shù)值都落在表長(zhǎng)允許范圍之內(nèi)就可以。基本思路如下：

1) 和Apriori的思想一樣，首先生成候選1—項(xiàng)目集Cl。算法簡(jiǎn)單地掃描事務(wù)數(shù)據(jù)庫(kù)，對(duì)每一個(gè)項(xiàng)目計(jì)數(shù)。

2) 設(shè)定最小事務(wù)支持?jǐn)?shù)(即min_support)，可以由存儲(chǔ)過(guò)程來(lái)計(jì)算，也可以由用戶自己指定。確定頻繁1—項(xiàng)目集的集合L1，如下表。頻繁項(xiàng)目集L1中的任何一個(gè)業(yè)務(wù)都大于或等于最小支持度。

3) 產(chǎn)生候選2—項(xiàng)目集。算法使用L1∞L1產(chǎn)生候選項(xiàng)目集C2。C2中的每一個(gè)項(xiàng)目集是對(duì)兩個(gè)屬于L1的頻繁項(xiàng)目集做一個(gè)連接來(lái)產(chǎn)生的。

4)掃描事務(wù)數(shù)據(jù)庫(kù)，計(jì)算C2中每個(gè)候選項(xiàng)目集的支持?jǐn)?shù)，用一個(gè)臨時(shí)表存放C2。

5) 選出事務(wù)中每個(gè)業(yè)務(wù)不小于最小支持度的事務(wù)，從而確定頻繁2項(xiàng)目集的集合L2，并計(jì)算其事務(wù)對(duì)應(yīng)的哈希函數(shù)與項(xiàng)目數(shù)2組合。

6) 產(chǎn)生3項(xiàng)候選集的集合C3，利用Apriori算法的特點(diǎn)，采用剪枝技術(shù)，刪除所有其子集不是頻繁項(xiàng)目集的候選項(xiàng)目集，從而大大縮減了3項(xiàng)候選集的大小，為生成頻繁項(xiàng)目集L3提高效率。

7) 生成頻繁3—項(xiàng)目集L3，計(jì)算每條事務(wù)的支持?jǐn)?shù)。

8) 如此循環(huán)下去，不斷生成候選集，再由此生成頻繁項(xiàng)目集，直到候選項(xiàng)為空。

運(yùn)用哈希算法主要是為生成下一個(gè)候選集過(guò)濾掉不需要得項(xiàng)目集。當(dāng)掃描數(shù)據(jù)庫(kù)來(lái)計(jì)算候選k項(xiàng)集得支持度得時(shí)候，運(yùn)用哈希技術(shù)來(lái)預(yù)先存儲(chǔ)(k+1)項(xiàng)候選集，也就是經(jīng)過(guò)一些修剪后把所有可能的(k+1)項(xiàng)集hash在一個(gè)hash表中。Hash表中每個(gè)hash單元由一個(gè)數(shù)字組成，該數(shù)字代表迄今有多少項(xiàng)集被hash到該單元。位矢量是基于hash表構(gòu)造的，如果Hash表中相應(yīng)的數(shù)目的個(gè)數(shù)大于或者等于s的話，對(duì)應(yīng)的位的值就設(shè)為1，否則為0。

4 實(shí)驗(yàn)分析

圖1用實(shí)例對(duì)Apriori算法進(jìn)行分析。第一次迭代中，Apriori算法簡(jiǎn)單的掃描所有事務(wù)，計(jì)算每一項(xiàng)的出現(xiàn)次數(shù)，得到了候選1項(xiàng)集Cl，假設(shè)事務(wù)的最小支持度為2，那么頻繁1項(xiàng)集L1，就由滿足最小支持度要求的候選1項(xiàng)集構(gòu)成。Apriori算法利用L1∞L1生成候選集C2。接下來(lái)，掃描數(shù)據(jù)庫(kù)中10個(gè)事務(wù)，計(jì)算C2中每個(gè)候選集的支持度。然后，基于C2中每個(gè)候選2項(xiàng)集的支持度可以確定頻繁2項(xiàng)集L2。候選集C3由L2產(chǎn)生，過(guò)程如下：L2中具有相同第一個(gè)項(xiàng)目的兩個(gè)頻繁2項(xiàng)集{AB}和{AC}首先識(shí)別出來(lái)。接著，Apriori檢查由前面兩個(gè)項(xiàng)目{AB}和{AC}組成的2項(xiàng)集{BC}是否構(gòu)成一個(gè)頻繁2項(xiàng)集。因?yàn)閧BC}本身是一個(gè)頻繁2項(xiàng)集，于是可以得到{ABC}的所有子集都是頻繁的，于是{ABC}成為一個(gè)候選3項(xiàng)集。同理可得{ABE}也是一個(gè)候選3項(xiàng)集。這就是利用上文所說(shuō)的Apriori性質(zhì)進(jìn)行連接和剪枝的過(guò)程。從L3中無(wú)法構(gòu)造候選4項(xiàng)集，此時(shí)算法終止。

從這個(gè)算法的過(guò)程來(lái)看，產(chǎn)生盡可能小的候選集Ci是很重要的，因?yàn)樵趻呙枵麄€(gè)數(shù)據(jù)庫(kù)的過(guò)程中要計(jì)算Ci中每一個(gè)項(xiàng)目的支持度。

圖2給出一個(gè)具體應(yīng)用哈希思想的例子。構(gòu)造哈希表的目的就是通過(guò)散列技術(shù)來(lái)壓縮候選集，那么哈希表的構(gòu)造方法在一定程度上決定了散列的效果。本文采用了除留取余法構(gòu)造hash函數(shù)：(x*factor+y) mod hashtblsize。顯然，兩個(gè)未定的參數(shù)：hash表的表長(zhǎng)和factor系數(shù)是決定散列效果的重要因素。因?yàn)椋绻１淼谋黹L(zhǎng)較小，那么散列的結(jié)果就是哈希表的每個(gè)bucket中都有多個(gè)候選集，如果每個(gè)bucket的計(jì)數(shù)都大于最小支持度，那么哈希表無(wú)法過(guò)濾掉任何一項(xiàng)，那么它不但沒(méi)什么壓縮過(guò)濾作用，而且構(gòu)造的過(guò)程還消耗了時(shí)間。而factor系數(shù)是個(gè)不確定的因素，例如，我們?nèi)=3，y=2，當(dāng)hashtblsize=10的時(shí)候，無(wú)論factor取10， 20， 30結(jié)果都相同，而當(dāng)hashtblsize=20的時(shí)候，結(jié)果就會(huì)產(chǎn)生差異。在實(shí)驗(yàn)分析一節(jié)我們通過(guò)實(shí)驗(yàn)對(duì)相同測(cè)試集，在相同最小支持度，不同表長(zhǎng)的情況下，運(yùn)用該算法產(chǎn)生的相關(guān)結(jié)果進(jìn)行分析，比較結(jié)果，我們可以得到，當(dāng)hash的表長(zhǎng)越長(zhǎng)時(shí)，散列的效果越好。而且我們驗(yàn)證了這樣的結(jié)論：初始候選集的生成，尤其是頻繁2項(xiàng)集，是提高關(guān)聯(lián)規(guī)則挖掘效率的關(guān)鍵。用hash表有效的生成頻繁2項(xiàng)集提高了算法效率。

5 結(jié)束語(yǔ)

針對(duì)目前關(guān)聯(lián)規(guī)則的經(jīng)典算法產(chǎn)生的侯選集較大、需要掃描的數(shù)據(jù)量較多的現(xiàn)狀，利用哈希技術(shù)和分治結(jié)合的方法，對(duì)現(xiàn)有Apriori算法進(jìn)行改進(jìn)，實(shí)現(xiàn)提高挖掘效率，提高給出推薦頁(yè)面的速度的目的。

參考文獻(xiàn)：

[1] 汪曉巖，胡慶生，莊鎮(zhèn)泉. 基于關(guān)聯(lián)規(guī)則挖掘的個(gè)性化智能推薦服務(wù)[J]. 計(jì)算機(jī)科學(xué)，2002，29(7):63-65.

[2] 徐寶文，張衛(wèi)豐. 數(shù)據(jù)挖掘技術(shù)在Web預(yù)取中的應(yīng)用研究[J]. 計(jì)算機(jī)學(xué)報(bào)，2001，24(4):89-91.

[3] 許兆新，周雙娥，郝燕玲. 最優(yōu)關(guān)聯(lián)規(guī)則的形式和挖掘思想的研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2001，37(20):118-119.

[4] 王運(yùn)峰，張蕾. 數(shù)據(jù)庫(kù)中關(guān)聯(lián)規(guī)則的并行挖掘算法[J]. 計(jì)算機(jī)工程與應(yīng)用，2001，37(16):99-100.

[5] 張仁平，卜淮原. 關(guān)聯(lián)規(guī)則挖掘快速更新算法的研究和實(shí)現(xiàn)[J]. 計(jì)算機(jī)工程與應(yīng)用，2001，37(6):101-103.