短信過濾系統設計分析

摘 要：設計了一種手機終端上基于短信內容的垃圾短信過濾系統。系統采用了平衡Winnow算法，該算法具有分類速度快、性能好以及支持在線更新的優點，適用于手機終端資源有限、需要實時或者定期更新分類器的情況。通過一系列的實驗分析，證明該方法的有效性，并給出了對該方法的全面評估。對于該算法將來在信息過濾領域的應用，提供了全面的分析依據。

關鍵詞：短信過濾系統; 垃圾過濾； 平衡Winnow算法； 在線更新

中圖分類號：TP391 文獻標志碼：A 文章編號：1001-3695(2008)08-2557-04

Spam filter for short message

HU Ri-le1，2，CAI Jie1，ZHONG Yi-xin1

(1. School of Information Engineering， Beijing University of Posts Telecommunications， Beijing100876， China； 2. Nokia Research Center， Beijing 100013， China)

Abstract:This paper proposed a content-based spam filter embedded in mobile phones.It used the balanced Winnow algorithm as the kernel classifier in the system， since the algorithm could classify texts faster， better and what’s more， it allowed on-line setting. The Winnow classifier was suitable for systems which had limited resources and needed to be renewed at intervals. Then implementeda series of experiments to prove the good performance of the system， and analyzed the method from many aspects. This paper gave a statistic support for the information filters using balanced Winnow.

Key words:spam filter for short massages;spam filter;balanced Winnow algorithm;on-line setting

垃圾信息過濾是目前人們比較關注的一類問題，它可以被看成是文本分類技術的一種應用^[1]。這個方面的研究現在主要集中在郵件領域。由于手機短信在中國的高增長率，短信內容安全已經上升為一個重要的話題。據2007年的一項調查顯示，14.19%的手機用戶每周收到10條以上垃圾短信。垃圾短信對于人們生活的干擾已經到了不容忽視的程度。

手機垃圾短信是指未經請求或允許而收到的、對接收者來說無用的短信，如未經短信接收人請求或允許而發送的商業廣告。垃圾短信的常見內容包括廣告信息、色情信息、假中獎信息、欺詐信息、惡作劇等。

現有的針對垃圾短信過濾的工作多使用規則方式（黑白名單設置、模式匹配），及常見的分類算法，如樸素貝葉斯、SVM、神經網絡BP方法等。基于規則的方法在一定程度上阻攔了一些垃圾短信的來源，但是對于大量的垃圾短信，規則方法就需要更多的用戶自定義設置，也更容易被反過濾。

設計手機上嵌入式的短信過濾系統，需要綜合考慮系統過濾信息的速度、過濾的性能以及對實時更新的需求。本文設計了一個基于平衡Winnow算法的短信過濾系統，并通過大量的實驗對該算法在信息過濾上的應用進行了詳細的分析。該算法具有過濾速度快、性能好、支持反饋更新的優點，在信息過濾領域有著很好的應用前景。本文給出的實驗分析將為該算法的應用提供全面的依據。

1 短信過濾系統設計

文本分類是指在給定的分類體系下，根據文本的內容自動判別文本類別的過程。近年來，文本分類技術已經逐漸與搜索引擎、信息推送、信息過濾等信息處理技術相結合，有效地提高了信息服務的質量。

本文運用文本分類的思想設計移動終端上的短信過濾系統。將垃圾短信的過濾問題映射為二值分類問題。

系統流程如圖1所示，包括四大部分，即特征提取、訓練分類模型、對未知短信分類和反饋更新模型。系統基本功能模塊包括文本預處理、特征提取、文本向量表示、核心分類算法。

2 文本預處理

2.1 中文分詞與詞性標注處理

漢語自動分詞和詞性標注屬于中文信息處理中兩個重要的基礎性問題。由于中文區別于印歐語系的特點，即詞匯之間沒有空格分隔符，當需要中文詞匯作為處理特征時，分詞便顯得不可缺少了。詞性標注的處理給詞匯一個恰當的詞性標記。在本系統中，采用了基于統計的分詞和詞形標注的一體化模型，對語料進行了切分和標注^[2]。

2.2 停用詞識別

停用詞表（stop list）的使用是為了去除一些無意義的詞匯或標記對特征提取產生的影響，起到了一定程度的降維和降低處理時間的作用。

在系統實現中，如果文本中的詞匯被識別出為停用詞，則不再參與文本向量表示，于是不再進行特征詞表的搜索匹配。

在本文的實驗中，只選用了簡單的stop list，即標點符號等。以便不干擾系統其他功能的分析。

2.3 特征回退

在本系統中，提取的特征為分詞后的詞匯。大量真實的語料不可避免的一個問題就是數據稀疏。于是本文采用了回退的思想，用于一定程度上解決數據稀疏的問題。特征回退指的是對于具體的詞匯，根據詞性標注以及同義詞林等，將其回退成更上一層的概念，然后再加入特征表。

例如：“1”“5”等數字，回退成“數字”概念；“13547384394”等電話號碼，回退成“數字串”概念。

本系統只采用了一些簡單的回退，但是也證明，回退思想會在實際操作中起到令人比較滿意的效果。

3 特征提取

如前所述，本系統采用分詞后的詞匯單元作為特征候選。特征提取從所有的候選特征中，按照一定的方法提取出對分類最有作用的一些特征，棄除對分類貢獻不大的候選特征，起到明顯的降維作用。

常用的特征提取方法是構造一些評價函數來衡量特征詞與類之間的關系。對于某個特征詞t，常用的評價函數有文檔頻度DF、信息增益IG、互信息MI、期望交叉熵ECE等。實驗^[3]證明，期望交叉熵的選取特征詞的效果優于其他幾種。

期望交叉熵的評價函數為

ECE（t）=Pr[t]c∈CPr[t]×log(Pr[c｜t] / Pr[c])(1)

其中：Pr[t]表示特征詞t出現的頻度；Pr[c]表示c類語料所占的比例；Pr[c|t]表示短信出現t的條件下屬于c類的概率。從式(1)可以看出，期望交叉熵反映了短信類別的概率分布和在出現了某個特征詞的條件下短信類別的概率分布之間的距離， 特征詞t的期望交叉熵越大， 對短信類別分布的影響也越大。

由于當Pr[c|t]

AECE（t）=Pr[t]c∈CPr[t]×｜log(Pr[c/t]/Pr[c])｜(2)

4 文本表示

文本的表示方法常用的有布爾邏輯型、向量空間型、概率型和混合型。向量空間模型(vector space model， VSM)^[4]是20世紀60年代末由G. Salton等人提出的，目前已經被廣泛應用于文本分類。

用VSM表示一條短信為n維向量(W1， W2， …，Wn)。其中：Wk(k=1，2，…，n)為第k個特征的權重；n為選定的特征數。

5 Winnow 分類算法

Winnow 算法是一種在二值屬性數據集上的線性分類算法^[5]。線性分類問題中表示分類界限的超平面等式如下：

W0a0+ W1a1+W2a2+ …+Wkak=0

其中：a1， a2，… ，ak分別是屬性的值；W0，W1，…， Wk是定義超平面的權值。如果所求出的和大于0，將它預測為第一個類；否則為第二個類。

在Winnow算法中，線性函數的閾值也是個用戶定義的參數，稱為θ，當且僅當滿足以下條件時（不平衡的Winnow），將這個實例分配到類1上：

W0a0+ W1a1+W2a2+ …+Wkak>θ

這種算法不允許有負的權值，于是就有了另一個版本稱為平衡的Winnow^[5]，允許使用負的權值。在本系統中采用了平衡Winnow的分類算法。這個版本包括兩個權值向量，判決方法不變：

(W0+-W0-)a0+ (W1+-W1-)a1+(W2+-W2-)a2+ …+

(Wk+ -Wk-)ak>θ

Winnow算法是錯誤驅動型的分類算法，即當出現錯分的實例時，Winnow才更新權值向量。通過將權值乘以參數α（或者α的倒數）來分別修改權值。平衡的Winnow算法如下：

當存在錯誤分類實例時，

對于每個實例a循環操作

使用當前的權值對實例a進行分類

如果預測類別不正確

如果a屬于第一個類

對于每個屬性值ai，且ai為1時

將Wi+ ×α

將Wi- /α

(如果ai為0，W+i和W-i保持不變)

否則

對于每個屬性值ai，且ai為1時

將Wi+ ×α

將Wi -/α

(如果ai為0，Wi+和Wi-保持不變)

Winnow算法是對于跟蹤數據集上的相關屬性非常有效的方法，可以用于實時設置（on-line setting），對于需要實時更新的短信過濾系統，有著較好的應用前景。

6 實驗資源及評價指標

6.1 語料庫

系統實驗所使用的語料庫全部來自現實短信資源。訓練語料與測試語料按3:1隨機分配，如表1所示。

表1 語料分布

短信訓練數據測試數據總量正常短信2 1987332 931垃圾短信430144574

6.2 評價指標

系統在實驗階段給出了比較詳盡的評測結果，包括兩類短信各自的準確率(precision)和召回率(recall)，以及衡量系統綜合性能的正確率(accuracy)。由于系統目標是垃圾短信過濾，于是增加了針對垃圾短信的綜合評價(F-score):

F-score=(2×p_s×r_s) / （p_s+r_s）(3)

其中：p_s表示垃圾短信的準確率；r_s表示垃圾短信的召回率；同理，p_n表示正常短信的準確率；r_n表示正常短信的召回率；accuracy表示系統的綜合性能正確率，F-score表示垃圾短信的F值。在接下面實驗結果中，均采用這六個表示方式。

在實際使用中，用戶會更關注垃圾短信過濾的性能(F-score)及正常短信的召回率(norm-recall)，確保系統在足夠安全的條件下（正常短信不丟失），得到所期望的垃圾過濾效果。

7 實驗及討論

在本文的短信過濾系統中，實驗語料來自于現實短信，兩類語料在數量上并不平衡，這在一定程度上表現了現實語料的分布。筆者采用了平衡的Winnow算法作為核心分類算法，該算法具有分類速度快、性能好、方便在線更新的特點^[6]。針對本系統的各個參數等進行了多組實驗，對本文的方法給出了全面的評估。

7.1 實驗組1

本組實驗（圖2）研究了訓練語料中兩類短信的比例對系統性能的影響。該組評價為訓練數據的選取提供了依據。

本組實驗中，特征數為200，α取1.5，θ取4，正常短信測試語料為733條，垃圾短信測試語料為144條。

結果分析：

a）隨著正常短信訓練語料的增加，r_n（正常短信召回率）增高，足夠多的正常語料，使之接近1（筆者所需要的）；

b）正常短信數量的增多將降低r_s（垃圾短信召回率），因為正常語料對參數的調整過多，分類界限會偏向spam區域，使得一些spam無法正確召回；

c）在目前語料規模下，取正常訓練短信數為垃圾訓練短信數量的三四倍時，系統性能較好（后續實驗取1 500:430）。

7.2 實驗組2

本組實驗探討了Winnow算法的訓練方式對系統性能的影響。Winnow算法的訓練過程是訓練樣本逐一修正模型參數的過程，于是不同的垃圾語料與正常語料的訓練順序對系統性能將產生不同的影響。該組評價為Winnow算法的使用方式提供了依據。

實驗采用了三種方式：a）先訓練垃圾語料，再訓練正常語料；b）先訓練正常語料，再訓料垃圾語料；c）交叉訓練（單條交叉訓練）。

結果分析：

a）第一種方式，由于正常語料規模大并且在后面訓練，會導致r_n較高，但是r_s較低。其綜合指標accuracy以及spam的F-score較高。

b）交叉訓練方式在實驗中性能一般，是由于兩類語料數量不平衡，交叉訓練方式在垃圾語料訓練完了之后，又退化成第一種方式，集中訓練剩下的正常語料。由于前一部分的交叉訓練，參數不是向一個方向調整，而是在波動，導致該方式比第一種方式性能稍差一些。

c）對于Winnow算法本身而言，認為交叉訓練方式可能對語料的規模會要求更高，即更多的訓練次數后才會穩定參數性能，但是應該比先后訓練兩部分語料效果要好，也要合理（認為參數調整以波動形式調整直到穩定更為合理）。

d）針對現階段的應用方向，以及短信過濾對r_n的高要求，后續實驗采用第一種訓練方式。

7.3 實驗組3

本組實驗（圖3）探討了特征數選取對系統性能的影響。該組評價為特征的選取提供了依據。特征提取過程中，依據各個特征的AECE值進行排序選取。由于存在多個特征享有同樣AECE值的情況，筆者提出了AECE值個數代替特征個數的方法，使得特征的選取更加公平。

本組實驗正常訓練樣本取1 500條，垃圾樣本取430條；正常測試樣本取733條，垃圾樣本取144條；α取1.5，θ取4。

結果分析：

a）特征數大于200后，性能會有所惡化，原因是訓練語料規模無法使超過一定數量的特征訓練穩定。

b）特征數減小時，性能也會惡化，原因是少數量特征無法表示足夠的信息量。

c）在目前的語料規模和系統下，特征在200左右時得到最好性能，后續實驗采用該值。

d）當語料規模變動時，該參數需要重新實驗獲得，特征數的最好取值與語料規模有著緊密的聯系。

7.4 實驗組4

本組實驗（圖4、5所示）研究了系統各參數對系統性能的影響。該組評價為系統參數的選取提供了依據。

圖4所示實驗中，正常訓練樣本取1 500條，垃圾樣本取430條；正常測試樣本取733條，垃圾樣本取144條；特征數取200，θ取4。

結果分析：

a）Alpha值取1~2比較好。

b）在本實驗中，alpha值取1.2~1.5系統性能較好，后續實驗取alpha為1.5。

c）Alpha取值在1~2之間對性能影響不是很顯著，原因可能是正反樣本各自特征比較明顯，區別度也較大，使得對參數變化不敏感。

圖5所示實驗中，正常訓練樣本取1 500條，垃圾樣本取430條；正常測試樣本取733條，垃圾樣本取144條；特征數取200，α取1.5。

結果分析：

a）當threshold參數取14~17時，系統性能穩定在最優點。

b）該參數的最優點取值隨著特征數量的增減而上下浮動，大致范圍在50以下。

7.5 實驗組5

本組實驗對Winnow算法在線更新特點進行了評價。該組實驗為Winnow算法應用中在線更新間隔選取提供了依據。

本組實驗正常訓練樣本取450條，垃圾樣本取430條;正常測試樣本取733條，垃圾樣本取144條;特征數量取300，模型訓練中α取8，θ取10。更新測試中α取1.5，θ取10。結果如表2所示。

表2 更新間隔調整實驗結果

參數非更新測試更新間隔：1更新間隔：2p_s0.989 7960.978 8730.978 571p_n0.939 6660.993 1970.990 502r_s0.673 6110.965 2780.951 389r_n0.998 6360.995 9070.995 907accuracy0.945 2680.990 8780.988 598F-score0.801 6530.972 0280.964 789detailss_97

s_n 47

n_s 1

n_n 732s_s 139

s_n 5

n_s 3

n_n730s_s 137

s_n 7

n_s 3

n_n 730更新間隔：3更新間隔：4更新間隔：5更新間隔：100.978 2610.978 5710.978 4170.984 9620.987 8210.990 5020.989 160.982 5270.937 50.951 3890.944 4440.909 7220.995 9070.995 9070.995 9070.997 2710.986 3170.988 5980.987 4570.982 8960.957 4470.964 7890.961 1310.945 848s_s 135

s_n 9

n_s 3

n_n 730s_s 137

s_n 7

n_s 3

n_n 730s_s 136

s_n 8

n_s 3

n_n 730s_s 131

s_n 13

n_s 2

n_n 731更新間隔：15更新間隔：20更新間隔：250.984 3750.9840.983 3330.975 9680.972 0740.965 6540.8750.854 1670.819 4440.997 2710.997 2710.997 2710.977 1950.973 7740.968 0730.926 4710.914 4980.893 939s_s 126

s_n 18

n_s 2

n_n 731s_s 123

s_n 21

n_s 2

n_n 731s_s 118

s_n 26

n_s 2

n_n 731表中:s_s表示垃圾短信被分為垃圾短信的數量;s_n表示垃圾短信被分為正常短信的數量;n_s表示正常短信被分為垃圾短信的數量;n_n表示正常短信被分為正常短信的數量。

結果分析：

a）本組實驗參數的選擇是為了便于實驗更新間隔，在錯誤率較高的情況下考察更新間隔調整對性能的影響。

b）實驗中的更新間隔為錯誤反饋個數。

c）由實驗結果可以看出，使用在線更新功能，能及時地修正模型，大大地減小錯誤率。

d）更新間隔增大，垃圾判錯率增高，但是正常短信召回率變化不大，說明系統在保證正常短信不丟失方面表現穩定。

e）最優更新間隔與語料規模、參數選擇有關，在當前實驗規模下可以選擇逐條錯誤反饋的方式。

8 結束語

本文提出了采用Winnow核心算法的嵌入移動終端式短信過濾系統。該算法具有分類速度快、性能好、支持在線更新的特點，對于終端上的過濾系統有著良好的應用前景。經過大量的實驗和分析，本文對該算法在過濾系統中的應用提供了可靠的依據和參考。在未來的工作中，特征回退模塊、特征提取模塊等均有著較大的改進潛力；另外還在系統中添加用戶定制類的規則控制模塊，以取得更優良的應用效果。

參考文獻:

[1]PAUL G. A plan for spam [ EB /OL ].（2002- 12- 10）.http: //www. Paulgraham.com / spam.html.

[2]張國華. 漢語自動分詞和詞性標注方法研究及系統實現[D].北京：中國科學院研究生院，2007.

[3]李凡，魯明羽，陸玉昌.關于文本特征抽取新方法的研究[J].清華大學學報:自然科學版， 2001，41(7):98- 101.

[4]SALTON G， WANG A， YANG C. A vector space model for information retrieval [J]. Journal of the American Society for Information Science， 1975， 18:613-620.

[5]LITTLESTONE N. Learning quickly when irrelevant attributes abound：a new linear-threshold algorithm [J]．Machine Learning，1988，4(2)：285-318．

[6]王斌，潘文峰.基于內容的垃圾郵件過濾技術綜述[J]. 中文信息學報， 2005，19(5):1-10.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文