基于樸素貝葉斯的中文垃圾短信過濾系統(tǒng)的設(shè)計

摘要：在傳統(tǒng)垃圾短信過濾系統(tǒng)基礎(chǔ)上引入了中文分詞算法和樸素貝葉斯算法，使其具有了自學習能力，克服了傳統(tǒng)垃圾短信系統(tǒng)需要人工設(shè)置、無法適應(yīng)短信內(nèi)容變化、誤判率高的缺點。實踐證明該短信過濾系統(tǒng)具有較高的準確率和適應(yīng)力。

關(guān)鍵詞：樸素貝葉斯；垃圾短信；短信過濾

中圖分類號：TP302文獻標識碼：A文章編號：1009-3044(2008)32-1178-03

Design of Chinese SMS Spam Filtering System Based on the Naive Bayes

MOU Xiao-guang1， GONG Li-ning2

(1.Library， Qingdao Agricultural University， Qingdao 266109， China; 2.Network Center， Qingdao Agricultural University， Qingdao 266109， China)

Abstract: The Chinese word segmentation algorithm and the Naive Bayes algorithm are introduced into the tradition of SMS spam filtering system， it has a self-learning ability to overcome the defects of artificial setup of traditional spam SMS system ， impossible adaptability to the changes in the content of the SMS and the high rate of miscarriage of justice. Practice has proved that the message filtering system has high accuracy and adaptability.

Key words: naive bayes; SMS spam; SMS filtering

1 引言

手機短信以其“短、快、新、奇”的模式已經(jīng)成為人們一種非常重要的通訊方式，然而我們在享受短信給我們帶來的便捷的同時，也不得不面對垃圾短信騷擾的無奈。據(jù)調(diào)查統(tǒng)計，2007年上半年，每位手機用戶平均每周收到8.29條垃圾短信[1]。垃圾短信的無處不在，已經(jīng)成為了電信系統(tǒng)的頑疾，給正在蓬勃發(fā)展的移動通信業(yè)帶來了極大的負面影響。

目前實現(xiàn)垃圾短信的監(jiān)控和過濾主要有兩種機制，即內(nèi)容關(guān)鍵字過濾機制和號碼黑名單機制[2]。其中，內(nèi)容關(guān)鍵字過濾機制中的關(guān)鍵字內(nèi)容主要依靠人工添加的方法來實現(xiàn)，尚無法實現(xiàn)自動添加；而號碼黑名單的生成可分為手工添加、實時自動生成和準實時自動生成等方法實現(xiàn)。但這兩種機制的缺點是實現(xiàn)方法呆板且防范數(shù)量有限，由于垃圾短信的形式在不斷演化，垃圾短信的發(fā)送特征和內(nèi)容也在不斷變化，為適應(yīng)這種變化，必須研發(fā)新的垃圾短信自適應(yīng)過濾系統(tǒng)，以提高系統(tǒng)的智能化水平。本文設(shè)計并實現(xiàn)了一個基于樸素貝葉斯的自適應(yīng)垃圾短信過濾系統(tǒng)，將貝葉斯分類和中文分詞技術(shù)引入垃圾短信過濾中，并將分析結(jié)果及時反饋給在線垃圾短信過濾系統(tǒng)，使系統(tǒng)具有更好的自適應(yīng)性和較高的智能化水平。

2 樸素貝葉斯分類算法

目前著名的文本分類方法有Bayes、LLSF、SVM、KNN、決策樹等[3]。貝葉斯(Bayes)分類方法是一種最常用的有指導(dǎo)的方法，以貝葉斯定理為理論基礎(chǔ)，是一種在已知先驗概率與條件概率的情況下的模式識別方法。貝葉斯分類器分兩種：一種是樸素貝葉斯分類器，它假設(shè)一個屬性對給定類的影響?yīng)毩⒂谄渌麑傩裕刺卣鳘毩⑿约僭O(shè)。當假設(shè)成立時，與其他分類算法相比，樸素貝葉斯分類器是最精確的。但是，文本屬性之間的依賴關(guān)系是可能存在的。另一種是貝葉斯網(wǎng)絡(luò)分類器。可以考慮屬性之間的依賴程度，其計算復(fù)雜度比樸素貝葉斯高得多，更能反映真實文本的情況。貝葉斯網(wǎng)絡(luò)分類器實現(xiàn)十分復(fù)雜，目前還停留在理論的研究階段。因此本系統(tǒng)采用樸素貝葉斯分類算法解決短信內(nèi)容檢測、分類問題。

樸素貝葉斯分類器假設(shè)特征對于給定類的影響?yīng)毩⒂谄渌卣鳎刺卣鳘毩⑿约僭O(shè)。對文本分類來說，它假設(shè)各個單詞Wi和Wj之間兩兩獨立，其原理見圖1。

設(shè)訓(xùn)練樣本集分為k類（正常短信和垃圾短信），記為C={C1，C2 ，…，Ck}，則每個類Ci的先驗概率為P(Ci)， i=1，2，…，k，其值為Ci類的樣本數(shù)除以訓(xùn)練集總樣本數(shù)n。對于新樣本d，其屬于Ci類的條件概率是P(d|Ci)。根據(jù)貝葉斯定理，Ci類的后驗概率為P(Ci|d)：

P(d)對于所有類均為常數(shù)，可以忽略，則式(1)簡化為

P(Ci| d)∝P(d | Ci)P(Ci)（2）

為避免P(Ci)等于0，采用拉普阿斯概率估計：

式中：|C|為訓(xùn)練集中類的數(shù)目，|DCi|為訓(xùn)練集中屬于類Ci的文檔數(shù)，|DC|為訓(xùn)練集包含的總文檔數(shù)。

在特殊情況下，訓(xùn)練樣本集中各類樣本數(shù)相等，此時分類的先驗概率相等，式(2)可以簡化：

P(Ci| d)∝P(d | Ci)（4）

樸素貝葉斯分類器將未知樣本歸于類的依據(jù)，如下：

P(Ci| d) =arg max{P(Cj| d)P(Cj)}，j =1，2，…，k。（5）

文檔d由其包含的特征詞表示，即d=(w1，…，wj，…，wm)，m是d的特征詞個數(shù)|d|，wj是第j個特征詞，由特征獨立性假設(shè)，則得

式中：P(wj|Ci)表示分類器預(yù)測單詞wj在類Ci的文檔中發(fā)生的概率。因此式(2)可轉(zhuǎn)換為

為避免式(7)中P(wj|Ci)等于0，可以采用拉普拉斯概率估計。有兩種方法計算P(wj|Ci)，即文檔型計算公式和詞頻型計算公式。

1)文檔型：不考慮單詞在文檔中的出現(xiàn)頻次，僅考慮單詞在文檔中是否出現(xiàn)，0表示未出現(xiàn)，1表示出現(xiàn)，依式(8)計算：

式中：N(doc(wj)|Ci)為Ci類文本中出現(xiàn)特征wj的文本數(shù)。

2)詞頻型：考慮單詞在文檔中出現(xiàn)的頻次，依式(9)計算：

式中：|V|表示特征詞表中總單詞數(shù)，TF(wj，Ci)表示單詞wj在類Ci的所有文檔中出現(xiàn)的頻次之和。

3 中文分詞算法

決定任何一條短信內(nèi)容的關(guān)鍵是短信中所含的實意詞，如果能夠準確地把能表達短信內(nèi)容的實意詞提取出來，那么就可以基本準確地把握短信的特征，并根據(jù)這些特征來判斷這條短信是否屬于垃圾短信。然而，對于一條正常的短信，我們很少用諸如 “*”“￥”“$”等特殊符號，但這些特殊符號往往正是垃圾短信的共同特征。垃圾短信用這些符號一是為了引起收件人的注意，二是為了躲避基于規(guī)則的過濾算法的過濾。針對這種情況，在中文分詞過程中我們首先對新收到的短信內(nèi)容進行特殊字符的過濾，然后再對過濾后的短信內(nèi)容進行分詞，從而最終提取短信中的關(guān)鍵詞。

目前流行的中文分詞法有：最大匹配法(MM法)、逆向最大匹配法(RMM、OMM、IMM)、逐詞匹配法、部件詞典法、詞頻統(tǒng)計法、設(shè)立標志法、并行分詞法、詞庫劃分和聯(lián)想匹配法等[4]。在本系統(tǒng)中我們使用雙向最大匹配分詞法對短信內(nèi)容進行分詞，它的優(yōu)點是高糾錯率和高歧義分析能力。雙向最大匹配分詞法的基本方法是將正向最大匹配法的結(jié)果和逆向最大匹配法的結(jié)果進行比較，一致的切分結(jié)果認為是正確的，不一致的切分結(jié)果則采用上下文相關(guān)信息選取一種分詞方法。

基本流程如下：

1)讀入文本數(shù)據(jù)作為匹配算法的詞典；（本系統(tǒng)采用新華字典1995年版）

2)對輸入的句子做正向最大匹配分詞，切分好的句子為MMSentence；

3)對輸入的句子做逆向最大匹配分詞，切分好的句子為RMMSentence；

4)比較MMSentence和RMMSentence，一致則輸出正確的切分，不一致則采用上下文相關(guān)信息選取一種分詞方法。

如果S′代表一個中文文本中的一個字符串，設(shè)詞表中最大詞長為MaxWordLength，則正向最大匹配算法可描述如下：

1)待切分的漢字串S，已切分的漢字串S′(S′初始為空串);

2)如果S為空串，轉(zhuǎn)(6);

3)從S左邊復(fù)制一個子串w作為候選詞，w盡可能長，但長度不超過MaxWordLength(詞表中的最大詞長);

4)如果在詞表中能找到w，或者w的長度為2，那么將w和一個詞界標記一起加到S′右邊，并且從S左邊去掉w，轉(zhuǎn)(2);

5)去掉w中最后一個漢字，轉(zhuǎn)(4);

6)結(jié)束，輸出S′。

逆向最大匹配法的具體方法與正向最大匹配法類似，只是取子串w是在句末進行，每次匹配不成功時，去掉漢字串前面的一個字。

4系統(tǒng)設(shè)計

本文系統(tǒng)的基本思路是，實時提取短信的相關(guān)信息及內(nèi)容，并將其反饋給在線過濾系統(tǒng)，通過黑白名單及非法關(guān)鍵字預(yù)處理、短信內(nèi)容中文分詞以及貝葉斯分類統(tǒng)計，以達到準確和智能過濾垃圾短信的目的。在線過濾系統(tǒng)包括三個模塊：短信預(yù)處理模塊、自動分詞模塊和貝葉斯分類模塊。系統(tǒng)架構(gòu)如圖2所示。

在線過濾系統(tǒng)的處理流程如下：1）實時接收從短消息中心發(fā)送的短消息信息并放入短信緩沖區(qū)內(nèi)保存。由于短消息過濾系統(tǒng)處理過程與短消息接收存在時差，實時短消息過濾會產(chǎn)生擁塞，緩沖區(qū)的使用可以保證短消息的及時接受以及避免擁塞現(xiàn)象的出現(xiàn)。2)短信預(yù)處理模塊，在該模塊中會存放預(yù)先定義的好的手機黑白名單以及非法關(guān)鍵字，這些黑白名單和關(guān)鍵字都是人為手工添加，當短消息的發(fā)送方或接受方的手機號碼存在于手機黑名單中，或者當短消息含有預(yù)定義的非法關(guān)鍵字時，該短消息將被定義為垃圾短消息，并被放入垃圾短信數(shù)據(jù)庫中。3）中文分詞模塊，其主要任務(wù)是將短消息內(nèi)容進行中英文分詞。該模塊首先剔除短消息中與內(nèi)容無關(guān)的特殊字符，例如：“本*公*司*代*售*各*種*發(fā)*票*……”中的“*”符號。再按雙向最大分詞法將內(nèi)容轉(zhuǎn)化為包含基本語義單位組成的關(guān)鍵字表列。4)貝葉斯分類模塊，利用貝葉斯將統(tǒng)計出的正常短信和垃圾短信特征概率，并將關(guān)鍵詞的分類，詞頻高的反饋更新在線過濾系統(tǒng)關(guān)鍵詞庫，系統(tǒng)設(shè)置一個閾值，綜合評價函數(shù)根據(jù)計算得到垃圾短信特征的值，跟閾值比較，如果大于這個閾值說明是正常短信，反之小于則是垃圾短信。

5 結(jié)論

本文在傳統(tǒng)垃圾短信過濾系統(tǒng)的基礎(chǔ)上引入了中文分詞算法和樸素貝葉斯算法。傳統(tǒng)垃圾短信系統(tǒng)的內(nèi)容過濾需要人工設(shè)置，不僅無法適應(yīng)短信內(nèi)容的變化和短信形式的多樣，而且誤判率高，維護困難。新系統(tǒng)的內(nèi)容過濾采用了樸素貝葉斯算法，具有自學習和更新能力，因此它能克服傳統(tǒng)過濾系統(tǒng)容易過時的問題，降低了短信誤判的風險。通過實驗證明，該短信過濾系統(tǒng)具有較高的準確率。

參考文獻：

[1] 黃日生.淺議垃圾短信之規(guī)制[J].通信與信息技術(shù)，2008，1(10):34-36.

[2] 潘文鋒.基于內(nèi)容的垃圾郵件過濾研究[D].北京:中國科學院計算技術(shù)研究所，2004.

[3] 李靜梅，孫麗華，張巧榮，等.一種文本處理中的樸素貝葉斯分類器[J].哈爾濱工程大學學報，2003，2(1):71-74.

[4] 黃昌寧.中文信息處理中的分詞問題[J].語言文字應(yīng)用，1997，2(1):72-78.