梁少剛

（寶雞職業(yè)技術(shù)學(xué)院 陜西 寶雞 721000）

0 引言

隨著計(jì)算機(jī)網(wǎng)絡(luò)、電子商務(wù)的發(fā)展，很多商業(yè)性網(wǎng)站中對(duì)于用戶的關(guān)注越來(lái)越多，因?yàn)榱私庥脩舻男枨蟛拍茉龈呔W(wǎng)站的收益，因此了解用戶瀏覽模式是一項(xiàng)重要的工作。如何從這些海量的訪問(wèn)信息中發(fā)現(xiàn)潛在的有用的信息，確定用戶瀏覽網(wǎng)頁(yè)的順序、頻繁訪問(wèn)哪些網(wǎng)頁(yè)，從而為用戶推薦網(wǎng)頁(yè)、推薦商品成為了一個(gè)新的研究課題。Web數(shù)據(jù)挖掘應(yīng)運(yùn)而生，Web數(shù)據(jù)挖掘就是從與WWW相關(guān)的資源和用戶瀏覽行為中抽取感興趣的、有用的模式和隱含的信息。Web上各種形式的文檔和用戶訪問(wèn)信息就構(gòu)成了Web數(shù)據(jù)挖掘的對(duì)象。

挖掘用戶訪問(wèn)模式常用算法有Web數(shù)據(jù)挖掘特有的用戶訪問(wèn)路徑模式挖掘算法(路徑分析技術(shù))和數(shù)據(jù)挖掘傳統(tǒng)算法,如關(guān)聯(lián)規(guī)則挖掘算法、序列模式挖掘算法等。而本文主要介紹如何利用Apriori算法來(lái)挖掘用戶的瀏覽模式。

1 Apriori算法概述

Apriori算法是由R.Agrawal等人提出的一種快速挖掘算法，是大多數(shù)關(guān)聯(lián)規(guī)則算法的基礎(chǔ)，它是一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。Apriori算法采用逐層搜索的迭代方法來(lái)找出所有的頻繁項(xiàng)目集，在第k次迭代過(guò)程中找出所有的頻繁k-項(xiàng)集Lk。該算法使用如下的Apriori性質(zhì)：一個(gè)項(xiàng)目集是頻繁項(xiàng)目集，則此項(xiàng)目集的所有子集構(gòu)成的項(xiàng)目集也一定是頻繁項(xiàng)目集；一個(gè)項(xiàng)目集是非頻繁項(xiàng)目集，則此項(xiàng)目集的所有超集(即包含此項(xiàng)目集的項(xiàng)目集)一定是非頻繁項(xiàng)目集。

Apriori算法的基本思想如下：C1=I，I為事務(wù)所包含的項(xiàng)目，掃描數(shù)據(jù)庫(kù)，得到頻繁1-項(xiàng)集L1，將L1中的項(xiàng)目集兩兩合并，產(chǎn)生C2，掃描數(shù)據(jù)庫(kù)，得到L2，此后在第k遍掃描中，則是首先利用Lk-1來(lái)生成Ck，若Ck=Φ，則算法結(jié)束，否則掃描數(shù)據(jù)庫(kù)得到Lk。在第k遍掃描中，第一步：連接步，通過(guò)Lk-1與自己連接來(lái)產(chǎn)生Ck（即侯選k-項(xiàng)集的集合）；第二步：剪枝步，Ck是Lk的超集，掃描數(shù)據(jù)庫(kù)，確定Ck中每個(gè)候選的計(jì)數(shù)，計(jì)數(shù)值大于等于最小支持度計(jì)數(shù)的所有候選項(xiàng)是頻繁的，從而屬于Lk，刪除不滿足條件的其候選項(xiàng)。

綜上所述，經(jīng)典的Apriori算法描述如算法1.1所示。算法1.1挖掘關(guān)聯(lián)規(guī)則的Apriori算法

輸入：事務(wù)數(shù)據(jù)庫(kù)D；最小支持度閾值min_sup輸出：D中的頻繁項(xiàng)集L Apriori算法自身雖然進(jìn)行了一定的優(yōu)化，但在實(shí)際應(yīng)用中還是存在一些問(wèn)題：

（1）需多次掃描事務(wù)數(shù)據(jù)庫(kù)，通過(guò)模式匹配檢查一個(gè)很大的侯選集合。由于挖掘的對(duì)象都是大型數(shù)據(jù)庫(kù)或數(shù)據(jù)倉(cāng)庫(kù)，這樣勢(shì)必影響算法的效率，要提高效率關(guān)鍵是減少數(shù)據(jù)庫(kù)遍歷的次數(shù)和數(shù)據(jù)庫(kù)的規(guī)模。

（2）可能產(chǎn)生大量的候選項(xiàng)集，不利于規(guī)則的產(chǎn)生。

為克服Apriori算法存在的問(wèn)題、提高算法效率，人們提出了許多Apriori算法的變形來(lái)優(yōu)化Apriori算法，如基于散列技術(shù)(散列項(xiàng)集計(jì)數(shù))、事務(wù)壓縮(壓所進(jìn)一步選代掃描的事務(wù)數(shù))、劃分(為找候項(xiàng)集劃分?jǐn)?shù)據(jù))、選樣(在給定數(shù)據(jù)的一個(gè)子集挖掘)、動(dòng)態(tài)項(xiàng)集技數(shù) (在掃描的不同點(diǎn)添加候選項(xiàng)集)等，這些算法從不同方面改善了Apriori算法的性能，提高了效率。

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

通過(guò)分析經(jīng)典的Apriori算法還有一些改進(jìn)算法的分析，可以看出，存在以下兩個(gè)問(wèn)題：

（1）更新支持度的時(shí)候，需要掃描數(shù)據(jù)庫(kù)，而此時(shí)，數(shù)據(jù)庫(kù)中有些項(xiàng)目已經(jīng)被證明是非頻繁的，可以不必掃描；有些事務(wù)根本不包括要尋找的項(xiàng)目，可以刪除。所以，減少事務(wù)的數(shù)目和修剪每次交易里的項(xiàng)目數(shù)也是提高算法性能的關(guān)鍵。

（2）Aprior算法在從k-項(xiàng)目集生成候選k+1-項(xiàng)目集時(shí)，采用的是連接操作，該操作要判斷是否前k-1項(xiàng)相同而第k項(xiàng)不同。這個(gè)操作占用了比較多的程序運(yùn)行時(shí)間，如果能減少比較次數(shù)，也可以提高算法的性能。

2.1 連接步的改進(jìn)

本文提出的連接步改進(jìn)算法：設(shè)l1和l2是Lk-1中的項(xiàng)集，項(xiàng)集中的項(xiàng)按它在整個(gè)數(shù)據(jù)庫(kù)中出現(xiàn)的頻率按升序排序，執(zhí)行連接 Lk-1×Lk-1時(shí)，若 l1[k-2]≠l2[k-2]，則停止對(duì) l1和 l2的連接操作，因?yàn)榇藭r(shí)產(chǎn)生的k-項(xiàng)集一定是冗余項(xiàng)集，以此來(lái)減少計(jì)算量。

證明：將Lk-1中的項(xiàng)按它在整個(gè)數(shù)據(jù)庫(kù)中出現(xiàn)的頻率按升序排序后，其中l(wèi)1[k-2]出現(xiàn)的個(gè)數(shù)應(yīng)該小于等于k-2，若l1[k-2]≠l2[k-2]，則 l1[k-2]出現(xiàn)的最大個(gè)數(shù)是 k-2。 而 Apriori算法的性質(zhì)有：如果(k-1)-頻繁項(xiàng)目集Lk-1中包含的單個(gè)項(xiàng)目I的個(gè)數(shù)小于k-1，則I不可能包含在頻繁k-項(xiàng)目集中。因此在 Lk-1×Lk-1時(shí)，若 l1[k-2]≠l2[k-2]，則 l1[k-2]不可能包含在頻繁k-項(xiàng)目集中，因此此時(shí)停止對(duì)l1和l2的連接操作。

因此對(duì)于算法1.1（輸入輸出均相同）我們可進(jìn)行如下的改變：

算法1.2對(duì)于連接步的改進(jìn)算法

2.2 剪枝步的改進(jìn)

由算法1.1中我們可以看出剪枝步的思想是，Ck是Lk的超集，掃描數(shù)據(jù)庫(kù)，確定Ck中每個(gè)候選的計(jì)數(shù)，計(jì)數(shù)值大于等于最小支持度計(jì)數(shù)的所有候選項(xiàng)是頻繁的，從而屬于Lk，刪除不滿足條件的其候選項(xiàng)。修剪步的改進(jìn)思想：先計(jì)算|Lk-1(i)|，其中，i∈I。即計(jì)算Lk-1中所有項(xiàng)目的頻度，再找出那些頻度小于k-1的項(xiàng)目，記為I/={i||Lk-1(i)|＜k-1}，再在Lk-1中去掉所有包含I/中元素的頻繁項(xiàng)目集而得到一個(gè)新的更小的 (k-1)-項(xiàng)頻繁項(xiàng)目集的集合L/k-1，再由L/k-1與自身相連接而直接生成候選k-項(xiàng)集的集合Ck。

證明：由Apriori算法的性質(zhì)可知，若k-項(xiàng)數(shù)據(jù)項(xiàng)目集I={i1,i2,…,ik}中，存在一個(gè) i∈I使得|Lk-1(i)|＜k-1 則 I不是頻繁項(xiàng)目集，其中|Lk-1(i)|表示(k-1)-項(xiàng)頻繁項(xiàng)目集的集合Lk-1中包含i的個(gè)數(shù)。假設(shè)I是k-項(xiàng)頻繁項(xiàng)目集，則它的k個(gè)(k-1)-項(xiàng)子集均在Lk-1中。則在由I生成的k個(gè) (k-1)-項(xiàng)子集中每一個(gè)項(xiàng)目i∈I共出現(xiàn)k-1次，而 |Lk-1(i)|＜k-1這與條件矛盾，故I不是頻繁項(xiàng)目集。

因此對(duì)于算法1.1（輸入輸出均相同）我們可進(jìn)行如下的改變：

算法1.3對(duì)于剪枝步的改進(jìn)算法

3 小結(jié)

本文詳細(xì)介紹了Apriori算法，并對(duì)Apriori算法的思想進(jìn)行了分析，在總結(jié)其不足后，提出了改進(jìn)的Apriori算法，從連接步和剪枝步兩部分提出了如何進(jìn)行改進(jìn)比給出了具體的設(shè)計(jì)思路。

[1]范明,孟小峰.數(shù)據(jù)挖掘概念與技術(shù)[M].北京:機(jī)械工業(yè)出版社,2001.

[2]周祥,鄭應(yīng)平,王令群.基于 Web的數(shù)據(jù)挖掘技術(shù)研究及其在電子商務(wù)中的應(yīng)用[J].電腦知識(shí)與技術(shù):學(xué)術(shù)交流,2005（11）.

[3]陳煉,孫金華,饒泓,廖遠(yuǎn),林渝.基于 Apriori改進(jìn)算法的 Web 日志挖掘支撐工具的實(shí)現(xiàn)[J].南昌大學(xué)學(xué)報(bào)：工科版,2007，29（2）.