劉伍穎， 王 琳

(廣東外語外貿(mào)大學 語言工程與計算實驗室 廣東 廣州 510420)

面向垃圾短信過濾的亞文檔集成學習

劉伍穎， 王 琳

(廣東外語外貿(mào)大學 語言工程與計算實驗室 廣東 廣州 510420)

針對垃圾短信過濾問題，提出了一種亞文檔集成學習方法.該方法采用亞文檔集成學習框架將短文本在線二值分類問題轉(zhuǎn)化成若干個子分類問題，并通過線性組合多個子問題的分類結(jié)果得出最終的分類預(yù)測.利用基于串頻索引的文本分類算法實現(xiàn)了一種有效的弱分類器.實驗數(shù)據(jù)表明亞文檔集成學習框架能夠提高現(xiàn)有文本分類算法的效能，而在亞文檔集成學習框架下，基于串頻索引的弱分類器過濾效果最佳.

垃圾短信過濾； 亞文檔集成學習； 串頻索引； TREC評測

0 引言

垃圾短信(SMS spam)是指在移動通信網(wǎng)絡(luò)中不請自來、不加選擇、大批量發(fā)送的長度在140字節(jié)以內(nèi)的文本文檔.自2008年開始，國內(nèi)12321網(wǎng)絡(luò)不良與垃圾信息舉報受理中心每年發(fā)布兩次《手機短信息狀況調(diào)查報告》.報告中的每周垃圾短信率和每周垃圾短信數(shù)是兩項非常關(guān)鍵的指標.每周垃圾短信率表示用戶平均每周收到的短信中垃圾短信所占的百分比.根據(jù)報告中的這兩項指標數(shù)據(jù)，我們繪制的2006—2015年垃圾短信態(tài)勢如圖1所示.

圖1 垃圾短信態(tài)勢

圖1的態(tài)勢顯示從2009—2010年每周垃圾短信率從50.40%直線下降到21.10%；2011—2013年每周垃圾短信率基本穩(wěn)定在23.00%.2006—2013年每周垃圾短信數(shù)約為10，雖然各個具體時段略有波動，但整體趨勢變化不大.從2014年至今用戶平均每周收到的垃圾短信數(shù)量又略有增加.由此可見，當前垃圾短信形勢依然嚴峻，垃圾短信占據(jù)手機短信半邊天的態(tài)勢沒有根本改變.

盡管垃圾短信泛濫，但由于隱私問題，公開的短信語料[1]比較少，主要有：SMS spam collection(http://www.dt.fee.unicamp.br/～tiago/smsspamcollection/)、NUS SMS corpus[2]、SMS Han message corpus (120 040 messages)(http://cbd.nichesite.org/CBD2013D001.htm)和我們的CSMS短信語料.CSMS數(shù)據(jù)是按時序從志愿者那里收集的真實短信，總共包含85 870個短信文檔(21 099個spam和64 771個ham)，其中每個短信文檔包含源電話號碼、目的電話號碼和短信正文三個子文檔，并且文檔的類別標簽是根據(jù)提供者的反饋進行人工標注的[3].

1 短信文本特征

垃圾短信過濾(SMS spam filtering)根據(jù)短信的各種特征，從動態(tài)變化的短信流中自動進行垃圾(spam)和非垃圾(ham)的二值分類，并據(jù)此阻止垃圾短信傳播.最早的垃圾信息過濾研究可追溯到上世紀80年代[4]，后逐漸分化為非基于內(nèi)容的過濾方法[5]和基于內(nèi)容的文本分類方法[6].在基于內(nèi)容的文本分類方法中，經(jīng)典Bayes算法簡單、易實現(xiàn)，據(jù)此實現(xiàn)的bogo過濾器成為了常用的參照基準(http://www.paulgraham.com/spam.html).后續(xù)研究表明松弛在線支持向量機算法過濾效果很好，據(jù)此實現(xiàn)的tftS3F過濾器在最近的TREC垃圾過濾評測中取得了多項最優(yōu)成績[7].我們曾提出了詞模型索引方法[8]，并研究了兩種索引粒度對標注短文本的存儲效能[9].在較短的短信文本中進行有效的特征提取是傳統(tǒng)基于內(nèi)容的文本分類方法面臨的主要難題.

圖2 CSMS短信數(shù)量分布Fig.2 SMS number distribution in CSMS

短信正文文本長度是一個重要的可計算特征.短信通常采用即時交互模式分段發(fā)送會話文本.而spam不易維繼會話，為了在一條信息中傳遞較完整的內(nèi)容，正文會比較長.但正常通信雙方有相互默認的背景認知，所以大多數(shù)ham省略了上下文，正文較短.通過對CSMS語料進行正文字節(jié)數(shù)統(tǒng)計可以進一步量化這種特征.統(tǒng)計結(jié)果如圖2所示，橫軸為短信正文字節(jié)數(shù)，縱軸為短信數(shù)量比重.圖2中兩條曲線差異顯著，ham曲線呈現(xiàn)出雙峰特性，而spam曲線呈現(xiàn)出單峰特性，主要集中在120～140字節(jié)之間.這種顯著差異證實了短信是交互式會話信息，spam正文字節(jié)數(shù)相對較大，而多數(shù)的ham正文文本長度約為20字節(jié).

經(jīng)過精確的數(shù)值計算可知,CSMS中最短的spam正文只有38字節(jié)，由此可知短信正文越短(<38字節(jié))，ham概率越高.該后驗規(guī)律說明了短信正文長度的垃圾區(qū)分性，這是會話式交互信息(QQ、MSN、微信等)特有的現(xiàn)象.因此正文長度的垃圾區(qū)分性規(guī)律可以普遍用于會話式交互信息的垃圾過濾.

表1 短信語料

我們從CSMS全集中挑選正文文本長度大于等于38字節(jié)的短信文檔組成一個CSMS-P子集，該子集包含34 242個短信文檔(21 099個spam和13 143個ham).具體的短信語料數(shù)量如表1所示.據(jù)CSMS和CSMS-P中的ham數(shù)可知正文長度的垃圾區(qū)分性規(guī)律可以正確分類79.71%的ham短信.而CSMS-P子集是正文長度的垃圾區(qū)分性規(guī)律無法勝任的部分數(shù)據(jù)，需要采用更高級的方法進行過濾.本文以下部分研究和實驗均采用CSMS-P子集數(shù)據(jù).

2 亞文檔集成學習垃圾短信過濾

根據(jù)最理想的用戶行為假定，垃圾短信過濾應(yīng)用可以建模成有監(jiān)督立即全反饋在線二值文本分類問題.又由于短信文檔包含多個相對獨立的子文檔，因此我們基于分而治之的策略利用這一結(jié)構(gòu)特性提出一種亞文檔集成學習方法.

2.1 亞文檔集成學習

如圖3所示，傳統(tǒng)集成學習的樣本粒度是文檔，例如基于放回隨機采樣的bagging方法[10]和基于錯誤驅(qū)動的boosting方法[11].而亞文檔集成學習的樣本粒度是子文檔.傳統(tǒng)集成學習的弱分類器往往是通過部分文檔學習得到的，而亞文檔集成學習的弱分類器是通過全部文檔的特定部分學習得到的.亞文檔集成學習充分利用了短信文檔包含多個相對獨立子文檔的結(jié)構(gòu)特性，將短信在線二值分類問題轉(zhuǎn)化成若干個子文檔空間上的子分類問題，各個子問題有其特有的特征、模型和結(jié)果，通過綜合多個子問題的結(jié)果得到最終結(jié)果[12].綜上可知亞文檔集成學習的基礎(chǔ)是基于文檔結(jié)構(gòu)特性的特征空間劃分.

圖3 傳統(tǒng)集成學習與亞文檔集成學習

根據(jù)上述亞文檔集成學習思想，我們設(shè)計的用于垃圾短信過濾的亞文檔集成學習框架如圖4所示.該框架主要由子文檔切分器、若干個弱分類器、結(jié)果合成器和反饋學習器構(gòu)成，主要過濾流程是：首先子文檔切分器將輸入的手機短信切分成若干個子文檔；其次每個弱分類器根據(jù)各自的分類模型預(yù)測輸入子文檔的類別，輸出結(jié)果為[0, 1]區(qū)間上的垃圾信度(SS)，反映樣本是spam的似然度；接著結(jié)果合成器將輸入的多個垃圾信度組合成最終垃圾信度；最后反饋學習器接收用戶輸入的類別反饋并分派給每個弱分類器，各弱分類器根據(jù)反饋增量學習更新自己的分類模型.

圖4 亞文檔集成學習框架

(1)

(2)

其中：S表示spam；H表示ham；Di表示第i個弱分類器涵蓋的子文檔；D表示短信文檔.根據(jù)式(1)和(2)所示的Bayes條件概率公式，我們可以通過反饋有監(jiān)督學習預(yù)測結(jié)果.

亞文檔集成學習框架是一種獨立于弱分類器的元框架，因此，任意的在線有監(jiān)督學習二值文本分類算法均可用于實現(xiàn)弱分類器.但亞文檔集成學習框架的有效性取決于子文檔切分器采用的切分策略、結(jié)果合成器采用的合成策略以及在線有監(jiān)督學習弱分類器的有效性.

2.2 切分策略和合成策略

由于短信文檔至少包含源電話號碼、目的電話號碼、短信正文3個子文檔，因此可以通過短信文檔結(jié)構(gòu)識別切分得到3個子文檔.此外采用信息抽取方法從短信正文中抽取垃圾區(qū)分特征碼也可以看成是一種切分策略.我們的子文檔切分器實現(xiàn)了電話號碼特征碼和標點符號特征碼抽取，因此又可以得到兩個子文檔.文檔結(jié)構(gòu)識別切分策略能夠利用文檔內(nèi)含的子文檔間的獨立性，而特征碼抽取切分策略則相當于特征復用和增強技術(shù)，不失為一種從短文本中提取有效特征的好方法[13].

亞文檔集成學習框架是基于在線有監(jiān)督學習的，其中關(guān)鍵的合成策略需要確定每個弱分類器各自結(jié)果的加權(quán)系數(shù).合成策略的好壞受到兩方面因素的制約：一是每個弱分類器在各自子文檔空間上的歷史表現(xiàn)；另一個是待過濾手機短信各個子文檔能夠提供的垃圾區(qū)分特征量.由此我們設(shè)計的合成策略綜合了上述兩種因素.基于弱分類器歷史表現(xiàn)的線性組合加權(quán)系數(shù)可以采用ROC分析得出的ROC曲線下部面積占比進行估計，ROC曲線下部面積占比能夠反映弱分類器在各種閾值情況下的效能累積量度.基于子文檔垃圾區(qū)分特征量的線性組合加權(quán)系數(shù)可以采用文本長度字節(jié)數(shù)進行估計.我們的結(jié)果合成器實現(xiàn)上述這種合成策略時，需要先分別對兩種估計進行歸一化，再將歸一化的加權(quán)系數(shù)進行算術(shù)平均合成.

3 實驗

通過在CSMS 數(shù)據(jù)集上進行TREC有監(jiān)督立即全反饋垃圾過濾實驗[14]，驗證亞文檔集成學習方法的有效性.

3.1 評價方法

由于spam和ham數(shù)量分布極不平衡，因此過濾器評價方法異于傳統(tǒng)文本分類.采用TREC垃圾過濾評價方法和評價工具[15]，包括當前性能、ROC分析[16]、全局性能、過濾耗時等.當前性能指標包括ham誤率(hm%)、spam誤率(sm%)和對數(shù)誤率(lam%)，計算公式如下：

其中：SH和HH分別表示ham評測集中過濾器分錯和分對的樣本數(shù);HS和SS則分別表示spam評測集中過濾器分錯和分對的樣本數(shù).這3個當前性能指標數(shù)值越小過濾器性能越高.

全局性能是指過濾器在不同垃圾信度閾值條件下表現(xiàn)出的過濾能力，通常包括ROC曲線上部面積(1-ROCA%)指標和可接受點(h=0.1%)指標，指標數(shù)值越小，過濾器性能越高[3].在TREC垃圾過濾評價方法中，通常以ROC曲線上部面積(1-ROCA%)為主要評價指標，并根據(jù)1-ROCA%數(shù)值排序參評的過濾器[15].

3.2 結(jié)果與討論

為了驗證亞文檔集成學習框架的有效性，我們在CSMS-P數(shù)據(jù)集上運行bogo分類器、tftS3F分類器以及ndtSFI分類器.其中ndtSFI分類器是根據(jù)我們提出的一種基于串頻索引的文本分類算法實現(xiàn)的，在垃圾郵件過濾上表現(xiàn)優(yōu)秀[17].一方面視短信文檔為純文本，分別運行上述3個分類器.另一方面根據(jù)本文提出的切分策略把短信文檔切分成5個子文檔，把上述3個分類器分別當成弱分類器集成進亞文檔集成學習框架，并運行相同的過濾任務(wù).其中采用亞文檔集成學習框架的分類器標識增加后綴(.sel).

實驗結(jié)果如表2所示，使用亞文檔集成學習框架后，bogo、tftS3F、ndtSFI3個分類器的全局性能(1-ROCA%指標)分別從0.476 3、0.002 4、0.243 7優(yōu)化為0.008 8、0.002 3、0.002 3.由此可知亞文檔集成學習框架能夠提高Bayes算法、松弛在線支持向量機算法、基于串頻索引的文本分類算法的性能.

表2數(shù)據(jù)還表明在3個采用亞文檔集成學習框架的過濾器當中，我們的ndtSFI.sel不僅全局性能最優(yōu)，1-ROCA%指標達到0.002 3，h=0.1%指標達到0.21，同時當前性能中hm%指標達到0.03，lam%指標達到0.11，也是最優(yōu)的，并且耗時(4.4分鐘)也是很少的.雖然sm%指標不是最優(yōu)，但垃圾過濾對于二值目標不是均等看待的，更注重低hm%條件下追求低lam%、低hm%是算法實用的前提.因此采用亞文檔集成學習框架，基于串頻索引的文本分類算法能夠在大大降低計算時間的情況下達到最優(yōu)的垃圾短信過濾效果.

表2 實驗結(jié)果

還可以通過ROC分析直觀評價上述實驗結(jié)果.實驗ROC曲線和ROC學習曲線分別如圖5、圖6所示.圖5中ndtSFI.sel的ROC曲線、左邊框、上邊框圍成的面積比較小，說明ndtSFI.sel的全局過濾性能十分理想.

圖5 ROC曲線

圖6 ROC學習曲線

如圖6所示.在訓練樣本達到約12 500時，ndtSFI.sel學習曲線達到理想的1-ROCA%性能(0.01)，平均1-ROCA%值能達到0.002 3，這說明采用亞文檔集成學習框架能夠使基于串頻索引的文本分類算法具有很強的在線學習能力.

亞文檔集成學習框架的有效性是因為：1) 通過劃分子文檔空間，文本特征粒度更細，減少文本特征混淆，提高表示的獨立性；2) 在子文檔空間上采用統(tǒng)計機器學習得到的分類模型更加適合該子文檔分類，增強統(tǒng)計的針對性；3) 在子文檔空間上進行特征抽取和分類模型更新更簡潔，提升計算的高效性[18].又由于弱分類器之間相互獨立，因此亞文檔集成學習框架具備較強的并行計算潛力.通過硬件重復多個弱分類器，理論上亞文檔集成學習框架過濾一條短信的耗時接近最慢弱分類器耗時.

4 結(jié)論

本文回顧了國內(nèi)垃圾短信態(tài)勢，統(tǒng)計分析了短信文本特征，提出一種亞文檔集成學習框架.該框架打破文檔級特征粒度，通過附加結(jié)構(gòu)信息將文本特征進行了細粒度區(qū)分，將結(jié)構(gòu)特性轉(zhuǎn)變?yōu)榭捎嬎闾卣?實驗結(jié)果表明亞文檔集成學習框架能夠顯著提升Bayes算法、松弛在線支持向量機算法、基于串頻索引的文本分類算法的過濾效能，特別是集成我們的基于串頻索引的文本分類算法能夠在大大降低計算時間的條件下達到最優(yōu)的垃圾短信過濾效果.

下一步研究將關(guān)注面向垃圾手機短信過濾的半監(jiān)督學習、主動學習、個性化學習，在已有的機器學習算法中引入亞文檔集成學習框架，通過加入巨量未標注短信，通過挖掘多個弱分類器之間的差異，發(fā)現(xiàn)有價值的未標注短信，通過構(gòu)建全局分類模型和個性化分類模型以提升過濾方法的效果.

[1] SARAH J D, MARK B, DEREK G. SMS spam filtering: methods and data[J]. Expert systems with applications, 2012, 39(10): 9899-9908.

[2] CHEN T, KAN M Y. Creating a live, public short message service corpus: the NUS SMS corpus[J]. Language resources and evaluation, 2013, 47(2): 299-335.

[3] 劉伍穎. 面向垃圾信息過濾的主動多域?qū)W習文本分類方法研究[D]. 長沙：國防科學技術(shù)大學, 2011.

[4] DENNING P J. Electronic junk[J]. Communications of the ACM, 1981, 25(3): 163-165.

[5] HU Y, GUO C, NGAI E W T, et al. A scalable intelligent non-content-based spam-filtering framework[J]. Expert systems with applications, 2010, 37(12): 8557-8565.

[6] KHORSI A. An overview of content-based spam filtering techniques[J]. Informatica, 2007, 31(3): 269-277.

[7] SCULLEY D, WACHMAN G M. Relaxed online SVMs for spam filtering[C]//The 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2007) Proceedings. Amsterdam, 2007: 415-422.

[8] 劉伍穎, 王挺. 基于詞模型索引的短文本在線過濾方法[J]. 華中科技大學學報(自然科學版), 2010, 38(4): 42-45.

[9] LIU W Y, WANG T. Index-based online text classification for SMS spam filtering[J]. Journal of computers, 2010, 5(6): 844-851.

[10]唐偉, 周志華. 基于Bagging的選擇性聚類集成[J]. 軟件學報, 2005, 16(4): 496-502.

[11]刁力力, 胡可云, 陸玉昌, 等. 用 Boosting方法組合增強Stumps進行文本分類[J]. 軟件學報, 2002, 13(8): 1361-1367.

[12]李欣雨, 袁方, 劉宇, 等. 面向中文新聞話題檢測的多向量文本聚類方法[J]. 鄭州大學學報(理學版), 2016, 48(2): 47-52.

[13]鄧冰娜, 王煜, 劉宇. 一種應(yīng)用于博客的垃圾評論識別方法[J]. 鄭州大學學報(理學版), 2011, 43(1): 65-69.

[14]CORMACK G V. Email spam filtering: a systematic review[J]. Foundations and trends in information retrieval, 2008, 1(4): 335-455.

[15]CORMACK G V. TREC 2007 spam track overview[C]// Proceedings of the Sixteenth Text Retrieval Conference, TREC 2007. Maryland: Gaithersburg, 2007: 500-274.

[16]FAWCETT T. An introduction to ROC analysis[J]. Pattern recognition letters, 2006, 27(8): 861-874.

[17]劉伍穎, 王挺. 結(jié)構(gòu)化集成學習垃圾郵件過濾[J]. 計算機研究與發(fā)展, 2012, 49(3): 628-635.

[18]DIETTERICH T G. Ensemble methods in machine learning[J]. International workshop on multiple classifier systems, 2000,1857(1):1-15.

(責任編輯：王海科)

Sub-document Ensemble Learning for SMS Spam Filtering

LIU Wuying, WANG Lin

(LaboratoryofLanguageEngineeringandComputing,GuangdongUniversityofForeignStudies,Guangzhou510420,China)

A sub-document ensemble learning (SEL) method was proposed to solve the problem of SMS spam filtering. The method used the SEL framework to break the online binary classification issue of short texts into several sub-issues, and made the final category prediction by a linear combination of several sub-results. Moreover, an effective weak classifier was implemented according to the string-frequency-index-based text classification algorithm. The experimental results showed that performances of previous text classification algorithms could be improved by the SEL framework, and the string-frequency-index-based weak classifier could achieve the state-of-the-art performance within the SEL framework.

SMS spam filtering；subdocument ensemble learning；string-frequency index；TREC evaluation

2016-10-30

國家語言文字工作委員會重點項目(ZDI 135-26)；廣東省高校特色創(chuàng)新項目(2015KTSCX035).

劉伍穎(1980—)，男，江西九江人，副研究員，主要從事計算語言學和自然語言處理研究，E-mail：wyliu@gdufs.edu.cn；通信作者：王琳(1983—)，女，山東威海人，講師，主要從事應(yīng)用語言學研究，E-mail：wanglin@nudt.edu.cn．

TP391.1

A

1671-6841(2017)03-0059-06

10.13705/j.issn.1671-6841.2016306