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

劉伍穎， 王 琳

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

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

劉伍穎， 王 琳

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

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

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

0 引言

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

圖1 垃圾短信態勢

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

盡管垃圾短信泛濫，但由于隱私問題，公開的短信語料[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數據是按時序從志愿者那里收集的真實短信，總共包含85 870個短信文檔(21 099個spam和64 771個ham)，其中每個短信文檔包含源電話號碼、目的電話號碼和短信正文三個子文檔，并且文檔的類別標簽是根據提供者的反饋進行人工標注的[3].

1 短信文本特征

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

圖2 CSMS短信數量分布Fig.2 SMS number distribution in CSMS

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

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

表1 短信語料

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

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

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

2.1 亞文檔集成學習

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

圖3 傳統集成學習與亞文檔集成學習

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

圖4 亞文檔集成學習框架

(1)

(2)

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

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

2.2 切分策略和合成策略

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

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

3 實驗

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

3.1 評價方法

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

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

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

3.2 結果與討論

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

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

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

表2 實驗結果

還可以通過ROC分析直觀評價上述實驗結果.實驗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) 在子文檔空間上采用統計機器學習得到的分類模型更加適合該子文檔分類，增強統計的針對性；3) 在子文檔空間上進行特征抽取和分類模型更新更簡潔，提升計算的高效性[18].又由于弱分類器之間相互獨立，因此亞文檔集成學習框架具備較強的并行計算潛力.通過硬件重復多個弱分類器，理論上亞文檔集成學習框架過濾一條短信的耗時接近最慢弱分類器耗時.

4 結論

本文回顧了國內垃圾短信態勢，統計分析了短信文本特征，提出一種亞文檔集成學習框架.該框架打破文檔級特征粒度，通過附加結構信息將文本特征進行了細粒度區分，將結構特性轉變為可計算特征.實驗結果表明亞文檔集成學習框架能夠顯著提升Bayes算法、松弛在線支持向量機算法、基于串頻索引的文本分類算法的過濾效能，特別是集成我們的基于串頻索引的文本分類算法能夠在大大降低計算時間的條件下達到最優的垃圾短信過濾效果.

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

[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] 劉伍穎. 面向垃圾信息過濾的主動多域學習文本分類方法研究[D]. 長沙：國防科學技術大學, 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]鄧冰娜, 王煜, 劉宇. 一種應用于博客的垃圾評論識別方法[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]劉伍穎, 王挺. 結構化集成學習垃圾郵件過濾[J]. 計算機研究與發展, 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)；廣東省高校特色創新項目(2015KTSCX035).

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

TP391.1

A

1671-6841(2017)03-0059-06

10.13705/j.issn.1671-6841.2016306