46.概率统计：如何利用朴素贝叶斯算法过滤垃圾短信

问题&＃xff1a;实现一个简单的垃圾短信过滤功能以及骚扰电话拦截功能&＃xff0c;该用什么样的数据结构和算法实现呢&＃xff1f;

1.算法解析

1.1 基于黑名单的过滤器

• 散列表、二叉树&＃xff0c;比较好内存&＃xff0c;存储有限
• 布隆过滤器&＃xff0c;省内存&＃xff0c;可能会误判
• 黑名单存储服务器&＃xff0c;需要联网&＃xff0c;网络通讯比较慢。

1.2 基于规则的过滤器

如果号码不在黑名单&＃xff0c;可以通过预设规则来过滤&＃xff1a;

• 短信中包含特殊单词&＃xff08;或词语&＃xff09;&＃xff0c;比如一些非法、淫秽、反动词语等&＃xff1b;

• 短信发送号码是群发号码&＃xff0c;非我们正常的手机号码&＃xff0c;比如&＃43;60389585&＃xff1b;

• 短信中包含回拨的联系方式&＃xff0c;比如手机号码、微信、QQ、网页链接等&＃xff0c;因为群发短信的号码一般都是无法回拨的&＃xff1b;

• 短信格式花哨、内容很长&＃xff0c;比如包含各种表情、图片、网页链接等&＃xff1b;

• 符合已知垃圾短信的模板。垃圾短信一般都是重复群发&＃xff0c;对于已经判定为垃圾短信的短信&＃xff0c;我们可以抽象成模板&＃xff0c;将获取到的短信与模板匹配&＃xff0c;一旦匹配&＃xff0c;我们就可以判定为垃圾短信。

何定义特殊单词&＃xff1f;概率统计。

1.3 基于概率统计的过滤器

1.3.1 朴素贝叶斯算法

假设事件A是“小明不去上学”&＃xff0c;事件B是“下雨了”。现在统计了一下过去10天的下雨情况和小明上学的情况&＃xff0c;作为样本数据。

规律&＃xff1a;在这10天中&＃xff0c;有4天下雨&＃xff0c;所以下雨的概率P(B)&＃61;4/10。10天中有3天&＃xff0c;小明没有去上学&＃xff0c;所以小明不去上学的概率P(A)&＃61;3/10。在4个下雨天中&＃xff0c;小明有2天没去上学&＃xff0c;所以下雨天不去上学的概率P(A|B)&＃61;2/4。在小明没有去上学的3天中&＃xff0c;有2天下雨了&＃xff0c;所以小明因为下雨而不上学的概率是P(B|A)&＃61;2/3。

公式表达&＃xff1a;

1.3.2 如何利用朴素贝叶斯算法&＃xff0c;来做垃圾短信的过滤

计算机没办法像人一样理解短信的含义&＃xff0c;需要把短信抽象成一组计算机可以理解并且方便计算的特征项&＃xff0c;用这一组特征项代替短信本身&＃xff0c;来做垃圾短信过滤。

通过分词算法&＃xff0c;把一个短信分割成n个单词。这n个单词就是一组特征项&＃xff0c;全权代表这个短信。

使用概率&＃xff0c;来表征一个短信是垃圾短信的可信程度。公式如下&＃xff1a;

实际没法通过样本数据统计得到这个概率。

朴素贝叶斯公式&＃xff1a;

P&＃xff08;W1W_{1}W1​&＃xff0c;W2W_{2}W2​&＃xff0c;W3W_{3}W3​&＃xff0c;…&＃xff0c;WnW_{n}Wn​同时出现在一条短信中 | 短信是垃圾短信&＃xff09;这个概率照样无法通过样本来统计得到。通过以下公式计算&＃xff1a;

独立事件发生的概率计算公式&＃xff1a;P(A*B) &＃61; P(A)*P(B)如果事件A和事件B是独立事件&＃xff0c;两者的发生没有相关性&＃xff0c;事件A发生的概率P(A)等于p1&＃xff0c;事件B发生的概率P(B)等于p2&＃xff0c;
那两个同时发生的概率P(A*B)就等于P(A)*P(B)。


基于上面的公司&＃xff0c;得到如下&＃xff1a;

其中&＃xff0c;P&＃xff08;WiW_{i}Wi​出现在短信中 | 短信是垃圾短信&＃xff09;表示垃圾短信中包含WiW_{i}Wi​这个单词的概率有多大。这个概率值通过统计样本很容易就能获得。我们假设垃圾短信有y个&＃xff0c;其中包含WiW_{i}Wi​的有x个&＃xff0c;那这个概率值就等于x/y。

P&＃xff08;短信是垃圾短信&＃xff09;表示短信是垃圾短信的概率 &＃61; 把样本中垃圾短信的个数除以总样本短信个数&＃xff0c;就是短信是垃圾短信的概率。