基于篩選壓縮的類Ａｐｒｉｏｒｉ算法的研究

摘要：該文根據用戶的Web訪問路徑應用關聯規則和類Apriori算法挖掘出該用戶的頻繁訪問路徑，通過對Apriori算法和目前針對提高該算法效率的各種優化技術的詳細分析和研究，對類Apriori算法進行了改進，提出了基于篩選壓縮的類Apriori挖掘算法，并進行了模擬實驗，比較結果顯示基于篩選壓縮的類Apriori挖掘算法挖掘用戶頻繁遍歷路徑的效率高于類Apriori算法，最終可獲取用戶的頻繁遍歷路徑。

關鍵詞：Web日志挖掘；頻繁遍歷路徑；類Apriori算法；篩選壓縮

中圖分類號：TP301文獻標識碼：A文章編號：1009-3044(2008)34-2038-04

The Research Based on the Homo-Apriori of Riddling Compression Algorithm

ZHANG Li， SHENG Yun-yao

(Computer Sicence and Engineering Department， Changzhou Institute of Mechatronic Technology， Changzhou 213164， China)

Abstract: Basing on the user's Web access path frequent access sequences were mined by using the association rules and homo-Apriori algorithm. The Apriori algorithms of association rules and all kinds of optimized techniques which were designed to promote the algorithms efficiency were studied and discussed in detail here. Based on the basic， the homo-Apriori algorithm was improved and the homo-Apriori algorithm of riddling compression was proposed. And hasing carried on the simulation， the result demonstrats that the frequent access sequences mined by homo-Apriori algorithm of riddling compression is quickly than it mined by homo-Apriori. Eventually， the algorithm of users frequent access sequences is found.

Key words: Web log mining; Frequent access sequences; Homo-Apriori algorithm; Riddling Compression

1 引言

WWW的迅速發展，在給人們帶來豐富信息和極大便利的同時，也隨之產生了一些覓待解決的問題，個性化的信息服務和構建智能化Web站點便是其中之一。一方面，不同層次、不同愛好和使用目的的瀏覽者需要個性化的信息服務；另一方面，Web站點的經營和管理者為提高網站的聲譽和效益，需要了解客戶需要什么和想做什么。其中包括根據大多數客戶的共同興趣，開展有針對性的信息服務，以及對特定的用戶開展個性化的信息服務和電子商務活動。直接或間接地解決這個問題的途徑之一就是將數據挖掘技術應用于Web服務器日志的挖掘。從用戶在Web上瀏覽行為數據中獲取用戶的頻繁訪問路徑，根據用戶的頻繁訪問路徑改進站點的設計和服務。開展個性化信息服務和有針對性的電子商務活動和構建智能化Web站點。

2 類Apriori算法

Web日志挖掘經過了數據預處理、事務識別后，已經生成了事務數據庫，事務中包含了用戶的瀏覽路徑，也就是最大向前引用路徑MFP。找出MFP中所有頻繁遍歷路徑的過程與挖掘關聯規則時從事務數據庫中找出所有的頻繁項集比較類似。因此，可以利用Apriori算法的思想來實現頻繁遍歷路徑的發現過程。

為方便以后的論述，現約定如下：

定義1 事務的長度為其包含的頁面數，一個有k個頁面引用的事務稱為一個k引用。

定義2 引用s1，s2，…，sn包含k引用r1，r2，…，rk，如果存在i，使得1≤j

定義3 如果一個k引用序列r1，r2，…，rk滿足以下條件：

（包含r1，r2，……，rk序列的MFP數）/（所有的MFP數）×100%>minsupport

則稱為頻繁k引用。其中，minsupport是預先定義好的最小支持度（在有些場合用minsupport乘以所有的MFP數作為最小支持度）。有了頻繁k引用的定義，就可以定義它們的集合Lk是所有頻繁k引用的集合，Lk中每個成員有兩個項（k引用，支持度S）。Ck是候選頻繁k引用的集合，候選頻繁k引用也就是潛在的頻繁k引用，該集合中每個成員也有兩個項（k引用，支持度S）。

類Apriori算法描述：使用逐層迭代方法基于候選產生找出頻繁遍歷路徑

輸入：

D：事務數據庫

Minsupport：最小支持度計數閾值

輸出：

R：D中的頻繁項集

方法：

1) C1={所有的頁面引用};

2) L1={c∈C1|c.count≥minsupport};

3) For(k=2;Lk-l≠Φ;k++)

{

4) Ck=adv_gen(Lk-1);

5) For each 事務t∈D

{

6) Ct=subset(Ck，t);

7) for each 候選c∈Ct

8) c.count++;

}

9) Lk={c∈Ck|c.count≥minsupport};

}

10) return R=R∪Lk;

說明：c.count表示引用c在事務數據庫D中被包含的次數。假設項集用item表示，c.count相當于如下SQL語句：

select item from D group by item having count(*)≥minsupport

算法的前兩步（步驟1)2)）是統計所有含一個頁面的引用出現的次數，然后決定頻繁1引用集L1。在步驟3)～9)，Lk-1用于產生候選Ck，以找出Lk，其中k>=2。adv_gen()產生候選，該過程在下面描述。一旦產生了所有的候選就掃描數據庫（步驟5)）。對于每個事務，使用subset函數找出該事務中是候選的所有子集（步驟6)），并對每個這樣的候選累加計數（步驟7)8)）。最后，所有滿足最小支持度的候選（步驟9)）形成頻繁項集的集合R（步驟10)）。

該過程和挖掘關聯規則時的Apriori算法類似，但是在Apriori算法中，只要兩個k-1維最大項集有k-2個元素相同就可以合并成一個k維候選項。而在挖掘頻繁遍歷路徑時，引用中的頁面是有序的，因此不能簡單地只要k-2個元素相同就行了，需要作如下的處理：Lk-1中任意兩個不同的(k-1)引用s1，s2，…，sk-1和r1，r2，…，rk-1，如果r1，r2，…，rk-1包含s1，s2，…，sk-2或者s1，s2，…，sk-1包含r1，r2，…，rk-2（包含的定義參見前面定義2），也就是說這兩個(k-1)引用中一個去掉第一個元素，另一個去掉最后一個元素后完全相等，則這兩個(k-1)引用可以合并成一個k引用。

這樣通過Lk-1求Ck的過程，adv_gen()可以用如下的SQL語句說明：

insert into Ck

select P.item1，P.item2，…，P.itemk-1，Q.itemk-1 from Lk-1 P，Lk-1 Q

Where P.item1=Q.item2，P.item2=Q.item3，…，P.itemk-2=Q.itemk-1

在Apriori算法中，從Lk-1中求出所有的候選k維項目集后，函數adv_gen()還要進行修剪，修剪的原則是：如果一個k項目集的某一個(k-1)維子集不在Lk-1中，則該k維項目集需從Ck中刪除。例如，Lk-1={AB，BC}，則根據求候選項目集的算法，Ck={ABC}，然后進行修剪，發現ABC的一個2維子集AC不在Lk-1中，將ABC從Ck中刪除。但是，在挖掘頻繁k引用時，一個k引用r1，r2，…，rk只有兩個(k-1)子引用r1，r2，…，rk-1和r2，…，rk，只有當這兩個(k-1)子引用都在Lk-1內時，r1，r2，…，rk才可能從Lk-1選出來，因此在這里進行修剪是沒有意義的。

Subset()函數的參數是候選引用集Ck和某一事務t，結果返回這一事務t中包含的候選引用集，即

subset(Ck，t) = {c|c∈Ck∩c?哿t}

下面用此算法對某用戶的瀏覽路徑進行分析，找出頻繁遍歷路徑。

該數據庫中有6個事務，集|D|=6。這里設定最小支持度minsupport＝2。

操作步驟：

1) 掃描D，對每個候選計數，統計每個頁面的支持度產生候選1引用集C1，C1:{{{C}，6}，{{G}，2}，{{GG}，1}，{{L}，2}，{{W}，2}，{{WC}，2}}；

2)比較候選支持度計數與最小支持度計數，找到滿足最小支持度的頁面加入到L1中，L1:{{{C}，6}，{{G}，2}，{{L}，2}，{{W}，2}，{{WC}，2}}；

3) 為發現頻繁引用2的集合L2，使用L1連接L1產生候選2引用集C2，由于頁面引用具有順序性，所以這里不是Apriori算法中的組合，而是排列，C2:{{ {C G}，2}，{{C L}，2}，{{C W}，2}，{{C WC}，0}，{{G C}，0}，{{G L}，0}，{{G W}，0}，{{G WC}，0}，{{L C}，0}，{{L G}，0}，{{L W}，0}，{{L WC}，0}，{{W C}，0}，{{W G}，0}，{{W L}，0}，{{W WC}，2}，{{WC C}，0}，{{WC G}，0}，{{WC L}，0}，{{WC W}，0}}；

4) 比較候選支持度計數與最小支持度計數，找到滿足最小支持度的頁面加入到L2中，L2:{{{C G}，2}，{{C L}，2}，{{C W}，2}，{{W WC}，2}}；

5) 依次類推，直到某一次發現Lk=Φ循環結束。

6) 最后得到此用戶頻繁引用頁面C-W-WC。

3 Apriori算法的瓶頸

傳統Apriori算法有兩個致命的性能瓶頸：

多次掃描事務數據庫需要很大的I/O負載，對每次k循環侯選集Ck中的每個元素都必須通過掃描數據庫一次來驗證其是否加入Lk；假如有一個頻繁大項集包含10個項的話那么就至少需要掃描事務數據庫10遍。

可能產生龐大的侯選集由Lk-1產生k侯選集Ck是指數增長的例如104的1頻繁項集就有可能產生接近107個元素的2侯選集。如此大的候選集對時間和主存空間都是一種挑戰。

4 對類Apriori挖算法的改進

Apriori是一種寬度優先算法，通過對數據庫D的多趟掃描來發現所有的頻繁項目集。由于數據庫D一般是海量存儲，所以對數據庫D多趟掃描將耗費大量時間和內存空間，隨著數據庫海量增大，這也就成為Apriori算法的瓶頸。針對這一點，研究產生了多種改進方法，如基于哈希(hash)表技術、劃分數據、采樣技術、動態項集計數等方法，這些方法為改善己有算法提供許多可以借鑒的思想。日志數據庫中數據也是海量的，而且隨著時間的推移，日志數據庫中數據越來越多，Apriori算法的瓶頸同樣也制約著類Apriori算法的挖掘效率，因此這里引入了數據刪除技術及壓縮來提高類Apriori挖掘算法對日志數據庫挖掘的效率和適應能力，得到的基于篩選壓縮的類Apriori挖掘算法。

4.1 算法描述

基于篩選壓縮的類Apriori挖掘算法利用了以下兩個事實：

1) 對于己生成的事務數據庫D，任意一個項集I的出現支持度與規模小于I的事務無關。所以可以刪除規模小于I的事務記錄。

2) 由于不包含任何k項集的事務不可能包含任何一個(k+l)頻繁項集。因此在生成(k+l)頻繁項集之前對這樣的事務記錄進行刪除操作，以便來減少下次掃描事務數據庫的次數。

利用在關聯規則中的連接操作運算，對于由k項集生成(k+1)項集，則僅對最后一位進行表記錄添加和表記錄刪除操作，產生新的候選頻繁項，并及時對表中項進行支持度判斷。

可以用臨時表的添加刪除來完成頻繁項的生成，在頻繁數據項產生時，對于不能滿足的項馬上刪除，而不是在生成數據項后進行統計、刪除，從而減少了空間耗費。用D表示數據庫，用|T|表示數據庫中事務T的規模，即T中引用的個數。用|k|表示引用集k的長度。其算法過程描述如下：

第一步：生成事務數據庫（經過數據預處理和事務識別后，就生成了事務數據庫）。

第二步：掃描事務數據庫，從中找出所有的引用長度為|k|=1的項的支持度，形成原始的頻繁引用集，生成臨時表table_1。

第三步：刪除操作，刪除事務數據庫中所有的引用長度小于|k|的事務。以及刪除事務數據庫中所有的不包含任何k項頻繁引用的事務。

第四步：對k頻繁關聯引用進行連接操作，以生成(k+l)項頻繁關聯引用。以k項頻繁關聯引用為基礎，k引用的其它引用集的最后一引用依次添加進table_2和刪除。進行判斷，產生(k+l)項頻繁關聯引用。(該過程有兩重嵌套循環)

1) 取生成的候選引用集中(長度為|k|)第i=1個引用。

2) 取第j=i+1引用且最后一引用與第i個引用集最后一引用不同的引用合并成k+l引用添加進臨時表table_2中，生成了(k+1)引用集，并計算其支持度。若支持度大于最小支持度minsupport，則生成了第一個頻繁關聯引用，保存該頻繁關聯引用。

3) j=j+1，若j為k引用集最后一個記錄則轉到4)，否則轉2)。

4) i=i+l，若i為k引用集最后一個記錄則轉到5)，否則轉2)。

5) 所有符合條件的k+1引用集生成，則table_2 為k+l相關聯引用，根據需要可對其進行保存。

第五步：k=k+l，把table_2 賦給bable_1，依次重復執行第三步，直到k引用集為Φ時終結。

4.2 算法模擬分析比較

利用表1(某用戶中的事務數據)將篩選壓縮的類Apriori挖掘算法與類Apriori算法進行比較，可得到類Apriori算法與基于臨時表的算法的掃描規模與空間耗費分析。

算法執行過程：

1) 掃描一遍數據庫D，對每個候選計數，統計每個頁面的支持度得到引用長度為1的引用及其支持度（S），生成表table_1。篩選出S>=minsupport的引用生成表table_2。這里假設最小支持度為0.2，這樣就可以確定table_2，table_2:{ {{C}，1}，{{G}，0.33}，{{L}，0.33}，{{W}，0.33}，{{WC}，0.33}}；

2) 刪除數據庫中引用不大于1的TID，表table_2的內容賦給table_1。這里所有TID都大于1，所以數據庫中記錄沒有變化；

3) 為發現頻繁引用2的集合L2，使用L1連接L1產生候選2引用集C2，并獲得其支持度。由于頁面引用具有順序性，所以這里是排列；

4) 比較候選支持度計數與最小支持度計數，找到滿足最小支持度的頁面加入到L2中，L2:{{ {C G}，0.33}，{{C L}，0.33}，{{C W}，0.33}，{{W WC}，0.33}}；

5) 刪除數據庫中引用長度不大于2的TID。此時數據庫記錄為T100，T300，T600。把table_2的內容賦值給table_1；

6) 重復步驟3，為發現L3，L2連接L2，根據Apriori性質“一個頻繁項集的所有子集也是頻繁的”，由此獲得L3，得到引用：{C W WC }，支持度：0.67；

7) 刪除數據庫中引用長度不大于3的TID。此時數據庫中記錄全部刪除完，算法結束；

8) 最后得到此用戶頻繁引用頁面C-W-WC。

5 結束論

由比較可見，刪除操作是基于篩選壓縮挖掘算法提高效率的關鍵，當挖掘到k頻繁引用時，在完成k-1頻繁引用挖掘后就著手刪除一次事務項不超過k-1個項事務，顯而易見，這將刪除數據庫中大量的記錄，生成k頻繁引用時掃描數據庫的工作量大大減少，這就是基于篩選壓縮挖掘算法提高效率的關鍵所在而類Apriori算法每次掃描都要徹底掃描整個原始數據庫D，這要耗費大量的時間。

■

圖1 時空耗費分析

6 模擬實驗

用開發的簡單Web日志挖掘系統SZS，對本算法進行了驗證：SZS系統的數據處理流程可簡要歸納為：將日志文件合并到數據庫中，數據清洗，用戶會話識別，事務識別和頻繁遍歷路徑識別。首先，用本文提出的算法替代該系統的挖掘頻繁遍歷路徑的部分，然后使用常州機電職業技術學院的Web服務器上的4月份的日志文件進行挖掘，并對原始數據文件進行初始化處理以后，獲得了大約2000條引用。令最小支持度為2%，即引用次數達到40次的頁面序列為頻繁遍歷路徑。挖掘找到頻繁遍歷路徑的結果如圖2所示，實驗結果表明本算法能夠有效地識別出頻繁遍歷路徑。

參考文獻：

[1] Han J，Kamber M.數據挖掘概念與技術[M].范明，孟小峰，譯.北京:機械工業出版社，2007.

[2] 楊怡玲.一個簡單的Web日志挖掘系統[J].上海交通大學學報，2000，34(7):932-935.

[3] 呂橙，易艷紅.一種挖掘Web用戶訪問模式的新方法MFP[J].小型微型計算機系統，2006，27(5):919-923.

[4] 呂橙，魏楚元.基于MFP方法的Web用戶訪問模式的模式發現[J].計算機應用 2007，27(3):555-569.

[5] HENM S，PARK J S，YU P S.Data mining for path traversal patterns in a Web environment[C].The 16th International Conference on Distributed Computing Systems.HongKong，1996:385-392.

[6] 唐北平，肖建華.通用Web日志挖掘系統設計實現[J].電腦知識技術，2006(11):310-311.