机器学习手记[2]---朴素贝叶斯在拼写检查的应用_google拼写检查 朴素贝叶斯

这篇文章的初始是源于一篇基于朴素贝叶斯进行拼写检查的文章，我做了这个文章，同时写了一些自己的感悟在里面。

文章请见：怎样写一个拼写检查器。http://blog.youxu.info/spell-correct.html

问题：拼写错误这个例子就我们在百度谷歌搜索时，打错了某个单词，会发现搜索引擎能够自动识别拼写错误，显示正确单词？
解决：如何做呢？可以根据简单的统计和朴素贝叶斯公式去计算得到。

首先看贝叶斯公式，规定我们真正想打的单词事件为p(想打c)，我们实际出来的单词事件为p(实际打w)
对于想打c，却打出w这种事件的贝叶斯等式： p(想打c|实际打w)*p(实际打w)=p(实际打w|想打c)*p(想打c)， 
其中 
化简
   p(想打c|实际打w)
=  p(实际打w|想打c)*p(想打c)/p(实际打w)
=  p(实际打w|想打c)*p(想打c)

现在我们面临了两个项：
1)   p(想打c)这个先验概率如何算呢？ 这个可以理解我，某个人闲着没事随便打些话，某个单词的概率，这个和我们的使用习惯有关，从大众来看，通过一本小说啊可以大概算出来各个单词出现的频率的
那么我们如何获取数据集，计算各个单词出现频率呢？

import re, collections  #re是正则式模块，用于文本数据集处理；collections是字典模块，生成一种特殊字典
def words(text): 
	return re.findall('[a-z]+', text.lower())   #查找所有单词，变成小写
def train(features):
    model = collections.defaultdict(lambda: 1)  #生成特殊字典，key可以动态增加，且所有value默认值为1
    for f in features:
        model[f] += 1   
    return model
NWORDS = train(words(file('big.txt').read()))   #将文本集处理为单词的dictionary，也就是做wordcount

2)  p(实际打w|想打c)打字错误
这个有两种错误，
一种是认知上错了，比如calendar，我就记成了calender是很常见的一个例子
另一种就是打字机械错误，就是按错了，这种情况可能有漏打，多打，顺序错，等等    比如想打weng，打出来wegn等等
这里我们只分析机械错误，分析两种情况
1）打错一个字  包含（少打一个字，多打一个字，错打一个字，单词中一个和另一个字母交换的情况）
2）打错两个字。 也包含类似少打多打等情况，其实错两个字也可以直接理解为在正确字-->打错一个字--->又打错了一个字这种情况


那么具体打错一个字和两个字怎么实现呢？

alphabet = 'abcdefghijklmnopqrstuvwxyz'  #一个字母表
def edits1(word):  #将word打错一个字的情况
   s = [  (word[:i], word[i:]) for i in range(len(word) + 1)  ]        #将word半劈，一般a，一般b         
   deletes    = [a + b[1:] for a, b in s if b]                         #缺
   transposes = [a + b[1] + b[0] + b[2:] for a, b in s if len(b)>1]    #调换1个字母
   replaces   = [a + c + b[1:] for a, b in s for c in alphabet if b]   #替换1个字母
   inserts    = [a + c + b     for a, b in s for c in alphabet]        #插入1个字母
   return set(deletes + transposes + replaces + inserts)
 
 
def known_edits2(word):  #错2个字母，就是在edits1()函数基础上嵌套一层
    return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)

我们知道，贝叶斯公式已经将之前的问题转化为P(w,c)=p(实际打w|想打c)*p(想打c)的问题,我们只需要横向比较
p(实际打w|想打c1)*p(想打c1)
p(实际打w|想打c2)*p(想打c2)
p(实际打w|想打c3)*p(想打c3)   
上面这三个事件的概率里面那个大些呢？那么想打的c就可能是哪个.


这个式子有两个因子，p(实际打w|想打c)和p(想打c)
后者我们根据之前的文本数据集可以计算得出，
但最大的困难是前者，因为我们根本没有训练数据集来训练计算这个因子，试想我们知道自己要打的是word这个词，但是你打的是wor, work,words等等这些情况概率都是怎么样的呢？ 
这个数据要做很多实验才能拿到。
那么如何办？ 我们简化一下，首先考虑下 p(实际打w|想打c)*p(想打c)这个乘积中两个因子的影响力问题。
1）我们假定打错类型不同的时候，p(实际打w|想打c) 的影响力远远大于p(想打c)这个因子。
什么意思？ 我说的"打错类型不同"，就是指打错错字数目的不同, 比如"w相比c只错一个"和"w相比c错了两个字"就是两个类别，
这两个类别对比我们可以发现，显然只打错一个字的事件概率更高些，比如实际打出来pigg，而我们想打的是pig，还是dig呢？pigg相对pig只多了一个字，pigg相对dig相对则错了两个字了，因此更可能要打的是pig 
因此，在错误类别不同的时候，我们假定这个乘积就是错一个字的情况概率更高些，根本不用计算这个乘积概率中的任何一个因子。


那么问题又来了，如果说打字错字数目是一样的呢？假如打出来实际是pigg，我们到底是想打piggy，还是pig呢？piggy和pig相比pigg都是一字之差啊
2）由此我们假定错字数目相同的时候，p(想打c)这个因子开始起作用了
由于pig更加常用些，所以P(piggy)<P(pig), 因此实际打出来pigg，我们一般更有可能打的pig，而不是piggy。
这种情况其实我们也并没有真正计算p(实际打w|想打c)*p(想打c)这个乘积，只是假定他们的p(实际打w|想打c)一样，然后看看谁的p(想打c)的概率大

上述这个思想是用这个代码去实现的

</pre><p><pre name="code" class="python">def correct(word):
    candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]                                                                     
    return max(candidates, key=lambda w: NWORDS[w])
#拼写分为四种情况：完全正确，错1，错2，词典没这个词，通过or匹配了之前的就无法匹配后面了，我们可以按顺序从中得到其中一种情况的集合
# 同一集合再根据文本数据集出现频率的高低进行筛选也就是max()函数的作用