KNN算法在垃圾郵件過(guò)濾中的應(yīng)用

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

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

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

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