前言
此算法不是机器学习中的算法,是开发中解决问题常用的工具的实现算法.毕竟我是开发嘛.术业有专攻.
位图和Bloom Filter
位图
一般接触到位图都是在对与一些海量数据的处理上,比如,在十亿个数中找到重复的或者判断是否存在等等,这个时候一般会有内存和机器的限制,不能直接保存整数,而是使用bit来代表每个数.
位图: 在Java中可以是BitSet,使用的话,也比较简单,底层应该也是数组,不过可以精确到每一bit,算一下,十亿个整数,每个证书是4个字节,那就是40亿字节,就是4GB左右的大小,如果我们用一位代表一个整数,那就是10亿位,8位一个字节,是128M左右.
Bloom Filter
Bloom Filter即布隆过滤器,我初次接触实在处理缓存击穿的时候用到的.这个后面说,先说主要用途.
一般是这样一个题,我在腾讯面试的时候遇到的,如何在10亿个url中找到重复的.
因为url不是整数,我们不能直接用位图,(当然还有分治的方法,这里先不说),所以我们可以马上想到,对url做hash,然后用位图,但是单单是位图不行,因为hash碰撞的问题太严重,而且我们刚才在用位图的时候还有一个问题没有提到,就是位图对于数据范围有要求.
想象一下,如果我们实在1千万个整数中找重,但是这一千万个整数的范围是整个整数范围,那么我们还是需要128M左右,因为位图是随着数据范围而不是数据量,但如果我们直接使用map存整数,只需要40M,这就出现了问题,这个时候就需要Bloom Filter
我们使用K个hash函数,对同一个url求哈希值,会得到K个不同的Hash值,分别记做X1,X2,X3…Xk.我们把这K个数字作为位图的下标,填入位图,也就是说我们用K个二进制位来表示一个数字的存在.
当我们查询某个url是否存在时,也是先进行k个Hash,得到Y1,Y2,Y3,…Yk,看是否对应位图的下标是否都为true,如果有一个不是,那就不存在.
很容易看出来,Bloom Filter是存在误判的,也就是我们判断是存在的,但有可能是因为Hash碰撞导致的,而事实不存在,但这个误判率可以通过调整Hash来减少到0.1%以下,大部分系统应该都是可以容忍这样的误判的.
有一句话是这样说的false is always false, true is true,也就是如果判断不存在那就一定不存在,如果判断存在,那可能存在.
缓存击穿中的应用
先介绍一下缓存击穿,就是查询一个一定不存在的数据,缓存肯定不会命中的,这导致每一次的查询都落到DB上,如果有人恶意攻击,就会有漏洞.
一般的解决办法有两个,一个是缓存中将这个数据保留在缓存,值就是空,不过要设置失效时间.
另一种就是使用Bloom Filter,在缓存服务的基础上,设置Bloom Filter数据结构,查找逻辑如下:
- 根据key查找缓存,如果存在值,就返回,如果不存在,向下
- 根据key查询缓存BF中的值,如果存在,说明该key不存对应的值,返回空,如果不存在,向下
- 查询db对应的值,如果存在,更新缓存,并返回值,如果不存在,更新BF,并返回空.
朴素贝叶斯算法
这应该是一种分类算法,我面试网易的时候被问到知道什么分类算法吗?当时我说不知道,然后就没了,所以赶紧记录一下.
先看一下公式:
P(A|B) = P(B|A) * P(A) / P(B)
就是很简单,就是我们高中概率的东西,翻译一下就是:
B事件发生的情况下A发生的概率 等于 A发生的情况下B发生的概率 * A发生的概率 然后除以 B发生的概率.
例子的话,就是垃圾短信的过滤.
基于概率统计的过滤器,是基于短信内容来判定是否是垃圾短信,而计算机没办法理解短信的含义(我们先不考虑机器学习和神经网络),所以我们需要通过特征项,代替短信,来做短信过滤.
首先通过分词算法,把一个短信分割成n个单词,这n个单词就是一组特征项,全权代表这个短信,因此判断一个短信是否是垃圾短信,就变成了判断同时包含这几个单词的短信是否是垃圾短信.
但是这个判断不可以非黑即白,需要一个可信度,我们这样:
P(短信是垃圾短信 | w1,w2,w3….wn同时出现在一条短信中)
如果我们用简单的计算概率的方法,我们没有很多包含w1,w2,w3…wn的短信,没办法计算,所以需要朴素贝叶斯算法.
P(短信是垃圾短信|w1,w2…wn在同一条短信里) = P(w1,w2,..wn在短信里|短信是垃圾短信)P(短信是垃圾短信) / P(w1,w2,…wn同时在一条短信中)
我们高中概率学中学到,如果A,B是独立事件,P(AB) = p(A) * P(B)
然后我们的P(w1,w2,..wn同时出现在一条短信中|短信是垃圾短信) =
P(w1出现在短信中|短信是垃圾短信) *
P(w2出现在短信中|短信是垃圾短信) *
P(w3出现在短信中|短信是垃圾短信) *
….
P(wn出现在短信中|短信是垃圾短信)
其中P(wi出现在短信中|短信是垃圾短信)很简单可以计算,假设垃圾短信y个,包含wix个,那这个值就是x/y
然后是P(短信是垃圾短信)这个更简单,就是垃圾短信数/总短信数
最后是P(w1,w2,…wn同时出现在一条短信中)按理说需要频繁集挖掘算法,但是这里就不需要了,我们可以通过上面的值,计算出这条短信是垃圾短信和不是垃圾短信的分子值,因为分母都是这个,所以分子大的,那概率就大,如果是垃圾短信的概率源大于不是,那这个短信就是垃圾短信.
判断垃圾短信这种需求,还是机器学习和神经网络靠谱一点,这里就是介绍一下朴素贝叶斯算法
协同过滤算法
我以前做了大数据的相关题目,就是商品推荐,当时使用的是基于频繁集的挖掘生成关联规则的方法,算法是Aprior.但是推荐算法数不胜数,还有一种就是协同过滤算法,这是一种倾向于挖掘喜好的推荐算法,和频繁集相比的话,多了对人的喜好的因素.举个简单例子:
我们就拿音乐推荐来说:
假设我们有5个人,有10首歌,每个人对每首歌都有喜爱程度,比如你收藏了,或者把它添加进歌单,肯定要比只是听过一次要更加喜欢,根据喜爱程度从高到低,分数为,5,4,3,2,1,0,-1.
然后我们就有了每个人对于这10首歌的喜爱程度的打分.
这个时候我们就得到一个二维数组,然后把每个人的对于10首歌的打分列为一个向量,就比如(5,1,3,4,0,0,-1,3,2,5)
这个时候我们有5个这样的向量,然后计算在向量空间里这5个向量的欧几里得距离,得到最每个人喜好最相近的那个人,然后就可以根据两人的听过的歌进行推荐.
还有根据歌曲进行的推荐,这样可以将歌曲进行推荐,
如果你用过网易云,可以发现在你进入软件时,有一个根据你人的推荐,然后你点进一首歌,又有根据歌曲的推荐,这就是二者的区别
后
大概就这样吧，有些例子都是找来的，记录一下
