基于免疫算法的Web數(shù)據(jù)挖掘技術(shù)的研究

周自斌

（安徽經(jīng)濟(jì)管理學(xué)院 信息工程系，安徽 合肥 230059）

基于免疫算法的Web數(shù)據(jù)挖掘技術(shù)的研究

周自斌

（安徽經(jīng)濟(jì)管理學(xué)院 信息工程系，安徽 合肥 230059）

現(xiàn)代計算機(jī)網(wǎng)絡(luò)的迅速發(fā)展和網(wǎng)絡(luò)數(shù)據(jù)量的大幅增加導(dǎo)致了對網(wǎng)絡(luò)數(shù)據(jù)挖掘的需求變的越來越迫切.網(wǎng)絡(luò)數(shù)據(jù)具有分布范圍廣、數(shù)據(jù)量大、時間跨度長等特點.如何對這些海量數(shù)據(jù)進(jìn)行高效查詢并對查詢結(jié)果進(jìn)行最優(yōu)收斂成為研究的熱點.免疫算法以遺傳算法的全局性群體搜索方式為基礎(chǔ)，模擬生物免疫系統(tǒng)對本代群體進(jìn)行優(yōu)化，有利于查詢結(jié)果的快速收斂，大大提高了查詢效果.

免疫算法；數(shù)據(jù)挖掘；最優(yōu)查詢

Web數(shù)據(jù)挖掘（Web Data Mining），是指在網(wǎng)絡(luò)環(huán)境中，從大量的分布在異構(gòu)網(wǎng)絡(luò)中的Web文檔庫中發(fā)現(xiàn)潛在的、有價值的信息，并對其加以分析，篩選和優(yōu)化，最終提交給用戶.隨著Internet的飛速發(fā)展，網(wǎng)絡(luò)用戶與日俱增，Web數(shù)據(jù)量也相應(yīng)的有了快速的增長.Web站點已經(jīng)被用戶廣泛接納為新的數(shù)據(jù)儲藏庫，在這些龐大的信息資源庫中蘊(yùn)含著具有巨大潛在價值的知識.同樣由于Web數(shù)據(jù)的分布化和多樣化，使得Web數(shù)據(jù)挖掘技術(shù)比單個數(shù)據(jù)倉庫的數(shù)據(jù)挖掘技術(shù)要復(fù)雜得多，如何提高Web數(shù)據(jù)挖掘技術(shù)的效率及穩(wěn)定性，已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域研究的熱點.

1 Web數(shù)據(jù)挖掘的工作原理

1.1 Web數(shù)據(jù)的特點

1.1.1 異構(gòu)網(wǎng)絡(luò)環(huán)境.在網(wǎng)絡(luò)環(huán)境中，每一個Web站點就是一個數(shù)據(jù)源，而由于這些站點的采用的網(wǎng)絡(luò)連接方式、網(wǎng)絡(luò)協(xié)議、操作系統(tǒng)等差異，導(dǎo)致了Web數(shù)據(jù)源的異構(gòu)性，直接影響了數(shù)據(jù)挖掘技術(shù)的效率和容錯率.

1.1.2 海量動態(tài)數(shù)據(jù).由于網(wǎng)絡(luò)中Web站點的數(shù)量不斷增加，Web數(shù)據(jù)量也在飛速增多，而且由于網(wǎng)絡(luò)數(shù)據(jù)的動態(tài)特性，導(dǎo)致數(shù)據(jù)更新快、淘汰快.如何提高數(shù)據(jù)挖掘技術(shù)的有效性以確保搜索結(jié)果是真正有價值的，已經(jīng)成為Web數(shù)據(jù)挖掘要解決的重點問題.

1.1.3 Web數(shù)據(jù)的結(jié)構(gòu)復(fù)雜性和多樣性.Web上的數(shù)據(jù)非常復(fù)雜，沒有特定的模型，每一站點的數(shù)據(jù)都是各自獨立設(shè)計，缺乏統(tǒng)一標(biāo)準(zhǔn)，而且每個站點蘊(yùn)含的信息呈多樣化，例如文本數(shù)據(jù)、圖表、音頻數(shù)據(jù)以及視頻數(shù)據(jù)等.這些差異都增加了Web數(shù)據(jù)挖掘的困難度.

1.1.4 用戶群體的廣泛性.數(shù)據(jù)挖掘最終是要為用戶提供服務(wù)的，而Internet龐大的用戶群導(dǎo)致眾口難調(diào)的問題格外突出，因此，需要Web數(shù)據(jù)挖掘系統(tǒng)有一定的智能性和相應(yīng)的學(xué)習(xí)機(jī)制，不斷跟蹤不同用戶的興趣和關(guān)注點，直至獲取最貼近用戶需求的結(jié)果.

1.2 Web數(shù)據(jù)挖掘的組成步驟

如圖1所示，Web數(shù)據(jù)挖掘包含以下幾個步驟和內(nèi)容：

圖1 Web數(shù)據(jù)挖掘的組成

1.2.1 信息檢索：自動對網(wǎng)絡(luò)中存在關(guān)聯(lián)關(guān)系的文檔進(jìn)行搜索，主要包括文檔的表示、索引的搜索.

1.2.2 信息提取：在文檔被檢索并初步篩選之后，自動從中提取有價值的信息，這一步驟主要是通過對頁面內(nèi)主要字段的語義進(jìn)行識別來完成的.

1.2.3 信息集成：針對提取的文檔進(jìn)行歸納和優(yōu)化，得到概要知識.自學(xué)習(xí)、自適應(yīng)的一些智能算法就在這一過程當(dāng)中被應(yīng)用.

1.2.4 信息分析：這一階段將對信息集成階段所生成的模式進(jìn)行解釋說明.即針對用戶提供的先驗信息，對集成的數(shù)據(jù)再次優(yōu)化，使之符合用戶的需求.最終生成有價值的信息提交給用戶.

2 免疫算法原理

以往經(jīng)常使用的遺傳算法或者以其為代表的進(jìn)化算法，在智能化處理事務(wù)的能力還有很大的不足，尤其對多峰值求解問題存在較大的缺陷，所以必須更加深入地挖掘與利用人類的智能資源.免疫算法（Immune Genetic Algorithm-IGA）基于生物免疫系統(tǒng)的自適應(yīng)學(xué)習(xí)、自我識別和主動攻擊侵入機(jī)體的抗原的原理，將生物免疫系統(tǒng)的特點引入遺傳算法.

在采用免疫算法進(jìn)行優(yōu)化求解時，將目標(biāo)函數(shù)和對應(yīng)的約束條件（可根據(jù)用戶的需求和關(guān)注點的差異而進(jìn)行調(diào)整）作為抗原輸入.隨后，產(chǎn)生初始抗體群，并通過遺傳操作及對抗體親和度的計算評價，在多代優(yōu)化后，找出針對該抗原的抗體，即問題的最優(yōu)解，同時保持了抗體多樣性，避免了局部過早收斂.

免疫算法的重點是在于合理的提取疫苗，即合適的抑制和刺激函數(shù)，并通過接種疫苗和免疫選擇兩步內(nèi)容來完成的.接種疫苗是為了提高適應(yīng)度，免疫選擇是為了防止群體的退化.

由此可以看出，免疫算法是在遺傳算法的基礎(chǔ)上，融入了免疫機(jī)制而形成的一種優(yōu)化算法，它解決了遺傳算法中經(jīng)常會出現(xiàn)的過早收斂與局部極值，也就是“早熟”的情況，大量的實驗數(shù)據(jù)證明，免疫算法是一種局部搜索能力更強(qiáng)，收斂性更好、魯棒性更高的新型優(yōu)化算法.

2.1 生物免疫系統(tǒng)

免疫是生物體的一種特性生理反應(yīng).生物的免疫系統(tǒng)在檢測到外來侵犯的抗原時，可自動產(chǎn)生相應(yīng)的抗體來抵抗乃至消滅抗原.抗體在攻擊抗原時，會產(chǎn)生一系列的反應(yīng)，通過吞噬作用來達(dá)到毀壞抗原的目的.在生物體中，淋巴細(xì)胞和抗體分子共同組成了免疫系統(tǒng)，而起到關(guān)鍵作用的淋巴細(xì)胞又包括T細(xì)胞（由胸腺產(chǎn)生）和B細(xì)胞（由骨髓產(chǎn)生）兩類.

圖2 生物免疫機(jī)制的抽象模型

免疫系統(tǒng)的功能主要是依靠抑制機(jī)理和主反饋機(jī)理之間的相互協(xié)作來實現(xiàn)的.免疫系統(tǒng)作為復(fù)雜的自適應(yīng)系統(tǒng)，具有能夠自我識別和消除異已的能力,并且有分布廣、自適應(yīng)性強(qiáng)、樣體呈多樣化、自組織及快速應(yīng)答等特點.圖2為生物免疫機(jī)制的抽象模型圖.

2.2 免疫算法的流程

免疫算法在基本遺傳算法的基礎(chǔ)框架上，利用求解問題的特征對遺傳算法的種群進(jìn)行疫苗接種，即根據(jù)先驗知識保留種群中的最優(yōu)群體，并保留最優(yōu)個體作為記憶細(xì)胞，以提高優(yōu)化速度，具體的流程如圖3所示.

圖3 免疫算法流程圖

以下為免疫算法的整體流程：

2.2.1 抗原識別:免疫算法所要解決的問題對象即為抗原，我們假設(shè)機(jī)體收到抗原的入侵，而免疫算法求解即為抵御抗原入侵的過程，那么首先就需要對抗原進(jìn)行識別，判斷此時侵入的抗原是不是類似于曾經(jīng)遇到過的抗原，這一步驟采用相似度函數(shù)進(jìn)行判斷，如果是的話，就可以調(diào)用以往的解決策略快速優(yōu)化.

2.2.2 初始抗體產(chǎn)生:如果第一步抗原識別的結(jié)果是此次入侵的抗原同以往抗原具有高相似度的特征，則從即記憶單元中抽取同以往抗原相對應(yīng)的抗體組成初始群體.否則，初始群體由隨機(jī)算法產(chǎn)生，同時也可根據(jù)先驗知識，實現(xiàn)設(shè)定好某些特定的抗體加入初始群體中，顯然，這種方式加快了免疫算法的搜索速度.

2.2.3 抗體適應(yīng)度評價:在當(dāng)前的群體中，計算所有抗體的適應(yīng)度，適應(yīng)度是篩選優(yōu)化操作所依賴的重要依據(jù).在免疫算法中，適應(yīng)度函數(shù)通常是用待優(yōu)化問題的目標(biāo)函數(shù)進(jìn)行變換得到的.

這里我們采用Marghny等人提出的適應(yīng)度函數(shù)：

n：用戶輸入的關(guān)鍵字的數(shù)量，#ki：在鏈接L中關(guān)鍵字 出現(xiàn)的次數(shù)；

M：頁面中總的鏈接數(shù)；

Fmax（p）和Fmin（p）分別表示為采用優(yōu)化算法后本代頁面質(zhì)量函數(shù)的最大值和最小值，顯然，最大值為m*n，最小值為0.

2.2.4 向記憶細(xì)胞分化:這一操作的目的即為更新數(shù)據(jù)庫，如果抗原是新的，則在當(dāng)前的抗體群中，抽取出適應(yīng)度高的抗體，并計算它與記憶單元中保存的抗體的相似度，并用這個抗體替換掉記憶單元中親和度最高的抗體.

定義抗原Ag和抗體Ab的親和度dij以及抗體Abi和抗體Abj間的親和度dij.抗體間親和度值越大,說明兩個抗體越相似,這里采用歐氏距離評價抗體間的親和度:

式中n為抗體屬性個數(shù)；Abik、Abjk分別為抗體Abi和Abj的第k個屬性；

任意兩個數(shù)據(jù)向量的最大距離定義為Dmax=

細(xì)胞分化的作用是將適應(yīng)度高的抗體存入記憶單元中，但并不對記憶單元中抗體的多樣性產(chǎn)生影響.

2.2.5 抗體的促進(jìn)和抑制:抗體的濃度和適應(yīng)度直接關(guān)系到對某一抗體究竟是采用刺激促進(jìn)還是抑制.抗體的濃度越高，該抗體被促進(jìn)的概率越小，而抗體的適應(yīng)度越高，該抗體被促進(jìn)的概率就越大，這樣做的目的是為了改善錯誤收斂與局部極值的情況.這里采用cooke等人提出的刺激度計算公式：

式中，第一項為抗原與抗體的適應(yīng)度；第二項為抗體之間的相互抑制程度；第三項為抗體之間的相互刺激作用；第四項為抗體的死亡（即淘汰）概率.

2.2.6 提取和接種疫苗：免疫算法的優(yōu)勢之一就是利用局部特征數(shù)據(jù)來群體優(yōu)化的過程，這是通過疫苗操作來完成的.在提取和接種疫苗時候，對局部特征信息加以關(guān)注，甚至搜索進(jìn)程圍繞數(shù)個局部特征信息展開，這就減少了求解過程中的一些重復(fù)和無效的工作，這也是免疫算法比遺傳算法更快收斂到最優(yōu)解的重要因素.

2.2.7 抗體產(chǎn)生:對上一個步驟所篩選出的抗體進(jìn)行交叉和變異操作，更新抗體群.交叉、變異算子是免疫算法中的核心運算環(huán)節(jié)，這一點是同遺傳算法相類似的.對于最常使用的二進(jìn)制編碼，通常有單點交又，兩點交叉等交方式；變異算子就是對某個抗體中的某一基因位做二進(jìn)制取反操作.而對于其它更復(fù)雜的編碼方式，交叉和變異要考慮的因素就大大增加了，例如要保證抗體的多樣性，避免未成熟收斂，又要確保抗體的有效性，避免無效搜索.

2.2.8 群體更新模:本代優(yōu)化完成后，把新產(chǎn)生的群體替換上代群體，同時淘汰掉抗體群適應(yīng)度最低的一部分，再隨機(jī)生成同樣數(shù)量的新抗體加入本代樣本群體中去，進(jìn)行下一代的進(jìn)化.

3 基于免疫學(xué)習(xí)算法的Web數(shù)據(jù)挖掘

將免疫優(yōu)化算法用于Web數(shù)據(jù)挖掘，可根據(jù)用戶需求的不同，合理的安排抗原和疫苗，在這里我們將用戶請求看作抗原，根據(jù)用戶請求得到目標(biāo)集,并進(jìn)行預(yù)處理后得到的有效數(shù)據(jù)看作抗體,以此為基礎(chǔ)數(shù)據(jù)，Web數(shù)據(jù)挖掘流程如圖4所示.

3.1 數(shù)據(jù)信息獲取和處理

Web頁面首先需創(chuàng)建一個數(shù)據(jù)集，此數(shù)據(jù)集必須是可以合并到現(xiàn)有數(shù)據(jù)庫的，然后才能被檢索和處理，處理過程如下：

圖4 Web數(shù)據(jù)挖掘流程

（1）標(biāo)識數(shù)據(jù)源，之后把它映射成可擴(kuò)展標(biāo)識語言XHTML,并查找數(shù)據(jù)內(nèi)的引用點；

（2）將數(shù)據(jù)映射成擴(kuò)展標(biāo)記語言XML；

（3）合并結(jié)果并對數(shù)據(jù)做進(jìn)一步分析處理.XML可以很便利的將XML的文檔描述與關(guān)系數(shù)據(jù)庫中的屬性對應(yīng)查找并建立映射關(guān)系，實施精確地查詢與模型抽取.應(yīng)用XML格式的最大優(yōu)勢是不僅可以兼容原有的Web應(yīng)用和原有信息，而且針對Web中不斷生成、更新的信息實現(xiàn)共享和交換.

3.2 仿真結(jié)果與分析

圖5 仿真結(jié)果

在實際應(yīng)用中，用戶可能會對多種數(shù)據(jù)特征感興趣，顯然，特征越多，算法越復(fù)雜，查詢耗時也更多，在仿真實驗中，為簡單起見，僅選取兩個反映數(shù)據(jù)特征的屬性，記為G1和G2.從數(shù)據(jù)集中選取400個數(shù)據(jù)作為初始訓(xùn)練樣本，16個數(shù)據(jù)為有效測試數(shù)據(jù).刺激閾值參數(shù)設(shè)定在[0,1]范圍內(nèi)，選擇初始抗體集合中的20%進(jìn)行克隆和變異，用400個樣本數(shù)據(jù)進(jìn)行訓(xùn)練后,對測試數(shù)據(jù)進(jìn)行仿真，將測試數(shù)據(jù)分為5類，對應(yīng)用戶可能感興趣的5個數(shù)據(jù)種類.仿真結(jié)果如圖5所示.由仿真結(jié)果可以看出，免疫算法能夠能夠較快的實現(xiàn)收斂,并可根據(jù)先驗知識對最優(yōu)解集合加以分類，效率和實用性都能夠得到保證.

4 總結(jié)

Web網(wǎng)絡(luò)數(shù)據(jù)挖掘是一個快速發(fā)展的新的研究方向，由于數(shù)據(jù)量大、分布廣、動態(tài)性和多樣性等特點，使得Web數(shù)據(jù)挖掘一直是智能化查詢領(lǐng)域的難點和熱點以往研究人員提出各種方法對查詢優(yōu)化方法進(jìn)行改進(jìn)，不斷的提高網(wǎng)絡(luò)數(shù)據(jù)查詢的智能化和人性化.本文闡述了Web數(shù)據(jù)挖掘的特點和操作步驟，詳細(xì)討論了免疫算法在Web數(shù)據(jù)挖掘中應(yīng)用中的實際可行的方法.仿真結(jié)果表明，本文所設(shè)計的方法可以有效的提高網(wǎng)絡(luò)數(shù)據(jù)查詢的收斂速度，并能夠?qū)崿F(xiàn)分類提交數(shù)據(jù)，滿足用戶的個性化需求.

〔1〕Hunt J E,Cooke D E.Learning using an artificial immune system[J].Journal of:Network and Computer Applications,1996,19（2）:189-212.

〔2〕Marghny,M.H.andA.F.Ali.Webminingbased on genetic algorithm [J].In Proceedingsof ICGST InternationalConference on Articial Intelligence and Machine Learning（AIML-05）,2005.

〔3〕Goldberg D E.Genetic Algorithms in Search,Optimization&Machine learing.Addison-Wesley Publishing,1989.

〔4〕王昕昕.遺傳算法與網(wǎng)絡(luò)數(shù)據(jù)挖掘[J].電腦知識與技術(shù)，2010，6（2）.

〔5〕王繼成,潘金貴,張福炎.Web文本挖掘技術(shù)研究[J].計算機(jī)研究與發(fā)展,2000,37（5）:513-520.

〔6〕張向鋒,丁斗章.基于免疫學(xué)習(xí)算法的Web數(shù)據(jù)挖掘方法[J].上海電機(jī)學(xué)院學(xué)報，2007（9）:213-216.

〔7〕毛國君,段立娟,王實,等.數(shù)據(jù)挖掘原理與算法[M].北京:清華大學(xué)出版社,2005.

TP311.13

A

1673-260X（2012）09-0030-04