5.3 顺序分析——搜狗输入法的智能纠错系统_数据挖掘：你必须知道的32个经典案例

5.3 顺序分析——搜狗输入法的智能纠错系统

收藏我要投稿

本文所属图书 > 数据挖掘：你必须知道的32个经典案例

本书是为广大数据分析师量身定做的入门读物，它旨在帮助读者站到大数据时代的制高点。数据分析处于统计学、计算机信息科学、运筹学、数据库等多种领域的交叉地带，大数据时代的到来更是大大丰富了数据分析的内涵立即去当当网订购

顺序分析是关联分析的一种，它能够在大量数据集中发现数据的关联性或相关性。顺序分析关心的数据的纵向排列，即一件事情发生后紧接着会发生什么事情。顺序分析所使用的频繁模式算法是一种适用且简单的算法，本小节以搜狗输入法为例讲解了顺序分析是如何被用于挖掘用户的固有输入习惯的。

5.3.1 搜狗输入法的王牌词库和智能算法

输入法是人类和计算机打交道不可或缺的工具，我们的电子设备上什么软件都可以没有，但是没有输入法的话，我们就没办法和计算机愉快的沟通。但输入法的功能并不止于此，如今的智能输入法存储了你所有的按键数据。不夸张的说，这些数据完全可以刻画出你是什么样的人。
输入法的优劣在于输入法是否足够智能。如今市面上流行的输入法有百度输入法、腾讯输入法、微软输入法和搜狗输入法等。平心而论，尽管搜狗公司的浏览器做的实在是不怎么样，但搜狗公司的输入法确实是最好的，而且比其他输入法好了不止一点点。
截止2015年5月，搜狗输入法已经更新到了7.5版本，现如今，搜狗输入法支持的经典模块有简拼输入、智能纠错和热门词汇。其他输入法固然也支持这些功能，但它们都不如搜狗输入法做的好。

图5.3 搜狗输入法和微软输入法简拼输入对比图
图5.3是搜狗输入法和微软输入法在简拼输入方面的对比图。我们同时使用数据分析的首字母“sjfx”作为测试对象，搜狗输入法列出的第一个选择就是“数据分析”，同时它还紧接着列出了“数据分析师”、“数据分析方法”和“实际分析”，这些词条都是我常用的词条，搜狗输入法通过分析我以往的输入记录，给出了这些选项。
而微软输入法的第一个选择是“手机飞信”，其后才是“数据分析”选项，这种罗列中规中矩，但并不够人性化。当然，我并不经常使用微软输入法，因此累积不到足够的用户记录可能是导致微软输入法表现不好的原因之一。

图5.4 搜狗输入法和微软输入法智能纠错对比图
图5.4是搜狗输入法和微软输入法在智能纠错方面的对比图。测试输入均为“shujufnexi”，其中n和e的位置打错了，正确输入应该是“shujufenxi”。搜狗输入法辨别出了这种错误，给出了“数据分析”这一选项，微软输入法则没有。
智能纠错模块不仅支持对按键顺序混乱的纠正，也支持对按键缺漏和拼音错误的纠正。比如“shujufexi”这一输入中少了一个n，但输入法仍能判别出这是“数据分析”的输入；而输入“shenmo”后，搜狗输入法会给出“什么（shenme）”的选项，在纠错的同时向用户指出错误。这些功能的实现一方面和用户个人的输入习惯相关，另一方面也和搜狗输入法中累积的上千万用户的输入记录相关。

图5.5 搜狗输入法和微软输入法热门词汇对比图
图5.5是搜狗输入法和微软输入法在热门词汇方面的对比图。测试词汇是2015年5月中旬爆红的“赵薇撞脸高圆圆”事件中的“撞脸”一词，搜狗输入法给出的第一个选项就是“撞脸”，而微软输入法则没有出现这一选项。显然，搜狗输入法在热词方面要比微软输入法好很多。搜狗输入法还提供了“云词库”功能，以保证联网用户能够实时获取最新热门词汇。
除了以上功能外，搜狗输入法也提供实时翻译、细胞词库、字符表情等多项功能。所有这些眼花缭乱的功能都依赖于搜狗输入算法的正常工作，而算法的正常工作又依赖于搜狗的庞大词库。这种简拼输入和智能纠错的功能尽管看起来并不起眼，但其实里边蕴含的算法原理是十分深刻的，本小节所关心的正是搜狗输入法中的顺序分析算法。

5.3.2 频繁树模式和顺序分析算法

我们在输入拼音时，总是遵循先后顺序输入一串字符，算法在分析输入的字符时也总是按照先后顺序来分析。这种先后顺序是有意义的，因此对于用户打字习惯的分析十分适合使用顺序分析法来分析。
搜狗输入法累积了用户的大量数据，这是它高度智能化的基础。在进行顺序分析前，搜狗输入法首先需要分解用户输入的序列，比如将sjfx分解为s'j'f'x，将shujufx分解为shu'ju'f'x。这种分解依赖于已知的词库，即工程师需要首先告诉输入法shu是一个字符，而sj就是两个单独的字符。

序号	顺序
1	s,j,f,x
2	s,j,f,x,f,f
3	s,j,w,j
4	s,h,s
5	s,j,f,x,s

图5.6 拼音顺序记录表
图5.6是一个简易的拼音顺序记录表，在表中，数据分析、数据分析方法、数据挖掘、上海市、数据分析师的简拼顺序分别出现了一遍。顺序分析的任务就是在这些记录中发现频繁出现的那些顺序，并在新顺序出现时，将它与已知频繁顺序相比较，找出新顺序的潜在规律或异常。
在顺序分析中，支持度和置信度是最重要的两个概念。支持度指的是顺序出现的频率。比如单个字符s在集合中出现了5次，它的支持度就是5，而sj这一顺序一共出了4次，它的支持度就是4；置信度则指的是当某一顺序出现后，其他顺序紧接着出现的频率。比如sj顺序出现后，紧接着出现fx的置信度是3，紧接着出现fxff的置信度是1。
将支持度除以集合的总数或置信度除以该前缀所对应的子集总数后，这两个值就落入了0到1之间，比如sj的支持度

，sjfx的支持度是

，而sjfx相对sj的置信度则是

。此时的支持度和置信度可以直接衡量某一顺序出现的概率，而不需再结合集合总数进行分析。
值得指出的是，支持度和置信度是两个单独的概念，二者之间没有任何关联，一个顺序的支持度高，置信度未必高，其置信度高，支持度也未必高。同时，我们感兴趣的是支持度和置信度同样高的顺序，一个顺序支持度低时，说明它出现的次数非常少，对它的研究没有意义；一个顺序置信度低时，说明关于它的结论不可靠。

图5.7 拼音顺序记录的频繁树
显而易见，顺序分析的本质思想是使用概率的知识来解决问题，一个顺序出现的概率大，则新顺序符合这个顺序的概率就大。比如我老是要输入“数据分析”这个词组，在我的记录里这个词组的频率就非常高，因此当我再次输入“sjfx”时，搜狗输入法就知道我想要输的是“数据分析”。
这种思想非常容易理解，困难的是如何把顺序合理的转化为数字、从而统计每个顺序出现的概率呢？图5.7是拼音顺序记录的频繁树表示，频繁树模式是一种非常好用的关联分析方法。
在图5.7中，每一个节点都由一对字母和数字组成，字母表示该节点的输入字符，数字表示该节点的支持度。这棵树从上往下读，最上边的节点是根节点，越靠近根节点，支持度就越大。根据图5.7，将所有顺序按照支持度从大到小排列后有{s:5}、{sj:4}、{sjfx:3}、{sjfxff:1}、{sjfxs:1}、{sjfxwj:1}、{shs:1}等七个顺序。
在顺序分析中，我们通常不会保留所有的顺序，而只是保留那些支持度高的、有意义的顺序。比如在本例中，我们将阈值设为1，即只保留顺序{s}、{sj}以及{sjfx}。同理，我们计算每个顺序的置信度，并设一个阈值来选出置信度较高的顺序。当用户输入s后，根据频繁树，我们将认为用户下一个将要输入的字符为j；当用户输入sj后，根据频繁树，我们将认为用户即将输入fx。
简拼输入是基础的顺序分析，它所涉及的顺序元素全都是单独的字符。在智能纠错中，顺序分析所涉及的元素则夹杂了多个字符，比如shujufx这一序列应当拆分为shu、ju、f、x这四个元素。将一个汉字的拼音视为一个整体能够简化计算，并且，这也是符合认知习惯的。
智能纠错寻找元素排列规律的方法与简拼输入并无不同，它寻找拼音错误的方法在于将每个汉字的拼音单独作为一个序列进行分析。比如对于“shujufnexi”这一序列来说，智能纠错首先将其分割为“shu、ju、f、ne、xi”这一序列，并搜索常见排列顺序，发现“shu、ju”后边总是跟随“fen、xi”，并比较“fne”和“fen”的相似度，最终确定这是一个需要纠正的错误。
热门词汇功能则在于调高了顺序分析算法中热门词汇所对应的序列的频率，从而保证热门词汇能够排在更靠前的位置。

5.3.3 顺序分析小结

和大多数机器学习问题相似，工程师没办法直接告诉程序：当一个用户输入“数据”后，他就马上要输入“分析”了。输入法程序必须自己学习这些规则，而顺序分析正是通过累积概率知识来赋予输入法程序学习能力，因此顺序分析是一个典型的机器学习算法。
顺序分析的思想十分简洁，但它是行之有效的，尤其是累积的概率知识足够多时。它总是被用于发现各种各样的顺序，比如购买了孕妇服的顾客在几个月内会购买婴儿玩具和纸尿裤，比如访问了A网页的用户会在两分钟内访问B网页，再比如这学期选《数据结构》这门课的同学会在下学期选《C语言》。这种分析方法可以用于零售网站为用户推荐产品或从正常访客中区分黑客。总的来说，顺序分析专门用于解决含有大量事务集，并且事务间存在顺序关系的问题。
顺序分析和决策树以及粗糙集的原理颇有相似之处，都是从概率知识中获取知识。但顺序分析擅长处理字符型数据和数值型数据，而决策树和粗糙集则需要将字符型数据转化为数值型离散数据。同时顺序分析将数据看做一个整体，关心数据中呈现的顺序规律；而决策树和粗糙集将自变量和因变量分割开来，关心的是最终的结论。
常用的顺序分析算法有Apriori算法和FP-growth算法，它们都具有具有原理简单、容易理解、擅于处理多种数据类型的优点，并对于解决某些特定问题具有不可替代的作用，但它同样也具有缺点。
首先，结果准确度和计算效率是顺序分析中一个不可调和的矛盾。顺序分析的精髓在于统计所有常见顺序出现的频率，由于一个长的顺序需要拆分多个短的顺序，因此随着集合中样本的增长，计算空间会呈指数增长，计算效率也会急速下降。同时顺序分析的结果准确度基本完全依赖于样本量的大小，因此，结果的准确度和计算效率就成了一对不可调和的矛盾。
其次，顺序分析仅能发现事件和事件之间的相关性，而不能发现一个事件引发另一个事件的原因。有时候我们能够轻易地理解顺序分析提供的规律中的内在关系，比如购买孕妇服的用户会在几个月后购买纸尿裤。但有时候这会让人困扰，比如购买黄酒的用户会在两天后购买香蕉。如果偶们不能理解顺序分析提供的规律中的内在关系，我们就不能给出准确合理的建议。
最后，顺序分析只在样本累积足够多时才能起到作用。这是一个冷启动问题，有的问题中它并不严重，比如我们使用输入法时不会苛刻地要求它第一天就猜出我们是数据分析师。但有时候则不然，比如在样本本来就有限，或者分析结果要的非常急的时候。这个缺点极大地局限了顺序分析能够解决的问题的范畴。

点击复制链接与好友分享!回本站首页

分享到：更多

您对本文章有什么意见或着疑问吗？请到论坛讨论您的关注和建议是我们前行的参考和动力

上一篇：1.3　功能

下一篇：1.5　小结

图文推荐

排行