基于規則提取量的Web日志關聯規則挖掘方法

摘 要:引入規則提取量的度量標準，提出一種基于免疫多克隆遺傳策略的Web日志關聯規則挖掘方法。該算法在遺傳算法的基礎上引入免疫多克隆算子，有效地克服了遺傳算法容易陷入局部最優的缺點，具有更強的全局與局部搜索能力。實驗結果表明，該算法能高效地解決Web日志關聯規則挖掘問題。

關鍵詞:Web日志挖掘; 關聯規則;遺傳算法; 規則提取量; 免疫多克隆算法

中圖分類號:TP311

文獻標志碼:A

文章編號:1001-3695(2010)02-0500-03

doi:10.3969/j.issn.1001-3695.2010.02.026

Web log association rules mining method based on rule extraction number

FU Bao-long

(Liuzhou Vocational Technological College， Liuzhou Guangxi 545006， China)

Abstract:The paper combined with the rule extraction number， brought forward a method of mining Web log association rule based on immune poly-clonal genetic strategy. The algorithm based on genetic algorithm introduced polyclonal immune operator， it effectively overcame the genetic algorithm vulnerable to the shortcomings of local optimum， and the global and local search capability was stonger. The experimental results show that the algorithm can efficiently solve the Web log association rule mining problem.

Key words:Web log mining; association rules; genetic algorithm; rules extraction number; immune poly-clonal algorithm

隨著互聯網的迅速增長，Internet上已經積累了大量的數據。為了能迅速地從互聯網上找到所需要的數據，基于Web的數據挖掘技術成為近年的研究熱點。關聯規則是Web日志挖掘領域中一個重要的研究方向，它的目的在于找出網站資源訪問記錄中隱含的相互關系。Web站點的日志數據記錄了用戶瀏覽Web站點時的大量信息，對這些日志數據進行有效的分析，可以發掘隱藏在其中的規律和模式。

目前，圍繞著Web日志挖掘中的關聯規則挖掘，國內外已經做了大量的研究工作，如Apriori、FP-Growth等，這些算法存在的共同問題是計算復雜度高、計算量大[1]。遺傳算法[2](genetic algorithm，GA)是一種基于自然選擇和群體遺傳機理的全局優化算法，在解決大空間、非線性、全局尋優等復雜問題時具有獨特的優越性。免疫算法[3](immune algorithm，IA)是模擬免疫系統對病菌的多樣性識別能力而設計出來的多峰值搜索算法，它能在保持種群個體多樣性和算法收斂之間取得平衡，加速優化過程。文獻[4]中提出了一種基于免疫遺傳算法的關聯規則挖掘算法，該算法具有很好的魯棒性和隱含并行性，能有效地進行全局優化搜索;文獻[5]提出了一種基于免疫遺傳算法的關聯規則挖掘模型，并把它用于ERP系統的關聯規則挖掘中，該模型具有收斂速度快、搜索精度高的特點。借鑒文獻[4，5]的思想，本文將遺傳算法引入到Web日志的關聯規則挖掘中，采用免疫多克隆策略對GA算法進行優化，以期能加快Web關聯規則挖掘的收斂速度，具有更強的全局和局部搜索能力。同時，引入規則提取量的度量機制，提出一種基于免疫多克隆遺傳策略(immune poly-clonal genetic strategy， IPCGS)的Web日志挖掘方法。

1 問題的定義

Web日志文件包含了大量的用戶訪問信息，如用戶的IP地址、所訪問的URL、訪問日期和時間、訪問方法(Get或Post)、訪問結果(成功、失敗、錯誤)、訪問的信息大小等。日志有不同的格式，如通用日志格式(common log format，CLF)和擴展通用日志格式(extended common log format，ECLF)等。無論是哪種日志格式，使用前必須對日志數據進行預處理，它是一個十分關鍵的步驟。一般Web日志數據的預處理主要經歷數據凈化、用戶識別、會話識別、路徑補充等步驟。

通過對Web日志數據進行預處理，可獲得用戶訪問頁面的集合P以及用戶會話集合T，記為P={p1，p2，…，pn}，其中pi=〈ip，url，time〉n(i=1，2，…，n);T={t1，t2，…，tm}，ti∈T是P的一個子集[4]。考慮用戶的具體瀏覽行為，本文將用戶訪問頁面的平均停留時間作為該頁面的權重，將瀏覽時間歸一化可得:w(pi，t)=(ti-tmin)/(tmax-tmin)。其中:tmax為單一頁面的最大瀏覽時間;tmin為單一頁面的最小瀏覽時間。為了便利于關聯規則的挖掘操作，根據預處理過的日志文件，計算出每一個用戶在這一時間段內訪問各頁面pj(j=1，2，…，n)的偏好，形成矢量t={w(p1，t)，w(p2，t)，…，w(pn，t)}，pi∈P。

為了便于分析問題，作以下形式化描述:

定義1 支持度sup(pi)。Sup(pi)=∑t∈TPi∈tw(pi，t)|{t∈T|pi∈t}|表示頁面pi∈P的支持度。

定義2 支持度sup(pi∪pj)。Sup(pi∪pj)=∑t∈TPi∈tw(pi，t)×w(pj，t)|{t∈T|pi∈t∧pj∈t}|表示頁面pi∪pj的支持度。

定義3 可信度conf(pipj)。Conf(pipj)=S(pi∪pj)S(pi)表示規則pipj的可信度。

定義4 IPCGS算法模型。IPCGS=(C，f，P0，Μ，Ψ，Ξ，Θ)是本文設計的挖掘算法。其中C是抗體的編碼，f是抗體的親和度評價函數，P0是初始抗體群，M是群體規模，Ψ是免疫選擇算子，Ξ是多克隆算子，Θ是克隆選擇算子。

2 IPCGS算法的基本流程

a)初始化。隨機生成一個初始抗體群A={a1，a2，…，an}，個體數為N，長度為L，L為待優化函數的自變量個數;采用實數編碼，設置最大進化代數genmax。

b)計算抗體的親和度。將抗體按照親和度降序排列，得到A′={a′1，a′2，…，a′N}，且f(a′i)≥f(a′i+1)，f()為親和度函數，同時令k=0。

c)選取A′中m個較高親和度的抗體，并對其進行克隆操作，得到新的抗體群A″。

d)對當前種群A″進行克隆變異操作，以概率Pm從A″中抽出抗體，對一個或多個屬性進行實值變異，使其以一定概率隨機變為其他屬性值，刪去此種群中不滿足支持度條件的抗體，經過變異后的新種群為A。

e)對A進行克隆交叉操作得到新種群A，交叉時使用離散重組法則，刪去此種群中不滿足支持度條件的抗體。

f)對種群A進行克隆選擇操作A′=Tcs(A)。若得到的某個抗體同時滿足最小支持度和最小置信度條件，則輸出此抗體，并把此抗體還原為原始屬性值，但仍把此抗體保留在種群之中。

g)當k≥genmax時，算法結束;否則，k=k+1并且把此時種群作為下一代計算的初始抗體種群，轉b)。

3 IPCGS算法的應用

3.1 抗體編碼

抗體是用來表示所求問題的候選解。在IPCGS算法里，將每個用戶事務表示成遺傳空間的基因型串結構數據，這些串結構數據的不同組合便構成了不同的點。隨機生成N個初始串結構數據，每個串結構數據稱為一個個體，N個個體構成一個群體，算法以這N個串結構數據作為初始點開始迭代。

3.2 親和度函數

親和度函數所代表的是問題的解和實際問題的接近程度，親和度評價函數的建立直接影響到算法的收斂速度，甚至導致算法失敗。因此，一定要結合具體問題的特征，建立不同的親和度函數。本文所用的親和度評價函數為

f(pipj)=sup(pipj)+conf(pipj)(1)

f(pipj)的計算公式表明在抗體群里，面對各種規則的競爭，只有支持度和可信度都高的抗體才有可能生存下來。

3.3 免疫選擇

選擇的目的是為了從當前抗體群中選出優良的個體，使它們有機會作為父代為下一代繁殖子孫。在當前抗體群F={x1，x2，…，xn}中，選擇個體xi(i=1，2，…，n)，能否參與新一輪進化取決于概率:

p(xi)=f(xi)∑Ni=1f(xi)(2)

其中:f(xi)為個體i的親和度函數值。

3.4 克隆算子

克隆算子[6]能有效擴大群體的規模，它的實質是將一個低維空間的問題轉換到更高維的空間中解決，然后將結果投影到低維空間中，從而獲得對問題更全面的認識。

抗原和抗體之間的親和度對應于優化問題的目標函數與解的匹配程度。克隆算子就是依據抗原與抗體的親和度函數f()，將解空間中的一個點ai(x)∈A(x)分裂成qi個相同的點a′i(x)∈A′(x)，然后經過免疫基因操作和克隆選擇變換獲得新的抗體群。

定義5 克隆操作TCc。令

TCc(A)=[TCc(a1)，TCc(a2)，…，TCc(an)]T(3)

其中:TCc(ai)=Ii×ai(i=1，2，…，n)，Ii為qi維行向量;qi為抗體ai的克隆規模，其滿足下式:

qi=g(Nc，f(ai))(4)

qi=int[Nc×f(ai)∑nj=1f(aj)]; i=1，2，…，n(5)

一般取Nc>n是與克隆規模有關的設定值，int()為上取整函數，克隆過后種群變為A′={A，A′1，…，A′n}。其中A′i=

{ai1，ai2，…，aiqi-1}，aij=ai，j=1，2，…，qi-1。

3.5 多克隆算子

多克隆算子包含克隆變異和克隆交叉兩個算子。

1)克隆變異[7] 對克隆后的群體A′中每個抗體進行克隆變異，提高群體中抗體的多樣性，擴大搜索范圍，以便尋找更加優秀的抗體。本文采用高頻變異對群體A′進行變異操作得到新種群A″。高頻變異的計算式[8]如下:

a′i=ai+ρ×f(ai)max(f(ai))×N(0，1)(6)

其中:ai、a′i分別表示變異前后的基因位值，N(0，1)是均值為0、方差為1的正態分布的隨機數;ρ為變異常數，用來控制子群中個體進行局部搜索的范圍，其大小根據種群中的個體數量選取，一般ρ=0.1。

2)克隆交叉 對目前種群A″進行克隆交叉操作，交叉時使用離散重組法則，刪去此種群中不滿足支持度條件的抗體，得到新的種群A。

3.6 克隆選擇

定義6 克隆選擇[9]TCs。若變異后對于任意的i=1，2，…，n，抗體b={a′ij|max f(a′ij)，j=1，2，…，qi-1}滿足f(a′i)

4 實驗及其分析

4.1 實驗環境及參數選取

為了驗證本文所提出的觀點和方法的有效性，分別對Apriori、GA算法及本文提出的IPCGS算法進行對比實驗。實驗所用數據來自于某高校的Web日志文件(www.lzzy.net)，日志文件大小為15 MB，記錄了從25/07/2008 04:47:34到26/10/2008 23:58:15時間段的頁面請求，其中包含10萬條記錄。日志數據中有391個不同的HTML頁面，經過數據預處理，從中識別出1 892個用戶會話。實驗所用的硬件平臺基本配置為Intel C2.0 GHz、1 GB內存，軟件平臺為WindowsXP和MATLAB 7.0 。算法運行了50次，得到的平均結果如圖1、2所示。實驗過程中用到的一些參數定義為:種群規模100，交叉概率Pc=0.85，最大迭代次數genmax=200，支持度閾值為5%，置信度閾值為85%。為了更好地分析算法性能，定義以下度量標準——規則提取量。

定義7 規則提取量Q。

Q=n∏ni=1hi(7)

其中:n表示實驗的次數;hi表示第i次實驗提取的規則數。

4.2 實驗結果及分析

圖1描述的是IPCGS、GA和Apriori算法產生的規則數比較，從圖中不難看出，IPCGS算法能有效地挖掘關聯規則，具有收斂速度快的特點。雖然Apriori算法所挖掘出來的規則數比IPCGS算法稍大，考慮到大數據量的情況下，這點差距可以忽略不計。基于GA算法的關聯挖掘與本文提出的IPCGS算法相比，兩者在初始階段挖掘的結果差異不大，但在后半階段兩者的差距不斷加大，這主要是因為通過引入免疫多克隆策略，算法可以減弱GA算法在計算過程中出現的退化現象，有利于群體的相對穩定，從而可以得到更多的符合條件的關聯規則。此外，該算法沒有固定個體的變異率，而是通過自適應的方式尋找最好的解，提高了收斂速度。圖2描述的是在產生同等規則提取量下三種算法運行時間的比較。從圖中可以明顯地看到，IPCGS算法的計算時間比其他兩種算法都具有相當大的優勢，雖然初始階段IPCGS算法的計算時間比GA算法要大，這是因為該算法引入多克隆算子，將解空間中的一個點分裂成多個相同的點，從而擴大解空間搜索范圍，其解空間變大是以計算時間增長為代價的。無論是GA算法還是IPCGS算法，它們的計算時間都比Apriori算法優異，這是因為Apriori算法需要多次掃描數據庫來尋找符合條件的關聯規則，而其他兩種算法不需要掃描數據庫。

5 結束語

通過對站點的Web日志數據進行分析可以發現潛在的、有用的模式或信息。本文引入規則提取量的度量機制，在傳統遺傳算法中加入免疫多克隆操作，提出一種基于免疫多克隆遺傳策略的Web日志關聯挖掘算法。與遺傳算法相比，該算法不僅降低遺傳算法的魯棒性，更兼顧了搜索速度、全局和局部的搜索能力。用該方法對某站點的Web日志數據進行關聯規則挖掘，理論分析和實驗表明，該算法能有效、快速地解決Web日志中的關聯規則挖掘問題。

參考文獻:

[1]SRIVASTAVA J， COOLEY R， DESHPANDE M.Web usage mining:discovery and application of usage patterns from Web data[J]. SIGKDD Explorations， 2000， 22(1):34-40.

[2]許國艷，史宇清.遺傳算法在關聯規則挖掘中的應用[J].計算機工程，2002，23(7):122-124.

[3]焦李成，杜海峰.人工免疫系統進展與展望[J].電子學報，2003，12(10):1540-1548.

[4]高堅.基于免疫遺傳算法的多維關聯規則挖掘[J].計算機工程與應用，2003，39(32):185-186.

[5]王琦，張洪偉.ERP中免疫遺傳算法的關聯規則挖掘[J].計算機應用研究，2005，23(8):172-175.

[6]MOBASHER B， DAI Hong-hua， LUO T， et al. Effective personalization based on association rule discovery from Web usage data[C]//Proc of the 3rd International Workshop on Web Information and Data Managerment. 2001:9-15.

[7]劉芳，孫楊軍.基于多克隆選擇的多維關聯規則挖掘算法[J].復旦學報:自然科學版，2004， 24(5):743-745.

[8]SCINVIVAS M，PATNAIK L M. Adaptive probabilities of crossover and mutation in genetic algorithm[J]. IEEE Trans on Systems Man and Cybemetics，1994，24(4):656-666.

[9]劉若辰，杜海峰，焦李成.免疫多克隆策略[J].計算機研究與發展，2004，41(4):571-576.