基于改進(jìn)平衡Winnow算法的短信過(guò)濾系統

摘要： 將黑白名單技術(shù)與Balanced Winnow 算法相結合，實(shí)現對垃圾短信的過(guò)濾。采用CHI 特征提取算法并對權重計算方法進(jìn)行改進(jìn)， 同時(shí)提出了去除訓練樣本中野點(diǎn)的想法， 通過(guò)判定去除野點(diǎn)， 減緩在訓練過(guò)程中出現的抖動(dòng)現象。實(shí)驗表明這種改進(jìn)對于提高訓練速度及提高短信過(guò)濾的性能均有很好的作用。

手機短信以其短小、迅速、簡(jiǎn)便、價(jià)格低廉等優(yōu)點(diǎn)成為一種重要的通信和交流方式， 受到眾多人士的青睞。然而， 手機短信與郵件一樣存在著(zhù)垃圾信息問(wèn)題。

目前， 垃圾短信過(guò)濾主要有黑名單過(guò)濾、關(guān)鍵詞過(guò)濾和基于文本分類(lèi)的內容過(guò)濾等方式。黑名單過(guò)濾和關(guān)鍵詞過(guò)濾方式能快速過(guò)濾垃圾短信， 但這兩種過(guò)濾方式實(shí)質(zhì)是基于規則的過(guò)濾， 雖然在一定程度上阻擋了一些垃圾短信， 但規則的方法需要更多的用戶(hù)自定義設置，很容易被反過(guò)濾?；谖谋痉诸?lèi)的短信過(guò)濾采用常見(jiàn)的分類(lèi)算法， 如樸素貝葉斯、SVM、神經(jīng)網(wǎng)絡(luò )等。黎路 等人將貝葉斯分類(lèi)應用到J2ME 模擬環(huán)境中成功地過(guò)濾了中獎短信和祝福短信。浙江大學(xué)的金展、范晶等 將樸素貝葉斯和支持向量機結合， 解決了傳統垃圾短信過(guò)濾系統短信特征和內容未能得到及時(shí)更新而導致過(guò)濾性能降低的問(wèn)題。王忠軍將基于樸素貝葉斯短信過(guò)濾算法與基于最小風(fēng)險貝葉斯算法進(jìn)行了實(shí)驗分析和比較，結論是基于最小風(fēng)險的短信過(guò)濾算法具有較好的性能。

然而， 短信過(guò)濾的準確率依賴(lài)于其訓練樣本的數量及質(zhì)量， 這些分類(lèi)算法需要經(jīng)過(guò)訓練學(xué)習建立分類(lèi)器模型，因此在速度上不能很好地滿(mǎn)足短信過(guò)濾實(shí)時(shí)性的要求。

從現有技術(shù)上來(lái)說(shuō)， 垃圾短信的過(guò)濾在準確率和效率方面仍然不能滿(mǎn)足現實(shí)需要。

本文針對現有短信過(guò)濾技術(shù)的不足， 設計了在手機終端的短信過(guò)濾系統， 根據垃圾短信的特點(diǎn)將黑白名單和基于內容過(guò)濾相結合。這種過(guò)濾方式要求能夠快速地對短信進(jìn)行分類(lèi)， 并且能夠實(shí)現用戶(hù)對短信過(guò)濾的個(gè)性化要求， 使垃圾短信過(guò)濾系統具有更好的過(guò)濾性能。

Winnow 算法是在1987 年由Nick LittleSTONe 提出并對可行性做了嚴格證明的線(xiàn)性分類(lèi)算法。當時(shí)的目標是想找到一種時(shí)空復雜度僅僅與分類(lèi)對象相關(guān)屬性相關(guān)的數量呈線(xiàn)性相關(guān)的算法。平衡Winnow 算法是對基本W(wǎng)innow 算法的一種改進(jìn)， 該算法具有過(guò)濾速度快、性能好、支持反饋更新的優(yōu)點(diǎn)， 在信息過(guò)濾領(lǐng)域有很好的應用前景， 尤其適合于對實(shí)時(shí)性要求較高的短信過(guò)濾系統。

本文設計并實(shí)現了一個(gè)基于平衡Winnow 算法的短信內容過(guò)濾系統， 對該算法在短信過(guò)濾系統上的應用進(jìn)行了詳細分析。分類(lèi)器的訓練過(guò)程分成預處理、訓練、分類(lèi)和反饋四個(gè)部分。

1 預處理模塊

預處理模塊包括中文分詞、特征提取以及短信的向量表示子模塊。

1.1 中文分詞

中文分詞是漢語(yǔ)所特有的研究課題。英語(yǔ)、法語(yǔ)等印歐語(yǔ)種詞與詞之間存在著(zhù)自然的分割， 一般不存在分詞的問(wèn)題。本系統采用了目前國內較多使用的中科院計算所開(kāi)發(fā)的漢語(yǔ)詞法分析系統ICTCLAS ( Institute ofComputing Technology ，Chinese Lexical Analysis System) 。

ICTCLAS 3.0 分詞速度單機996 Kb/s，分詞精度98.45%，API 不超過(guò)200 KB， 各種詞典數據壓縮后不到3 MB， 是當前相對較好的漢語(yǔ)詞法分析器。

1.2 特征提取

特征提取的方法目前也有很多， 常用的特征選取方法有： 文檔頻率DF(Document Frequency) 、信息增益IG(Information Gain) 、互信息MI(Mutual Information) 、χ2統計等。

本文將分詞后的詞作為候選特征， 然后使用特征提取算法從中提取出對分類(lèi)最有用的一些特征， 去除對分類(lèi)貢獻不大的候選特征， 以降低特征的維數。其中χ2的主要思想是認為詞條與類(lèi)別之間符合χ2分布。χ2 統計量的值越高， 特征項和類(lèi)別之間的獨立性越小、相關(guān)性越強， 即特征項對此類(lèi)別的貢獻越大。χ2 是一個(gè)歸一化的值， 該方法比其他方法能減少50％左右的詞匯， 具有分類(lèi)效果好的優(yōu)點(diǎn)。本文中采用χ2統計進(jìn)行特征提取。

但不是簡(jiǎn)單地令特征項的權重xi=1 或0 ， 而是令xi=f(χ2)或0 ， 這里χ2 特指特征對應的χ2 統計值， 對應關(guān)系f 根據實(shí)際情況而定。實(shí)驗中(n 是一個(gè)正整數， 取n=4) 。實(shí)驗表明比用布爾權重表示效果要好。

1.3 文本向量表示目前應用較多的是向量空間模型VSM (VectorSpace Model) ， 文中用VSM 將一條短信表示為(W1，W2，…，Wk，…，Wn)的向量形式。其中：Wk(k=1 ，2 ，…，n)為第k 個(gè)特征的權重，n 為選定的特征數。