利用改進的Apriori算法挖掘用戶瀏覽網頁模式

梁少剛

（寶雞職業技術學院 陜西 寶雞 721000）

0 引言

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

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

1 Apriori算法概述

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

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

綜上所述，經典的Apriori算法描述如算法1.1所示。算法1.1挖掘關聯規則的Apriori算法

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

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

（2）可能產生大量的候選項集，不利于規則的產生。

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

2 改進的Apriori算法

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

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

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

2.1 連接步的改進

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

證明：將Lk-1中的項按它在整個數據庫中出現的頻率按升序排序后，其中l1[k-2]出現的個數應該小于等于k-2，若l1[k-2]≠l2[k-2]，則 l1[k-2]出現的最大個數是 k-2。 而 Apriori算法的性質有：如果(k-1)-頻繁項目集Lk-1中包含的單個項目I的個數小于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的超集，掃描數據庫，確定Ck中每個候選的計數，計數值大于等于最小支持度計數的所有候選項是頻繁的，從而屬于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算法的性質可知，若k-項數據項目集I={i1,i2,…,ik}中，存在一個 i∈I使得|Lk-1(i)|＜k-1 則 I不是頻繁項目集，其中|Lk-1(i)|表示(k-1)-項頻繁項目集的集合Lk-1中包含i的個數。假設I是k-項頻繁項目集，則它的k個(k-1)-項子集均在Lk-1中。則在由I生成的k個 (k-1)-項子集中每一個項目i∈I共出現k-1次，而 |Lk-1(i)|＜k-1這與條件矛盾，故I不是頻繁項目集。

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

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

3 小結

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

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

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

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