琼海做球网站,不动户激活 e路护航安全组件,湖南郴州,怎么添加wordpress模板文件概述
上篇文章我们讲到#xff0c;如何用位图、布隆过滤器#xff0c;来过滤重复数据。本章#xff0c;我们再讲一个跟过滤相关的问题#xff0c;如果过滤垃圾短信#xff1f;
垃圾短信和骚扰电话#xff0c;我想每个人都收到过吧#xff1f;买房、贷款、投资理财、开…概述
上篇文章我们讲到如何用位图、布隆过滤器来过滤重复数据。本章我们再讲一个跟过滤相关的问题如果过滤垃圾短信
垃圾短信和骚扰电话我想每个人都收到过吧买房、贷款、投资理财、开发票各种垃圾短信和骚扰电话不胜其扰。如果你是一个手机应用的开发工程师让你实现一个简单的垃圾短信过滤功能以及骚扰电话拦截功能该用什么样的数据结构和算法实现呢 算法解析
实际上解决这个问题并不会涉及很高深的算法。本章就带你一块看下如何利用简单的数据结构和算法解决这种看似非常复杂的问题。
1.基于黑名单的过滤器
我们可以维护一个骚扰电话号码和垃圾短信发送号码的黑名单。这个黑名单的收集有很多途径比如我们可以从一些公开的网站上下载也可以通过类似 “260骚扰电话拦截” 的功能通过用户自主标记骚扰电话来收集。 对于被多个用户标记并且标记个数超过一定阈值的号码我们就可以定义为骚扰电话并将它将入到黑名单中。
如果黑名单中的电话号码不多我们可以使用散列表、二叉树等动态数据结构来存储对于内存的消耗并不会很大。如果我们把每个号码看做一个字符串并且假设平均长度是 16 个字节那存储 50 万个电话号码大约需要 10MB 的内存空间。即便是对手机这样的内存有效的设备来说这点内存消耗也是可以接收的。
但是如果黑名单中的电话号码很多呢比如有 500 万个。这个时候如果再用散列表存储那就需要大约 100MB 的存储空间。为了实现一个拦截功能耗费用户如此多的手机内存这显然有点儿不合理。
上篇文章我们讲了布隆过滤器最大的特点就是节省空间所以用它来解决这个问题再适合不过了。如果我们要存储 500 万个手机号我们把位图大小设置为 10 倍数据大小也就是 5000 万那也只需要使用 5000 万个二进制位5000 万bits换算成字节也就是不到 7MB 的存储空间比起散列表的解决方案内存的消耗减少了很多。
实际上我们还有一种时间换空间的方法可以将内存的消耗优化到极致。
我们可以把黑名单存储在服务器上把过滤和拦截的核心工作交给服务器端来做。手机端只负责将要检查的号码发送给服务器端服务器端通过查黑名单判断这个号码是否应该被拦截并将结果返回给手机端。
用这个思路完全不需要占用手机内存。不过有利就有弊。我们知道网络通信是比较慢的所以网络延迟就会导致处理速度降低。而且这个方案还有个硬性要求那就是只有在联网的情况下才能正常工作。
基于黑名单的过滤器我讲完了不过你可能还会说布隆过滤器会有判错的概率呀如果它把一个重要的电话或者短信当成垃圾短信或者骚扰电话拦截了对于用户来说这是无法接受的。你说的没错这是一个很大的问题。不过我们现在先放一放等三种过滤器都讲完之后再来解答。
2.基于规则的过滤器
刚刚讲了一种基于黑名单的垃圾短信过滤方法但是如果某个垃圾短信发送者的号码并不在黑名单中那这种方法就没有办法拦截了。所以基于黑名单的过滤方式还不够完善我们再继续看一种基于规则的过滤方式。
对于垃圾短信来说我们还可以通过短信内容来判断某条短信是否是垃圾短信。我们预先设置一些规则如果某条短信符合这些规则我们就可以判定它为垃圾短信。实际上规则有很多比如下面几个
短信中包含特殊单词或词语比如一些非法、淫秽、反动词语等。短信发送号码是群发号码非我们正常的手机号吗。短信中包含回拨的联系方式比如手机号码、微信、QQ、网页链接等因为群发短信的号码一般是无法回拨的。短信格式花哨、内容很长比如各种表情、图片、网页链接等。符合已知垃圾短信的模板。垃圾短信一般都是重复群发对于已经判定为垃圾短信的短信我们可以抽象成模板将获取到的短信与模板匹配一旦匹配我们就可以判定为垃圾短信。
当然如果短信只是满足其中的一条规则如果就判定为垃圾短信那会存在比较大的误判的情况。我们可以综合多条规则进行判定。比如满足 2 条以上才会被判定为垃圾短信或者每条规则对应一个不同的得分满足哪条规则我们就累加对应的分数某条短信的总得分超过某个阈值才会被判定为垃圾短信。
不过我只是给出了一些指定规则的思路具体落实到执行层面其实还有很大的距离还有很多细节需要处理。比如第一条规则我们该如何定义特殊单词第二条规则中我们该如何定义什么样的号码是群发号码等等。限于篇幅我就不一一详细讲解了。这里只讲一下如何定义特殊单词
如果我们只是拍脑袋想哪些单词属于特殊单词那势必有比较大的主观性也很容易遗漏掉某些单词。实际上我们可以基于概率统计的方法借助计算机强大的计算能力找出哪些单词最常出现在垃圾短信中将这些最常出现的单词作为特殊单词用来过滤短信。
不过这种方法的前提是我们有大类的样本数据也就是说要有大类的短信比如 1000 万条短信并且我们还要求每条短信都做好了标记它是垃圾短信还是非垃圾短信。
我们对这 1000 万条短信进行分词处理借助中文或者英文分词法去掉 “的、和、是” 等没有意义的停用词Stop Words得到 n 个不同的单词。针对每个单词我们统计有多少个垃圾短信出现了这个单词有多少个非垃圾短信出现 这个单词进而求出每个单词出现在垃圾短信中的概率以及出现在非垃圾短信中的概率。如果某个单词出现在垃圾短信中的概率远大于出现在非垃圾短信中的概率那我们就把这个单词作为特殊词用来过滤垃圾短信。
文字描述不好理解我举个例子来解释细下。 3.基于概率统计的过滤器
基于规则的过滤看起来很直观也很好理解但是它也有一定的局限性。
一方面这些规则受人的思维方式的局限规则未免太过简单。另一方面垃圾短信发送至可能会针对规则精心设计短信绕过这些规则的拦截。
对此我们再来看一种更加高级的过滤方式基于概率统计的过滤方式。
这种基于概率统计的过滤方式基础理论是基于朴素贝叶斯算法。为了让你更好地理解下面的内容我们先通过一个非常简单的例子来看下什么是朴素贝叶斯算法
假设事件 A 是 “小明不去上学”事件 B 是 “下雨了”。我们现在统计一下过去 10 天的下雨情况和小明上学的情况作为样本数据。 我们来分析一下这组样本有什么规律。
在这 10 天中有 4 天下雨所以下雨的概率 P(B)4/10。10 天中有 3 天小明没有去上学所以小明不去上学的概率是 P(A)3/10。在 4 个下雨天中小明有 2 天没有去上学所以下雨天不去上学的概率 P(A|B)2/4。在小明没有去上学的 3 天中有 2 天下雨了所以小明因为下雨不去上学的概率是 P(B|A)2/3。
实际上这 4 个概率值之间有一定的关系这个关系就是朴素贝叶斯算法我们用公司表示出来就是下面这个样子。 朴素贝叶斯算法是不是非常简单我们用一个公式就可以将它概况。弄懂了朴素贝叶斯算法我们在回到垃圾短信过滤这个问题上看看如何利用朴素贝叶斯算法来做垃圾短信的过滤。
基于概率统计的过滤器是基于短信内容来判断是否是垃圾短信。而计算机没有办法像人一样理解短信的含义。所以我们需要把短信抽象成一组计算机可以理解并且方便计算的特征项用这一组特征项代替短信本身来做垃圾短信过滤。
我们可以通过分词算法把一个短信分割成 n 个单词。这 n 个单词就是一组特征项全权代表这个短信。因此判定一个短信是否是垃圾短信这样一个问题就变成了判定同时包含这几个单词的短信是否是垃圾短信。
不过这里我们并不像基于规则的过滤器那样非黑即白一个短信要么被判定为垃圾短信、要么被判定为非垃圾短信。我们使用概率来表征一个短信是垃圾短信的可信度。如果我们用公式将这个概率表示出来就是下面这个样子 尽管我们有大量的短信样本但是我们没法通过样本数据统计得到这个概率。为什么不可以呢你可能会说我只需要统计同时包含 W 1 , W 2 , W 3 , . . . , W n W_{1},W_{2},W_{3},...,W_{n} W1,W2,W3,...,Wn 这 n 个单词的短信有多少个我们假设有 x 个然后看这里属于垃圾短信的有几个我们假设有 y 个那包含 W 1 , W 2 , W 3 , . . . , W n W_{1},W_{2},W_{3},...,W_{n} W1,W2,W3,...,Wn 这 n 个单词的短信是垃圾短信的概率是 y/x。
理想很丰满但现实很骨感。你忽视了非常重要的一点那就是样本的数量再大比较也是有限的样本中不会有太多同时包含 W 1 , W 2 , W 3 , . . . , W n W_{1},W_{2},W_{3},...,W_{n} W1,W2,W3,...,Wn 的短信甚至很多时候样本中根本不存在这样的短信。没有样本也就无法计算概率。所以这样的推理方式虽然正确但在实践中并不好用。
这个时候朴素贝叶斯公式就可以派上用场了。我们通过朴素贝叶斯公式将这个概率的求解分解为其他三个概率的求解。你可以看我话的图。那转化之后的三个概率是否可以通过样本统计得到呢 P ( W 1 , W 2 , W 3 , . . . , W n 同时出现在一条短信中 ∣ 短信是垃圾短信 ) P(W_{1},W_{2},W_{3},...,W_{n}同时出现在一条短信中 | 短信是垃圾短信) P(W1,W2,W3,...,Wn同时出现在一条短信中∣短信是垃圾短信) 这个概率照样无法通过样本统计得到。但是我们可以基于下面这条著名的概率规则来计算。
独立事件发生的概率计算公式 P(A*B)P(A)*P(B)。
如果事件 A 和事件 B 是独立事件两者的发生没有相关性事件 A 发生的概率 P(A) 等于 p1事件 B 发生的概率 P(B) 等于 p2那两个同时发生的概率 P(A*B) 就等于 P(A)*P(B)。
基于这条独立事件发生概率的计算公式我们可以把 P ( W 1 , W 2 , W 3 , . . . , W n 同时出现在一条短信中 ∣ 短信是垃圾短信 ) P(W_{1},W_{2},W_{3},...,W_{n}同时出现在一条短信中 | 短信是垃圾短信) P(W1,W2,W3,...,Wn同时出现在一条短信中∣短信是垃圾短信) 分解为下面这个公式 其中 P ( W i 出现在短信中 ∣ 短信是垃圾短信 ) P(W_{i} 出现在短信中 | 短信是垃圾短信) P(Wi出现在短信中∣短信是垃圾短信) 表示垃圾短信中包含 W i W_{i} Wi 这个单词的概率有多大。这个概率值通过样本很容易就能获得。我们假设垃圾短信有 y 个其中包含 W i W_{i} Wi 的有 x 个那这个概率值就等于 x/y。 P ( 短信是垃圾短信 ) P(短信是垃圾短信) P(短信是垃圾短信) 表示短信是垃圾短信的概率这个很容易得到。我们把样本中垃圾短信的个数除以总样本个数就是短信是垃圾短信的概率。
不过 P ( W 1 , W 2 , W 3 , . . . , W n 同时出现在一条短信中 ) P(W_{1},W_{2},W_{3},...,W_{n}同时出现在一条短信中) P(W1,W2,W3,...,Wn同时出现在一条短信中) 这个概率还是不好通过样本统计得到原因前面说过了样本空间有限。不过我们没有必要非得计算这部分的概率值。为什么这么说呢
实际上我们可以分别计算同时包含 W 1 , W 2 , W 3 , . . . , W n W_{1},W_{2},W_{3},...,W_{n} W1,W2,W3,...,Wn 这 n 个单词的短信是垃圾短信和非垃圾短信的概率。假设它们分别是 p1 和 p2。我们并不需要单纯的基于 p1 值的大小来判断是否是垃圾短信而是通过对比 p1 和 p2 值的大小来判断一条短信是否是垃圾短信。更细化一点讲那就是如果 p1 是 p2 的很多倍比如 10 倍我们才确信这条短信是垃圾短信。 基于这连个概率的倍数来判断是否是垃圾短信的方法我们就可以不用计算 P ( W 1 , W 2 , W 3 , . . . , W n 同时出现在一条短信中 ) P(W_{1},W_{2},W_{3},...,W_{n}同时出现在一条短信中) P(W1,W2,W3,...,Wn同时出现在一条短信中) 这一部分的值了因为计算 p1 和 p2 的时候都会包含这个概率值的计算所以在求解 p1 和 p2 的倍数 (p1/p2) 的时候我们也就不需要这个值了。
总结
本章讲解了基于黑名单、规则、概率统计三种垃圾短信的过滤方法实际上本章讲的这三种方法还可以应用到很多类似过滤、拦截的领域比如垃圾邮件的过滤等等。
在讲黑名单过滤的时我讲到 布隆过滤器可能会存在误判可能会导致用户投诉。实际上我们可以结合三种不同过滤方式的结果对同一个短信处理如果三种都标明这个短信是垃圾短信我们才把它当做垃圾短信拦截过滤这样就会更精准。当然在实际的工程中我们还需要结合具体的场景以及大量的实验不断去调整策略权衡垃圾短信判定的准确率是否会把不是垃圾短信的短信错判为垃圾短信和召回率是否能把所有的垃圾短信都找到来实现我们的需求。
