基于改進(jìn)貝葉斯算法的垃圾短信過濾研究＊

金小梅，毛本清

（衢州學(xué)院，浙江 衢州 324000）

現(xiàn)實(shí)生活中，我們手機(jī)用戶經(jīng)常會(huì)接到諸如中獎(jiǎng)、返稅等詐騙短信，嚴(yán)重影響了我們的正常生活，有的已經(jīng)對(duì)部分用戶造成不小的經(jīng)濟(jì)損失。手機(jī)垃圾短信現(xiàn)象不僅在我國(guó)大量存在，在歐美等發(fā)達(dá)國(guó)家也廣泛存在，已成為世界性的問題。因此如何從已有的手機(jī)短信中挖掘出垃圾短信的特點(diǎn)，從而對(duì)短信進(jìn)行分類，成為相關(guān)領(lǐng)域?qū)＜业难芯恐攸c(diǎn)。

現(xiàn)有手機(jī)垃圾短信攔截技術(shù)主要分為以下兩類：①手機(jī)號(hào)碼的黑白名單技術(shù)[1]。對(duì)未備案的短時(shí)間內(nèi)發(fā)送大量短信的號(hào)碼添到黑名單列表，實(shí)現(xiàn)垃圾短信的攔截。②文本內(nèi)容過濾技術(shù)。鄰近分類算法（k-Nearest Neighbor，簡(jiǎn)稱KNN算法）、決策樹與樸素貝葉斯算法是其中的代表，主要包括三個(gè)方面，分別是基于文本內(nèi)容過濾、基于規(guī)則過濾與基于關(guān)鍵字過濾。

樸素貝葉斯算法是文本文檔分類算法中較為有效的算法，其特點(diǎn)是速度快、效率高、耗費(fèi)少、應(yīng)用廣泛，由于穩(wěn)定性較好、實(shí)現(xiàn)簡(jiǎn)單，且易于開發(fā)維護(hù)，因此能夠滿足手機(jī)短信過濾要求。

1 樸素貝葉斯算法

樸素貝葉斯算法思想核心是求解向量X=（x1，x2，…，xm），歸屬C=（C1，C2，…，Ck）的概率值p（Ci∣X），最大的概率值所對(duì)應(yīng)的Cj即為X 所屬類別。過程如下[2]：

設(shè)A 代表訓(xùn)練數(shù)據(jù)集A1，A2，…，Am；k 個(gè)類：C1，C2，…，Ck；用m 維特征向量來表示數(shù)據(jù)樣本x 各屬性值，即X=（x1，x2，…，xm），其中xi∈Ai（1≤i≤m）。

計(jì)算數(shù)據(jù)集各類中各屬性的條件概率，即p（xi∣C1），p（xi∣C2），…，p（xi∣Ck），（1≤i≤m）。

根據(jù)條件概率和樸素貝葉斯算法的假定，計(jì)算未知樣本在各類中的后驗(yàn)概率：

后驗(yàn)概率的最大值所對(duì)應(yīng)的類即為該未知樣本的分類：

由以上步驟可知，樸素貝葉斯分類模型的實(shí)現(xiàn)，主要分為4 個(gè)部分：①假定X=（x1，x2，…，xm）為一個(gè)待處理的分類文本，xi為X 的第i 個(gè)特征屬性向量；②類集合C（C1，C2，…，Ck）為預(yù)先類集合；③計(jì)算p（C1∣X），p（C2∣X），…，p（Ck∣X）；④如果存在p（Cj∣X）=max｛p（C1∣X），p（C2∣X），…，p（Ck∣X｝，則X∈Cj.

因此，我們可以根據(jù)訓(xùn)練集來計(jì)算某已知文本類的先驗(yàn)概率，再計(jì)算其后驗(yàn)概率，對(duì)后續(xù)新的文本類進(jìn)行分析預(yù)測(cè)，在已知的分類概率的條件下，由此可得待處理文本屬于某一類概率值，最后取其中的最大值，將待處理文本歸類到最大值的那類中。需要說明的是，類別之間是相互獨(dú)立的，模型具有收斂性。樸素貝葉斯算法閾值分類流程如圖1 所示。

貝葉斯算法雖然速度較快、正確率高，但存在誤判的情況[3]。在樸素貝葉斯公式中，如果，待定樣本X 即歸為Ci類，反之為Cj類，但如果樣本比例不均衡，容易造成誤判，為避免誤判造成的損失，我們采取自學(xué)習(xí)方式進(jìn)行，選擇合適閾值提高模型準(zhǔn)確性。閾值α的具體選擇依賴于其在訓(xùn)練數(shù)據(jù)集上的表現(xiàn)，當(dāng)時(shí)，把待定樣本歸為Ci類，如果本屬Ci類的樣本，結(jié)果錯(cuò)判給Cj類的較多，則我們可以取閾值；如果本屬Cj類的樣本，結(jié)果錯(cuò)判給Ci類的較多，則取閾值，這樣能顯著提高模型的準(zhǔn)確率[4]。

圖1 樸素貝葉斯算法閾值分類流程圖

2 短信短語特征項(xiàng)提取

垃圾短信特征項(xiàng)的提取，我們以基本短語為單位的分詞方法。結(jié)合基本短語構(gòu)成算法，并根據(jù)基本短語的定義實(shí)現(xiàn)由詞到基本短語的轉(zhuǎn)換?；径陶Z模式特征項(xiàng)提取應(yīng)當(dāng)遵循的以下兩個(gè)規(guī)則[5]。

2.1 一般名詞短語結(jié)構(gòu)模型的界定

短語結(jié)構(gòu)模型的界定，是一種確定不同類型短語的邊界位置的過程，是以單詞為構(gòu)件形成短語的主要步驟。作為能代表文本主要特征的一般名詞短語和動(dòng)詞短語，其界定規(guī)則對(duì)降低特征項(xiàng)空間的維度及提高準(zhǔn)確性來說非常重要。趙軍、黃昌寧等人根據(jù)詞語潛在的依存關(guān)系，分析了漢語簡(jiǎn)單非嵌套式名詞短語（baseNP）的結(jié)構(gòu)，并給出了相關(guān)定義：①baseNP＋baseNP，如“公路里程”“高校教師”等；②baseNP＋名詞｜名動(dòng)詞，“公路建設(shè)”“高校發(fā)展”等；③限定性定語＋baseNP，如“雙核”“三好學(xué)生”等；④限定性定語＋名詞｜名動(dòng)詞，如“中國(guó)信息公路”“第三世界國(guó)家”。

2.2 一般動(dòng)詞短語結(jié)構(gòu)模型的界定

一般動(dòng)詞短語結(jié)構(gòu)模型形式主要有：①述補(bǔ)結(jié)構(gòu)，如壓馬路、走路等；②述賓結(jié)構(gòu)，如修改論文、選角等；③狀中結(jié)構(gòu)，如立刻動(dòng)手、到黃山游玩等；④連動(dòng)結(jié)構(gòu)，如去洗手、開動(dòng)等；⑤聯(lián)合結(jié)構(gòu)，如邊走邊唱、甲和乙等；⑥其他動(dòng)詞短語，如“著了過”屬性的動(dòng)詞，睡了、坐著、想了想、聽說過等。短信文本短語特征項(xiàng)提取是先把第一個(gè)分詞詞語對(duì)后面的詞語分別進(jìn)行組合，通過過程測(cè)試檢驗(yàn)則認(rèn)為合格，如果不符則將該短信所有短語列為垃圾短信短語（詞語）向量集，則取下一個(gè)分詞詞語重復(fù)上述過程，直到最后一個(gè)詞語完成組合測(cè)試為止，垃圾短信過濾處理流程如圖2 所示。

利用統(tǒng)計(jì)思想，基于互信息方法劃分分詞短語的邊界?；バ畔⑹强疾煲粋€(gè)消息中兩信號(hào)間的相互依賴度的度量，也是分詞詞語間結(jié)合的緊密程度的度量，通過短信文本相鄰詞性標(biāo)記的互信息值大小來進(jìn)行判斷，其極小值的位置為短語的邊界?；バ畔⒎椒ǖ挠?jì)算如下式所示：

圖2 垃圾短信過濾處理流程示意圖

利用互信息值算法如下。

輸入：訓(xùn)練樣本向量集x

輸出：由詞語和短語組成新的向量空間x_temp

Begin

fid=fopen(sFileName，’x’);

if(fid!={})

for each fid into x do

while x_i!=x_j

z_ij=sqrt[(x_i)^2+(x_j)^2]

case min_i=inf，nbor_i=i

case min_i=z_ij； nbor_i=j

end

while x_i!=x_temp

flag(i，x_temp)=-1

break ；end

while x_i=x_temp

flag(i，temp)=1

delet(x_i)

break ；end

for each x_i in x do

x_temp=nbor_i

flag(i，x_temp)=-1

xdelet(x_temp)

break ；end

if delet(x_i)

output x

else output x_temp

end

基于短語貝葉斯垃圾短信過濾方法的主要改進(jìn)在于利用互信息計(jì)算對(duì)短信文本特征項(xiàng)提取算法。該算法特征項(xiàng)提取以短語為單位，降低樣本空間規(guī)模，在此基礎(chǔ)上訓(xùn)練樣本集，生成分類模型，實(shí)現(xiàn)文本短信過濾。

3 實(shí)驗(yàn)與結(jié)果

為清晰表達(dá)比較結(jié)果，引入了幾個(gè)參數(shù)，定義如下：

SP 反映垃圾短信過濾系統(tǒng)的可靠性，側(cè)重安全性；SR反映垃圾短信過濾系統(tǒng)的效率，側(cè)重有效性；F 則綜合兩者的指標(biāo)，側(cè)重綜合性能。

我們以短信為例進(jìn)行試驗(yàn)，其中含正常短信1 032 條，手機(jī)攔截短信375 條。以短語為單位得到特征項(xiàng)數(shù)為20 783，其中BaseNP 為13 542，BaseVP 有7 241 個(gè)，而以詞為單位得到特征項(xiàng)數(shù)為173 657.這樣降低樣本空間規(guī)模，縮減計(jì)算量，提高系統(tǒng)效率。

下面測(cè)試在KNN 方法（詞模式下）、改進(jìn)貝葉斯算法（詞模式下）及改進(jìn)貝葉斯算法（短語模式下）3 種不同方式下過濾性能上的表現(xiàn)。SR、SP 與F 值比較結(jié)果如圖3 所示。

圖3 三種方式過濾性能比較結(jié)果

實(shí)驗(yàn)測(cè)試表明，在綜合性能指標(biāo)上，詞模式下KNN 算法與改進(jìn)貝葉斯算法沒有多大差異，但短語模式下的改進(jìn)貝葉斯算法要比前兩者高出近2%；而在SR、SP 數(shù)據(jù)的比較上，詞模式下的貝葉斯算法并沒有較KNN 算法高明，甚至在SR 比較中要低1.56%，短語模式下卻比兩者高出許多，其中SP 達(dá)到了94.51%，可知以短語為單位進(jìn)行特征提取，然后再進(jìn)行分類過濾所得的結(jié)果，更優(yōu)于詞模式下的KNN算法與貝葉斯算法。

短語模式下改進(jìn)貝葉斯算法在查全率、查準(zhǔn)率及綜合指標(biāo)等方面都有一定的提高，但在特征項(xiàng)提取階段還存在諸多人為因素，機(jī)器的認(rèn)別程度還存在較大不足，機(jī)器對(duì)文本短語分類依然有進(jìn)一步改善的可能。