摘 要： 將黑白名單技術與chinaaet.com/search/?q=Balanced Winnow" title="Balanced Winnow">Balanced Winnow算法相結合，實現對垃圾短信的過濾。采用CHI特征提取算法并對權重計算方法進行改進，同時提出了去除訓練樣本中野點的想法，通過判定去除野點，減緩在訓練過程中出現的抖動現象。實驗表明這種改進對于提高訓練速度及提高短信過濾的性能均有很好的作用。
關鍵詞： balanced Winnow；短信過濾；CHI；野點
手機短信以其短小、迅速、簡便、價格低廉等優點成為一種重要的通信和交流方式，受到眾多人士的青睞。然而，手機短信與郵件一樣存在著垃圾信息問題。
目前，垃圾短信過濾主要有黑名單過濾、關鍵詞過濾和基于文本分類的內容過濾等方式。黑名單過濾和關鍵詞過濾方式能快速過濾垃圾短信，但這兩種過濾方式實質是基于規則的過濾，雖然在一定程度上阻擋了一些垃圾短信，但規則的方法需要更多的用戶自定義設置，很容易被反過濾。基于文本分類的短信過濾采用常見的分類算法，如樸素貝葉斯、SVM、神經網絡等。黎路[1]等人將貝葉斯分類應用到J2ME模擬環境中成功地過濾了中獎短信和祝福短信。浙江大學的金展、范晶等[2]將樸素貝葉斯和支持向量機結合，解決了傳統垃圾短信過濾系統短信特征和內容未能得到及時更新而導致過濾性能降低的問題。王忠軍[3]將基于樸素貝葉斯短信過濾算法與基于最小風險貝葉斯算法進行了實驗分析和比較，結論是基于最小風險的短信過濾算法具有較好的性能。然而，短信過濾的準確率依賴于其訓練樣本的數量及質量，這些分類算法需要經過訓練學習建立分類器模型，因此在速度上不能很好地滿足短信過濾實時性的要求。從現有技術上來說，垃圾短信的過濾在準確率和效率方面仍然不能滿足現實需要。
本文針對現有短信過濾技術的不足，設計了在手機終端的短信過濾系統，根據垃圾短信的特點將黑白名單和基于內容過濾相結合。這種過濾方式要求能夠快速地對短信進行分類，并且能夠實現用戶對短信過濾的個性化要求，使垃圾短信過濾系統具有更好的過濾性能。
Winnow算法是在1987年由Nick Littlestone提出并對可行性做了嚴格證明的線性分類算法[4]。當時的目標是想找到一種時空復雜度僅僅與分類對象相關屬性相關的數量呈線性相關的算法。平衡Winnow算法是對基本Winnow算法的一種改進，該算法具有過濾速度快、性能好、支持反饋更新的優點，在信息過濾領域有很好的應用前景，尤其適合于對實時性要求較高的短信過濾系統。
本文設計并實現了一個基于平衡Winnow算法的短信內容過濾系統，對該算法在短信過濾系統上的應用進行了詳細分析。分類器的訓練過程分成預處理、訓練、分類和反饋四個部分。
1 預處理模塊
預處理模塊包括中文分詞、特征提取以及短信的向量表示子模塊。
1.1 中文分詞
中文分詞是漢語所特有的研究課題。英語、法語等印歐語種詞與詞之間存在著自然的分割，一般不存在分詞的問題。本系統采用了目前國內較多使用的中科院計算所開發的漢語詞法分析系統ICTCLAS[5](Institute of Computing Technology，Chinese Lexical Analysis System)。ICTCLAS 3.0分詞速度單機996 Kb/s，分詞精度98.45%，API不超過200 KB，各種詞典數據壓縮后不到3 MB，是當前相對較好的漢語詞法分析器。
2 構造分類器
訓練分類器是研究的重點，采用Balanced Winnow算法并對其進行改進。
2.1 Winnow分類算法
Winnow算法是二值屬性數據集上的線性分類算
在平衡Winnow算法中，一旦參數α、β和閾值θ確定下來后，將在訓練過程中不斷更新權重向量w+和w-至最適合這組參數。因此對參數的依賴較小，需要手工調整的參數不多。
2.3 去除野點
在短信過濾中，短信樣本是由手動或自動方式收集的，收集的過程中難免會出錯，因此短信樣本集中可能存在一些被人為錯分的樣本點，即野點。這些野點在訓練時，會使得分類器產生嚴重的抖動現象，降低分類器的性能。因此，好的分類器應具有識別野點的能力[11]。
對于Winnow算法，若樣本中存在野點，則野點在訓練時以較大的概率出現在兩分類線之外，且分類錯誤。這些野點對分類器的訓練過程產生很大的影響，可能會造成分類器的“過度學習”。因此引入損失函數，按照損失函數的定義，這些野點損失較大，因此可以通過給損失函數設置一個上界函數來處理線性分類器中的野點問題，如圖1所示。
圖1所示為兩類線性可分情況，圖中實心點和空心點分別表示兩類訓練樣本，H為兩類樣本沒有被錯誤地分開的分類線，H1和H2分別為平行于分類線H且與分類線H的距離為單位距離的兩條直線。直線G(t)為平衡Winnow算法中第t輪迭代后損失函數的上界線。該上界線是關于迭代次數t的函數，因此可以將該上界線G(t)對應的上界函數記為g(t)。從圖1可知，在直線G(t)左下側誤分樣本的損失較少，可以認為這些誤分樣本是由于當前分類器的性能較低而誤分的；在直線G(t)右上側誤分的樣本由于在第t輪迭代后損失仍較大，則可以認為這些誤分的樣本是野點。根據線性分類器和野點的性質可知，上界函數g(t)具有以下性質：
(1)隨著Winnow算法中迭代次數t的增加，上界函數g(t)單調遞減，并且遞減的速率也隨著t的增加而遞減，即上界函數的導數g(t)為單調遞減函數；
在每一輪訓練中，若該樣本的G(t)值大于分類線的值，并且超過一定的閾值，且不屬于該類，則判定該樣本具有野點的性質，應當在訓練集中將該樣本去除，以便提高下一輪訓練的準確性。這樣不僅有效削弱了分類器的抖動現象，而且提高了分類器的性能。
3 系統反饋
Winnow是一種在線學習的、以錯誤為驅動的分類器，適于結合增量式學習來解決自適應問題，實現用戶的個性化要求。平衡Winnow算法是基本Winnow算法的另外一種形式，同樣具有在線更新能力。在分類器訓練過程中，對錯分的短信通過α和β更新類別權重向量，實現對分類器的更新，平衡Winnow算法中w+和w-的雙向調節，使算法的訓練速度更快，適合于對分類實時性要求較高的短信過濾系統。
4 實驗資源及分析與評價
本文在自建短信語料庫的基礎上完成對比實驗，其中正常短信1 892條，垃圾短信270條，將短信語料庫隨機分成5等份，其中4份用于訓練樣本，1份作為測試樣本。
4.1 評價指標
分類系統評價指標如下，包括兩類短信各自的準確率(precision)和召回率(recall)，由于系統目標是垃圾短信過濾，于是增加了針對垃圾短信的綜合評價指標(F1):F1=(2×準確率×召回率)/(準確率+召回率)。
4.2 實驗結果分析
(1)實驗1：探討改進的特征權重計算方法對實驗結果的影響。實驗結果如表1所示。
其中測試樣本中正常短信被誤分為垃圾短信條數為22條，正常短信召回率為94.2%；垃圾短信被誤分為正常短信8條，準確率僅為67.7%。
其中測試樣本中正常短信被誤分為垃圾短信條數為18條，正常短信召回率為96.1%；而測試用的垃圾短信正確識別了44條，準確率為71.0%。由此可見，參數對實驗結果的影響不大。
(3)實驗3：去除野點對實驗結果的影響。實驗結果如表3所示。
從實驗結果分析，僅有12條正常短信和8條垃圾短信被錯誤分類。通過去除野點，發現不僅緩減了抖動現象，而且提高了分類器的分類性能及正常短信的召回率。
Balanced Winnow在訓練速度和分類速度上具有較大優勢，所以具有更高的實用價值，非常適合短信過濾的要求。另外，Winnow作為一種在線學習方法，在訓練集合不斷擴大的情況下能夠快速對分類器進行更新。正是基于Winnow不斷學習、不斷調整的機制，使其非常適合用戶自己定制需要的分類標準。隨著用戶不斷地反饋調整，整個系統會表現出越來越好的效果。
參考文獻
[1] 黎路，秦衛平．淺析貝葉斯分類方法在手機垃圾短信過濾系統中的應用[J]．科技廣場，2007(7):76-78．
[2] 金展，范晶．基于樸素貝葉斯和支持向量機的自適應垃圾短信過濾系[J]．計算機應用，2008，28(3):714-718．
[3] 王忠軍．文本分類在短信過濾中的應用[D]．遼寧:大連理工大學，2006．
[4] LITTLESTONE N. Learning quickly when irrelevant attributes abound: a new linear threshold algorithm. Machine Learning， 1988(2):285-318．
[5] YANG YI MING， PEDERSEN JAN． A comparative study on feature selection in text categorization proceedings of the 14th international conference on machine learning[C]． Nashville： Morgan Kaufmann， 1997:412-420．
[6] 周志軍．中文郵件分類系統的研究及其實現[D]．蘇州:蘇州大學，2005．
[7] 潘文峰，王斌．Winnow算法在垃圾郵件過濾中的應用[C]．第一屆全國信息檢索與內容安全學術會議論文集，上海，2004．