基于改進平衡Winnow算法的短信過濾系統

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

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

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

然而， 短信過濾的準確率依賴于其訓練樣本的數量及質量， 這些分類算法需要經過訓練學習建立分類器模型，因此在速度上不能很好地滿足短信過濾實時性的要求。

從現有技術上來說， 垃圾短信的過濾在準確率和效率方面仍然不能滿足現實需要。

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

Winnow 算法是在1987 年由Nick LittleSTONe 提出并對可行性做了嚴格證明的線性分類算法。當時的目標是想找到一種時空復雜度僅僅與分類對象相關屬性相關的數量呈線性相關的算法。平衡Winnow 算法是對基本Winnow 算法的一種改進， 該算法具有過濾速度快、性能好、支持反饋更新的優點， 在信息過濾領域有很好的應用前景， 尤其適合于對實時性要求較高的短信過濾系統。

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

1 預處理模塊

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

1.1 中文分詞

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

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

1.2 特征提取

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

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

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

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