基于樸素貝葉斯算法的垃圾短信智能識別系統(tǒng)

劉秋陽+林澤鋒+欒青青

摘要：在信息化時代，垃圾短信、詐騙短信越來越成為人們?nèi)粘Ｉ钪械睦_。在對垃圾短信的發(fā)展及市面上現(xiàn)有的攔截垃圾短信的軟件進(jìn)行分析后，發(fā)現(xiàn)垃圾短信為了躲避攔截在不斷變化，攔截軟件需要更加智能的去識別這些垃圾短信。為了應(yīng)對不斷變化的垃圾短信，為了解決聯(lián)網(wǎng)舉報、黑白名單等傳統(tǒng)垃圾短信攔截模式觸及不到的盲區(qū)，提出通過機(jī)器學(xué)習(xí)的方式讓垃圾短信的攔截更加具智能化。該文就解決垃圾短信智能識別的問題，主要闡述了基于樸素貝葉斯公式的垃圾智能識別算法，分析了其算法效率，介紹了該算法在安卓平臺上的設(shè)計，并對該系統(tǒng)進(jìn)行了測試和評估。

關(guān)鍵詞：垃圾短信智能識別；機(jī)器學(xué)習(xí)；樸素貝葉斯公式

中圖分類號：TP18 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2016）12-0190-03

1 概述

1.1 背景介紹

科技高速發(fā)展的今天，智能手機(jī)已經(jīng)越來越成為人們?nèi)粘Ｉ钪斜夭豢扇鄙俚囊徊糠至?。騷擾電話和垃圾短信不僅嚴(yán)重干擾了人們的日常生活，甚至對于那些認(rèn)知能力較差的群體，容易使其上當(dāng)受騙，造成精神和財產(chǎn)上的損失。國家立法并不完善，無法做到手機(jī)號碼實名制，預(yù)防垃圾短信的任務(wù)艱巨困難?，F(xiàn)在市面上的垃圾短信攔截軟件普遍具有以下缺點：

1）不支持用戶個性化的識別功能。每臺手機(jī)無法根據(jù)用戶的偏好提供相應(yīng)的攔截服務(wù)；

2）很大程度依賴黑白名單，在白名單聯(lián)系人手機(jī)被盜后無法預(yù)防詐騙短信；

3）收集用戶信息。需要連接網(wǎng)絡(luò)，將用戶的信息上傳至企業(yè)，一定程度上侵害了用戶的隱私權(quán)。

1.2 我們的改進(jìn)

針對以上情況，為了更好識別、過濾垃圾短信，在本文中，我們設(shè)計了一種基于樸素貝葉斯算法的垃圾短信智能識別系統(tǒng)。該系統(tǒng)存儲了大量有利于判別垃圾短信的關(guān)鍵詞，根據(jù)短信內(nèi)容中出現(xiàn)的關(guān)鍵詞進(jìn)行垃圾短信判斷，也可以根據(jù)用戶的反饋進(jìn)行智能學(xué)習(xí)，提供符合用戶需求的服務(wù)。除此之外，在不連接移動蜂窩網(wǎng)絡(luò)的情況下也可正常使用，不會將數(shù)據(jù)上傳至服務(wù)器，保證不對用戶的信息進(jìn)行收集與竊取。

2 貝葉斯算法

2.1 貝葉斯算法的簡介

樸素貝葉斯算法是用于分類的概率算法，在具有大量數(shù)據(jù)的情況下通過概率分析、判定某物是否能歸于某類，具有很高的準(zhǔn)確度。對于攔截垃圾短信這一課題，我們也可以用樸素貝葉斯公式對短信進(jìn)行分類，類別有二：垃圾短信和正常短信，在具備大量關(guān)鍵詞出現(xiàn)概率的條件下我們能對短信進(jìn)行實時分類，實現(xiàn)了對垃圾短信的判定。

2.2 分類器的數(shù)學(xué)模型

根據(jù)測試，MI>2時該特征能起到判別的作用，故此值可作為選擇關(guān)鍵詞的依據(jù)。無論一個關(guān)鍵詞是集中出現(xiàn)在垃圾短信中還是集中出現(xiàn)在正常短信中，該關(guān)鍵詞對區(qū)分垃圾短信與正常短信都產(chǎn)生了貢獻(xiàn)，應(yīng)收納進(jìn)關(guān)鍵詞數(shù)據(jù)庫中。但事實上，垃圾短信數(shù)量與正常短信數(shù)量有很懸殊的差距，正常短信的數(shù)量要遠(yuǎn)大于垃圾短信的數(shù)量，若選取集中出現(xiàn)在正常短信的關(guān)鍵詞，該關(guān)鍵詞的MI值很難大于2。故實際運用中多數(shù)選取集中出現(xiàn)在垃圾短信的關(guān)鍵詞作為特征。

5 算法效率分析

在具備各個關(guān)鍵詞的相關(guān)條件概率和先驗概率的情況下，可以對短信進(jìn)行判斷。先驗概率的計算只需一步即可完成，時間效率是線性的。計算關(guān)于各個關(guān)鍵詞的條件概率是需要進(jìn)行累乘來實現(xiàn)。假設(shè)有N個關(guān)鍵詞，其中包含在短信文本中的關(guān)鍵詞有N個，累乘的時間效率為O（N）。根據(jù)經(jīng)驗，一個短信文本中含有的關(guān)鍵詞數(shù)量遠(yuǎn)不及存儲的關(guān)鍵詞集，N<

6 系統(tǒng)設(shè)計與實現(xiàn)

6.1 系統(tǒng)的組成

該智能識別垃圾短信系統(tǒng)主要包含兩個功能，判斷垃圾短信功能和智能學(xué)習(xí)功能。判斷垃圾短信功能分為下面三個部分：識別短信部分、比較關(guān)鍵詞部分和計算概率部分。學(xué)習(xí)功能由用戶反饋的機(jī)制實現(xiàn)，具體分為：手動添加垃圾短信，手動刪除垃圾短信。

6.2數(shù)據(jù)庫的設(shè)計

除了存儲各個能作為判別特征的關(guān)鍵詞，還應(yīng)該在數(shù)據(jù)庫中存儲該關(guān)鍵詞相應(yīng)的屬性，包括：各個關(guān)鍵詞在垃圾短信中存在的個數(shù)、各個關(guān)鍵詞在正常短信中存在的個數(shù)，這二者幫助系統(tǒng)計算條件概率。但僅是這些還不夠，根據(jù)前文所述，該系統(tǒng)所需要存儲的數(shù)據(jù)還包括統(tǒng)計的所有垃圾短信的個數(shù)和所有正常短信的個數(shù)，這樣一來，系統(tǒng)通過總體數(shù)目的比值求得先驗概率，利于我們進(jìn)行之后的判斷。

6.3 判斷垃圾短信的流程

如圖1所示，

1）識別短信。當(dāng)接到一條短信后系統(tǒng)首先識別該條短信，判斷其是圖片形式的短信還是文字形式的短信。若為圖片，系統(tǒng)采用OCR算法將圖片轉(zhuǎn)化為文字，若為文字則不進(jìn)行轉(zhuǎn)化。

2）統(tǒng)一將短信識別成文字后，將該段文字與手機(jī)中的關(guān)鍵詞數(shù)據(jù)庫中的關(guān)鍵詞逐個進(jìn)行比較。利用KMP算法進(jìn)行對每個關(guān)鍵詞的比較，比較n次（n為數(shù)據(jù)庫中關(guān)鍵詞的個數(shù)），可以找出既存在于該段文字又存在于關(guān)鍵詞數(shù)據(jù)庫的關(guān)鍵詞。從數(shù)據(jù)庫中找到并記錄有關(guān)這些關(guān)鍵詞的概率。

3）利用樸素貝葉斯公式整合這些概率進(jìn)行計算，如2.2所述。若最終算得該短信是垃圾短信的概率較是正常短信的概率大，則判斷該短信為垃圾短信。進(jìn)而，阻止短信接收。

6.4 根據(jù)用戶標(biāo)記智能學(xué)習(xí)功能

用戶對垃圾短信的認(rèn)定一定程度上是個性化的，在系統(tǒng)幫助篩選大部分垃圾短信的同時，還應(yīng)留給用戶一定權(quán)限去更改關(guān)鍵詞判斷時的權(quán)重。在用戶的角度上，該學(xué)習(xí)機(jī)制分為兩個功能，一是將垃圾短信標(biāo)記為正常短信，二是將正常短信判定為垃圾短信。用戶可以獲取垃圾短信列表，把自己認(rèn)定不是垃圾短信的短信進(jìn)行標(biāo)記，此時，通過KMP算法掃描出該條短信具有數(shù)據(jù)庫中哪些關(guān)鍵詞，把這些關(guān)鍵詞在正常短信中存在的個數(shù)加上1，在垃圾短信中存在的個數(shù)減去1。然后垃圾短信的總個數(shù)減去1，正常短信的總個數(shù)加上1；同理，用戶還可以將正常短信判定為垃圾短信，過程與上述相似，只是在數(shù)據(jù)庫中各個數(shù)據(jù)的變化情況與之相反。用戶獲取短信列表后，選擇想標(biāo)記為垃圾短信的短信，事件發(fā)生后用KMP做相似處理，數(shù)據(jù)庫中各個相關(guān)數(shù)據(jù)進(jìn)行相應(yīng)變化。從系統(tǒng)的角度上，用戶的選擇改變了判斷垃圾短信時的先驗概率與條件概率，對最后的結(jié)果產(chǎn)生了影響。

6.5 系統(tǒng)效率分析

時間效率的分析：在判斷垃圾短信功能部分，將該段文字與數(shù)據(jù)庫中關(guān)鍵詞比較所采用的KMP算法效率分析如下：已知兩個長度分別為m和n的字符串之間用KMP算法進(jìn)行匹配，需要O（m+n）[2]。在實際中，文本長度m遠(yuǎn)大于關(guān)鍵詞長度n，故n可以忽略不計，則用一個關(guān)鍵詞去匹配文本需要的時間是O（m），假設(shè)數(shù)據(jù)庫中含有N個關(guān)鍵詞，則通過KMP算法比較得出短信文本中含有的數(shù)據(jù)庫中的關(guān)鍵詞這一步驟需要O（m*N）的時間。計算過程的效率分析即是樸素貝葉斯的算法效率分析，已在2.3論述。在智能學(xué)習(xí)部分，系統(tǒng)同樣需要掃描短信文本比較找出既存在文本中又在數(shù)據(jù)庫中的關(guān)鍵詞。此時，用KMP算法完成該步驟，效率同樣是O（m*N）。相對于識別與計算，整個系統(tǒng)耗時最大的部分在于KMP算法掃描比較文本與數(shù)據(jù)庫中的關(guān)鍵詞，是主要的時間消耗部分。

6.6 系統(tǒng)測試與評估

經(jīng)統(tǒng)計，527條短信中，有500條正常短信，有27條垃圾短信。選取了下列一些關(guān)鍵詞，并統(tǒng)計了它們分別在垃圾短信和正常短信中出現(xiàn)的個數(shù)。根據(jù)2.2特征的選取，以下幾個關(guān)鍵詞可以作為特征存儲到數(shù)據(jù)庫中：樓盤、工行卡號、辦號、情色、大盤、未讀信息、換號、打錢、收購。且這些關(guān)鍵詞都是有助于判斷短信為垃圾短信的關(guān)鍵詞。

經(jīng)測試，若一條短信包含以上關(guān)鍵詞的個數(shù)大于等于2，則系統(tǒng)判定其是垃圾短信（情況A）。在短信只包含其中一個關(guān)鍵詞情況中，包含有些特征效果明顯的關(guān)鍵詞（MI數(shù)值大）的短信能被判定為垃圾短信（情況B）。其他的短信盡管包含有助于判斷為垃圾短信的關(guān)鍵詞，但該關(guān)鍵詞的MI值不足以支持該關(guān)鍵詞單獨存在去直接判斷其為垃圾短信，這部分的短信被系統(tǒng)認(rèn)定為正常短信。

只包含樓盤這一關(guān)鍵詞的短信被系統(tǒng)判定是正常短信。此時用戶若手動標(biāo)記其為垃圾短信，第二條只包含樓盤這一關(guān)鍵詞的短信接收時就會被系統(tǒng)屏蔽掉（情況C）。

只包含收購這一關(guān)鍵詞的短信被系統(tǒng)為正常短信，且用戶需要標(biāo)記兩次，下次發(fā)送同樣短信即可判斷為垃圾短信（情況D）。在本次測試的數(shù)據(jù)中沒有出現(xiàn)需要標(biāo)記三次的情況。

經(jīng)過統(tǒng)計，27條垃圾短信中，有25條短信可以最終被識別為垃圾短信。識別率為92.6%。

在這25條中，情況A占了17條，情況B占了2條，情況C占了3條，情況D占了3條。

參考文獻(xiàn)：

[1] 余芳，姜云飛.一種基于樸素貝葉斯分類的特征選擇方法[J].中山大學(xué)學(xué)報，2004，9（5）：119-120.

[2] 楊戰(zhàn)海.KMP模式匹配算法的研究分析[J].計算機(jī)與數(shù)字工程，2010，38（5）：38-41.