金小梅，毛本清

（衢州學院，浙江 衢州 324000）

現(xiàn)實生活中，我們手機用戶經(jīng)常會接到諸如中獎、返稅等詐騙短信，嚴重影響了我們的正常生活，有的已經(jīng)對部分用戶造成不小的經(jīng)濟損失。手機垃圾短信現(xiàn)象不僅在我國大量存在，在歐美等發(fā)達國家也廣泛存在，已成為世界性的問題。因此如何從已有的手機短信中挖掘出垃圾短信的特點，從而對短信進行分類，成為相關領域專家的研究重點。

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

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

1 樸素貝葉斯算法

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

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

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

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

后驗概率的最大值所對應的類即為該未知樣本的分類：

由以上步驟可知，樸素貝葉斯分類模型的實現(xiàn)，主要分為4 個部分：①假定X=（x1，x2，…，xm）為一個待處理的分類文本，xi為X 的第i 個特征屬性向量；②類集合C（C1，C2，…，Ck）為預先類集合；③計算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ù)新的文本類進行分析預測，在已知的分類概率的條件下，由此可得待處理文本屬于某一類概率值，最后取其中的最大值，將待處理文本歸類到最大值的那類中。需要說明的是，類別之間是相互獨立的，模型具有收斂性。樸素貝葉斯算法閾值分類流程如圖1 所示。

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

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

2 短信短語特征項提取

垃圾短信特征項的提取，我們以基本短語為單位的分詞方法。結合基本短語構成算法，并根據(jù)基本短語的定義實現(xiàn)由詞到基本短語的轉換。基本短語模式特征項提取應當遵循的以下兩個規(guī)則[5]。

2.1 一般名詞短語結構模型的界定

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

2.2 一般動詞短語結構模型的界定

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

利用統(tǒng)計思想，基于互信息方法劃分分詞短語的邊界?；バ畔⑹强疾煲粋€消息中兩信號間的相互依賴度的度量，也是分詞詞語間結合的緊密程度的度量，通過短信文本相鄰詞性標記的互信息值大小來進行判斷，其極小值的位置為短語的邊界?；バ畔⒎椒ǖ挠嬎闳缦率剿荆?/p>

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

利用互信息值算法如下。

輸入：訓練樣本向量集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

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

3 實驗與結果

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

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

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

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

圖3 三種方式過濾性能比較結果

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

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