机器学习:单词拼写纠正器python实现

主要推送关于对算法的思考以及应用的消息。培养思维能力,注重过程,挖掘背后的原理,刨根问底。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎您的关注。

01

朴素贝叶斯分类实战

前面介绍了贝叶斯的基本理论,朴素贝叶斯分类器,拉普拉斯修正,文章的链接如下:

机器学习:说说贝叶斯分类

朴素贝叶斯分类器:例子解释

朴素贝叶斯分类:拉普拉斯修正

在这3篇推送中用例子详细阐述了贝叶斯公式和朴素贝叶斯如何做分类,以及如何修正一些属性某些取值概率。

下面,借助朴素贝叶斯分类器的基本思想,编写一个单词拼写纠正器,它大致实现的功能如下:

  1. 如果用户输入的单词存在,则直接提示在字典中发现,并返回
  2. 如果单词不在词典中,纠正器会猜测用户的可能输入,然后做出最多两步的距离调整,并返回纠正后,用户最可能想输入的前三个单词
  3. 如果经过最多的两步调整后,还是未找到,则提示想输入的单词在字典中不存在。

02

纠正器实现原理

1 如用户输入了 hella,纠正后发现的3个最有可能的输入如下:

'want to input: hello', 'hell', 'fella'

2 如用户输入了appropreate,纠正器纠正后:

'want to input: appropriate'

3 如用户输入了owesomes,纠正器纠正后:

'want to input: awesome'

4 如用户输入了grduallyare,纠正器纠正后:

grduallyare not found in dictionary!

以上是纠正器能实现的纠正实例,那么该如何实现这么一个单词拼写错误检查和纠正的工具呢。

如果用户实际输入的单词为 w(word的简写), 然后拼写纠正器猜测用户实际想输入的单词为 c1, c2 , c3 , ....... 因此,我们可以猜测用户输入了 P(c1 | w) ,P(c2 | w),P(c3 | w)等等这些多种猜测。如果发现P(c1 | w) 的概率最大,那么用户很有可能想输入的那个单词为 c1 。这个概率可以统一表示为:

P(c | w)

如何求解这个概率的最大值?

将以上概率做如下转化来求解:用户想输入的很可能在语料库的这个 c 时,有可能被错误的输入为了 w1,w2,w3 ,...... 则这个概率可以统一表示为:

P(w | c)

用户错误地输入成 w1,w2,w3,......,它们之间是相互独立的,因此可以根据朴素贝叶斯分类器的理论,进一步将后验概率 P(c | w) 的求解转化为求解如下的目标函数:

max ( P(c) * P(w | c) / P(w) )

上式中 P(c)为先验概率,下载一个比较丰富的单词拼写都正确的英文单词库后,统计下每个单词出现的频次,就是单词 c 的出现的概率;

P(w) 是与问题分类无关的量,因为用户有可能输入任意一个单词;

P(w | c) 是一个类条件概率:用户想输入c(c在语料库中是有对应的,在此处需要注意:我们取的语料库不能100%保证一定存在任意一个正确的单词,所以在统计的过程中,假定单词至少出现1次),但是被错误地输入为了 wi 的概率。

P(w | c) 的求解方法通常会有很多种,比如用户想输入hello,但是实际输入了 hella,它们之间的区别仅仅是最后一个字符输入错误,这个出现的概率还是挺大的吧;但是,再看看下面这个例子。

如果用户想输入awesome, 但是实际输入成了owesomes,输错了1个字符,多添加了 1个字符,这种情况发生的概率就比上面那种小一些吧。

因此,在本文中设计的纠正器没有直接去量化 P(w | c) 这个概率,而是采取了从定性上进行分析,通常经过一步调整出现的概率大于经过两步调整出现的概率。所以,当纠正器遇到一个待纠正的词语时,它会纠正一步,如果发现了,就直接返回了;否则才会进行两步调整,这种调整的优先级的原理是根据 P(w | c) 。

这样先验概率 P(c) 和类条件概率 P(w | c) 的求解方法就弄明白了,当一步纠正就能在语料库找到对应后,就不会进行两步纠正,但是一步纠正会返回多个,此时再根据P(c)找出这些中的出现频次最多的,这样最终的结果便是猜测到的用户最有可能想输入的单词。

03

纠正器Python代码

构建先验概率P(c),语料库下载了老友记的1-10部+呼啸山庄全部组成的单词库。

import re, collections
def tolower(text):
    return re.findall('[a-z]+',text.lower())
def prior(cwords):
    model = collections.defaultdict(lambda:1)
    for f in cwords:
        model[f]+=1
    return model
ipath = './bigword.txt'
uipath = ipath.encode("utf8")
htxt = open(uipath,'r',errors ='ignore')
cwords = tolower(htxt.read())
#get P(c)
nwords = train(cwords) 
nwords

类条件概率

alpha = 'abcdefghijklmnopqrstuvwxyz'
#一步调整
def version1(word):
    n = len(word)
    add_a_char = [word[0:i] + c + word[i:] for i in range(n+1) for c in alpha]
    delete_a_char = [word[0:i] + word[i+1:] for i in range(n)]
    revise_a_char = [word[0:i] + c + word[i+1:] for i in range(n) for c in alpha]
    swap_adjacent_two_chars = [word[0:i] + word[i+1]+ word[i]+ word[i+2:] for i in range(n-1)] 
    return set( add_a_char + delete_a_char +
               revise_a_char +  swap_adjacent_two_chars)
#两步调整  
def version2(word):
    return set(e2 for e1 in edits1(word) for e2 in edits1(e1))

朴素贝叶斯分类器

def identify(words):
    return set(w for w in words if w in nwords)
def getMax(wanteds):
    threewanteds=[]
    maxword = max(wanteds,key=lambda w : nwords[w])
    threewanteds.append('want to input: '+ maxword)
    wanteds.remove(maxword)
    if len(wanteds)>0:
        maxword = max(wanteds,key=lambda w : nwords[w])
        threewanteds.append(maxword)
        wanteds.remove(maxword)
        if len(wanteds)>0:
            maxword = max(wanteds,key=lambda w : nwords[w])
            threewanteds.append(maxword)   
    return threewanteds
def bayesClassifier(word):
    #如果字典中有输入的单词,直接返回
    if identify([word]):
        return 'found: '+ word
    #一步调整
    wanteds = identify(version1(word)) 
    if len(wanteds)>0:
        return getMax(wanteds)
    #两步调整
    wanteds = identify(version2(word))
    if len(wanteds)>0:
        return getMax(wanteds)
    #不再修正,直接提示这个单词不在当前的词典中
    else:    
        return [word + ' not found in dictionary!' ]

测试1 :

测试2 :

测试3 :

测试4 :

如有需要这个拼写检查器的Jupyter notebook的,想自己亲自实践下的,请@我。

原文发布于微信公众号 - 算法channel(alg-channel)

原文发表时间:2017-11-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏自学笔记

Aggregation Model : Blending , Bagging , Boosting

比如现在有一支股票,你不知道是跌还是涨。你有T个friends,每一个friend对应的建议分别是g1,g2,g3...gn,那么你应该怎么选择建议?

13430
来自专栏数据科学学习手札

(数据科学学习手札21)sklearn.datasets常用功能详解

作为Python中经典的机器学习模块,sklearn围绕着机器学习提供了很多可直接调用的机器学习算法以及很多经典的数据集,本文就对sklearn中专门用来得到已...

38890
来自专栏量化投资与机器学习

【Matlab量化投资】支持向量机择时策略

推出【Matlab量化投资系列】 机器学习 所谓机器学习,其实就是根据样本数据寻找规律,然后再利用这些规律来预测未来的数据(结果)。 但是,直到今天,机器学习...

29560
来自专栏数据派THU

从零开始用Python实现k近邻算法(附代码、数据集)

63480
来自专栏数据结构与算法

中国剩余定理详解

引入 我国古代数学著作《孙子算经》中有一道题目,它的描述是这样的 今有物不知其数,三三数之余二;五五数之余三;七七数之余二。问物几何? 这道题用现代数学理...

390110
来自专栏大数据文摘

机器学习算法一览(附python和R代码)

258140
来自专栏机器之心

专栏 | 为模型减减肥:谈谈移动/嵌入式端的深度学习

机器之心专栏 作者:李飞 本文为机器之心矽说专栏系列文章之一,对模型压缩进行了深度解读。 1. 为什么要为深度学习模型减肥 随着深度学习的发展,神经网络模...

44480
来自专栏杨熹的专栏

机器学习-多元线性回归

A. 用途: 可以用来预测,由多种因素影响的结果。 B. 建立公式: ? C. 求解方法: 方法1. Gradient Descent: ? ...

36050
来自专栏人工智能LeadAI

时间序列异常检测 EGADS Surus iForest

时间序列异常检测 (原文链接:http://wurui.cc/tech/time-series-anomaly-detection/) 本文总结了我在时间序列异...

1.6K40
来自专栏Duncan's Blog

NP-Hard问题(重点关注k-median问题)

启发式搜索在状态空间中对每一个要搜索的位置按照某种方式进行评估,得到最优的位置,再从这个位置进行搜索直到达到目标.常用的启发式算法包括:禁忌搜索/遗传算法/进化...

19640

扫码关注云+社区

领取腾讯云代金券