林蔭

摘 要： 垃圾郵件具有特征維數(shù)高、樣本不平衡等特點(diǎn)，針對(duì)近鄰算法（KNN）或支持向量機(jī)（SVM）存在虛警率高等難題，基于組合優(yōu)化理論，提出基于KNN?SVM的垃圾郵件過濾組合模型。首先提取垃圾郵件的特征項(xiàng)，并構(gòu)建垃圾郵件過濾模型的輸入向量，然后采用KNN對(duì)垃圾郵件訓(xùn)練樣本進(jìn)行選擇，將訓(xùn)練樣本縮減到k個(gè)，并采用支持向量機(jī)對(duì)[k]個(gè)樣本訓(xùn)練和建模進(jìn)行垃圾郵件過濾，最后采用中文郵件集對(duì)KNN?SVM的性能進(jìn)行分析。結(jié)果表明，KNN?SVM提高了垃圾郵件過濾的準(zhǔn)確率，大幅度降低了虛警率，而且垃圾郵件的過濾速度可以滿足郵件處理的在線需求。

關(guān)鍵詞： 垃圾郵件； 模式識(shí)別提??； K近鄰算法； 特征提取

中圖分類號(hào)： TN915.08?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）23?0090?03

Spam mail filtering model based on K nearest neighbor algorithm

and support vector machine

LIN Yin

（Changzhou University Huaide College， Changzhou 213016， China）

Abstract： The spam mail has the characteristics of high feature dimension， unbalance sample， etc. To overcome the high false alarm rate existing in K nearest neighbor （KNN） algorithm or support vector machine （SVM）， a spam mail filtering combination model based on KNN?SVM is proposed according to the combinatorial optimization theory. The feature items of spam mail are extracted to construct the input vector of the spam mail filtering model. And then the KNN algorithm is used to select the training samples of spam mail， so as to reduce the quantity training samples to k. The support vector machine is used to train and model the k samples for spam mail filtering. The Chinese mail set is used to analyze the performance of KNN?SVM. The results show that the KNN?SVM based model improved the accuracy of spam mail filtering， reduced the false alarm rate greatly， and the filtering speed of spam mail can meet the online demand of mail processing.

Keywords： spam mail； pattern recognition and extraction； K nearest neighbor algorithm； feature extraction

0 引 言

電子郵件（Email）是包含文字、圖像、視頻的特殊文本，已經(jīng)成為網(wǎng)絡(luò)上交流、溝通的工具[1]。大量統(tǒng)計(jì)與研究報(bào)告表明，垃圾郵件占了全世界郵件的50%以上，對(duì)人們生活、工作帶來了干擾，而且浪費(fèi)了大量的網(wǎng)絡(luò)帶寬[2]。提高垃圾郵件過濾的準(zhǔn)確率，保證信息安全，引起了人們的廣泛關(guān)注[3]。

垃圾郵件過濾的實(shí)質(zhì)是對(duì)郵件進(jìn)行分類，將其識(shí)別為合法郵件或者垃圾郵件，若為垃圾郵件則過濾掉，否則讓其通過[4]。垃圾郵件過濾是一種分類問題，分類器的構(gòu)建直接影響過濾效果，當(dāng)前常采用K近鄰算法（K Nearest Neighbor Algorithm，KNN）和支持向量機(jī)（Support Vector Machine，SVM）[5?7]建立垃圾郵件過濾的分類器，對(duì)于英文郵件，它們獲得了理想的過濾效果，垃圾郵件過濾的虛警率低[8]。對(duì)于中文郵件，過濾效果卻很差，這是因?yàn)橹形睦]件是一種超文本，不僅具有一般文本的特征，而且樣本極不平均、特征維數(shù)高，采用KNN進(jìn)行處理，易出現(xiàn)“維數(shù)災(zāi)”難題，過濾速度慢；SVM雖然不存在“維數(shù)災(zāi)”難題，但是對(duì)于大規(guī)模垃圾郵件，訓(xùn)練時(shí)間長(zhǎng)，無法滿足垃圾郵件在線過濾要求[9?11]。

為了提高垃圾郵件過濾的準(zhǔn)確率，加快垃圾郵件的過濾速度，提出了KNN?SVM的垃圾郵件過濾組合模型，并采用中文郵件數(shù)據(jù)集對(duì)KNN?SVM的性能進(jìn)行測(cè)試，以驗(yàn)證其有效性，同時(shí)與當(dāng)前經(jīng)典垃圾郵件過濾模型進(jìn)行對(duì)比分析，驗(yàn)證其優(yōu)越性。

1 提取郵件特征

垃圾郵件的建模與過濾過程中，無法直接對(duì)垃圾郵件進(jìn)行過濾操作，首先需要對(duì)郵件內(nèi)容進(jìn)行分析，找出一些關(guān)鍵元素，如詞、字或短詞等，從而提取郵件特征。通常采用有向圖描述郵件內(nèi)容，結(jié)構(gòu)見圖1，S表示郵件中的句子，NP表示郵件中的名詞，VP表示郵件中的動(dòng)詞，PP表示郵件的介詞短語。

4 結(jié) 語

在垃圾郵件過濾過程中，分類器的設(shè)計(jì)直接影響過濾效果，針對(duì)當(dāng)前單一KNN和SVM的缺陷，提出了基于KNN?SVM的垃圾郵件過濾模型，結(jié)果表明，KNN?SVM能夠改善垃圾郵件的過濾效率，而且可以獲得較高的過濾準(zhǔn)確率，具有良好的實(shí)際應(yīng)用價(jià)值。

在未來的工作中將引入更優(yōu)的SVM參數(shù)優(yōu)化方法，對(duì)SVM分類能力進(jìn)行改善以獲得更好的垃圾郵件過濾結(jié)果。

參考文獻(xiàn)

[1] 王斌，潘文鋒.基于內(nèi)容的垃圾郵件過濾技術(shù)綜述[J].中文信息學(xué)報(bào)，2005，19（5）：4?5.

[2] 李國(guó)明，湯文亮.反垃圾郵件技術(shù)及其最新展望[J].網(wǎng)絡(luò)通訊與安全，2007（16）：959.

[3] 梁志文，楊金民，李元旗.基于多項(xiàng)式模型和低風(fēng)險(xiǎn)的貝葉斯垃圾郵件過濾算法[J].中南大學(xué)學(xué)報(bào)（自然科學(xué)版），2013，44（7）：2787?2792.

[4] 李瀟，羅軍勇，尹美娟.基于結(jié)構(gòu)特征分析與文本分類的郵件篩選[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010，31（21）：4555?4558.

[5] 鄭煒，沈文，張英鵬.基于改進(jìn)樸素貝葉斯算法的垃圾郵件過濾器的研究[J].西北工業(yè)大學(xué)學(xué)報(bào)，2010，28（4）：622?627.

[6] 李雯，劉培玉.基于貝葉斯的垃圾郵件過濾算法的研究[J].計(jì)算機(jī)工程與應(yīng)用，2007，43（23）：174?177.

[7] 陳琴，梁家榮.基于遺傳算法和發(fā)送行為的垃圾郵件檢測(cè)模型[J].廣西大學(xué)學(xué)報(bào)（自然科學(xué)版），2010，35（6）：1007?1010.

[8] 張俊麗，張帆.改進(jìn)KNN算法在垃圾郵件過濾中的應(yīng)用[J].現(xiàn)代圖書情報(bào)技術(shù)，2007（4）：75?78.

[9] 鄒漢斌，雷紅艷，鄧衛(wèi)紅.支持向量機(jī)在反垃圾郵件過濾中的應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì)，2007，28（9）：2015?2017.

[10] 強(qiáng)永妍，楊庚.中文垃圾郵件的索引分詞法的研究與設(shè)計(jì)[J].計(jì)算機(jī)應(yīng)用，2007，27（9）：2234?2236.

[11] 雷劍剛，孫細(xì)斌.一種智能垃圾郵件過濾模型的仿真研究[J].計(jì)算機(jī)仿真，2013，30（5）：370?373.

[12] 閆鵬，鄭雪峰，朱建勇，等.一種基于嵌入式特征選擇的垃圾郵件過濾模型[J].小型微型計(jì)算機(jī)系統(tǒng)，2009，30（8）：1616?1620.