基于抽樣的垃圾短信過濾方法

(電子科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 成都 610054)



摘 要：現(xiàn)有垃圾短信過濾系統(tǒng)主要采用對(duì)短信進(jìn)行逐條分析判斷的技術(shù)，因此處理的效率比較低。針對(duì)這一過濾技術(shù)的不足，提出了一個(gè)基于抽樣的垃圾短信過濾方法，該方法引入用戶信任度的概念，根據(jù)用戶的信任度對(duì)用戶發(fā)送的短信進(jìn)行抽樣過濾，極大地提高了處理效率。同時(shí)該方法整合了多項(xiàng)垃圾短信過濾技術(shù)（黑白名單、關(guān)鍵詞及內(nèi)容過濾技術(shù)），較之單一的過濾方法在準(zhǔn)確率和效率上有很大的提高。

關(guān)鍵詞：垃圾短信； 用戶信任度； 抽樣過濾； 文本分類

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：10013695(2009)03093303



Filtering algorithm of junk SMS based on sample



ZHONG Yanhui， FU Yan， CHEN Anlong， GUAN Na



(School of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu 610054， China)



Abstract:The existing filter system of junk SMS use the technology which judge SMS one by one， therefore its efficiency is quite low. To overcome the shortcomings of existing filtering technologies， this paper proposed a filtering algorithm of junk SMS based on sample. Introduced the concept of user’s confidence， and filtered messages by SMS center according to user’s confidence. Implemented three kinds of filtering technology (black/white list based， key words based， content based) on junk short message filtering method， which increase the efficiency very significantly.

Key words：junk shortmessage; user’s confidence; sample filtering; text categorization



近幾年來，由于移動(dòng)通信技術(shù)的快速發(fā)展，催化了諸多增值服務(wù)的產(chǎn)生。短信作為移動(dòng)通信的增值服務(wù)之一，在為人們提供價(jià)格低廉和便捷的通信服務(wù)的同時(shí)，滋生了大量以傳播淫穢色情、商業(yè)欺詐以及商業(yè)廣告等不良信息為目的垃圾短信[1]，并嚴(yán)重干擾人們生活、妨害社會(huì)安全以及造成網(wǎng)絡(luò)擁塞，垃圾短信的監(jiān)管問題已經(jīng)受到社會(huì)各界的廣泛重視[2]。除了從立法層面加強(qiáng)對(duì)信息發(fā)布進(jìn)行監(jiān)管外，更重要的是要從技術(shù)層面探索有效的垃圾短信防范技術(shù)。因此，研究短信智能監(jiān)管技術(shù)和系統(tǒng)，建立一個(gè)高效、準(zhǔn)確、可靠的短信監(jiān)管平臺(tái)，實(shí)現(xiàn)短信內(nèi)容的監(jiān)管，不僅有利于國家安全和社會(huì)穩(wěn)定，保護(hù)人民財(cái)產(chǎn)和正常生活，而且有重要的社會(huì)價(jià)值。目前，針對(duì)垃圾短信泛濫問題主要的過濾技術(shù)有基于黑∕白名單的垃圾短信過濾、基于規(guī)則的垃圾短信過濾和基于內(nèi)容的垃圾短信過濾[3]。黑∕白名單技術(shù)有很大的局限性，而基于規(guī)則的垃圾術(shù)也有一些不盡人意的地方，如規(guī)則需要人工指定，沒有經(jīng)驗(yàn)的用戶會(huì)影響規(guī)則的有效性和準(zhǔn)確率。鑒于此，目前對(duì)垃圾短信的過濾研究很多都集中到內(nèi)容分析方面。但是只有對(duì)短信進(jìn)行逐條分析，才能判斷是否為垃圾短信，因此處理的效率比較低。不管是基于關(guān)鍵詞還是基于內(nèi)容的垃圾短信過濾方法，都存在大量運(yùn)算，這樣會(huì)造成短信服務(wù)中心網(wǎng)絡(luò)堵塞[1，2]。

對(duì)以上提到的各種技術(shù)在垃圾短信過濾中的不足，本文融合黑名單、關(guān)鍵字和內(nèi)容過濾技術(shù)，提出了一個(gè)基于抽樣過濾的垃圾短信過濾方法，在一定程度上彌補(bǔ)了采用單一處理方法所存在的問題。同時(shí)，實(shí)驗(yàn)表明該方法提高了垃圾短信過濾的效率和準(zhǔn)確性。

1 基于抽樣的垃圾短信過濾系統(tǒng)的架構(gòu)

傳統(tǒng)的垃圾短信過濾方法需要對(duì)短信進(jìn)行逐條分析，才能判斷是否是垃圾短信，因此處理的效率較低。但實(shí)際情況是大部分用戶所發(fā)送的短信都不是垃圾短信，沒有必要逐條分析。在兼顧垃圾短信過濾的準(zhǔn)確率和效率前提下，本文在傳統(tǒng)垃圾短信過濾方法的基礎(chǔ)上，創(chuàng)新地提出給每個(gè)用戶設(shè)定一個(gè)信任度，并根據(jù)用戶信任度的不同，對(duì)發(fā)送到短信服務(wù)中心的短信進(jìn)行不同強(qiáng)度的抽樣，抽樣到的短信根據(jù)構(gòu)成短信的文字信息進(jìn)行分類，而不必對(duì)每一條短信進(jìn)行逐條分析，提高了垃圾短信處理效率，一定程度上解決了短信服務(wù)中心網(wǎng)絡(luò)堵塞問題。本文設(shè)計(jì)的基于抽樣的垃圾短信過濾系統(tǒng)主要包括以下步驟：

a)為用戶設(shè)置一個(gè)用戶信任度。

b)根據(jù)短信用戶的信任度，對(duì)經(jīng)過短信服務(wù)中心的短信進(jìn)行不同強(qiáng)度的抽樣過濾，用戶信任度越低，抽樣強(qiáng)度越高;反之，亦然。未被抽樣到的短信作為正常短信予以發(fā)送，被抽樣到的短信作為可疑短信由步驟c）處理。

c)被抽樣到的可疑短信采用依據(jù)構(gòu)成短信的文字信息確定短信是否是垃圾短信，如是，直接過濾掉；如果不是，認(rèn)為是正常短信，予以發(fā)送。

d)依據(jù)用戶短信發(fā)送情況，更新該用戶的信任度。正常短信的發(fā)送量越大，垃圾短信的發(fā)送量越小，用戶信任度就會(huì)提高，反之則降低。

依據(jù)構(gòu)成短信的文字信息判定是否為垃圾短信的過濾方法，主要有前述的基于關(guān)鍵詞或基于內(nèi)容的垃圾短信過濾方法。基于抽樣的垃圾短信過濾系統(tǒng)設(shè)計(jì)如圖1所示。它創(chuàng)新性地采用了基于用戶信任度抽樣的思想，同時(shí)融合了多種傳統(tǒng)的垃圾短信過濾技術(shù)，構(gòu)建了一個(gè)有效垃圾短信過濾系統(tǒng)。

2 系統(tǒng)中的主要過濾模塊分析

系統(tǒng)的過濾部分主要包括四個(gè)模塊，即用戶信任度抽樣過濾、短信長度過濾、短信關(guān)鍵詞過濾和短信內(nèi)容過濾。以下分別對(duì)四個(gè)模塊進(jìn)行詳細(xì)描述。

1）過濾模塊 1：用戶信任度抽樣過濾

所謂用戶信任度抽樣，是指根據(jù)用戶的信任度對(duì)用戶所發(fā)送的短信進(jìn)行相應(yīng)頻度(強(qiáng)度)的抽樣過濾。用戶信任度是指對(duì)用戶發(fā)送正常短信的信任程度，由用戶垃圾短信的發(fā)送量、正常短信的發(fā)送量和總的短信發(fā)送量計(jì)算而成。如果用戶信任度不同，那么用戶抽樣監(jiān)測的頻率(強(qiáng)度)也就不一樣。被抽樣到的垃圾短信作為可疑短信1，到短信長度的過濾模塊進(jìn)行確認(rèn)；未被抽樣到的短信作為正常短信，并予以發(fā)送。

此外，本文結(jié)合傳統(tǒng)的黑/白名單過濾方法[4]。如果用戶的信任度為0，那么表示該用戶為黑名單用戶，則該用戶所發(fā)送的短信是垃圾短信，將直接過濾掉；當(dāng)用戶的信任度為1，則表示該用戶為白名單用戶，即特權(quán)用戶，用戶所發(fā)送的短信是正常短信，直接給予通過。這樣就將本文提出的抽樣過濾方法與傳統(tǒng)的黑/白名單過濾方法很好地結(jié)合起來了。

2）過濾模塊2：短信長度的過濾

接收用戶信任度抽樣過濾模塊來的可疑短信1，計(jì)算短信內(nèi)容的長度，判斷短信內(nèi)容的長度是否超過設(shè)定的閾值。當(dāng)短信長度超過設(shè)定閾值時(shí)，該短信為可疑短信2，到關(guān)鍵詞過濾模塊進(jìn)行確認(rèn)；短信的長度小于設(shè)定閾值時(shí)，該短信為正常短信，并予以發(fā)送。

基于短信長度的過濾方法主要根據(jù)設(shè)定的垃圾短信最小長度閾值來判斷用戶發(fā)送的短信是否為正常短信。由于短信的長度小于70個(gè)中文字符，可以根據(jù)短信的長度對(duì)短信進(jìn)行初步判定，一般長度比較短的短信是垃圾短信的可能性相對(duì)比較小。在該模塊中的短信長度可以通過分析歷史垃圾短信的長度分布模式而動(dòng)態(tài)設(shè)定。

3）過濾模塊3：短信關(guān)鍵詞過濾

接收短信長度過濾模塊來的可疑短信2。根據(jù)設(shè)定的關(guān)鍵詞列表，監(jiān)測用戶發(fā)送的短信中是否含有設(shè)定關(guān)鍵詞[4]。若含有，則認(rèn)為是垃圾短信，予以過濾；反之，則該短信作為可疑短信3到短信內(nèi)容過濾模塊進(jìn)行確認(rèn)。

4）過濾模塊4：短信內(nèi)容過濾

短信內(nèi)容過濾主要根據(jù)短信的內(nèi)容進(jìn)行分類過濾。在本文中，該內(nèi)容過濾主要采用貝葉斯分類算法[5~7]，接收關(guān)鍵詞過濾模塊來的可疑短信3，對(duì)其進(jìn)行自動(dòng)分類。分類為正常短信的將直接予以發(fā)送；若判斷為垃圾短信，則攔截。同時(shí)根據(jù)新擴(kuò)充的正常短信和垃圾短信更新分類器。

根據(jù)用戶的信任度確定對(duì)不同短信用戶的過濾強(qiáng)度，這樣使得大部分用戶所發(fā)送的短信都能直接通過，只有小部分用戶所發(fā)送的短信接受相應(yīng)的檢測，大大提高了過濾系統(tǒng)的處理效率；此外，本文還整合了傳統(tǒng)的垃圾短信過濾技術(shù)，構(gòu)成了一個(gè)多層的垃圾短信過濾方法，對(duì)抽樣到的短信進(jìn)行有效的判別，較之采用單一過濾技術(shù)，在準(zhǔn)確性和效率上都有了很大提高。

3 系統(tǒng)主要處理流程

3.1 用戶信任度抽樣流程

首先給每個(gè)用戶設(shè)定一個(gè)信任度。以下是用戶信任度抽樣過濾模塊的具體算法描述： 

a)初始化用戶信息。統(tǒng)計(jì)用戶總的短信發(fā)送量sumi，正常短信的發(fā)送量mi。用戶的信任度為

crediti=credit_MINm/sumi≤credit_MIN

mi/sumi其他credit_MAXmi/sumi≥credit_MAX

（1）

其中：i是用戶編號(hào)；最小信任度credit_MIN和最大信任度credit_MAX可以根據(jù)情況自適應(yīng)地調(diào)整以符合實(shí)際要求。為了防止某些普通用戶的信任度過低導(dǎo)致用戶發(fā)送的短信直接被認(rèn)為是垃圾短信，或者信任度過高導(dǎo)致對(duì)使用用戶疏于監(jiān)控。黑名單用戶信任度為0，特權(quán)用戶信任度為1，直接過濾或予以發(fā)送，這類用戶不需要進(jìn)行抽樣分析短信的文字內(nèi)容，即可判定短信是否是垃圾短信。此時(shí)，用戶發(fā)送垃圾短信的頻率為

junk_pi=(sumi-mi)/sumi=1-crediti(2)

當(dāng)用戶為沒有歷史信息的新用戶時(shí)，則用戶信任度設(shè)為credit=credit_MIN，用戶短信的發(fā)送量sumi和正常短信的發(fā)送量mi都為0，此時(shí)需要連續(xù)對(duì)新用戶發(fā)送的短信進(jìn)行抽樣，以獲取用戶發(fā)送短信的情況。設(shè)置有連續(xù)抽樣標(biāo)志flagi。flagi=true表示需要連續(xù)抽樣；flagi=1表示信任度概率連續(xù)抽樣。當(dāng)用戶發(fā)送的短信需要連續(xù)抽樣時(shí)，n表示連續(xù)為正常短信的最大條數(shù)。此時(shí)設(shè)有一個(gè)計(jì)數(shù)器n1i，表示連續(xù)檢測時(shí)連續(xù)為正常短信的數(shù)量，初始值為0。

b)接收用戶短信，檢索用戶信任度，判斷是否為0、1或其他值。如果為0，則為黑名單用戶，短信予以攔截；如果為1，則為特權(quán)用戶，短信予以直接通過，并發(fā)送；如果為其他值，則轉(zhuǎn)到步驟c)。

c)用戶短信發(fā)送量sumi=sumi+1，當(dāng)連續(xù)抽樣標(biāo)志flagi=true時(shí)，轉(zhuǎn)到短信長度過濾模塊；否則按信任度概率選擇當(dāng)前短信是否需要抽樣檢測。若抽樣到則轉(zhuǎn)到短信長度過濾模塊；否則進(jìn)入正常短信處理流程。

3.2 用戶短信長度過濾流程

從用戶信任度抽樣過濾模塊中接收可疑短信1，進(jìn)行短信長度過濾。設(shè)垃圾短信的長度大于等于x，因此，當(dāng)短信長度小于x時(shí)，則認(rèn)為該短信是正常短信，予以直接通過并發(fā)送；對(duì)短信長度大于等于x的短信作為可疑短信2，需進(jìn)入關(guān)鍵詞過濾模塊確認(rèn)。其具體的過濾步驟為：

a)接收用戶信任度抽樣過濾模塊來的可疑短信1；

b)計(jì)算每條短信的長度x；

c)判斷短信的長度是否大于設(shè)置的閾值x，如果小于設(shè)定閾值轉(zhuǎn)到步驟d)，否則轉(zhuǎn)到步驟e)；

d)短信為正常短信，進(jìn)入正常短信處理流程；

e)該短信為可疑短信2，轉(zhuǎn)到關(guān)鍵詞過濾模塊進(jìn)行處理。

3.3 關(guān)鍵詞過濾流程

根據(jù)設(shè)定的關(guān)鍵詞列表，監(jiān)測用戶發(fā)送的短信中是否含有設(shè)定關(guān)鍵詞。

a)接收短信長度過濾模塊來的可疑短信2。

b)根據(jù)設(shè)定的關(guān)鍵詞列表，判斷短信中是否含有列表中的關(guān)鍵詞。若無，則將該短信作為可疑短信3，轉(zhuǎn)到短信內(nèi)容過濾模塊；若有，則認(rèn)為是垃圾短信，進(jìn)入垃圾短信處理流程。

3.4 內(nèi)容過濾流程

短信內(nèi)容過濾主要根據(jù)短信的內(nèi)容進(jìn)行分類過濾。具體的過濾步驟如下：

a)接收短信關(guān)鍵詞過濾模塊來的可疑短信3作為待分類短信。

b)對(duì)訓(xùn)練樣本和可疑短信進(jìn)行分詞。

c)基于幾率比的特征提取。

d)采用貝葉斯分類算法，對(duì)可疑短信3進(jìn)行分類：

(a)若是垃圾短信，則進(jìn)入垃圾短信處理流程。

(b)若是正常短信，則進(jìn)入正常短信處理流程。

3.5 正常短信處理流程

當(dāng)用戶短信確定為正常短信后，正常短信的發(fā)送量mi=mi+1，并判斷連續(xù)抽樣標(biāo)志flagi是否為true：如果flagi=1，則該短信予以發(fā)送，返回到用戶信任度過濾模塊；如果flagi=true，則連續(xù)正常短信數(shù)nli=nli+1。判斷nli是否小于(1-crediti)×n：如果nli＜(1-crediti)×n，則發(fā)送該短信，返回到抽樣過濾模塊；若nli≥(1-crediti)×n，則flagi=1，nli=0，并發(fā)送該短信，返回到過用戶信任度抽樣過濾模塊。

3.6 垃圾短信的處理流程

當(dāng)用戶短信確定為垃圾短信后，判斷連續(xù)抽樣標(biāo)志flagi是否是true：如果flagi=true，則連續(xù)正常短信數(shù)nli=0；若flagi=flase，則連續(xù)正常短信數(shù)nli=0，flagi=true。將該短信予以攔截，返回到用戶信任度抽樣過濾模塊。

4 實(shí)驗(yàn)與分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

目前對(duì)垃圾短信過濾的研究還不多見，由于短信涉及個(gè)人隱私問題，公開的短信語料暫時(shí)還沒有。為此，本文自建了2 000條短信的語料庫。該短信語料庫含有垃圾短信和正常短信各1 000條。將這2 000條短信各自均分成5份，隨機(jī)各自選取3份合成訓(xùn)練集(1 200條)，其余合成測試集(800條)。共做5組實(shí)驗(yàn)，即5次交叉驗(yàn)證，取其平均值作為參評(píng)結(jié)果。

4.2 實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)

目前對(duì)垃圾短信過濾性能進(jìn)行評(píng)價(jià)的指標(biāo)主要有以下兩個(gè)方面：

首先，假設(shè)測試集合中共有N條短信，定義幾個(gè)變量（表1），顯然有 N=A+B+C+D。

定義如下評(píng)價(jià)指標(biāo)：

a)召回率（recall）：recall=A/(A+C)×100%

這個(gè)指標(biāo)反映了垃圾短信過濾的能力，召回率越高，誤否認(rèn)就越少。

b)正確率（precision）：precision=A/(A+B)×100%

這個(gè)指標(biāo)反映了過濾系統(tǒng)辨別垃圾短信的能力，正確率越大，將非垃圾短信判定為垃圾短信的可能性就越小。

表1 變量定義表

判 斷垃圾短信合法短信

判為垃圾短信AB

判為正常短信 CD

4.3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)在Windows XP平臺(tái)上進(jìn)行，采用基于VC++平臺(tái)的C++編程語言實(shí)現(xiàn)。其中分詞算法采用了中國科學(xué)院計(jì)算技術(shù)研究所的分詞系統(tǒng)ICTCLAS(Institute of Computing Technology，Chinese Lexical Analysis System)；特征選擇采用幾率比 (oddsratio，OR)方法。特征詞庫的存儲(chǔ)采用哈希表存儲(chǔ)結(jié)構(gòu)。

表2和3表明：隨著特征數(shù)量的增加，兩個(gè)方法中的召回率和正確率都在相應(yīng)增加，說明在內(nèi)容過濾部分恰當(dāng)?shù)剡x擇特征數(shù)量對(duì)分類的召回率和正確率有很大的影響。此外，本文所采用的方法比單一的貝葉斯方法在垃圾短信過濾上的召回率和準(zhǔn)確率都有很大的提高，而且處理時(shí)間也大大降低（表2和3）。但由于目前中文分詞技術(shù)及貝葉斯分類算法還存在一些不足，本文中的方法在準(zhǔn)確率方面必然受到一定的影響。

5 結(jié)束語

本文提出了一個(gè)基于抽樣的垃圾短信過濾方法，創(chuàng)新性地引入了用戶信任度的概念，有效地對(duì)每個(gè)用戶進(jìn)行不同強(qiáng)度的監(jiān)管，同時(shí)引入可疑短信庫，彌補(bǔ)了把正常短信判為垃圾短信的損失。本文的實(shí)驗(yàn)結(jié)果是在程序初始運(yùn)行時(shí)得出，由于該方法具有自動(dòng)更新的功能，隨著程序的持續(xù)運(yùn)行，其效率和準(zhǔn)確性將會(huì)有所提高。下一步工作是尋找一種更有效的適合于貝葉斯分類的特征提取方法以及從垃圾短信庫中自動(dòng)有效提取關(guān)鍵字的方法。

參考文獻(xiàn)：

［1］人民網(wǎng). 數(shù)字中國[EB/OL].(200505). http://www.people.com.cn.

[2]中國社會(huì)科學(xué)院. 手機(jī)托起“第五媒體”[EB/OL]. （2005）. http://www.cass.net.cn.

[3]易陽鋒.垃圾短信監(jiān)控的原理與實(shí)現(xiàn)[J].中興通訊技術(shù)，2005，12(6):4954.

[4]胡于進(jìn)，周小鈴，凌鈴，等.基于向量空間模型的貝葉斯文本分類方法[J].計(jì)算機(jī)與數(shù)字工程，2004，32(6):2830，77.

[5]CRISTIANINI N， SHAWE T J. An introduction to support vector machines and other kernelbased learning methods［M］. Cambridge: Cambridge University Press， 2000.

[6]LIU Tao， LIU Shengping， CHEN Zheng， et al. An evaluation on feature selection for text clustering[C]//Proc of the 20th International Conference on Machine Learning (ICML03). 2003:488495.

[7]TAN A H，YU P. A comparative study on Chinese text categorization methods[C]//PRICAI 2000 Workshop on Text and Web Mining. 2000:2435.