閆紅靜 ,邸書靈
(1.石家莊鐵道大學(xué) 研究生學(xué)院,河北 石家莊 050043;2.石家莊鐵道大學(xué) 信息科學(xué)與技術(shù)學(xué)院,河北 石家莊 050043)
手機(jī)短信以其短小、迅速、簡便、價(jià)格低廉等優(yōu)點(diǎn)成為一種重要的通信和交流方式,受到眾多人士的青睞。然而,手機(jī)短信與郵件一樣存在著垃圾信息問題。
目前,垃圾短信過濾主要有黑名單過濾、關(guān)鍵詞過濾和基于文本分類的內(nèi)容過濾等方式。黑名單過濾和關(guān)鍵詞過濾方式能快速過濾垃圾短信,但這兩種過濾方式實(shí)質(zhì)是基于規(guī)則的過濾,雖然在一定程度上阻擋了一些垃圾短信,但規(guī)則的方法需要更多的用戶自定義設(shè)置,很容易被反過濾?;谖谋痉诸惖亩绦胚^濾采用常見的分類算法,如樸素貝葉斯、SVM、神經(jīng)網(wǎng)絡(luò)等。黎路[1]等人將貝葉斯分類應(yīng)用到J2ME模擬環(huán)境中成功地過濾了中獎短信和祝福短信。浙江大學(xué)的金展、范晶等[2]將樸素貝葉斯和支持向量機(jī)結(jié)合,解決了傳統(tǒng)垃圾短信過濾系統(tǒng)短信特征和內(nèi)容未能得到及時(shí)更新而導(dǎo)致過濾性能降低的問題。王忠軍[3]將基于樸素貝葉斯短信過濾算法與基于最小風(fēng)險(xiǎn)貝葉斯算法進(jìn)行了實(shí)驗(yàn)分析和比較,結(jié)論是基于最小風(fēng)險(xiǎn)的短信過濾算法具有較好的性能。然而,短信過濾的準(zhǔn)確率依賴于其訓(xùn)練樣本的數(shù)量及質(zhì)量,這些分類算法需要經(jīng)過訓(xùn)練學(xué)習(xí)建立分類器模型,因此在速度上不能很好地滿足短信過濾實(shí)時(shí)性的要求。從現(xiàn)有技術(shù)上來說,垃圾短信的過濾在準(zhǔn)確率和效率方面仍然不能滿足現(xiàn)實(shí)需要。
本文針對現(xiàn)有短信過濾技術(shù)的不足,設(shè)計(jì)了在手機(jī)終端的短信過濾系統(tǒng),根據(jù)垃圾短信的特點(diǎn)將黑白名單和基于內(nèi)容過濾相結(jié)合。這種過濾方式要求能夠快速地對短信進(jìn)行分類,并且能夠?qū)崿F(xiàn)用戶對短信過濾的個(gè)性化要求,使垃圾短信過濾系統(tǒng)具有更好的過濾性能。
Winnow算法是在1987年由Nick Littlestone提出并對可行性做了嚴(yán)格證明的線性分類算法[4]。當(dāng)時(shí)的目標(biāo)是想找到一種時(shí)空復(fù)雜度僅僅與分類對象相關(guān)屬性相關(guān)的數(shù)量呈線性相關(guān)的算法。平衡Winnow算法是對基本W(wǎng)innow算法的一種改進(jìn),該算法具有過濾速度快、性能好、支持反饋更新的優(yōu)點(diǎn),在信息過濾領(lǐng)域有很好的應(yīng)用前景,尤其適合于對實(shí)時(shí)性要求較高的短信過濾系統(tǒng)。
本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)基于平衡Winnow算法的短信內(nèi)容過濾系統(tǒng),對該算法在短信過濾系統(tǒng)上的應(yīng)用進(jìn)行了詳細(xì)分析。分類器的訓(xùn)練過程分成預(yù)處理、訓(xùn)練、分類和反饋四個(gè)部分。
預(yù)處理模塊包括中文分詞、特征提取以及短信的向量表示子模塊。
中文分詞是漢語所特有的研究課題。英語、法語等印歐語種詞與詞之間存在著自然的分割,一般不存在分詞的問題。本系統(tǒng)采用了目前國內(nèi)較多使用的中科院計(jì)算所開發(fā)的漢語詞法分析系統(tǒng)ICTCLAS[5](Instituteof Computing Technology,Chinese LexicalAnalysisSystem)。ICTCLAS 3.0分詞速度單機(jī)996 Kb/s,分詞精度98.45%,API不超過 200 KB,各種詞典數(shù)據(jù)壓縮后不到 3 MB,是當(dāng)前相對較好的漢語詞法分析器。
特征提取的方法目前也有很多,常用的特征選取方法有[5]:文檔頻率 DF(Document Frequency)、信息增益 IG(Information Gain)、互信息 MI(Mutual Information)、χ2統(tǒng) 計(jì)等。
本文將分詞后的詞作為候選特征,然后使用特征提取算法從中提取出對分類最有用的一些特征,去除對分類貢獻(xiàn)不大的候選特征,以降低特征的維數(shù)。其中χ2的主要思想是認(rèn)為詞條與類別之間符合χ2分布。χ2統(tǒng)計(jì)量的值越高,特征項(xiàng)和類別之間的獨(dú)立性越小、相關(guān)性越強(qiáng),即特征項(xiàng)對此類別的貢獻(xiàn)越大。χ2是一個(gè)歸一化的值,該方法比其他方法能減少50%左右的詞匯,具有分類效果好的優(yōu)點(diǎn)[6]。本文中采用χ2統(tǒng)計(jì)進(jìn)行特征提取。但不是簡單地令特征項(xiàng)的權(quán)重 xi=1或0,而是令xi=f(χ2)或 0,這里χ2特指特征對應(yīng)的 χ2統(tǒng)計(jì)值,對應(yīng)關(guān)系 f根據(jù)實(shí)際情況而定。實(shí)驗(yàn)中令xi=(n是一個(gè)正整數(shù),取n=4)。實(shí)驗(yàn)表明比用布爾權(quán)重表示效果要好。
目前應(yīng)用較多的是向量空間模型VSM(Vector Space Model),文中用 VSM將一條短信表示為(W1,W2,…,Wk,…,Wn)的向量形式。其中:Wk(k=1,2,…,n)為第k個(gè)特征的權(quán)重,n為選定的特征數(shù)。
訓(xùn)練分類器是研究的重點(diǎn),采用Balanced Winnow算法并對其進(jìn)行改進(jìn)。
Winnow算法是二值屬性數(shù)據(jù)集上的線性分類算法。線性分類問題中表示分類界限的超平面等式如下:w0α0+w1α1+w2α2+…+wkαk=0,其中:α0,α1,…,αk分別是屬性的值;w0,w1,…,wk是超平面的權(quán)值。如果其值大于0,則預(yù)測為第一類否則為第二類。
Winnow算法是錯(cuò)誤驅(qū)動型的分類算法,即當(dāng)出現(xiàn)錯(cuò)分的實(shí)例時(shí)才更新權(quán)值向量。設(shè)定兩個(gè)學(xué)習(xí)系數(shù)α和β(其中 α>1,β<1),通過將權(quán)值乘以參數(shù) α(或 β)來分別修改權(quán)值。
在實(shí)驗(yàn)中,采用文獻(xiàn)[7]中統(tǒng)一α和β為一個(gè)參數(shù)的方法,令β=1/α,沒有影響分類效果,但有效簡化了參數(shù)的選擇??梢詾椴煌念悇e確定不同的θ值,但實(shí)驗(yàn)表明:對于不同的類別選擇同樣的θ值,結(jié)果幾乎是一樣的,所以在每次獨(dú)立的實(shí)驗(yàn)中都取相同的θ值,大小是訓(xùn)練文本所含的平均特征數(shù),而初始的w+和w-分別取全2和全1向量。
在平衡Winnow算法中,一旦參數(shù) α、β和閾值 θ確定下來后,將在訓(xùn)練過程中不斷更新權(quán)重向量w+和w-至最適合這組參數(shù)。因此對參數(shù)的依賴較小,需要手工調(diào)整的參數(shù)不多。
在短信過濾中,短信樣本是由手動或自動方式收集的,收集的過程中難免會出錯(cuò),因此短信樣本集中可能存在一些被人為錯(cuò)分的樣本點(diǎn),即野點(diǎn)。這些野點(diǎn)在訓(xùn)練時(shí),會使得分類器產(chǎn)生嚴(yán)重的抖動現(xiàn)象,降低分類器的性能。因此,好的分類器應(yīng)具有識別野點(diǎn)的能力[11]。
對于Winnow算法,若樣本中存在野點(diǎn),則野點(diǎn)在訓(xùn)練時(shí)以較大的概率出現(xiàn)在兩分類線之外,且分類錯(cuò)誤。這些野點(diǎn)對分類器的訓(xùn)練過程產(chǎn)生很大的影響,可能會造成分類器的“過度學(xué)習(xí)”。因此引入損失函數(shù),按照損失函數(shù)的定義,這些野點(diǎn)損失較大,因此可以通過給損失函數(shù)設(shè)置一個(gè)上界函數(shù)來處理線性分類器中的野點(diǎn)問題,如圖1所示。
圖1所示為兩類線性可分情況,圖中實(shí)心點(diǎn)和空心點(diǎn)分別表示兩類訓(xùn)練樣本,H為兩類樣本沒有被錯(cuò)誤地分開的分類線,H1和H2分別為平行于分類線H且與分類線H的距離為單位距離的兩條直線。直線G(t)為平衡Winnow算法中第t輪迭代后損失函數(shù)的上界線。該上界線是關(guān)于迭代次數(shù)t的函數(shù),因此可以將該上界線G(t)對應(yīng)的上界函數(shù)記為g(t)。從圖1可知,在直線G(t)左下側(cè)誤分樣本的損失較少,可以認(rèn)為這些誤分樣本是由于當(dāng)前分類器的性能較低而誤分的;在直線G(t)右上側(cè)誤分的樣本由于在第t輪迭代后損失仍較大,則可以認(rèn)為這些誤分的樣本是野點(diǎn)。根據(jù)線性分類器和野點(diǎn)的性質(zhì)可知,上界函數(shù)g(t)具有以下性質(zhì):
(1)隨著Winnow算法中迭代次數(shù)t的增加,上界函數(shù)g(t)單調(diào)遞減,并且遞減的速率也隨著t的增加而遞減,即上界函數(shù)的導(dǎo)數(shù)g(t)為單調(diào)遞減函數(shù);
(2)上界函數(shù)既不能太大,也不能太小。太大會降低判斷野點(diǎn)的能力,太小則會誤判正常樣本為野點(diǎn)。
在每一輪訓(xùn)練中,若該樣本的G(t)值大于分類線的值,并且超過一定的閾值,且不屬于該類,則判定該樣本具有野點(diǎn)的性質(zhì),應(yīng)當(dāng)在訓(xùn)練集中將該樣本去除,以便提高下一輪訓(xùn)練的準(zhǔn)確性。這樣不僅有效削弱了分類器的抖動現(xiàn)象,而且提高了分類器的性能。
Winnow是一種在線學(xué)習(xí)的、以錯(cuò)誤為驅(qū)動的分類器,適于結(jié)合增量式學(xué)習(xí)來解決自適應(yīng)問題,實(shí)現(xiàn)用戶的個(gè)性化要求。平衡Winnow算法是基本W(wǎng)innow算法的另外一種形式,同樣具有在線更新能力。在分類器訓(xùn)練過程中,對錯(cuò)分的短信通過α和β更新類別權(quán)重向量,實(shí)現(xiàn)對分類器的更新,平衡Winnow算法中 w+和w-的雙向調(diào)節(jié),使算法的訓(xùn)練速度更快,適合于對分類實(shí)時(shí)性要求較高的短信過濾系統(tǒng)。
本文在自建短信語料庫的基礎(chǔ)上完成對比實(shí)驗(yàn),其中正常短信1 892條,垃圾短信270條,將短信語料庫隨機(jī)分成5等份,其中4份用于訓(xùn)練樣本,1份作為測試樣本。
分類系統(tǒng)評價(jià)指標(biāo)如下,包括兩類短信各自的準(zhǔn)確率(precision)和召回率(recall),由于系統(tǒng)目標(biāo)是垃圾短信過濾,于是增加了針對垃圾短信的綜合評價(jià)指標(biāo)(F1):F1=(2×準(zhǔn)確率×召回率)/(準(zhǔn)確率+召回率)。
(1)實(shí)驗(yàn)1:探討改進(jìn)的特征權(quán)重計(jì)算方法對實(shí)驗(yàn)結(jié)果的影響。實(shí)驗(yàn)結(jié)果如表1所示。
表1 特征權(quán)重計(jì)算方法對實(shí)驗(yàn)結(jié)果的影響
其中測試樣本中正常短信被誤分為垃圾短信條數(shù)為22條,正常短信召回率為94.2%;垃圾短信被誤分為正常短信8條,準(zhǔn)確率僅為67.7%。
(2)實(shí)驗(yàn)2:統(tǒng)一參數(shù)和取固定的閾值θ之后對實(shí)驗(yàn)結(jié)果的影響。該實(shí)驗(yàn)中?。害?1.5、β=1/1.5、θ=15。實(shí)驗(yàn)結(jié)果如表2所示。
表2 選定參數(shù)對實(shí)驗(yàn)結(jié)果的影響
其中測試樣本中正常短信被誤分為垃圾短信條數(shù)為18條,正常短信召回率為96.1%;而測試用的垃圾短信正確識別了44條,準(zhǔn)確率為71.0%。由此可見,參數(shù)對實(shí)驗(yàn)結(jié)果的影響不大。
(3)實(shí)驗(yàn)3:去除野點(diǎn)對實(shí)驗(yàn)結(jié)果的影響。實(shí)驗(yàn)結(jié)果如表3所示。
表3 去除野點(diǎn)對實(shí)驗(yàn)結(jié)果的影響
從實(shí)驗(yàn)結(jié)果分析,僅有12條正常短信和8條垃圾短信被錯(cuò)誤分類。通過去除野點(diǎn),發(fā)現(xiàn)不僅緩減了抖動現(xiàn)象,而且提高了分類器的分類性能及正常短信的召回率。
Balanced Winnow在訓(xùn)練速度和分類速度上具有較大優(yōu)勢,所以具有更高的實(shí)用價(jià)值,非常適合短信過濾的要求。另外,Winnow作為一種在線學(xué)習(xí)方法,在訓(xùn)練集合不斷擴(kuò)大的情況下能夠快速對分類器進(jìn)行更新。正是基于Winnow不斷學(xué)習(xí)、不斷調(diào)整的機(jī)制,使其非常適合用戶自己定制需要的分類標(biāo)準(zhǔn)。隨著用戶不斷地反饋調(diào)整,整個(gè)系統(tǒng)會表現(xiàn)出越來越好的效果。
[1]黎路,秦衛(wèi)平.淺析貝葉斯分類方法在手機(jī)垃圾短信過濾 系 統(tǒng) 中 的 應(yīng) 用[J].科 技 廣 場 ,2007(7):76-78.
[2]金展,范晶.基于樸素貝葉斯和支持向量機(jī)的自適應(yīng)垃圾短信過濾系[J].計(jì)算機(jī)應(yīng)用,2008,28(3):714-718.
[3]王忠軍.文本分類在短信過濾中的應(yīng)用[D].遼寧:大連理工大學(xué),2006.
[4]LITTLESTONE N.Learningquicklywhen irrelevantattributes 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]周志軍.中文郵件分類系統(tǒng)的研究及其實(shí)現(xiàn)[D].蘇州:蘇州大學(xué),2005.
[7]潘文峰,王斌.Winnow算法在垃圾郵件過濾中的應(yīng)用[C].第一屆全國信息檢索與內(nèi)容安全學(xué)術(shù)會議論文集,上海,2004.