利用改進的Apriori算法挖掘用戶瀏覽網(wǎng)頁模式

梁少剛

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

0 引言

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

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

1 Apriori算法概述

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

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

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

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

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

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

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

2 改進的Apriori算法

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

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

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

2.1 連接步的改進

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

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

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

算法1.2對于連接步的改進算法

2.2 剪枝步的改進

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

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

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

算法1.3對于剪枝步的改進算法

3 小結(jié)

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

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

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

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