1、KNNKNN算法在垃圾算法在垃圾郵件過濾郵件過濾中的應用中的應用第七組第七組1.引言 目前,常用的垃圾郵件過濾算法主要有:黑白名單過濾法、基于規則的方法和基于統計的方法。而KNN(KNearestNeighbor)就是一種簡單的基于統計的過濾算法。2.系統設計 應用郵件過濾，將訓練文本分為合法郵件和垃圾郵件,進行預處理,并提取特征詞,將處理結果存入訓練集數據庫;待測文本經過特征提取后,與訓練集數據庫中的全部訓練文本進行相似度計算,利用KNN分類器,將待測文本進行分類。若待測文本被判為合法郵件,則系統輸出該郵件,否則,系統予以過濾。3 文本預處理 （1） 文本表示 用向量空間模型表示文本, 然后

2、排除停用詞,合并數字和人名等詞匯,并統計詞頻。 （2）特征提取 對詞進行特征項選擇,可以降低向量空間的維數,提高程序運行效率。考慮到垃圾郵件所出現的詞特征突出(如/賺錢0、/成人0等),過濾時只需考慮這些特征詞即可,故在電子郵件過濾系統中,采用互信息進行特征提取效果比較好。互信息量越大,名詞和類別同時出現的概率就越大,因此應該選擇互信息大的詞作為特征詞。 （3）相似度計算 在KNN算法中,相似度的選擇也很重要,算法的關鍵就在于找出與其最相似的K個文本,利用夾角余弦 計算相似度。 其中,m為特征向量的維數k,wik表示第i個文本的第k個特征項的權重值。4.經典KNN算法 算法的基本思路:在訓練文

3、本集中找出與待測文本距離最近的K個文本,然后計算新文本屬于每類的權重,最后將其分到權重最大的一類中,算法如下:(1)在訓練文本集中選出與待測文本最相似的K個文本。(2)依次計算新文本屬于每類的權重,計算公式如下: 其中,x為新文本的特征向量,y(xi,cj)為類別屬性函數,如果文本xi屬于類cj,那么函數值為1,否則為0。(3)比較權重值,將新文本劃分到權重最大的那個類別中。5.改進的KNN算法 在經典KNN算法中,一般先設定一個初始K值,然后根據實驗測試的結果調整K的大小,然而,在電子郵件過濾系統中,K值不能自動調整,而且K取值不當或訓練文本分布不均會降低過濾性能,影響過濾效果。因此,對KN

4、N的權重算法進行改進,使其能適應動態變化的電子郵件過濾系統。 垃圾郵件過濾的性能評價通常借用文本分類的相關指標。評估映射準確程度的參照物是人工分類結果，測試結果與人工分類結果越相近,分類的準確程度就越高。實驗 本實驗的測試語料來源于Ling-Spam14,它是由希臘學者Androutsopoulos等人提供,由提供者收到的垃圾郵件和來自于語言學家郵件列表(LinguistList)的合法郵件構成,其公用的合法郵件沒有加密。語料中含合法郵件2412篇,垃圾郵件481篇,為了驗證訓練文本集集的分布對過濾性能的影響,本文選取合法郵件50篇,垃圾郵件480篇,取其中4/5作為訓練集,1/5為測試集,改變K值進行實驗,并計算其平均值,實驗中L=9,實驗結果如表所示 由上表看出: 隨著K值的增大,經典KNN正確率減小,而召回率增大,這是因為本文實驗樣本中,合法郵件數量小于非法郵件,系統將待測文本分到垃圾郵件類的概率增大,所以此算法將合法郵件誤判為垃圾郵件的可能性大,而垃圾郵件漏網的少,改進KNN受K值變化影響不大。通過比較改進KNN和經典KNN的值可