垃圾短信，垃圾邮件和推销的电话使我们深受其扰，不过也有些手机软件助手，可以帮助我们垃圾这些垃圾短信和电话，这些软件的背后的算法是什么？
一 黑名单
像360手机卫士这种APP在手机本地或云端保存一份电话的手机黑名单数据，来电的时候手机判断下就可以决定是否为骚扰电话了，本地存储，黑名单的数据量如果很大的话，可能会占内存比较大，不过这个可以借鉴以前的布隆过滤器这种数据结构来解决，但是布隆过滤器有误判的可能，有可能来电非黑名单却当成黑名单进行处理了，这对于拦截软件来说是比较严重的问题，所以可能是多种方法来结合判断，或者对于布隆过滤判断是属于黑名单的电话，再通过一次联网到网上的云端再判断一次是否为真正为黑名单用户，不过这就需要联网，还存在延迟的可能；对于布隆过滤器判断为正常用户的，则一定是正常用户，那么大部分时间是不需要联网判断或结合其他办法判断的。
二 规则判断
像很多病毒检测软件，或IDS或WAF软件一样，垃圾短信和骚扰电话 也可以建立自己的规则库，通过规则库进行垃圾短信的判断，同样像IDS等软件存在误判的情况一样，垃圾短信采用规则判断的话，也存在一定的误判性，一般也要结合其他的判断规则综合判断。
规则有下面几个：
短信中包含特殊词语，比如非法，反动词语。
短信发送的号码是群发号码，非我们正常的手机号码。
短信很长，包含很多图片表情，网页链接等。
电话号码非正常形式，比如+702233等
凡是规则判断，都存在着检测死板，不能检测到不在规则里面的情况，而且会被有心者特意设计避开规则的垃圾短信等。
三 基于统计信息进行垃圾短信判断
直观地想一下，垃圾短信，垃圾邮件这些一般都包含特定的词语，或者链接等，那么我们反过来统计邮件中特定的词语的数量，达到一定标准，我们就判断为垃圾邮件。
现在对于这种垃圾邮件的判断问题，一般都通过机器学习来解决，在机器学习的算法中，做垃圾邮件判断这个是属于一个二分类问题，可以用很多中算法来解决，常用的有决策树，贝叶斯，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上的例子：
一所学校里面有 60% 的男生，40% 的女生。男生总是穿长裤，女生则一半穿长裤一半穿裙子。有了这些信息之后我们可以容易地计算“随机选取一个学生，他（她）穿长裤的概率和穿裙子的概率是多大”，这个就是前面说的“正向概率”的计算。然而，假设你走在校园中，迎面走来一个穿长裤的学生（很不幸的是你高度近似，你只看得见他（她）穿的是否长裤，而无法确定他（她）的性别），你能够推断出他（她）是女生的概率是多大吗？
我们用两种算法进行计算，一是自己直观想，二是用朴素贝叶斯。
假设学校一共有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+|D) = P(D|f+)*P(f+)/P(D)
p(f-|D) = P(D|f-)*P(f-)/P(D)
其中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.平凡而又神奇的贝叶斯方法
