基于免疫遺傳退火算法的Ｗｅｂ關聯(lián)規(guī)則挖掘方法
2009-01-01 00:00:00符保龍黃崇爭
計算機應用研究 2009年2期
(1.柳州職業(yè)技術學院，廣西 柳州 545006；2.中國人民大學 信息學院，北京 100472)
摘 要：根據關聯(lián)規(guī)則挖掘的要求與特點，結合免疫算法，遺傳算法和模擬退火算法的優(yōu)點，提出一個基于免疫遺傳退火算法的Web關聯(lián)規(guī)則挖掘方法。實驗結果表明，與遺傳算法和模擬退火算法相比，基于免疫遺傳退火算法的關聯(lián)規(guī)則發(fā)現(xiàn)在Web挖掘中具有一定的優(yōu)勢。
關鍵詞：Web挖掘;關聯(lián)規(guī)則;遺傳算法;退火算法;免疫遺傳退火算法
中圖分類號：TP311 文獻標志碼：A
文章編號：10013695(2009)02047803
Web association rules method based on immune genetic annealing algorithm
FU Baolong1，HUANG Chongzheng2
(1.Liuzhou Vocational Technological College， Liuzhou Guangxi 545006，China；2.College of Information， Renmin University， Beijing 100472， China)
Abstract:According to the requirement and the character of association rule mining，combined with the advantage of genetic algorithm， simulated annealing algorithm，and immune algorithm， a mining method of association rules was proposed. From the experiment result， it is concluded that ，contrast to traditional method，the Web association rules ming based on immune genetic annealing algorithm have certain comparative advantage.
Key words:Web mining;association rules; genetic algorithm(GA); simulated annealing algorithm; immune genetic annealing algorithm(IGAA)
在互聯(lián)網技術的強力推動下，Web已經成為信息制造、加工和處理的主要平臺，其承載的數(shù)據量正在迅速膨脹。為了幫助用戶在浩如煙海的Web中迅速找到相關的信息，自動從Web文檔和服務中發(fā)現(xiàn)和抽取信息的Web挖掘技術已成為數(shù)據挖掘研究中的熱點。Web挖掘是指使用數(shù)據挖掘技術在WWW數(shù)據中發(fā)現(xiàn)潛在的、有用的模式或信息[1]。關聯(lián)規(guī)則是Web挖掘的一個重要研究課題，其目的在于找出網站資源訪問記錄中隱含的相互關系[2，3]。運用關聯(lián)規(guī)則挖掘技術能夠從服務器以及瀏覽器端的日志記錄中自動發(fā)現(xiàn)隱藏在數(shù)據中的模式信息，了解系統(tǒng)的訪問模式以及用戶的行為模式，從而作出預測性分析。
目前，廣泛使用的關聯(lián)規(guī)則挖掘算法是Aprior算法或其改進算法。這些算法的基本思想是將關聯(lián)規(guī)則的挖掘分解為兩步：首先找到所有支持度大于用戶最小支持度的項集，這些項集稱為頻集；然后從找到的頻集中構造其可信度大于用戶最小可信度的關聯(lián)規(guī)則。算法的核心思想是找到頻集，這個過程其實是一個全局搜索的過程，而遺傳算法(GA)就是一種全局優(yōu)化算法，它可以有效地避免搜索過程的局部最優(yōu)解。遺傳算法是一類模擬生物進化的智能優(yōu)化算法[4，5]，它在解決組合優(yōu)化問題中具有明顯的優(yōu)勢和特色，但在分類規(guī)則挖掘問題上，若采用Michigan方法，最優(yōu)個體并不能代表問題的最優(yōu)解，問題的解要通過一組染色體來表示，因此該方法存在染色體集成的問題。在研究中發(fā)現(xiàn)，并不是適應度高的染色體集成在一起形成的解越好，這就要求算法不僅要能找出適應度高的個體，還要能找出適應度不高但能提高最終挖掘結果準確性的那部分個體。能否找出這些適應度不高的個體并在進化過程中保留這些個體，是決定基于遺傳算法的關聯(lián)規(guī)則方法性能好壞的關鍵。這不僅要求算法具有很好的全局搜索能力和局部搜索能力，而且能在進化過程中維持多樣性的有效探索。免疫算法(immune algorithm，IA)是模擬免疫系統(tǒng)針對病菌的多樣性識別能力而設計出來的多峰值搜索算法[6~9]。它的搜索目標具有一定的分散性、獨立性，能在保持種群個體的多樣性和算法收斂之間取得平衡，加速優(yōu)化過程。模擬退火算法(simulated annealing，SA)是一種基于蒙特卡羅迭代求解的啟發(fā)式隨機搜索算法[10，11]，它將熱力學的退火平衡模型引入問題求解中，以利于尋找全局最優(yōu)解[12]。本文充分結合GA、IA、SA三種優(yōu)化算法的優(yōu)點，提出了一種新的基于免疫遺傳退火算法（IGAA）的Web關聯(lián)規(guī)則挖掘方法。
1 Web關聯(lián)規(guī)則挖掘模型
Web日志文件中存儲的是用戶訪問站點信息的記錄，每條記錄包括訪問日期、時間、用戶IP地址、方法、用戶代理等。首先進行數(shù)據預處理，濾掉多余的記錄，合并相關數(shù)據并將不恰當?shù)幕蛉哂嗟臄?shù)據項從數(shù)據集中清除；然后識別會話，標簽通過惟一的會話ID關聯(lián)點擊流記錄，驗證事件次數(shù)與描述該會話的記錄是否保持邏輯一致性；再根據用戶在每個頁面停留的時間，選定一個時間閾值，訪問時間在20~200 s，即表示對訪問的當前頁面有興趣，保留興趣的記錄，否則，表示對訪問的當前頁面沒有興趣；最后進行事務劃分，將所得到的會話記錄劃分成粒度更小的事務。為了便于分析Web挖掘問題，本文特作以下形式化定義：
定義1 Web事務。在事務文件中出現(xiàn)的所有頁面集合P，表示為P={p1，p2，…，pn}。其中每個頁面pi（i=1，2，…，n）通過其URL地址惟一表示。事務集合U表示為U={u1，u2，…，um}，每個事務uj（j=1，2，…，m）均為頁面集合P的子集。
定義2 向量轉換。事務集合中的每一個事務uj（j=1，2，…，m）可以轉換為頁面空間上的n維向量，u=〈w(p1，u)，w(p2，u)，…，w(pn，u)〉。其中：w(pi，u)為事務u在頁面pi（i=1，2，…，n）上的權重。
定義3 頁面權值。 假定將用戶訪問頁面的平均停留時間作為該頁面的權值。整個事務的權值為weight(uk)=|uk|i=1w(pi，uk)/|uk|。
定義4 支持度S（pi）。頁面pi∈p的支持度為S(pi) =u∈U Pi∈uw(pi，u)/|{u∈U|Pi∈u}|。
定義5 支持度S(pi∪pj)。頁面pi∪pj的支持度為S(pi∪pj)=u∈U Pi∈uw(pi，u)×w(pj，u)/|{u∈U|Pi∈u∧Pj∈u}|。
定義6 可信度C(pipj)。規(guī)則pipj的可信度為C(pipj)=S(pi∪pj)/S(pi)。
定義7 IGAA算法。IGAA=(Ω，f，P0，N，T0，Γ，Ψ)是本文設計的IGAA算法。其中：Ω是個體的編碼方法；f是適應度函數(shù)；P0是初始種群；N是群體規(guī)模；T0是初始溫度；Φ是變異算子；Γ是交叉算子；Ψ是選擇算子。
2 免疫遺傳退火算法的應用
2.1 染色體編碼及初始群體
本文將每個事務編碼為一個染色體，染色體的基因對應于事務中的頁面權值，然后采用自然數(shù)編碼方式，隨機產生N個位數(shù)為n的群體。N表示群體中所含個體的數(shù)量，是用戶自定義的一定數(shù)量事務集的子集。
2.2 適應度函數(shù)
適應度函數(shù)的選取對遺傳算法的收斂速度影響以及能否找到最優(yōu)解至關重要。各種文獻中定義的適應度函數(shù)大多以支持度和可信度為基礎，比較復雜的適應度函數(shù)如jmeasure function 和PS metric也是由簡單的函數(shù)組合而成。本文直接以可信度作為適應度函數(shù)的參考標準。
定義8 適應度函數(shù)。fit(pipj)=λ×C(pipj)，λ為常數(shù)。
2.3 免疫選擇
在當前群體F={x1，x2，…，xn}中，選擇個體xi，能否參與新一輪進化取決于概率
P(xi)=ef(xi)/Tk/ni=1
ef(xi)/Tk
其中：f(xi)是個體xi的適應度函數(shù)值；Tk為進化到第k代時，免疫遺傳退火算法的退火溫度；Tk+1=Tk×(1-k/M)，T0=1為算法初始溫度，當Tk=0時，免疫遺傳退火算法找到最優(yōu)解，算法自然結束。
2.4 遺傳交叉
交叉是指將兩個父代個體的部分結構加以替換重組而生成新個體的操作[13]。本文定義的交叉算子如下：在[0，1]內隨機生成一個數(shù)rc=random[0，1]，若rc 2.5 退火變異 變異操作的作用是在種群出現(xiàn)局部收斂時通過變異算子的突變，使整個種群能保持一定的多樣性[14]。本文定義的變異算子如下：在[0，1]內隨機生成一個數(shù)rm=random[0，1]，若rm 2.6 算法描述 a）初始化控制參數(shù)。群體規(guī)模N，交叉概率Pc，變異概率Pm，初始溫度T0，進化代數(shù)k=0，并對基因進行編碼，隨機產生初始種群。 b）評價個體的適應度。計算個體的可信度、支持度和適應度值，將結果添加到有趣規(guī)則表，并將大于最小閾值的規(guī)則添加到關聯(lián)規(guī)則表中。 c）對群體分別進行免疫選擇，遺傳交叉和退火變異操作。 d）將每次挖掘的結果都存放在關聯(lián)規(guī)則表associationrule中，其記錄有規(guī)則結構、支持度、可信度等項目。對遺傳進化得到的個體，先在有趣規(guī)則表interestrule和關聯(lián)規(guī)則表associationrule中搜索，如果有，則直接讀取其支持度和可信度；否則，在數(shù)據庫中搜索并計算支持度和可信度，并將結果添加到表interestrule中，將大于最小閾值的規(guī)則添加到表associationrule中。 e）當Tk=0時，退火過程自然結束;否則，Tk+1=Tk×(1-k/M)，k=k+1，并將步驟c)得到的新群體，按適應度進行排序，截取前面的N個子代個體作為新的父代群體，算法返回到步驟b）。 3 測試結果及其分析 3.1 實驗環(huán)境及參數(shù)選取 為了驗證所提出的觀點和方法的有效性， 在Pentium4 1.80 GHz CPU和1 GB內存的 PC 機上，采用MATLAB 7.0作了大量的仿真實驗。實驗過程中用到的一些參數(shù)定義為：種群規(guī)模150、交叉概率0.85、變異概率0.1、初始溫度為1。 3.2 實驗結果及分析 圖1顯示的是在人工數(shù)據集上運行本文的算法，該數(shù)據集包含700個事務，25個屬性。算法運行了20次得到的平均結果。從圖1中可以看出，IGAA算法能有效地挖掘關聯(lián)規(guī)則，并且有較好的收斂速度。圖2描述的是IGAA、GA和SA產生的規(guī)則準確率比較。不難看出，IGAA算法挖掘出來的規(guī)則的準確率較高。如果迭代次數(shù)足夠大，規(guī)則的準確率可達到100%。在表1中，筆者選擇三個大小不同的事務數(shù)據集，均來自大學Web日志文件（http://www.ccnu.edu.cn）。在三個數(shù)據集中，IGAA能發(fā)現(xiàn)全局優(yōu)化的關聯(lián)規(guī)則，其有些與傳統(tǒng)GA發(fā)現(xiàn)的相同，有些規(guī)則的準確性更優(yōu)于傳統(tǒng)GA的發(fā)現(xiàn)。然而，IGAA最好運行時間明顯比GA短。 表1 IGAA和GA運行結果的比較 數(shù)據集大小IGAA規(guī)則數(shù)目GA規(guī)則數(shù)目IGAA最好運行時間/sGA最好運行時間/s Web挖掘是使用數(shù)據挖掘技術在WWW數(shù)據中發(fā)現(xiàn)潛在的、有用的模式或信息。關聯(lián)規(guī)則是Web挖掘的一個重要研究領域。本文采用免疫遺傳退火算法對頁面進行了關聯(lián)規(guī)則挖掘，并就挖掘出的規(guī)則的正確率和簡潔性與傳統(tǒng)的遺傳算法進行了對比。實驗結果表明該算法用于Web關聯(lián)規(guī)則挖掘所得出結果的正確率和簡潔性都比較好，具有一定的應用前途。 參考文獻： ［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):3440. [2]FU X，BUDZIK J，HAMMOND K J.Mining navigation history for recommendation[C]//Proc of International Conference on Intelligent User Interfaces.New Orleans:ACM Press，2000:576583. [3]MOBASHER B，DAI H，LUO T.Active personalization based on association rule discovery from Web usage data[C]//Proc of the 3rd ACM Workshop on Web Information and Data Managerment.Atlanta:[s.n.]，2001:779787. [4]劉忠仁，孫圣和.帶有頂端增強算子的遺傳算法[J].哈爾濱工業(yè)大學學報，2002，34(5):687690. [5]劉勇國，李學明，張偉.基于遺傳算法的特征子集選擇[J].計算機工程，2003，29(6):6770. [6]肖人彬，王磊.人工免疫系統(tǒng)：原理、模型、分析及展望[J].計算機學報，2002，25(12):12811293. [7]王磊，潘進，焦李成.免疫規(guī)劃[J].計算機學報，2000，23(8):806812. [8]HUNT J，De COOKE.Learning using an artificial immune system[J].Journal of Network and Computer Applications，1996，19(2):189212. [9] 焦李成，杜海峰.人工免疫系統(tǒng)進展與展望[J].電子學報，2003，31(10):15401548. [10]YU H M，YAO P J，F(xiàn)ANG H，et al.Combined genetic algorithm/ simulated annealing algorithm for largescale system energy integration[J].Computers and Chemical Engineering，2000，24(8):20232035. [11]王雪梅，王義和.模擬退火算法與遺傳算法的結合[J].計算機學報，1997，20(4):381384. [12]SHU W N，ZHENG S J.A parallel genetic simulated annealing hybrid algorithm for task scheduling[J].Wuhan University Journal of Natural Sciences，2006，12(5):5660. [13] SCINVIVAS M，PATNAIK M.Adaptive probabilities of crossover and mutation in genetic algorithm[J].IEEE Trans on SMC，1994，24(4):656666. [14]SHU W，HE B.A quantum genetic simulated annealing algorithm for task scheduling[J].ACM Computing Surveys，2006，33(1):115127.
