短信過濾系統(tǒng)設(shè)計分析

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

關(guān)鍵詞：短信過濾系統(tǒng); 垃圾過濾； 平衡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

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

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

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

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

1 短信過濾系統(tǒng)設(shè)計

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

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

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

2 文本預(yù)處理

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

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

2.2 停用詞識別

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

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

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

2.3 特征回退

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

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

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

3 特征提取

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

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

期望交叉熵的評價函數(shù)為

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

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

由于當(dāng)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等人提出的，目前已經(jīng)被廣泛應(yīng)用于文本分類。

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

5 Winnow 分類算法

Winnow 算法是一種在二值屬性數(shù)據(jù)集上的線性分類算法^[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是定義超平面的權(quán)值。如果所求出的和大于0，將它預(yù)測為第一個類；否則為第二個類。

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

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

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

(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算法是錯誤驅(qū)動型的分類算法，即當(dāng)出現(xiàn)錯分的實例時，Winnow才更新權(quán)值向量。通過將權(quán)值乘以參數(shù)α（或者α的倒數(shù)）來分別修改權(quán)值。平衡的Winnow算法如下：

當(dāng)存在錯誤分類實例時，

對于每個實例a循環(huán)操作

使用當(dāng)前的權(quán)值對實例a進行分類

如果預(yù)測類別不正確

如果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算法是對于跟蹤數(shù)據(jù)集上的相關(guān)屬性非常有效的方法，可以用于實時設(shè)置（on-line setting），對于需要實時更新的短信過濾系統(tǒng)，有著較好的應(yīng)用前景。

6 實驗資源及評價指標

6.1 語料庫

系統(tǒng)實驗所使用的語料庫全部來自現(xiàn)實短信資源。訓(xùn)練語料與測試語料按3:1隨機分配，如表1所示。

表1 語料分布

短信訓(xùn)練數(shù)據(jù)測試數(shù)據(jù)總量正常短信2 1987332 931垃圾短信430144574

6.2 評價指標

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

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

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

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

7 實驗及討論

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

7.1 實驗組1

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

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

結(jié)果分析：

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

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

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

7.2 實驗組2

本組實驗探討了Winnow算法的訓(xùn)練方式對系統(tǒng)性能的影響。Winnow算法的訓(xùn)練過程是訓(xùn)練樣本逐一修正模型參數(shù)的過程，于是不同的垃圾語料與正常語料的訓(xùn)練順序?qū)ο到y(tǒng)性能將產(chǎn)生不同的影響。該組評價為Winnow算法的使用方式提供了依據(jù)。

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

結(jié)果分析：

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

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

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

d）針對現(xiàn)階段的應(yīng)用方向，以及短信過濾對r_n的高要求，后續(xù)實驗采用第一種訓(xùn)練方式。

7.3 實驗組3

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

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

結(jié)果分析：

a）特征數(shù)大于200后，性能會有所惡化，原因是訓(xùn)練語料規(guī)模無法使超過一定數(shù)量的特征訓(xùn)練穩(wěn)定。

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

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

d）當(dāng)語料規(guī)模變動時，該參數(shù)需要重新實驗獲得，特征數(shù)的最好取值與語料規(guī)模有著緊密的聯(lián)系。

7.4 實驗組4

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

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

結(jié)果分析：

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

b）在本實驗中，alpha值取1.2~1.5系統(tǒng)性能較好，后續(xù)實驗取alpha為1.5。

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

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

結(jié)果分析：

a）當(dāng)threshold參數(shù)取14~17時，系統(tǒng)性能穩(wěn)定在最優(yōu)點。

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

7.5 實驗組5

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

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

表2 更新間隔調(diào)整實驗結(jié)果

參數(shù)非更新測試更新間隔：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表示垃圾短信被分為垃圾短信的數(shù)量;s_n表示垃圾短信被分為正常短信的數(shù)量;n_s表示正常短信被分為垃圾短信的數(shù)量;n_n表示正常短信被分為正常短信的數(shù)量。

結(jié)果分析：

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

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

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

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

e）最優(yōu)更新間隔與語料規(guī)模、參數(shù)選擇有關(guān)，在當(dāng)前實驗規(guī)模下可以選擇逐條錯誤反饋的方式。

8 結(jié)束語

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

參考文獻:

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

[2]張國華. 漢語自動分詞和詞性標注方法研究及系統(tǒng)實現(xiàn)[D].北京：中國科學(xué)院研究生院，2007.

[3]李凡，魯明羽，陸玉昌.關(guān)于文本特征抽取新方法的研究[J].清華大學(xué)學(xué)報:自然科學(xué)版， 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]王斌，潘文峰.基于內(nèi)容的垃圾郵件過濾技術(shù)綜述[J]. 中文信息學(xué)報， 2005，19(5):1-10.

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