劉秋陽(yáng)+林澤鋒+欒青青

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

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

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

1 概述

1.1 背景介紹

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

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

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

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

1.2 我們的改進(jìn)

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

2 貝葉斯算法

2.1 貝葉斯算法的簡(jiǎn)介

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

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

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

5 算法效率分析

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

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

6.1 系統(tǒng)的組成

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

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

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

6.3 判斷垃圾短信的流程

如圖1所示，

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

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

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

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

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

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

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

6.6 系統(tǒng)測(cè)試與評(píng)估

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

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

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

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

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

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

參考文獻(xiàn)：

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

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