曾垂剛

【摘 要】在對(duì)互聯(lián)網(wǎng)信息過濾分析的基礎(chǔ)上，提出了一個(gè)新的反垃圾郵件方案。介紹了遺傳算法在該系統(tǒng)中的應(yīng)用，針對(duì)垃圾郵件的先驗(yàn)知識(shí)往往體現(xiàn)在對(duì)原始數(shù)據(jù)中有價(jià)值的特征屬性變量集的選擇上，利用遺傳算法對(duì)特征屬性變量子集的選擇進(jìn)行優(yōu)化，找到相對(duì)最優(yōu)的由特征向量表示的特征屬性變量集。

【關(guān)鍵詞】適應(yīng)度 反垃圾郵件 數(shù)據(jù)挖掘

【中圖分類號(hào)】TP3【文獻(xiàn)標(biāo)識(shí)碼】A【文章編號(hào)】1672-5158（2013）02-0163-02

該遺傳算法生成的模型建立在解決垃圾郵件的數(shù)據(jù)分析的新方法基礎(chǔ)上。在模型的決策樹上，每個(gè)結(jié)點(diǎn)數(shù)據(jù)被設(shè)計(jì)成擁有一個(gè)隨機(jī)系數(shù)，這樣的話，數(shù)據(jù)與系數(shù)相乘成為判斷該項(xiàng)數(shù)據(jù)記錄是否代表郵件合法的確定性權(quán)重。這里的系數(shù)基于Ephemeral Random Constants（ERC），是特定于數(shù)學(xué)建模的遺傳算法生成的隨機(jī)數(shù)。該系數(shù)的微小變化也會(huì)導(dǎo)致進(jìn)化變異產(chǎn)生。

此系統(tǒng)中，之所以要選取特征子集，是考慮到特征子集的選取是在反垃圾郵件中提高機(jī)器學(xué)習(xí)算法性能的可行辦法。特征子集的選取能提高學(xué)習(xí)算法的準(zhǔn)確度，減少計(jì)算量，同時(shí)可以減少測(cè)試數(shù)據(jù)量，降低分類過程中的消耗等。進(jìn)行特征子集選取，最重要的目標(biāo)就是提高郵件檢測(cè)的準(zhǔn)確率，減少分類運(yùn)算等過程中的數(shù)據(jù)量。

在系統(tǒng)調(diào)用序列數(shù)據(jù)的挖掘過程中，使用特征向量法，用特征向量的一位標(biāo)識(shí)一個(gè)短序列，用挖掘算法就能從特征向量集中找出垃圾郵件的規(guī)則來。然而，由于短序列的數(shù)量較大，導(dǎo)致特征向量位數(shù)過大，特征向量集也相應(yīng)過大。為了更高效可行地使用數(shù)據(jù)挖掘算法，采用遺傳算法對(duì)特征向量集進(jìn)行優(yōu)化，尋找特征子集，利于后續(xù)的數(shù)據(jù)挖掘。

在使用遺傳算法的過程中，用特征向量的位數(shù)決定其個(gè)體的大小，隨機(jī)構(gòu)造50個(gè)二進(jìn)制位串的個(gè)體，其中“0”、“1”代表該位置的短序列是否入選特征子集，如圖2所示。在此基礎(chǔ)上，進(jìn)行遺傳得到最優(yōu)個(gè)體，該最優(yōu)個(gè)體必然是“0”、“1”交替的位串，將其所有“1”所在位置進(jìn)行分析，可以得到“1”所在位置代表的短序列集，這就是要尋找的特征子集。后續(xù)挖掘算法根據(jù)該特征子集中的短序列，對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行分類等挖掘工作。（如圖2）

采用標(biāo)準(zhǔn)交叉算子和變異算子，交叉概率取0.6，變異概率取0.001。遺傳過程中，個(gè)體的選擇比較復(fù)雜。因?yàn)檫@里是針對(duì)垃圾郵件檢測(cè)進(jìn)行的優(yōu)化，所以在選擇個(gè)體時(shí)，是將該個(gè)體代表的入選子集的短序列應(yīng)用到數(shù)據(jù)分類算法（RIPPER），該算法訓(xùn)練數(shù)據(jù)并應(yīng)用規(guī)則得到測(cè)試數(shù)據(jù)，根據(jù)檢測(cè)的性能來確定上述要選擇的個(gè)體的適應(yīng)度值。根據(jù)個(gè)體的適應(yīng)度值就可以對(duì)其進(jìn)行選擇，繼續(xù)遺傳優(yōu)化工作。

研究表明，個(gè)體的適應(yīng)值可以取決于有垃圾郵件被正確檢測(cè)到和有正常郵件被誤判為攻擊，同時(shí)考慮個(gè)體中置“1”位的數(shù)目。本系統(tǒng)設(shè)計(jì)的適應(yīng)度函數(shù)為：F（Xi）=（a/A-b/B）/（δ*m）；Xi表示某個(gè)個(gè)體，（a/A-b/B）的含意正如前述，m是Xi中“1”的個(gè)數(shù)，δ是m對(duì)于該適應(yīng)度函數(shù)的相關(guān)系數(shù)。也就是說，a/A是檢出率，b/B是誤報(bào)率，高檢出率低誤報(bào)率使適應(yīng)度函數(shù)值高，低檢出率高誤報(bào)率使適應(yīng)度函數(shù)值低。個(gè)體中置“1”的位數(shù)越少，適應(yīng)度值越大，當(dāng)然這是出于尋找最小特征子集的考慮，其影響的強(qiáng)弱，用相關(guān)系數(shù)δ去控制。

本系統(tǒng)采用的遺傳算法的基本步驟如下：

1.設(shè)定進(jìn)化代數(shù)g=0，生成包含n個(gè)個(gè)體的初始化群體P（g）；

2.在該群體中對(duì)每個(gè)個(gè)體估值，計(jì)算各自適應(yīng)度f（x）；

3.通過如下步驟，生成新的群體P（g+1）：

A.根據(jù)個(gè)體適應(yīng)度f（x），從P（g）中選擇兩個(gè)個(gè)體作為父代；（適應(yīng)度值越大，選中的機(jī)會(huì)越大）；

參考文獻(xiàn)

[1] Richard Blum，開放源碼郵件系統(tǒng)安全，人民郵電出版社，2002年11月

[2] 曹麒麟，張千里，垃圾郵件與反垃圾郵件技術(shù)，人民郵電出版社， 2003年2月

[3] 黃羽.基于智能體技術(shù)的入侵檢測(cè)系統(tǒng)及相關(guān)技術(shù)研究：[碩士學(xué)位論文]，電子科技大學(xué)，2003年3月