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

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

2、均有很好的作用。 手機短信以其短小、迅速、簡便、價格低廉等優(yōu)點成為一種重要的通信和交流方式， 受到眾多人士的青睞。然而， 手機短信與郵件一樣存在著垃圾信息問題。 目前， 垃圾短信過濾主要有黑名單過濾、關鍵詞過濾和基于文本分類的內容過濾等方式。黑名單過濾和關鍵詞過濾方式能快速過濾垃圾短信， 但這兩種過濾方式實質是基于規(guī)則的過濾， 雖然在一定程度上阻擋了一些垃圾短信， 但規(guī)則的方法需要更多的用戶自定義設置，很容易被反過濾?；谖谋痉诸惖亩绦胚^濾采用常見的分類算法， 如樸素貝葉斯、SVM、神經網絡等。黎路 等人將貝葉斯分類應用到J2ME 模擬環(huán)境中成功地過濾了中獎短信和祝福短信。浙江大學的金展、范晶

3、等 將樸素貝葉斯和支持向量機結合， 解決了傳統垃圾短信過濾系統短信特征和內容未能得到及時更新而導致過濾性能降低的問題。王忠軍將基于樸素貝葉斯短信過濾算法與基于最小風險貝葉斯算法進行了實驗分析和比較，結論是基于最小風險的短信過濾算法具有較好的性能。 然而， 短信過濾的準確率依賴于其訓練樣本的數量及質量， 這些分類算法需要經過訓練學習建立分類器模型，因此在速度上不能很好地滿足短信過濾實時性的要求。 從現有技術上來說， 垃圾短信的過濾在準確率和效率方面仍然不能滿足現實需要。 本文針對現有短信過濾技術的不足， 設計了在手機終端的短信過濾系統， 根據垃圾短信的特點將黑白名單和基于內容過濾相結合。這種過濾

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

5、用進行了詳細分析。分類器的訓練過程分成預處理、訓練、分類和反饋四個部分。 1 預處理模塊 預處理模塊包括中文分詞、特征提取以及短信的向量表示子模塊。 1.1 中文分詞 中文分詞是漢語所特有的研究課題。英語、法語等印歐語種詞與詞之間存在著自然的分割， 一般不存在分詞的問題。本系統采用了目前國內較多使用的中科院計算所開發(fā)的漢語詞法分析系統ICTCLAS ( Institute Technology ，Chinese Lexical Analysis System) 。 ICTCLAS 3.0 分詞速度單機996 Kb/s，分詞精度98.45%，API 不超過200 KB， 各種詞典數據壓縮后不到3

6、 MB， 是當前相對較好的漢語詞法分析器。 1.2 特征提取 特征提取的方法目前也有很多， 常用的特征選取方法有： 文檔頻率DF(Document Frequency) 、信息增益IG(Information Gain) 、互信息MI(Mutual Information) 、2統計等。 本文將分詞后的詞作為候選特征， 然后使用特征提取算法從中提取出對分類最有用的一些特征， 去除對分類貢獻不大的候選特征， 以降低特征的維數。其中2分布。2 是一個歸一化的值， 該方法比其他方法能減少50左右的詞匯， 具有分類效果好的優(yōu)點。本文中采用2統計進行特征提取。 但不是簡單地令特征項的權重xi=1 或0

7、， 而是令xi=f(2 特指特征對應的(n 是一個正整數， 取n=4) 。實驗表明比用布爾權重表示效果要好。 1.3 文本向量表示目前應用較多的是向量空間模型VSM (VectorSpace Model) ， 文中用VSM 將一條短信表示為(W1，W2，Wk，Wn)的向量形式。其中：Wk(k=1 ，2 ，n)為第k 個特征的權重，n 為選定的特征數。 2 構造分類器 訓練分類器是研究的重點，采用Balanced Winnow 算法并對其進行改進。 2.1 Winnow 分類算法 Winnow 算法是二值屬性數據集上的線性分類算法。線性分類問題中表示分類界限的超平面等式如下： w00+w11+w

8、22+wkk=0 ， 其中：0，1，k分別是屬性的值；w0，w1， ，wk是超平面的權值。如果其值大于0 ， 則預測為第一類否則為第二類。 Winnow 算法是錯誤驅動型的分類算法， 即當出現錯分的實例時才更新權值向量。設定兩個學習系數 和(其中1，1) ， 通過將權值乘以參數( 或) 來分別修改權值。 2.2 Balanced Winnow 分類算法 標準的Winnow 算法不允許有負的權值， 于是就有了另一個稱為平衡的Winnow 版本， 允許使用負的權值。 對Winnow 算法的基本形式， 權重向量的每一維都是正數。Balanced Winnow 是用w+-w-代替w， 當則將實例歸為該

9、類。Balanced Winnow 的權重更新策略為： (1) 如果， 但文本不屬于該類， 則要降低權重：對j=1，d，如果xj0 ， 則xj0 ， w+j =w+j ，w-j =w-j ，1，01。 (2) 如果但文本應屬于該類， 則要提高權重：對j=1，2，d，如果xj0， 則w+j =w+j ，w-j =w-j ，1，01。 在實驗中， 采用文獻7 中統一 和 為一個參數的方法， 令=1/， 沒有影響分類效果， 但有效簡化了參數的選擇。可以為不同的類別確定不同的 值， 但實驗表明： 對于不同的類別選擇同樣的 值， 結果幾乎是一樣的， 所以在每次獨立的實驗中都取相同的 值， 大小是訓練文本

10、所含的平均特征數， 而初始的w+和w-分別取全2 和全1 向量。 在平衡Winnow 算法中， 一旦參數、 和閾值 確定下來后， 將在訓練過程中不斷更新權重向量w+和w-至最適合這組參數。因此對參數的依賴較小， 需要手工調整的參數不多。 2.3 去除野點 在短信過濾中，短信樣本是由手動或自動方式收集的， 收集的過程中難免會出錯， 因此短信樣本集中可能存在一些被人為錯分的樣本點， 即野點。這些野點在訓練時， 會使得分類器產生嚴重的抖動現象， 降低分類器的性能。因此，好的分類器應具有識別野點的能力。 對于Winnow 算法，若樣本中存在野點， 則野點在訓練時以較大的概率出現在兩分類線之外， 且分類

11、錯誤。 這些野點對分類器的訓練過程產生很大的影響， 可能會造成分類器的“ 過度學習” 。因此引入損失函數， 按照損失函數的定義， 這些野點損失較大， 因此可以通過給損失函數設置一個上界函數來處理線性分類器中的野點問題， 如圖1 所示。 圖1 所示為兩類線性可分情況， 圖中實心點和空心點分別表示兩類訓練樣本，H 為兩類樣本沒有被錯誤地分開的分類線，H1 和H2 分別為平行于分類線H 且與分類線H 的距離為單位距離的兩條直線。直線G(t)為平衡Winnow 算法中第t 輪迭代后損失函數的上界線。該上界線是關于迭代次數t 的函數， 因此可以將該上界線G(t)對應的上界函數記為g(t)。從圖1 可知，

12、 在直線G(t)左下側誤分樣本的損失較少， 可以認為這些誤分樣本是由于當前分類器的性能較低而誤分的； 在直線G(t) 右上側誤分的樣本由于在第t 輪迭代后損失仍較大， 則可以認為這些誤分的樣本是野點。根據線性分類器和野點的性質可知，上界函數g(t)具有以下性質： (1) 隨著Winnow 算法中迭代次數t 的增加， 上界函數g(t) 單調遞減， 并且遞減的速率也隨著t 的增加而遞減， 即上界函數的導數g(t)為單調遞減函數；(2) 上界函數既不能太大， 也不能太小。太大會降低判斷野點的能力， 太小則會誤判正常樣本為野點。 根據上界函數的這些特性， 可以考慮一個平行于分類線H 的線性函數作為損失

13、函數的上界函數。即g(t)=其中： 為常數值； 直線G(t) 平行于分類線H； 為損失因子， 也稱為學習率， 可以在訓練分類器的時候指定其值。 在每一輪訓練中， 若該樣本的G(t) 值大于分類線的值， 并且超過一定的閾值， 且不屬于該類， 則判定該樣本具有野點的性質， 應當在訓練集中將該樣本去除， 以便提高下一輪訓練的準確性。這樣不僅有效削弱了分類器的抖動現象， 而且提高了分類器的性能。 3 系統反饋 Winnow 是一種在線學習的、以錯誤為驅動的分類器， 適于結合增量式學習來解決自適應問題， 實現用戶的個性化要求。平衡Winnow 算法是基本Winnow 算法的另外一種形式， 同樣具有在線更

14、新能力。在分類器訓練過程中， 對錯分的短信通過 和 更新類別權重向量，實現對分類器的更新， 平衡Winnow 算法中w+和w-的雙向調節(jié)， 使算法的訓練速度更快， 適合于對分類實時性要求較高的短信過濾系統。 4 實驗資源及分析與價 本文在自建短信語料庫的基礎上完成對比實驗， 其中正常短信1 892 條， 垃圾短信270 條， 將短信語料庫隨機分成5 等份， 其中4 份用于訓練樣本，1 份作為測試樣本。 4.1 價指標 分類系統價指標如下， 包括兩類短信各自的準確率(precision) 和召回率(recall) ， 由于系統目標是垃圾短信過濾， 于是增加了針對垃圾短信的綜合價指標(F1): F

15、1=(2×準確率×召回率)/( 準確率+召回率)。 4.2 實驗結果分析 (1) 實驗1： 探討改進的特征權重計算方法對實驗結果的影響。實驗結果如表1 所示。 表1 特征權重計算方法對實驗結果的影響。 其中測試樣本中正常短信被誤分為垃圾短信條數為22 條， 正常短信召回率為94.2%； 垃圾短信被誤分為正常短信8 條， 準確率僅為67.7%。 (2) 實驗2： 統一參數和取固定的閾值 之后對實驗結果的影響。該實驗中?。?1.5 、=1/1.5 、=15 。實驗結果如表2 所示。 表2 選定參數對實驗結果的影響 其中測試樣本中正常短信被誤分為垃圾短信條數為18 條， 正常短信召回率為96.1%； 而測試用的垃圾短信正確識別了44 條， 準確率為71.0%。由此可見， 參數對實驗結果的影響不大。 (3) 實驗3： 去除野點對實驗結果的影響。實驗結果如表3 所示。 表3 去除野點對實驗結果的影響。 從實驗結果分析， 僅有12 條正