基于隨機森林的異常郵件檢測方法研究與實現(xiàn)

，，

（1.湖南工業(yè)大學(xué) 計算機學(xué)院，湖南 株洲 412007；2.中南大學(xué) 自動化學(xué)院，湖南 長沙 410083）

0 引言

近年來，隨著網(wǎng)絡(luò)通信技術(shù)飛速發(fā)展，電子郵件成為人們?nèi)粘Ｉ詈凸ぷ鞯闹饕涣鞣绞街唬惓｀]件問題也隨之而來。異常郵件占用了大量的網(wǎng)絡(luò)資源，對互聯(lián)網(wǎng)中的用戶造成了巨大影響和威脅，甚至導(dǎo)致用戶損失數(shù)據(jù)和金錢。異常郵件破壞性強、傳播速度快、危害范圍廣，如何有效阻斷異常郵件的傳播，提高對異常郵件的判別能力是當(dāng)前研究的迫切要求。為了保護用戶的權(quán)益、減少網(wǎng)絡(luò)帶寬和資源的消耗，異常郵件的鑒別與過濾技術(shù)也逐漸受到研究者的重視。本文結(jié)合隨機森林算法的優(yōu)點，突破郵件特征提取、分類及異常郵件檢測等關(guān)鍵技術(shù)難點，并與典型的算法進行實驗對比分析，實驗結(jié)果表明該方法在準(zhǔn)確率等方面具有明顯優(yōu)勢。

1 國內(nèi)外研究現(xiàn)狀與分析

異常郵件概念自1978年提出以來，全世界的專家學(xué)者對異常郵件檢測技術(shù)進行研究與實踐，至今為止已取得了豐碩的研究成果。

郵件分類檢測方法大體可以分為兩類：基于IP地址的郵件檢測技術(shù)和基于內(nèi)容的郵件檢測技術(shù)[1]。在基于IP地址的郵件檢測技術(shù)中主要包括黑白名單檢測技術(shù)[2]、實時黑名單檢測技術(shù)以及主機名反向驗證技術(shù)[3]等。實際應(yīng)用中，黑名單檢測技術(shù)和白名單檢測技術(shù)通常結(jié)合起來應(yīng)用于服務(wù)器。而基于內(nèi)容的異常郵件檢測技術(shù)是目前主流異常郵件檢測過濾技術(shù)。為了提高過濾效果，反異常郵件產(chǎn)品往往結(jié)合使用多種過濾技術(shù)[4-5]。

郵件的分類其實質(zhì)是對文本信息進行處理，現(xiàn)有的K-近鄰、貝葉斯、神經(jīng)網(wǎng)絡(luò)、支持向量機、決策樹等經(jīng)典機器學(xué)習(xí)算法[6-9]被廣泛應(yīng)用到專利文本分類領(lǐng)域。于是，研究者試圖將對文本的處理方法引入郵件分類處理中，通過文本聚類或分類方法將郵件分為異常和正常兩類。但是與普通文本相比，郵件具有不一樣的特點，它是一種非結(jié)構(gòu)化的文本，采用一般的文本分類算法和傳統(tǒng)的機器學(xué)習(xí)方法不能很好地區(qū)分正常和異常郵件，錯誤率較高[10]。

為了緩解此問題，在研究大量參考文獻的基礎(chǔ)上，課題組發(fā)現(xiàn)隨機森林（random forest，RF）算法是機器學(xué)習(xí)中一個可嘗試的精確分類算法[11-12]，該算法由 Leo Breiman等在21世紀(jì)初提出[13]。它是一種利用多棵決策樹對樣本進行訓(xùn)練并預(yù)測的分類器，與其他算法相比具有以下幾個方面的優(yōu)點：1）具有通用性，適合多種環(huán)境，可用于聚類分析，引導(dǎo)無監(jiān)督聚類、異常檢測和數(shù)據(jù)透視等；2）不需要剪枝，相比單一決策樹算法不易產(chǎn)生過擬合；3）對異常值、噪聲數(shù)據(jù)不敏感，能保持良好的精確度；4）能提取高維數(shù)據(jù)的主要特征，可用于數(shù)據(jù)降維。本文在異常郵件中的過濾技術(shù)基礎(chǔ)上，結(jié)合隨機森林算法，設(shè)計并實現(xiàn)了異常郵件檢測方法。實驗結(jié)果表明，該算法獲得了較高判別率。

2 整體思路

本研究采用的方法在機器學(xué)習(xí)領(lǐng)域被稱作有監(jiān)督學(xué)習(xí)[14-15]（supervised learning）方法，因此實現(xiàn)的流程也按照有監(jiān)督學(xué)習(xí)的基本步驟完成。有監(jiān)督學(xué)習(xí)是指用已知某種特性的樣本作為訓(xùn)練集，以建立一個數(shù)學(xué)模型再用已建立的模型來預(yù)測未知樣本，其流程如圖1所示。

圖1 整體流程圖Fig.1 Overall flow chart

如圖1所示，本文具體思路如下。

1）數(shù)據(jù)清洗。數(shù)據(jù)收集完畢后，由于數(shù)據(jù)集中可能存在無關(guān)或冗余信息，將影響郵件分類的精確度，有必要進行數(shù)據(jù)清洗。具體步驟：根據(jù)indexFolder/indexFile索引文件對郵件數(shù)據(jù)集合（dataSet/data/…）處理，得到處理后的數(shù)據(jù)文件processxx_xxx到dataSet/processSet文件夾下，以及Result_process01到dataSet/firstResult文件夾下。

2）特征提取[16]。分別對獲取的郵件地址、郵件服務(wù)器數(shù)量、郵件發(fā)送時間及郵件內(nèi)容進行特征提取，具體是：對Result_process01文件中數(shù)據(jù)進行特征提取，生成數(shù)據(jù)文件Result_process02到dataSet/secondResult文件夾下，本文為了判斷郵件長度對異常郵件信息量的影響，得到了在不同郵件長度下異常郵件占比，以及在不同郵件長度大小下郵件信息量的大小。

3）數(shù)據(jù)分割。將收集的郵件集按照比例分為測試集和訓(xùn)練集,并輸出到對應(yīng)的文件夾，具體是：對Result_process02文件進行分割（train_test_split）得到x_train、x_test、y_test3個集合，分別對應(yīng)輸出到testSet文件夾下和trainSet文件夾下。

4）模型訓(xùn)練[17]。首先對訓(xùn)練集進行詞頻權(quán)重計算（term frequency-inverse document frequency，tfidf）并做奇異值降解（singular value decomposition，SVD），構(gòu)建對應(yīng)的數(shù)據(jù)矩陣用來填充。

5）結(jié)果分析。經(jīng)過訓(xùn)練后，對分割好的測試集進行預(yù)測得到結(jié)果并進行對比，輸出結(jié)果圖以及結(jié)果表到result文件夾下。

算法的詳細流程如下。

2.1 郵件數(shù)據(jù)集合處理

本研究收集了近10 000封郵件，其中有異常郵件和非異常郵件，已通過索引文件對各個郵件分類，并且按照（spam../data/000/000 或者 ham../data/000/001，前者標(biāo)記為data/000/000是異常郵件，后者標(biāo)記為data/000/001是非異常郵件）格式存放，之后的數(shù)據(jù)處理利用索引文件中存放的信息定位到各個郵件，并獲取各個郵件數(shù)據(jù)。對于單一的文本信息類型郵件，每一封郵件都有著固定的格式（From為發(fā)送方，To為接收方，Date為日期，Content為具體內(nèi)容）。為了方便后續(xù)特征提取，此處按照郵件固定格式將所有郵件合并，每一封郵件內(nèi)所有信息按照固定格式排成一行（將一封郵件按照From、To、Date、Content的格式放在一行上），制作成二維表的形式合并到一個文本文件中。即從10 000封郵件文本中，將各個郵件文本按格式提取，之后壓縮到同一個文本文件中方便處理。

2.2 特征提取

異常郵件的建模與過濾過程中，無法直接對異常郵件進行過濾操作，首先需要對異常郵件進行分析，找出一些關(guān)鍵元素，如詞、字或短詞等，從而提取郵件特征[18]。為了提高過濾效果，使用正則表達式對分詞后的郵件進行二次處理[19]。對郵件數(shù)據(jù)集合處理完畢后，得到一個由二維表[20]填充的文本文檔。具體方法如下：

1）對郵件地址的提取。采用正則表達式re.findall(r"@([A-Za-z0-9]*.[A-Za-z0-9.]+)",str(str1))根據(jù)郵件格式獲取郵件地址。

2）對郵件服務(wù)器數(shù)量提取。str(df.xx_address.unique().shape)將獲取的郵件地址進行歸一化處理，得到郵件收發(fā)服務(wù)器類別的數(shù)量。

3）對時間的提取。采用rex=r"([A-Za-z]+d?[AZa-z]*).*?(d{2}):d{2}:d{2}.*"提取時間。

同樣利用正則表達式根據(jù)格式對時間進行提取，獲取的結(jié)果少數(shù)為none，另外一部分則根據(jù)時間段劃分（由于某一封郵件是否是異常郵件并不能僅根據(jù)一個準(zhǔn)確的時間來判斷，因此劃分不同時間段作為特征提取出來）。

4）對內(nèi)容長度提取。根據(jù)數(shù)據(jù)清洗完成后的文件，通過二維表格形式讀取，并獲取內(nèi)容列中不同的長度，然后對不同長度段分不同類型（由于某一封郵件是否是異常郵件并不能僅根據(jù)一個準(zhǔn)確的內(nèi)容長度來判斷，因此劃分不同內(nèi)容長度類型作為特征提取出來），此處將內(nèi)容長度不大于10的劃分為0，不大于100的劃分為1，不大于500的劃分為2，不大于1 000的劃分為3，…，不大于50 000的劃分為13，否則為14。圖2為郵件長度對異常郵件所占比例的影響。

圖2 郵件長度對異常郵件所占比例的影響Fig.2 Effect of mail length on the proportion of abnormal mail

從圖2的實驗結(jié)果可以看出，郵件內(nèi)容長度類型不大于1時，異常郵件占比高，不小于2時占比逐漸下降。而郵件內(nèi)容長度類型在2到10之間時，異常郵件占比隨內(nèi)容長度呈現(xiàn)凸增長，在7的位置達到極大值，而后趨減。

2.3 數(shù)據(jù)集分割以及模型訓(xùn)練

在經(jīng)過了上述的郵件集合處理以及特征提取之后，讀取得到的文件并進行分割。利用sklearn.model_selection 中的train_test_split隨機將 10 000 封郵件集按照比例分為測試集和訓(xùn)練集，并輸出到對應(yīng)的文件夾下。再將訓(xùn)練集合中已經(jīng)分詞好的內(nèi)容部分進行類型轉(zhuǎn)換，從文本數(shù)據(jù)轉(zhuǎn)換為數(shù)值型數(shù)據(jù)以進行特征提取，也就是tf-idf權(quán)重計算部分，即詞頻以及逆文本頻率指數(shù)的計算，再將數(shù)據(jù)進行模型轉(zhuǎn)換得到數(shù)據(jù)模型。

2.4 模型填充

由于在sklearn庫中已有對各個算法的詳細實現(xiàn)，本文只需按參數(shù)要求，向各個算法實現(xiàn)的函數(shù)填充數(shù)據(jù)參數(shù)即可獲得對應(yīng)的算法模型。另因本文主要研究隨機森林算法，而隨機森林算法又基于決策樹，所以此處僅列出決策樹算法和隨機森林算法在模型填充時候的參數(shù)選擇。本文經(jīng)過多次調(diào)參，力求得到最精確的結(jié)果。下面提供關(guān)于決策樹分類器以及隨機森林分類器主要參數(shù)。

decision_tree算法：

在構(gòu)建decision_tree模型時，采用sklearn.tree下的DecisionTreeClassisfier的決策樹分類器模型，設(shè)置參數(shù)如下。

1）criterion為切分質(zhì)量的評價準(zhǔn)則。默認(rèn)為'mse'(mean squared error)。

2）splitter為在每個節(jié)點切分的策略。

3）max_depth為指定樹的最大深度。如果為None，則表示樹的深度不限，直到每個葉子都是純凈的，即葉節(jié)點中所有樣本都屬于同一個類別，或者葉子節(jié)點中包含小于min_samples_split個樣本。

4）random_state。該參數(shù)如果為整數(shù)，則它指定了隨機數(shù)生成器的種子；如果為RandomState實例，則指定了隨機數(shù)生成器；如果為None，則使用默認(rèn)的隨機數(shù)生成器。

5）max_leaf_nodes。如果為None，則葉子節(jié)點數(shù)量不限。如果不為None，則max_depth被忽略。

random_forest算法：

random_forest本身是建立在decision_tree的基礎(chǔ)上，在構(gòu)建random_forest模型時，采用sklearn.svm下的隨機森林分類器模型，設(shè)置參數(shù)如下：

1）n_estimators。該參數(shù)為弱學(xué)習(xí)器的最大迭代次數(shù)，或者是最大弱學(xué)習(xí)器的個數(shù)。一般來說參數(shù)越小，越容易欠擬合；越大，越容易過擬合。默認(rèn)為10，實際參數(shù)和learning_rate一起考慮。

2）criterion。對樹做劃分時，對特征的評價標(biāo)準(zhǔn)。分類模型和回歸模型的損失函數(shù)不同。分類RF對應(yīng)的有基尼指數(shù)gini，另一個標(biāo)準(zhǔn)是信息增益，回歸RF默認(rèn)是均方差mse，另一個可選擇的標(biāo)準(zhǔn)是絕對值差mae，本文采用信息增益作為劃分標(biāo)準(zhǔn)，下文將進行討論。

3）max_depth。該參數(shù)為樹的最大深度，默認(rèn)為None，直到使每一個葉節(jié)點只有一個類別，或是達到min_samples_split。

4）random_state。如果給定相同的參數(shù)和訓(xùn)練數(shù)據(jù)，random_state的確定值將始終產(chǎn)生相同的結(jié)果。一個具有不同隨機狀態(tài)的多個模型的集合，并且所有最優(yōu)參數(shù)有時比單個隨機狀態(tài)更好。

3 算法描述

3.1 決策樹算法

決策樹是數(shù)據(jù)挖掘領(lǐng)域應(yīng)用最廣泛的方法之一，在很多實際應(yīng)用中都被采用。它是一種非線性監(jiān)督學(xué)習(xí)模型，能將數(shù)據(jù)分成不同的類別并對未知數(shù)據(jù)進行預(yù)測。決策模型將結(jié)果分解為if-then-else規(guī)則，并以樹型結(jié)構(gòu)展示。這種樹形模型的高可讀性使得人機更易于理解發(fā)現(xiàn)的知識。推斷決策樹的過程主要由以下幾個方面決定：

1）分割標(biāo)準(zhǔn)，即用于選擇要插入節(jié)點和分支屬性的方法；

2）停止分支的標(biāo)準(zhǔn)；

3）在葉節(jié)點上分配類標(biāo)簽或概率分布的方法；

4）用于簡化樹結(jié)構(gòu)的后修剪過程。

目前有兩種分割標(biāo)準(zhǔn)：傳統(tǒng)的分割標(biāo)準(zhǔn)和基于不精確概率的分割標(biāo)準(zhǔn)。區(qū)分它們的一個基本點是如何從數(shù)據(jù)中獲得概率。通常，傳統(tǒng)標(biāo)準(zhǔn)使用香農(nóng)準(zhǔn)則作為信息的基本測度。而基于不精確概率的準(zhǔn)則使用最大熵測度，這種測量方法基于最大不確定度原理，在經(jīng)典信息理論中被廣泛使用，稱為最大信息增益（information gain，IG）原理，本文在構(gòu)建決策樹時也是采用這種方法。

設(shè)屬性X為一般特征，其值屬于 {x1,x2,…,xt}，信息增益IG解釋如下：

1）數(shù)據(jù)集D的熵C定義為

2）屬性X生成的平均熵為

3）最后可得信息增益（IG）為

3.2 隨機森林算法

隨機森林是由多顆決策樹構(gòu)成的。如果必須對一個新實例進行分類，那么這個實例的特性將呈現(xiàn)給森林中的每顆決策樹，每顆決策樹返回一個分類值，投票給該類。最后，由隨機森林給出的分類值是與類變量的最優(yōu)投票相關(guān)聯(lián)的值，超過了森林中的所有決策樹。每顆決策樹具有以下特征：

1）若N是一個數(shù)據(jù)集中的實例數(shù)，那么隨機森林從原始數(shù)據(jù)中選擇一個隨機樣本，替換N個實例，此樣本將作為構(gòu)建決策樹的訓(xùn)練集。

2）若M是數(shù)據(jù)集中的特征數(shù)，則指定一個m<

3）對于樹中的每一個節(jié)點，

①從M個原始特征中隨機選擇m個特征；

②根據(jù)這m個特征計算分割標(biāo)準(zhǔn)，具有最佳值的特征用于拆分節(jié)點。

4）在構(gòu)建完每顆決策樹之后沒有修剪。

4 實驗及結(jié)果分析

4.1 實驗環(huán)境及數(shù)據(jù)說明

實驗平臺包括：

操作系統(tǒng)為Windows10；

IDE 為Pycharm 2019.1.1，Python 3.7.3；

實驗數(shù)據(jù)為10 000封郵件，其中有一定數(shù)量異常郵件和一定數(shù)量非異常郵件，均由IndexFile的索引文件指明（spam代表異常郵件，ham代表非異常郵件）。

4.2 實驗結(jié)果及分析

本文從3個指標(biāo)對算法性能進行對比分析，具體定義如下：

FN（false negative），被判定為負樣本、事實上是正樣本的數(shù)目。

FP（false positive），被判定為正樣本、事實上是負樣本的數(shù)目。

TN（true negative），被判定為負樣本、事實上也是負樣本的數(shù)目。

TP（true positive），被判定為正樣本、事實上也是正樣本的數(shù)目。

準(zhǔn)確率=所有預(yù)測正確的樣本/總的樣本，即，（TP+TN）/總樣本數(shù)目；在本文中，準(zhǔn)確率=對異常郵件測試集中預(yù)測的樣本數(shù)目/所有測試集中的樣本數(shù)目；

召回率=將正類預(yù)測為正類/所有正真的正類，即，TP/（TP+TN）；在本文中召回率=對異常郵件測試集中預(yù)測的樣本數(shù)目/所有測試集中的異常郵件樣本數(shù)目。

F1值=正確率*召回率*2/(正確率+召回率)；F1值是精確率和召回率的調(diào)和平均數(shù)。

本文采用了準(zhǔn)確率、召回率、F1值3個主要的評判標(biāo)準(zhǔn)，并對6種算法，包括隨機森林、K最近鄰（k-NearestNeighbor，KNN）、梯度提升樹（gradient Boosting decison tree，gbdt）、貝葉斯、決策樹、支持向量機（support vector machine，SVM），在上述3個標(biāo)準(zhǔn)和模型構(gòu)建時間上進行對比。測試郵件集合的大小分別為500,1 000,1 500,2 000,2 500，對比結(jié)果分別如圖3～6所示。

圖3 準(zhǔn)確率對比圖Fig.3 Accuracy comparison chart

圖4 召回率對比圖Fig.4 Recall rate comparison chart

圖5 F1值對比圖Fig.5 Comparison chart of F1 values

圖6 模型構(gòu)建時間對比圖Fig.6 Model construction time contrast diagram

從控制臺輸出結(jié)果以及對比圖中不難發(fā)現(xiàn)，在同組訓(xùn)練集與測試集的情況下，隨機森林算法的準(zhǔn)確率為0.985 89，召回率為0.993 68，F(xiàn)1 值為0.989 77，均優(yōu)于其它算法。但在模型構(gòu)建時間上隨機森林算法慢于貝葉斯算法、決策樹算法、KNN。不過，由于計算機性能不斷增強，并且出現(xiàn)了云計算以及并行計算等計算模式，在模型構(gòu)建時間上，并不是一個嚴(yán)重的問題。

5 總結(jié)與展望

異常郵件檢測是一個概率性問題，準(zhǔn)確率不高或者誤判都會給用戶帶來困擾。通過實驗分析表明本文采用的隨機森林算法比其他幾種算法有明顯優(yōu)勢。但仍存在以下幾個方面可以進一步研究：

1）一個足夠大的郵件集合數(shù)據(jù)庫對異常郵件的檢測非常重要，樣本量越大也越能高精準(zhǔn)的預(yù)判未知郵件。因此合理構(gòu)建一個共享的郵件集合倉庫是有必要的。

2）異常郵件類型件在不斷變化，利用單一的異常郵件檢測機制是不合理的，可以考慮在不同的算法之間取長補短，將各種算法進行整合，以達到更高的準(zhǔn)確率。

3）也同樣由于本文只是針對于純文本的郵件格式，格式單一，而異常郵件在當(dāng)今社會不只是文本類型，比如音頻、視頻、壓縮文件等異常郵件。近年來，研究人員對圖像異常郵件的識別和過濾技術(shù)的研究較為關(guān)注，但當(dāng)前研究出的過濾系統(tǒng)都不能很好地實現(xiàn)異常郵件圖像的識別和分類，難以滿足圖像型異常郵件過濾的準(zhǔn)確性、實時性及高效性要求。