垃圾短信，垃圾郵件和推銷的電話使我們深受其擾，不過也有些手機軟件助手，可以幫助我們垃圾這些垃圾短信和電話，這些軟件的背後的算法是什麽？
像360手機衛士這種APP在手機本地或雲端保存壹份電話的手機黑名單數據，來電的時候手機判斷下就可以決定是否為騷擾電話了，本地存儲，黑名單的數據量如果很大的話，可能會占內存比較大，不過這個可以借鑒以前的布隆過濾器這種數據結構來解決，但是布隆過濾器有誤判的可能，有可能來電非黑名單卻當成黑名單進行處理了，這對於攔截軟件來說是比較嚴重的問題，所以可能是多種方法來結合判斷，或者對於布隆過濾判斷是屬於黑名單的電話，再通過壹次聯網到網上的雲端再判斷壹次是否為真正為黑名單用戶，不過這就需要聯網，還存在延遲的可能；對於布隆過濾器判斷為正常用戶的，則壹定是正常用戶，那麽大部分時間是不需要聯網判斷或結合其他辦法判斷的。
像很多病毒檢測軟件，或IDS或WAF軟件壹樣，垃圾短信和騷擾電話 也可以建立自己的規則庫，通過規則庫進行垃圾短信的判斷，同樣像IDS等軟件存在誤判的情況壹樣，垃圾短信采用規則判斷的話，也存在壹定的誤判性，壹般也要結合其他的判斷規則綜合判斷。
規則有下面幾個：
凡是規則判斷，都存在著檢測死板，不能檢測到不在規則裏面的情況，而且會被有心者特意設計避開規則的垃圾短信等。
直觀地想壹下，垃圾短信，垃圾郵件這些壹般都包含特定的詞語，或者鏈接等，那麽我們反過來統計郵件中特定的詞語的數量，達到壹定標準，我們就判斷為垃圾郵件。
現在對於這種垃圾郵件的判斷問題，壹般都通過機器學習來解決，在機器學習的算法中，做垃圾郵件判斷這個是屬於壹個二分類問題，可以用很多中算法來解決，常用的有決策樹，貝葉斯，SVM，神經網絡等，其中貝葉斯算法是屬於壹個基於統計學的算法，也是本次要介紹的算法。
貝葉斯算法是為了解決“逆序概率”的問題，舉個簡單的例子，比如我們袋子中有10個紅球，8個白球，然後隨機從袋子中拿出壹個球，問是紅球的概率是多少？這是壹個非常簡單的概率問題，結果就是10/(10+8),這種正向概率問題比較好理解。那麽反過來，如果我們只知道袋子中有紅球和白球，但是不知道數量和比例，我們拿了幾次球，通過拿出這些球的顏色是否可以推斷出袋子中兩種球的比例那？
貝葉斯算法中有些根據以前經驗總結出來的概率，稱為先驗概率，可以理解成先前的經驗的概率，所以叫先驗概率，比如清明時節壹般會下雨，下雨的概率大概為70%，這就是通過以前的經驗總結的；
後驗概率， 是事情發生了，推測可能原因，比如小明遲到了，那麽起晚了造成遲到的概率假設為30%，這就是後驗概率。條件概率，就是在壹個事情假設A發生的情況下，另外壹個事情B也發生的概率，記作P(B|A),讀作在A發生的情況下，B發生的概率，比如起晚的情況下，小明遲到的概率。
總結壹句話：先驗概率是經驗總結，後驗概率是由果推因，條件概率是由因推果。
根據條件概率的定義，可以推導出貝葉斯公式，推導過程在百科裏面如下：
說明：
1）P(A|B) = A和B同時發生的概率/B發生的概率，直觀想下，B發生的概率壹定大於A和B同時發生的概率，相除的含義就是在B發生的概率情況下，有多少A也同時發生的概率，也就符合了條件概率的定義。
2）把除法變乘法就得到了合並後的式子，再變化下，就得到了貝葉斯公式。
可能還比較抽象,舉個wiki上的例子：
我們用兩種算法進行計算，壹是自己直觀想，二是用樸素貝葉斯。
假設學校壹***有U個人，直觀想法計算：
P(是女生|穿褲子） = 所有穿褲子的女生數量/所有穿褲子的人數
= U*0.4（女生數量）*0.5（壹半穿褲子） / (U*0.4*0.5 +U*0.6*1)
= 0.2*U /0.8*U = 25%
如果用樸素貝葉斯算法：
P(是女生|穿褲子) = P(穿褲子|是女生) *P(是女生)/P(穿褲子)
= 0.5*0.4/[(0.6*1 +0.4*0.5）/1]
= 0.2 /0.8
= 25%
說明： P(穿褲子） = 穿褲子人數/總人數= U*0.6*1 + U*0.4*0.5/U = 80%
這樣看起來，樸素貝葉斯公式也不是很難。
具體來看下垃圾郵件的分類問題：我們用D表示壹封郵件，D是由很多單詞組成。用f+表示是垃圾郵件，用f-表示是正常郵件，根據貝葉斯公式，問題形式化：
其中P(f+)和P(f-)比較容易得到，算下壹個郵箱裏面有多少個是垃圾郵件，多少個是正常郵件即可，不過最好多找幾個，算下平均值，這就是所謂的先驗概率。
P(D|f+) 表示是垃圾郵件，單詞出現的概率，把D展開成N個單詞就是:
P(d1,d2,d3...dn|f+) 即垃圾郵件中，同時出現這些單詞的概率，這個沒辦法求，假設這些單詞之間是獨立的，沒有什麽關聯關系，那麽P(d1,d2,d3...dn|f+) 就可以擴展為P(d1|f+)* P(d2|f+) P(d3|f+).... P(dn|f+) 這個裏面的獨立假設，就是樸素貝葉斯的樸素來源，因為不是那麽精確，所以叫樸素。計算壹個單詞在垃圾郵件中出現的概率就比較簡單了。
翻譯壹下：
P(垃圾郵件|單詞d1，單詞d2...單詞dn同時出現） =[ P(單詞d1,單詞d2...同時出現|是垃圾郵件）*P(是垃圾郵件)]/P(單詞d1,單詞d2...同時出現在壹封郵件裏面）
根據獨立假設：
P(垃圾郵件|單詞d1，單詞d2...單詞dn同時出現） =[ P(單詞d1出現|是垃圾郵件）*P(單詞d2出現|是垃圾郵件）*P(單詞d3出現|是垃圾郵件）...*P(是垃圾郵件)]/P(單詞d1,單詞d2...同時出現在壹封郵件裏面）
其實我們在判斷是否是垃圾郵件的時候，並壹定要計算出來P(單詞d1,單詞d2...同時出現在壹封郵件裏面），這個也無法精確計算，我們只需要比較垃圾郵件的概率和非垃圾郵件的概率，取大的那壹個就可以了，那麽久只要計算：
P(垃圾郵件|單詞d1，單詞d2...單詞dn同時出現） =[ P(單詞d1出現|是垃圾郵件）*P(單詞d2出現|是垃圾郵件）*P(單詞d3出現|是垃圾郵件）...*P(是垃圾郵件)]
P(正常郵件|單詞d1，單詞d2...單詞dn同時出現） =[ P(單詞d1出現|是正常郵件）*P(單詞d2出現|是正常郵件）*P(單詞d3出現|是正常郵件）...*P(是正常郵件)]
1.找到N封郵件，標記好垃圾郵件和非垃圾郵件。
2.對N封郵件進行去掉停詞部分，然後采用分詞算法做分詞。
3.分別計算每個詞在垃圾郵件中出現的比例，在正常郵件中出現的比例
4.帶入公式算下哪個概率相對大壹些，就屬於哪個分類。
這裏面總結的比較簡單，貝葉斯算法，還有很多沒有說到，我也理解的不夠深刻，先只聊點這種簡單的吧，下壹篇將找個例子實戰下樸素貝葉斯算法。
參考：
1. 數據結構和算法之美：概率統計
2. 數據分析實戰：樸素貝葉斯
3. 平凡而又神奇的貝葉斯方法