曾垂剛

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

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

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

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

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

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

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

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

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

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

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

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

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

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

參考文獻

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

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

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