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

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

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

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

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

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

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

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

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

1 預(yù)處理模塊

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

1.1 中文分詞

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

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

1.2 特征提取

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

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

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

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