基于KNN?SVM的垃圾郵件過濾模型

林蔭

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

關鍵詞： 垃圾郵件； 模式識別提取； K近鄰算法； 特征提取

中圖分類號： TN915.08?34； TP393 文獻標識碼： A 文章編號： 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）是包含文字、圖像、視頻的特殊文本，已經成為網絡上交流、溝通的工具[1]。大量統計與研究報告表明，垃圾郵件占了全世界郵件的50%以上，對人們生活、工作帶來了干擾，而且浪費了大量的網絡帶寬[2]。提高垃圾郵件過濾的準確率，保證信息安全，引起了人們的廣泛關注[3]。

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

為了提高垃圾郵件過濾的準確率，加快垃圾郵件的過濾速度，提出了KNN?SVM的垃圾郵件過濾組合模型，并采用中文郵件數據集對KNN?SVM的性能進行測試，以驗證其有效性，同時與當前經典垃圾郵件過濾模型進行對比分析，驗證其優越性。

1 提取郵件特征

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

4 結 語

在垃圾郵件過濾過程中，分類器的設計直接影響過濾效果，針對當前單一KNN和SVM的缺陷，提出了基于KNN?SVM的垃圾郵件過濾模型，結果表明，KNN?SVM能夠改善垃圾郵件的過濾效率，而且可以獲得較高的過濾準確率，具有良好的實際應用價值。

在未來的工作中將引入更優的SVM參數優化方法，對SVM分類能力進行改善以獲得更好的垃圾郵件過濾結果。

參考文獻

[1] 王斌，潘文鋒.基于內容的垃圾郵件過濾技術綜述[J].中文信息學報，2005，19（5）：4?5.

[2] 李國明，湯文亮.反垃圾郵件技術及其最新展望[J].網絡通訊與安全，2007（16）：959.

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

[4] 李瀟，羅軍勇，尹美娟.基于結構特征分析與文本分類的郵件篩選[J].計算機工程與設計，2010，31（21）：4555?4558.

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

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

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

[8] 張俊麗，張帆.改進KNN算法在垃圾郵件過濾中的應用[J].現代圖書情報技術，2007（4）：75?78.

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

[10] 強永妍，楊庚.中文垃圾郵件的索引分詞法的研究與設計[J].計算機應用，2007，27（9）：2234?2236.

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

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