面向垃圾短信過濾的亞文檔集成學(xué)習(xí)

劉伍穎， 王 琳

(廣東外語外貿(mào)大學(xué) 語言工程與計(jì)算實(shí)驗(yàn)室 廣東 廣州 510420)

面向垃圾短信過濾的亞文檔集成學(xué)習(xí)

劉伍穎， 王 琳

(廣東外語外貿(mào)大學(xué) 語言工程與計(jì)算實(shí)驗(yàn)室 廣東 廣州 510420)

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

垃圾短信過濾； 亞文檔集成學(xué)習(xí)； 串頻索引； TREC評測

0 引言

垃圾短信(SMS spam)是指在移動通信網(wǎng)絡(luò)中不請自來、不加選擇、大批量發(fā)送的長度在140字節(jié)以內(nèi)的文本文檔.自2008年開始，國內(nèi)12321網(wǎng)絡(luò)不良與垃圾信息舉報(bào)受理中心每年發(fā)布兩次《手機(jī)短信息狀況調(diào)查報(bào)告》.報(bào)告中的每周垃圾短信率和每周垃圾短信數(shù)是兩項(xiàng)非常關(guān)鍵的指標(biāo).每周垃圾短信率表示用戶平均每周收到的短信中垃圾短信所占的百分比.根據(jù)報(bào)告中的這兩項(xiàng)指標(biāo)數(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，雖然各個具體時(shí)段略有波動，但整體趨勢變化不大.從2014年至今用戶平均每周收到的垃圾短信數(shù)量又略有增加.由此可見，當(dāng)前垃圾短信形勢依然嚴(yán)峻，垃圾短信占據(jù)手機(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ù)是按時(shí)序從志愿者那里收集的真實(shí)短信，總共包含85 870個短信文檔(21 099個spam和64 771個ham)，其中每個短信文檔包含源電話號碼、目的電話號碼和短信正文三個子文檔，并且文檔的類別標(biāo)簽是根據(jù)提供者的反饋進(jìn)行人工標(biāo)注的[3].

1 短信文本特征

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

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

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

經(jīng)過精確的數(shù)值計(jì)算可知,CSMS中最短的spam正文只有38字節(jié)，由此可知短信正文越短(<38字節(jié))，ham概率越高.該后驗(yàn)規(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ī)律無法勝任的部分?jǐn)?shù)據(jù)，需要采用更高級的方法進(jìn)行過濾.本文以下部分研究和實(shí)驗(yàn)均采用CSMS-P子集數(shù)據(jù).

2 亞文檔集成學(xué)習(xí)垃圾短信過濾

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

2.1 亞文檔集成學(xué)習(xí)

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

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

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

圖4 亞文檔集成學(xué)習(xí)框架

(1)

(2)

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

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

2.2 切分策略和合成策略

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

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

3 實(shí)驗(yàn)

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

3.1 評價(jià)方法

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

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

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

3.2 結(jié)果與討論

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

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

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

表2 實(shí)驗(yàn)結(jié)果

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

圖5 ROC曲線

圖6 ROC學(xué)習(xí)曲線

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

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

4 結(jié)論

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

下一步研究將關(guān)注面向垃圾手機(jī)短信過濾的半監(jiān)督學(xué)習(xí)、主動學(xué)習(xí)、個性化學(xué)習(xí)，在已有的機(jī)器學(xué)習(xí)算法中引入亞文檔集成學(xué)習(xí)框架，通過加入巨量未標(biāo)注短信，通過挖掘多個弱分類器之間的差異，發(fā)現(xiàn)有價(jià)值的未標(biāo)注短信，通過構(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習(xí)文本分類方法研究[D]. 長沙：國防科學(xué)技術(shù)大學(xué), 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]. 華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 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]. 軟件學(xué)報(bào), 2005, 16(4): 496-502.

[11]刁力力, 胡可云, 陸玉昌, 等. 用 Boosting方法組合增強(qiáng)Stumps進(jìn)行文本分類[J]. 軟件學(xué)報(bào), 2002, 13(8): 1361-1367.

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

[13]鄧冰娜, 王煜, 劉宇. 一種應(yīng)用于博客的垃圾評論識別方法[J]. 鄭州大學(xué)學(xué)報(bào)(理學(xué)版), 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)化集成學(xué)習(xí)垃圾郵件過濾[J]. 計(jì)算機(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.

(責(zé)任編輯：王海科)

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

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

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

TP391.1

A

1671-6841(2017)03-0059-06

10.13705/j.issn.1671-6841.2016306