文章目錄

• • 1. 基于黑名單過(guò)濾
  • 2. 基于規(guī)則過(guò)濾
  • 3. 基于概率統(tǒng)計(jì)過(guò)濾
  • 4. 總結(jié)

上一節(jié)我們講到，如何用位圖、布隆過(guò)濾器，來(lái) 過(guò)濾重復(fù)數(shù)據(jù)。今天，我們?cè)僦v一個(gè)跟過(guò)濾相關(guān)的問(wèn)題，如何過(guò)濾垃圾短信？

1. 基于黑名單過(guò)濾

可以維護(hù)一個(gè)騷擾電話號(hào)碼和垃圾短信發(fā)送號(hào)碼的黑名單。

• 黑名單的搜集，有很多途徑，比如，公開(kāi)的網(wǎng)站下載，用戶自主標(biāo)記。標(biāo)記個(gè)數(shù)超過(guò)一定閾值的號(hào)碼，我們就可以定義為騷擾電話，并將它加入到我們的黑名單中。
• 如果黑名單中的電話號(hào)碼不多的話，我們可以使用散列表、二叉樹(shù)等動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)，對(duì)內(nèi)存的消耗并不會(huì)很大。如果我們把每個(gè)號(hào)碼看作一個(gè)字符串，并且假設(shè)平均長(zhǎng)度是16個(gè)字節(jié)，那存儲(chǔ)50萬(wàn)個(gè)電話號(hào)碼，大約需要10MB的內(nèi)存空間。對(duì)于手機(jī)這樣的內(nèi)存有限的設(shè)備來(lái)說(shuō)，這點(diǎn)內(nèi)存的消耗也是可以接受的。
• 黑名單中的電話號(hào)碼很多呢？比如有500萬(wàn)個(gè)。這個(gè)時(shí)候，如果再用散列表存儲(chǔ)，就需要大約100MB的存儲(chǔ)空間。為了實(shí)現(xiàn)一個(gè)攔截功能，耗費(fèi)如此多的手機(jī)內(nèi)存，顯然有點(diǎn)不合理。
• 布隆過(guò)濾器最大的特點(diǎn)就是比較省存儲(chǔ)空間，所以，用它來(lái)解決這個(gè)問(wèn)題再合適不過(guò)。如果我們要存儲(chǔ)500萬(wàn)個(gè)手機(jī)號(hào)碼，我們把位圖大小設(shè)置為10倍數(shù)據(jù)大小，也就是5000萬(wàn)，那也只需要使用5000萬(wàn)個(gè)二進(jìn)制位（5000萬(wàn)bits），換算成字節(jié)，也就是不到7MB的存儲(chǔ)空間。比起散列表的解決方案，內(nèi)存的消耗減少了很多。
• 時(shí)間換空間，把黑名單存儲(chǔ)在服務(wù)器端上，把過(guò)濾和攔截的核心工作，交給服務(wù)器端來(lái)做。手機(jī)端只負(fù)責(zé)將要檢查的號(hào)碼發(fā)送給服務(wù)器端，服務(wù)器端通過(guò)查黑名單，判斷這個(gè)號(hào)碼是否應(yīng)該被攔截，并將結(jié)果返回給手機(jī)端。這個(gè)解決思路完全不占用手機(jī)內(nèi)存。不過(guò)網(wǎng)絡(luò)通信是比較慢的，所以，網(wǎng)絡(luò)延遲就會(huì)導(dǎo)致處理速度降低。而且必須聯(lián)網(wǎng)。
• 布隆過(guò)濾器會(huì)有判錯(cuò)的概率！如果它把一個(gè)重要的電話或短信，當(dāng)成垃圾攔截了，對(duì)于用戶來(lái)說(shuō)，這是無(wú)法接受的。這是一個(gè)很大的問(wèn)題。

2. 基于規(guī)則過(guò)濾

如果某個(gè)垃圾短信發(fā)送者的號(hào)碼并不在黑名單中，那這種方法就沒(méi)辦法攔截了。所以，基于黑名單的過(guò)濾，還不夠完善，再繼續(xù)看基于規(guī)則的過(guò)濾。

• 通過(guò)短信的內(nèi)容，來(lái)判斷是垃圾短信。預(yù)先設(shè)定一些規(guī)則，如果短信符合這些規(guī)則，就判定它是垃圾短信。規(guī)則可以有很多，比如：

短信中包含特殊單詞（或詞語(yǔ)），比如一些非法、淫穢、反動(dòng)詞語(yǔ)等；

發(fā)送號(hào)碼是群發(fā)號(hào)碼，非正常的手機(jī)號(hào)碼，比如+60389585；

短信中包含回?fù)艿穆?lián)系方式，比如手機(jī)號(hào)碼、微信、QQ、網(wǎng)頁(yè)鏈接等，因?yàn)槿喊l(fā)短信的號(hào)碼一般都是無(wú)法回?fù)艿?#xff1b;

短信格式花哨、內(nèi)容很長(zhǎng)，比如包含各種表情、圖片、網(wǎng)頁(yè)鏈接等；

符合已知垃圾短信的模板。與模板匹配，就可以判定為垃圾短信。

可以綜合多條規(guī)則進(jìn)行判斷。比如，滿足2條以上才會(huì)被判定為垃圾短信；
或者每條規(guī)則對(duì)應(yīng)一個(gè)不同的得分，某條短信的總得分超過(guò)某個(gè)閩值，才會(huì)被判定為垃圾短信。

以上規(guī)則還有很多細(xì)節(jié)需要處理。比如，第1條規(guī)則中，我們?cè)撊绾味x特殊單詞；第2條規(guī)則中，我們?cè)撊绾味x什么樣的號(hào)碼是群發(fā)號(hào)碼等等。

這里只講一下，如何定義特殊單詞？
可以基于概率統(tǒng)計(jì)的方法，借助計(jì)算機(jī)強(qiáng)大的計(jì)算能力，找出哪些單詞最常出現(xiàn)在垃圾短信中，將這些最常出現(xiàn)的單詞，作為特殊單詞，用來(lái)過(guò)濾短信。
這種方法的前提是，有大量的樣本數(shù)據(jù)，也就是說(shuō)，要有大量的短信（比如1000萬(wàn)條短信），并且每條短信都做好了標(biāo)記，它是垃圾短信還是非垃圾短信。

對(duì)這1000萬(wàn)條短信，進(jìn)行分詞處理（借助中文或者英文分詞算法），去掉“的、和、是”等沒(méi)有意義的停用詞（Stop words），得到n個(gè)不同的單詞。針對(duì)每個(gè)單詞，統(tǒng)計(jì)有多少個(gè)垃圾短信出現(xiàn)了這個(gè)單詞，有多少個(gè)非垃圾短信會(huì)出現(xiàn)這個(gè)單詞，求出每個(gè)單詞出現(xiàn)在垃圾短信中的概率，以及出現(xiàn)在非垃圾短信中的概率。如果某個(gè)單詞出現(xiàn)在垃圾短信中的概率，遠(yuǎn)大于出現(xiàn)在非垃圾短信中的概率，就把這個(gè)單詞作為特殊單詞。

3. 基于概率統(tǒng)計(jì)過(guò)濾

基于規(guī)則的過(guò)濾器，看起來(lái)很直觀，也很好理解，但是它也有一定的局限性。一方面，這些規(guī)則受人的思維方式局限，規(guī)則未免太過(guò)簡(jiǎn)單；另一方面，垃圾短信發(fā)送者可能會(huì)針對(duì)規(guī)則，精心設(shè)計(jì)短信，繞過(guò)這些規(guī)則的攔截。對(duì)此，我們?cè)賮?lái)看一種更加高級(jí)的過(guò)濾方式，基于概率統(tǒng)計(jì)的過(guò)濾方式。

基于概率統(tǒng)計(jì)的過(guò)濾，基礎(chǔ)理論是基于樸素貝葉斯算法。先通過(guò)一個(gè)非常簡(jiǎn)單的例子來(lái)看下，什么是樸素貝葉斯算法？
假設(shè)事件A是“小明不去上學(xué)”，事件B是“下雨了”。我們現(xiàn)在統(tǒng)計(jì)了一下過(guò)去10天的下雨情況和小明上學(xué)的情況，作為樣本數(shù)據(jù)。

我們來(lái)分析一下，這組樣本有什么規(guī)律。在這10天中，有4天下雨，所以下雨的概率P（B）=4/10。10天中有3天，小明沒(méi)有去上學(xué)，所以小明不去上學(xué)的概率P（A）=3/10。在4個(gè)下雨天中，小明有2天沒(méi)去上學(xué)，所以下雨天不去上學(xué)的概率P（A|B）=2/4。在小明沒(méi)有去上學(xué)的3天中，有2天下雨了，所以小明因?yàn)橄掠甓簧蠈W(xué)的概率是P（BIA）=2/3。實(shí)際上，這4個(gè)概率值之間，有一定的關(guān)系，這個(gè)關(guān)系就是樸素貝葉斯算法，我們用公式表示出來(lái)，就是下面這個(gè)樣子。

我們需要把短信抽象成一組計(jì)算機(jī)可以理解并且方便計(jì)算的特征項(xiàng)，用這一組特征項(xiàng)代替短信本身，來(lái)做垃圾短信過(guò)濾。

可以通過(guò)分詞算法，把一個(gè)短信分割成n個(gè)單詞。這n個(gè)單詞就是一組特征項(xiàng)，全權(quán)代表這個(gè)短信。因此，判定一個(gè)短信是否是垃圾短信，就變成了，判定同時(shí)包含這幾個(gè)單詞的短信是否是垃圾短信。
不過(guò)，這里并不像基于規(guī)則的過(guò)濾器那樣，非黑即白。我們使用概率，來(lái)表征一個(gè)短信是垃圾短信的可信程度。

盡管有大量的短信樣本，但是我們沒(méi)法通過(guò)樣本數(shù)據(jù)統(tǒng)計(jì)得到這個(gè)概率。你可能會(huì)說(shuō)，我只需要統(tǒng)計(jì)同時(shí)包含W₁，W₂，W₃，……W_n 這n個(gè)單詞的短信有多少個(gè)（我們假設(shè)有x個(gè)），然后看這里面屬于垃圾短信的有幾個(gè)（假設(shè)y個(gè)），那包含W₁，W₂，W₃，……W_n 這n個(gè)單詞的短信是垃圾短信的概率就是y/x。

But，實(shí)際情況，樣本中不會(huì)有太多同時(shí)包含W₁，W₂，W₃，……W_n 的短信的，甚至根本不存在這樣的短信。沒(méi)有樣本，也就無(wú)法計(jì)算概率。

這個(gè)時(shí)候，樸素貝葉斯公式就可以派上用場(chǎng)了。通過(guò)樸素貝葉斯公式，將這個(gè)概率的求解，分解為其他三個(gè)概率的求解。如下。那轉(zhuǎn)化之后的三個(gè)概率是否可以通過(guò)樣本統(tǒng)計(jì)得到呢？

P（W₁，W₂，W₃，……W_n 同時(shí)出現(xiàn)在一條短信中 | 短信是垃圾短信）這個(gè)概率照樣無(wú)法通過(guò)樣本來(lái)統(tǒng)計(jì)得到。但是我們可以基于下面這條著名的概率規(guī)則來(lái)計(jì)算。
獨(dú)立事件發(fā)生的概率計(jì)算公式：P（AB）=P（A）X P（B）
事件A和事件B是獨(dú)立事件，兩者的發(fā)生沒(méi)有相關(guān)性，那兩個(gè)同時(shí)發(fā)生的概率 P（A*B）就等于 P（A）*P（B）。
基于這條獨(dú)立事件發(fā)生概率的計(jì)算公式，把P（W₁，W₂，W₃，……W_n 同時(shí)出現(xiàn)在一條短信中 | 短信是垃圾短信）分解為下面這個(gè)公式：

其中，P（W_i 出現(xiàn)在短信中 | 短信是垃圾短信）表示垃圾短信中包含W_i 這個(gè)單詞的概率有多大。

P（短信是垃圾短信）把樣本中垃圾短信的個(gè)數(shù)除以總樣本短信個(gè)數(shù)。

不過(guò)，P（W₁，W₂，W₃，……W_n 同時(shí)出現(xiàn)在一條短信中）這個(gè)概率還是不好通過(guò)樣本統(tǒng)計(jì)得到，原因前面說(shuō)過(guò)了，樣本空間有限。不過(guò)，我們沒(méi)必要非得計(jì)算這一部分的概率值。為什么這么說(shuō)呢？

實(shí)際上，我們可以分別計(jì)算同時(shí)包含W₁，W₂，W₃，……W_n 這n個(gè)單詞的短信，是垃圾短信和非垃圾短信的概率。假設(shè)它們分別是 P1 和 P2。我們可以通過(guò)對(duì)比 P1 和 P2 值的大小，來(lái)判斷一條短信是否是垃圾短信。如果 P1 是 P2 的很多倍（比如10倍），我們確信這條短信是垃圾短信。

在求解 P1 和 P2 倍數(shù)（P1/P2）的時(shí)候，我們也就不需要這個(gè)值。

4. 總結(jié)

今天，講了基于黑名單、規(guī)則、概率統(tǒng)計(jì)三種垃圾短信的過(guò)濾方法，這三種方法，還可以應(yīng)用到很多類似的過(guò)濾、攔截的領(lǐng)域，比如垃圾郵件的過(guò)濾等等。

在講黑名單過(guò)濾的時(shí)候，我講到布隆過(guò)濾器可能會(huì)存在誤判情況，可能會(huì)導(dǎo)致用戶投訴。

實(shí)際上，我們可以結(jié)合三種不同的過(guò)濾方式的結(jié)果，對(duì)同一個(gè)短信處理，如果三者都表明這個(gè)短信是垃圾短信，才把它當(dāng)作垃圾短信攔截過(guò)濾，這樣就會(huì)更精準(zhǔn)。

在實(shí)際的工程中，還需要結(jié)合具體的場(chǎng)景，以及大量的實(shí)驗(yàn)，不斷去調(diào)整策略，權(quán)衡垃圾短信判定的準(zhǔn)確率（是否會(huì)把不是垃圾的短信錯(cuò)判為垃圾短信）和召回率（是否能把所有的垃圾短信都找到），來(lái)實(shí)現(xiàn)我們的需求。

總結(jié)

以上是生活随笔為你收集整理的朴素贝叶斯算法--过滤垃圾短信的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。