周自斌

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

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

周自斌

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2.2 信息提?。涸谖臋n被檢索并初步篩選之后，自動(dòng)從中提取有價(jià)值的信息，這一步驟主要是通過(guò)對(duì)頁(yè)面內(nèi)主要字段的語(yǔ)義進(jìn)行識(shí)別來(lái)完成的.

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

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

2 免疫算法原理

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

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

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

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

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

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

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

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

2.2 免疫算法的流程

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

圖3 免疫算法流程圖

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

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

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

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

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

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

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

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

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

定義抗原Ag和抗體Ab的親和度dij以及抗體Abi和抗體Abj間的親和度dij.抗體間親和度值越大,說(shuō)明兩個(gè)抗體越相似,這里采用歐氏距離評(píng)價(jià)抗體間的親和度:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 仿真結(jié)果

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

4 總結(jié)

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

〔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í)與技術(shù)，2010，6（2）.

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

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

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

TP311.13

A

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