贝叶斯分类

第二部分、贝叶斯分类

    说实话，友人刘未鹏有一篇讲的贝叶斯的文章：数学之美番外篇：平凡而又神奇的贝叶斯方法，已经把贝叶斯讲的很清晰透彻了，我再讲也是如李白看到崔颢在黄鹤楼上所提的：登黄鹤楼

昔人已乘黄鹤去，此地空余黄鹤楼；

黄鹤一去不复返，白云千载空悠悠。

    后便大为折服，已无什兴致再提了(偶现在就是这感觉)，然文章还得继续写。So，本文第二部分之大部分基本整理自未鹏兄之手(做了部分改动)，若有任何不妥之处，还望读者和未鹏兄海涵，谢谢。

2.1、什么是贝叶斯分类

     据维基百科上的介绍，贝叶斯定理是关于随机事件A和B的条件概率和边缘概率的一则定理。

    如上所示，其中P(A|B)是在B发生的情况下A发生的可能性。在贝叶斯定理中，每个名词都有约定俗成的名称：

• P(A)是A的先验概率或边缘概率。之所以称为"先验"是因為它不考虑任何B方面的因素。
• P(A|B)是已知B发生后A的条件概率（直白来讲，就是先有B而后=>才有A），也由于得自B的取值而被称作A的后验概率。
• P(B|A)是已知A发生后B的条件概率（直白来讲，就是先有A而后=>才有B），也由于得自A的取值而被称作B的后验概率。
• P(B)是B的先验概率或边缘概率，也作标准化常量（normalized constant）。

    按这些术语，Bayes定理可表述为：后验概率 = (相似度*先验概率)/标准化常量，也就是說，后验概率与先验概率和相似度的乘积成正比。另外，比例P(B|A)/P(B)也有时被称作标准相似度（standardised likelihood），Bayes定理可表述为：后验概率 = 标准相似度*先验概率。

2.2 贝叶斯公式如何而来

    贝叶斯公式是怎么来的？下面再举wikipedia 上的一个例子：

一所学校里面有 60% 的男生，40% 的女生。男生总是穿长裤，女生则一半穿长裤一半穿裙子。有了这些信息之后我们可以容易地计算“随机选取一个学生，他（她）穿长裤的概率和穿裙子的概率是多大”，这个就是前面说的“正向概率”的计算。然而，假设你走在校园中，迎面走来一个穿长裤的学生（很不幸的是你高度近似，你只看得见他（她）穿的是否长裤，而无法确定他（她）的性别），你能够推断出他（她）是男生的概率是多大吗？

    一些认知科学的研究表明（《决策与判断》以及《Rationality for Mortals》第12章：小孩也可以解决贝叶斯问题），我们对形式化的贝叶斯问题不擅长，但对于以频率形式呈现的等价问题却很擅长。在这里，我们不妨把问题重新叙述成：你在校园里面随机游走，遇到了 N 个穿长裤的人（仍然假设你无法直接观察到他们的性别），问这 N 个人里面有多少个女生多少个男生。

    你说，这还不简单：算出学校里面有多少穿长裤的，然后在这些人里面再算出有多少女生，不就行了？

    我们来算一算：假设学校里面人的总数是 U 个。60% 的男生都穿长裤，于是我们得到了 U * P(Boy) * P(Pants|Boy) 个穿长裤的（男生）（其中 P(Boy) 是男生的概率 = 60%，这里可以简单的理解为男生的比例；P(Pants|Boy) 是条件概率，即在 Boy 这个条件下穿长裤的概率是多大，这里是 100% ，因为所有男生都穿长裤）。40% 的女生里面又有一半（50%）是穿长裤的，于是我们又得到了 U * P(Girl) * P(Pants|Girl) 个穿长裤的（女生）。加起来一共是 U * P(Boy) * P(Pants|Boy) + U * P(Girl) * P(Pants|Girl) 个穿长裤的，其中有 U * P(Girl) * P(Pants|Girl) 个女生。两者一比就是你要求的答案。

    下面我们把这个答案形式化一下：我们要求的是 P(Girl|Pants) （穿长裤的人里面有多少女生），我们计算的结果是 U * P(Girl) * P(Pants|Girl) / [U * P(Boy) * P(Pants|Boy) + U * P(Girl) * P(Pants|Girl)] 。容易发现这里校园内人的总数是无关的，两边同时消去U，于是得到

 

P(Girl|Pants) = P(Girl) * P(Pants|Girl) / [P(Boy) * P(Pants|Boy) + P(Girl) * P(Pants|Girl)]

 

    注意，如果把上式收缩起来，分母其实就是 P(Pants) ，分子其实就是 P(Pants, Girl) 。而这个比例很自然地就读作：在穿长裤的人（ P(Pants) ）里面有多少（穿长裤）的女孩（ P(Pants, Girl) ）。

    上式中的 Pants 和 Boy/Girl 可以指代一切东西，So，其一般形式就是：

P(B|A) = P(A|B) * P(B) / [P(A|B) * P(B) + P(A|~B) * P(~B) ]

    收缩起来就是：

P(B|A) = P(AB) / P(A)

    其实这个就等于：

P(B|A) * P(A) = P(AB)

    更进一步阐述，P(B|A)便是在条件A的情况下，B出现的概率是多大。然看似这么平凡的贝叶斯公式，背后却隐含着非常深刻的原理。

2.3、拼写纠正

    经典著作《人工智能：现代方法》的作者之一 Peter Norvig 曾经写过一篇介绍如何写一个拼写检查/纠正器的文章，里面用到的就是贝叶斯方法，下面，将其核心思想简单描述下。

    首先，我们需要询问的是：“问题是什么？”

    问题是我们看到用户输入了一个不在字典中的单词，我们需要去猜测：“这个家伙到底真正想输入的单词是什么呢？”用刚才我们形式化的语言来叙述就是，我们需要求：

P(我们猜测他想输入的单词 | 他实际输入的单词)

    这个概率。并找出那个使得这个概率最大的猜测单词。显然，我们的猜测未必是唯一的，就像前面举的那个自然语言的歧义性的例子一样；这里，比如用户输入： thew ，那么他到底是想输入 the ，还是想输入 thaw ？到底哪个猜测可能性更大呢？幸运的是我们可以用贝叶斯公式来直接出它们各自的概率，我们不妨将我们的多个猜测记为 h1 h2 .. （ h 代表 hypothesis），它们都属于一个有限且离散的猜测空间 H （单词总共就那么多而已），将用户实际输入的单词记为 D （ D 代表 Data ，即观测数据），于是

P(我们的猜测1 | 他实际输入的单词)

    可以抽象地记为：

P(h1 | D)

    类似地，对于我们的猜测2，则是 P(h2 | D)。不妨统一记为：

P(h | D)

运用一次贝叶斯公式，我们得到：

P(h | D) = P(h) * P(D | h) / P(D)

    对于不同的具体猜测 h1 h2 h3 .. ，P(D) 都是一样的，所以在比较 P(h1 | D) 和 P(h2 | D) 的时候我们可以忽略这个常数。即我们只需要知道：

P(h | D) ∝ P(h) * P(D | h) （注：那个符号的意思是“正比例于”，不是无穷大，注意符号右端是有一个小缺口的。）

    这个式子的抽象含义是：对于给定观测数据，一个猜测是好是坏，取决于“这个猜测本身独立的可能性大小（先验概率，Prior ）”和“这个猜测生成我们观测到的数据的可能性大小”（似然，Likelihood ）的乘积。具体到我们的那个 thew 例子上，含义就是，用户实际是想输入 the 的可能性大小取决于 the 本身在词汇表中被使用的可能性（频繁程度）大小（先验概率）和 想打 the 却打成 thew 的可能性大小（似然）的乘积。

    剩下的事情就很简单了，对于我们猜测为可能的每个单词计算一下 P(h) * P(D | h) 这个值，然后取最大的，得到的就是最靠谱的猜测。更多细节请参看未鹏兄之原文。

2.4、贝叶斯的应用

2.4.1、中文分词

 

    贝叶斯是机器学习的核心方法之一。比如中文分词领域就用到了贝叶斯。浪潮之巅的作者吴军在《数学之美》系列中就有一篇是介绍中文分词的。这里介绍一下核心的思想，不做赘述，详细请参考吴军的原文。

    分词问题的描述为：给定一个句子（字串），如：

    南京市长江大桥

    如何对这个句子进行分词（词串）才是最靠谱的。例如：

1. 南京市/长江大桥

2. 南京/市长/江大桥

 

    这两个分词，到底哪个更靠谱呢？

    我们用贝叶斯公式来形式化地描述这个问题，令 X 为字串（句子），Y 为词串（一种特定的分词假设）。我们就是需要寻找使得 P(Y|X) 最大的 Y ，使用一次贝叶斯可得：

P(Y|X) ∝ P(Y)*P(X|Y)

     用自然语言来说就是 这种分词方式（词串）的可能性 乘以 这个词串生成我们的句子的可能性。我们进一步容易看到：可以近似地将 P(X|Y) 看作是恒等于 1 的，因为任意假想的一种分词方式之下生成我们的句子总是精准地生成的（只需把分词之间的分界符号扔掉即可）。于是，我们就变成了去最大化 P(Y) ，也就是寻找一种分词使得这个词串（句子）的概率最大化。而如何计算一个词串：

W1, W2, W3, W4 ..

    的可能性呢？我们知道，根据联合概率的公式展开：P(W1, W2, W3, W4 ..) = P(W1) * P(W2|W1) * P(W3|W2, W1) * P(W4|W1,W2,W3) * .. 于是我们可以通过一系列的条件概率（右式）的乘积来求整个联合概率。然而不幸的是随着条件数目的增加（P(Wn|Wn-1,Wn-2,..,W1) 的条件有 n-1 个），数据稀疏问题也会越来越严重，即便语料库再大也无法统计出一个靠谱的 P(Wn|Wn-1,Wn-2,..,W1) 来。为了缓解这个问题，计算机科学家们一如既往地使用了“天真”假设：我们假设句子中一个词的出现概率只依赖于它前面的有限的 k 个词（k 一般不超过 3，如果只依赖于前面的一个词，就是2元语言模型（2-gram），同理有 3-gram 、 4-gram 等），这个就是所谓的“有限地平线”假设。

     虽然上面这个假设很傻很天真，但结果却表明它的结果往往是很好很强大的，后面要提到的朴素贝叶斯方法使用的假设跟这个精神上是完全一致的，我们会解释为什么像这样一个天真的假设能够得到强大的结果。目前我们只要知道，有了这个假设，刚才那个乘积就可以改写成： P(W1) * P(W2|W1) * P(W3|W2) * P(W4|W3) .. （假设每个词只依赖于它前面的一个词）。而统计 P(W2|W1) 就不再受到数据稀疏问题的困扰了。对于我们上面提到的例子“南京市长江大桥”，如果按照自左到右的贪婪方法分词的话，结果就成了“南京市长/江大桥”。但如果按照贝叶斯分词的话（假设使用 3-gram），由于“南京市长”和“江大桥”在语料库中一起出现的频率为 0 ，这个整句的概率便会被判定为 0 。 从而使得“南京市/长江大桥”这一分词方式胜出。

 

2.4.2、贝叶斯图像识别，Analysis by Synthesis

    贝叶斯方法是一个非常 general 的推理框架。其核心理念可以描述成：Analysis by Synthesis （通过合成来分析）。06 年的认知科学新进展上有一篇 paper 就是讲用贝叶斯推理来解释视觉识别的，一图胜千言，下图就是摘自这篇 paper ：

 

 

 

 

    首先是视觉系统提取图形的边角特征，然后使用这些特征自底向上地激活高层的抽象概念（比如是 E 还是 F 还是等号），然后使用一个自顶向下的验证来比较到底哪个概念最佳地解释了观察到的图像。

2.4.3、最大似然与最小二乘

 

 

 

 

    学过线性代数的大概都知道经典的最小二乘方法来做线性回归。问题描述是：给定平面上 N 个点，（这里不妨假设我们想用一条直线来拟合这些点——回归可以看作是拟合的特例，即允许误差的拟合），找出一条最佳描述了这些点的直线。

    一个接踵而来的问题就是，我们如何定义最佳？我们设每个点的坐标为 (Xi, Yi) 。如果直线为 y = f(x) 。那么 (Xi, Yi) 跟直线对这个点的“预测”：(Xi, f(Xi)) 就相差了一个 ΔYi = |Yi – f(Xi)| 。最小二乘就是说寻找直线使得 (ΔY1)^2 + (ΔY2)^2 + .. （即误差的平方和）最小，至于为什么是误差的平方和而不是误差的绝对值和，统计学上也没有什么好的解释。然而贝叶斯方法却能对此提供一个完美的解释。

    我们假设直线对于坐标 Xi 给出的预测 f(Xi) 是最靠谱的预测，所有纵坐标偏离 f(Xi) 的那些数据点都含有噪音，是噪音使得它们偏离了完美的一条直线，一个合理的假设就是偏离路线越远的概率越小，具体小多少，可以用一个正态分布曲线来模拟，这个分布曲线以直线对 Xi 给出的预测 f(Xi) 为中心，实际纵坐标为 Yi 的点 (Xi, Yi) 发生的概率就正比于 EXP[-(ΔYi)^2]。（EXP(..) 代表以常数 e 为底的多少次方）。

    现在我们回到问题的贝叶斯方面，我们要想最大化的后验概率是：

P(h|D) ∝ P(h) * P(D|h)

 

    又见贝叶斯！这里 h 就是指一条特定的直线，D 就是指这 N 个数据点。我们需要寻找一条直线 h 使得 P(h) * P(D|h) 最大。很显然，P(h) 这个先验概率是均匀的，因为哪条直线也不比另一条更优越。所以我们只需要看 P(D|h) 这一项，这一项是指这条直线生成这些数据点的概率，刚才说过了，生成数据点 (Xi, Yi) 的概率为 EXP[-(ΔYi)^2] 乘以一个常数。而 P(D|h) = P(d1|h) * P(d2|h) * .. 即假设各个数据点是独立生成的，所以可以把每个概率乘起来。于是生成 N 个数据点的概率为 EXP[-(ΔY1)^2] * EXP[-(ΔY2)^2] * EXP[-(ΔY3)^2] * .. = EXP{-[(ΔY1)^2 + (ΔY2)^2 + (ΔY3)^2 + ..]} 最大化这个概率就是要最小化 (ΔY1)^2 + (ΔY2)^2 + (ΔY3)^2 + .. 。 熟悉这个式子吗？

    除了以上所介绍的之外，贝叶斯还在词义消岐，语言模型的平滑方法中都有一定应用。下节，咱们再来简单看下朴素贝叶斯方法。

2.5、朴素贝叶斯方法

    朴素贝叶斯方法是一个很特别的方法，所以值得介绍一下。在众多的分类模型中，应用最为广泛的两种分类模型是决策树模型(Decision Tree Model)和朴素贝叶斯模型（Naive Bayesian Model，NBC）。 朴素贝叶斯模型发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。
     同时，NBC模型所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。理论上，NBC模型与其他分类方法相比具有最小的误差率。但是实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的，这给NBC模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC模型的性能最为良好。

    接下来，我们用朴素贝叶斯在垃圾邮件过滤中的应用来举例说明。

2.5.1、贝叶斯垃圾邮件过滤器

    问题是什么？问题是，给定一封邮件，判定它是否属于垃圾邮件。按照先例，我们还是用 D 来表示这封邮件，注意 D 由 N 个单词组成。我们用 h+ 来表示垃圾邮件，h- 表示正常邮件。问题可以形式化地描述为求：

P(h+|D) = P(h+) * P(D|h+) / P(D)

 

P(h-|D) = P(h-) * P(D|h-) / P(D)

 

    其中 P(h+) 和 P(h-) 这两个先验概率都是很容易求出来的，只需要计算一个邮件库里面垃圾邮件和正常邮件的比例就行了。然而 P(D|h+) 却不容易求，因为 D 里面含有 N 个单词 d1, d2, d3, .. ，所以P(D|h+) = P(d1,d2,..,dn|h+) 。我们又一次遇到了数据稀疏性，为什么这么说呢？P(d1,d2,..,dn|h+) 就是说在垃圾邮件当中出现跟我们目前这封邮件一模一样的一封邮件的概率是多大！开玩笑，每封邮件都是不同的，世界上有无穷多封邮件。瞧，这就是数据稀疏性，因为可以肯定地说，你收集的训练数据库不管里面含了多少封邮件，也不可能找出一封跟目前这封一模一样的。结果呢？我们又该如何来计算 P(d1,d2,..,dn|h+) 呢？

    我们将 P(d1,d2,..,dn|h+)  扩展为： P(d1|h+) * P(d2|d1, h+) * P(d3|d2,d1, h+) * .. 。熟悉这个式子吗？这里我们会使用一个更激进的假设，我们假设 di 与 di-1 是完全条件无关的，于是式子就简化为 P(d1|h+) * P(d2|h+) * P(d3|h+) * .. 。这个就是所谓的条件独立假设，也正是朴素贝叶斯方法的朴素之处。而计算 P(d1|h+) * P(d2|h+) * P(d3|h+) * .. 就太简单了，只要统计 di 这个单词在垃圾邮件中出现的频率即可。关于贝叶斯垃圾邮件过滤更多的内容可以参考这个条目，注意其中提到的其他资料。

2.6、层级贝叶斯模型

 

 

 

 

    层级贝叶斯模型是现代贝叶斯方法的标志性建筑之一。前面讲的贝叶斯，都是在同一个事物层次上的各个因素之间进行统计推理，然而层次贝叶斯模型在哲学上更深入了一层，将这些因素背后的因素（原因的原因，原因的原因，以此类推）囊括进来。一个教科书例子是：如果你手头有 N 枚硬币，它们是同一个工厂铸出来的，你把每一枚硬币掷出一个结果，然后基于这 N 个结果对这 N 个硬币的 θ （出现正面的比例）进行推理。如果根据最大似然，每个硬币的 θ 不是 1 就是 0 （这个前面提到过的），然而我们又知道每个硬币的 p(θ) 是有一个先验概率的，也许是一个 beta 分布。也就是说，每个硬币的实际投掷结果 Xi 服从以 θ 为中心的正态分布，而 θ 又服从另一个以 Ψ 为中心的 beta 分布。层层因果关系就体现出来了。进而 Ψ 还可能依赖于因果链上更上层的因素，以此类推。

2.7、基于newsgroup文档集的贝叶斯算法实现

2.7.1、newsgroup文档集介绍与预处理

    Newsgroups最早由Lang于1995收集并在[Lang 1995]中使用。它含有20000篇左右的Usenet文档，几乎平均分配20个不同的新闻组。除了其中4.5%的文档属于两个或两个以上的新闻组以外，其余文档仅属于一个新闻组，因此它通常被作为单标注分类问题来处理。Newsgroups已经成为文本分类聚类中常用的文档集。美国MIT大学Jason Rennie对Newsgroups作了必要的处理，使得每个文档只属于一个新闻组，形成Newsgroups-18828。 

 

 （注：本2.7节内容主要援引自参考文献条目8的内容，有任何不妥之处，还望原作者及众读者海涵，谢谢)

 

    要做文本分类首先得完成文本的预处理，预处理的主要步骤如下：

1. 英文词法分析，去除数字、连字符、标点符号、特殊 字符，所有大写字母转换成小写，可以用正则表达式：String res[] = line.split("[^a-zA-Z]")；
2. 去停用词，过滤对分类无价值的词；
3. 词根还原stemming，基于Porter算法。

1. private static String lineProcess(String line, ArrayList<String> stopWordsArray) throws IOException {    
2.     // TODO Auto-generated method stub    
3.     //step1 英文词法分析，去除数字、连字符、标点符号、特殊字符，所有大写字母转换成小写，可以考虑用正则表达式    
4.     String res[] = line.split("[^a-zA-Z]");    
5.     //这里要小心，防止把有单词中间有数字和连字符的单词 截断了，但是截断也没事    
6.         
7.     String resString = new String();    
8.     //step2去停用词    
9.     //step3stemming,返回后一起做    
10.     for(int i = 0; i < res.length; i++){    
11.         if(!res[i].isEmpty() && !stopWordsArray.contains(res[i].toLowerCase())){    
12.             resString += " " + res[i].toLowerCase() + " ";    
13.         }    
14.     }    
15.     return resString;    
16. }   

2.7.2、特征词的选取

    首先统计经过预处理后在所有文档中出现不重复的单词一共有87554个，对这些词进行统计发现：
出现次数大于等于1次的词有87554个
出现次数大于等于3次的词有36456个 
出现次数大于等于4次的词有30095个
    特征词的选取策略：
策略一：保留所有词作为特征词 共计87554个
策略二：选取出现次数大于等于4次的词作为特征词共计30095个 
    特征词的选取策略：采用策略一，后面将对两种特征词选取策略的计算时间和平均准确率做对比

2.7.3、贝叶斯算法描述及实现

 

    根据朴素贝叶斯公式，每个测试样例属于某个类别的概率 =  所有测试样例包含特征词类条件概率P(tk|c)之积 * 先验概率P(c)

在具体计算类条件概率和先验概率时，朴素贝叶斯分类器有两种模型：

    (1) 多项式模型( multinomial model )  –以单词为粒度
类条件概率P(tk|c)=(类c下单词tk在各个文档中出现过的次数之和+1)/（类c下单词总数+训练样本中不重复特征词总数）
先验概率P(c)=类c下的单词总数/整个训练样本的单词总数

    (2) 伯努利模型（Bernoulli model）   –以文件为粒度

类条件概率P(tk|c)=（类c下包含单词tk的文件数+1）/(类c下文件总数+2)

先验概率P(c)=类c下文件总数/整个训练样本的文件总数
本分类器选用多项式模型计算，根据斯坦福的《Introduction to Information Retrieval 》课件上所说，多项式模型计算准确率更高。

    贝叶斯算法的实现有以下注意点：

1. 计算概率用到了BigDecimal类实现任意精度计算；
2. 用交叉验证法做十次分类实验，对准确率取平均值；
3. 根据正确类目文件和分类结果文计算混淆矩阵并且输出；
4.  Map<String,Double> cateWordsProb key为“类目_单词”, value为该类目下该单词的出现次数，避免重复计算。

    贝叶斯算法实现类如下NaiveBayesianClassifier.java（author：yangliu）

 

1. package com.pku.yangliu;  
2. import java.io.BufferedReader;  
3. import java.io.File;  
4. import java.io.FileReader;  
5. import java.io.FileWriter;  
6. import java.io.IOException;  
7. import java.math.BigDecimal;  
8. import java.util.Iterator;  
9. import java.util.Map;  
10. import java.util.Set;  
11. import java.util.SortedSet;  
12. import java.util.TreeMap;  
13. import java.util.TreeSet;  
14. import java.util.Vector;  
15.   
16. /**利用朴素贝叶斯算法对newsgroup文档集做分类，采用十组交叉测试取平均值 
17.  * 采用多项式模型,stanford信息检索导论课件上面言多项式模型比伯努利模型准确度高 
18.  * 类条件概率P(tk|c)=(类c 下单词tk 在各个文档中出现过的次数之和+1)/(类c下单词总数+|V|) 
19.  */  
20. public class NaiveBayesianClassifier {  
21.       
22.     /**用贝叶斯法对测试文档集分类 
23.      * @param trainDir 训练文档集目录 
24.      * @param testDir 测试文档集目录 
25.      * @param classifyResultFileNew 分类结果文件路径 
26.      * @throws Exception  
27.      */  
28.     private void doProcess(String trainDir, String testDir,  
29.             String classifyResultFileNew) throws Exception {  
30.         // TODO Auto-generated method stub  
31.         Map<String,Double> cateWordsNum = new TreeMap<String,Double>();//保存训练集每个类别的总词数  
32.         Map<String,Double> cateWordsProb = new TreeMap<String,Double>();//保存训练样本每个类别中每个属性词的出现词数  
33.         cateWordsProb = getCateWordsProb(trainDir);  
34.         cateWordsNum = getCateWordsNum(trainDir);  
35.         double totalWordsNum = 0.0;//记录所有训练集的总词数  
36.         Set<Map.Entry<String,Double>> cateWordsNumSet = cateWordsNum.entrySet();  
37.         for(Iterator<Map.Entry<String,Double>> it = cateWordsNumSet.iterator(); it.hasNext();){  
38.             Map.Entry<String, Double> me = it.next();  
39.             totalWordsNum += me.getValue();  
40.         }  
41.         //下面开始读取测试样例做分类  
42.         Vector<String> testFileWords = new Vector<String>();  
43.         String word;  
44.         File[] testDirFiles = new File(testDir).listFiles();  
45.         FileWriter crWriter = new FileWriter(classifyResultFileNew);  
46.         for(int i = 0; i < testDirFiles.length; i++){  
47.             File[] testSample = testDirFiles[i].listFiles();  
48.             for(int j = 0;j < testSample.length; j++){  
49.                 testFileWords.clear();  
50.                 FileReader spReader = new FileReader(testSample[j]);  
51.                 BufferedReader spBR = new BufferedReader(spReader);  
52.                 while((word = spBR.readLine()) != null){  
53.                     testFileWords.add(word);  
54.                 }  
55.                 //下面分别计算该测试样例属于二十个类别的概率  
56.                 File[] trainDirFiles = new File(trainDir).listFiles();  
57.                 BigDecimal maxP = new BigDecimal(0);  
58.                 String bestCate = null;  
59.                 for(int k = 0; k < trainDirFiles.length; k++){  
60.                     BigDecimal p = computeCateProb(trainDirFiles[k], testFileWords, cateWordsNum, totalWordsNum, cateWordsProb);  
61.                     if(k == 0){  
62.                         maxP = p;  
63.                         bestCate = trainDirFiles[k].getName();  
64.                         continue;  
65.                     }  
66.                     if(p.compareTo(maxP) == 1){  
67.                         maxP = p;  
68.                         bestCate = trainDirFiles[k].getName();  
69.                     }  
70.                 }  
71.                 crWriter.append(testSample[j].getName() + " " + bestCate + "\n");  
72.                 crWriter.flush();  
73.             }  
74.         }  
75.         crWriter.close();  
76.     }  
77.       
78.     /**统计某类训练样本中每个单词的出现次数 
79.      * @param strDir 训练样本集目录 
80.      * @return Map<String,Double> cateWordsProb 用"类目_单词"对来索引的map,保存的val就是该类目下该单词的出现次数 
81.      * @throws IOException  
82.      */  
83.     public Map<String,Double> getCateWordsProb(String strDir) throws IOException{  
84.         Map<String,Double> cateWordsProb = new TreeMap<String,Double>();  
85.         File sampleFile = new File(strDir);  
86.         File [] sampleDir = sampleFile.listFiles();  
87.         String word;  
88.         for(int i = 0;i < sampleDir.length; i++){  
89.             File [] sample = sampleDir[i].listFiles();  
90.             for(int j = 0; j < sample.length; j++){  
91.                 FileReader samReader = new FileReader(sample[j]);  
92.                 BufferedReader samBR = new BufferedReader(samReader);  
93.                 while((word = samBR.readLine()) != null){  
94.                     String key = sampleDir[i].getName() + "_" + word;  
95.                     if(cateWordsProb.containsKey(key)){  
96.                         double count = cateWordsProb.get(key) + 1.0;  
97.                         cateWordsProb.put(key, count);  
98.                     }  
99.                     else {  
100.                         cateWordsProb.put(key, 1.0);  
101.                     }  
102.                 }  
103.             }  
104.         }  
105.         return cateWordsProb;     
106.     }  
107.       
108.     /**计算某一个测试样本属于某个类别的概率 
109.      * @param Map<String, Double> cateWordsProb 记录每个目录中出现的单词及次数  
110.      * @param File trainFile 该类别所有的训练样本所在目录 
111.      * @param Vector<String> testFileWords 该测试样本中的所有词构成的容器 
112.      * @param double totalWordsNum 记录所有训练样本的单词总数 
113.      * @param Map<String, Double> cateWordsNum 记录每个类别的单词总数 
114.      * @return BigDecimal 返回该测试样本在该类别中的概率 
115.      * @throws Exception  
116.      * @throws IOException  
117.      */  
118.     private BigDecimal computeCateProb(File trainFile, Vector<String> testFileWords, Map<String, Double> cateWordsNum, double totalWordsNum, Map<String, Double> cateWordsProb) throws Exception {  
119.         // TODO Auto-generated method stub  
120.         BigDecimal probability = new BigDecimal(1);  
121.         double wordNumInCate = cateWordsNum.get(trainFile.getName());  
122.         BigDecimal wordNumInCateBD = new BigDecimal(wordNumInCate);  
123.         BigDecimal totalWordsNumBD = new BigDecimal(totalWordsNum);  
124.         for(Iterator<String> it = testFileWords.iterator(); it.hasNext();){  
125.             String me = it.next();  
126.             String key = trainFile.getName()+"_"+me;  
127.             double testFileWordNumInCate;  
128.             if(cateWordsProb.containsKey(key)){  
129.                 testFileWordNumInCate = cateWordsProb.get(key);  
130.             }else testFileWordNumInCate = 0.0;  
131.             BigDecimal testFileWordNumInCateBD = new BigDecimal(testFileWordNumInCate);  
132.             BigDecimal xcProb = (testFileWordNumInCateBD.add(new BigDecimal(0.0001))).divide(totalWordsNumBD.add(wordNumInCateBD),10, BigDecimal.ROUND_CEILING);  
133.             probability = probability.multiply(xcProb);  
134.         }  
135.         BigDecimal res = probability.multiply(wordNumInCateBD.divide(totalWordsNumBD,10, BigDecimal.ROUND_CEILING));  
136.         return res;  
137.     }  
138.   
139.     /**获得每个类目下的单词总数 
140.      * @param trainDir 训练文档集目录 
141.      * @return Map<String, Double> <目录名，单词总数>的map 
142.      * @throws IOException  
143.      */  
144.     private Map<String, Double> getCateWordsNum(String trainDir) throws IOException {  
145.         // TODO Auto-generated method stub  
146.         Map<String,Double> cateWordsNum = new TreeMap<String,Double>();  
147.         File[] sampleDir = new File(trainDir).listFiles();  
148.         for(int i = 0; i < sampleDir.length; i++){  
149.             double count = 0;  
150.             File[] sample = sampleDir[i].listFiles();  
151.             for(int j = 0;j < sample.length; j++){  
152.                 FileReader spReader = new FileReader(sample[j]);  
153.                 BufferedReader spBR = new BufferedReader(spReader);  
154.                 while(spBR.readLine() != null){  
155.                     count++;  
156.                 }         
157.             }  
158.             cateWordsNum.put(sampleDir[i].getName(), count);  
159.         }  
160.         return cateWordsNum;  
161.     }  
162.       
163.     /**根据正确类目文件和分类结果文件统计出准确率 
164.      * @param classifyResultFile 正确类目文件 
165.      * @param classifyResultFileNew 分类结果文件 
166.      * @return double 分类的准确率 
167.      * @throws IOException  
168.      */  
169.     double computeAccuracy(String classifyResultFile,  
170.             String classifyResultFileNew) throws IOException {  
171.         // TODO Auto-generated method stub  
172.         Map<String,String> rightCate = new TreeMap<String,String>();  
173.         Map<String,String> resultCate = new TreeMap<String,String>();  
174.         rightCate = getMapFromResultFile(classifyResultFile);  
175.         resultCate = getMapFromResultFile(classifyResultFileNew);  
176.         Set<Map.Entry<String, String>> resCateSet = resultCate.entrySet();  
177.         double rightCount = 0.0;  
178.         for(Iterator<Map.Entry<String, String>> it = resCateSet.iterator(); it.hasNext();){  
179.             Map.Entry<String, String> me = it.next();  
180.             if(me.getValue().equals(rightCate.get(me.getKey()))){  
181.                 rightCount ++;  
182.             }  
183.         }  
184.         computerConfusionMatrix(rightCate,resultCate);  
185.         return rightCount / resultCate.size();    
186.     }  
187.       
188.     /**根据正确类目文件和分类结果文计算混淆矩阵并且输出 
189.      * @param rightCate 正确类目对应map 
190.      * @param resultCate 分类结果对应map 
191.      * @return double 分类的准确率 
192.      * @throws IOException  
193.      */  
194.     private void computerConfusionMatrix(Map<String, String> rightCate,  
195.             Map<String, String> resultCate) {  
196.         // TODO Auto-generated method stub    
197.         int[][] confusionMatrix = new int[20][20];  
198.         //首先求出类目对应的数组索引  
199.         SortedSet<String> cateNames = new TreeSet<String>();  
200.         Set<Map.Entry<String, String>> rightCateSet = rightCate.entrySet();  
201.         for(Iterator<Map.Entry<String, String>> it = rightCateSet.iterator(); it.hasNext();){  
202.             Map.Entry<String, String> me = it.next();  
203.             cateNames.add(me.getValue());  
204.         }  
205.         cateNames.add("rec.sport.baseball");//防止数少一个类目  
206.         String[] cateNamesArray = cateNames.toArray(new String[0]);  
207.         Map<String,Integer> cateNamesToIndex = new TreeMap<String,Integer>();  
208.         for(int i = 0; i < cateNamesArray.length; i++){  
209.             cateNamesToIndex.put(cateNamesArray[i],i);  
210.         }  
211.         for(Iterator<Map.Entry<String, String>> it = rightCateSet.iterator(); it.hasNext();){  
212.             Map.Entry<String, String> me = it.next();  
213.             confusionMatrix[cateNamesToIndex.get(me.getValue())][cateNamesToIndex.get(resultCate.get(me.getKey()))]++;  
214.         }  
215.         //输出混淆矩阵  
216.         double[] hangSum = new double[20];  
217.         System.out.print("    ");  
218.         for(int i = 0; i < 20; i++){  
219.             System.out.print(i + "    ");  
220.         }  
221.         System.out.println();  
222.         for(int i = 0; i < 20; i++){  
223.             System.out.print(i + "    ");  
224.             for(int j = 0; j < 20; j++){  
225.                 System.out.print(confusionMatrix[i][j]+"    ");  
226.                 hangSum[i] += confusionMatrix[i][j];  
227.             }  
228.             System.out.println(confusionMatrix[i][i] / hangSum[i]);  
229.         }  
230.         System.out.println();  
231.     }  
232.   
233.     /**从分类结果文件中读取map 
234.      * @param classifyResultFileNew 类目文件 
235.      * @return Map<String, String> 由<文件名，类目名>保存的map 
236.      * @throws IOException  
237.      */  
238.     private Map<String, String> getMapFromResultFile(  
239.             String classifyResultFileNew) throws IOException {  
240.         // TODO Auto-generated method stub  
241.         File crFile = new File(classifyResultFileNew);  
242.         FileReader crReader = new FileReader(crFile);  
243.         BufferedReader crBR = new BufferedReader(crReader);  
244.         Map<String, String> res = new TreeMap<String, String>();  
245.         String[] s;  
246.         String line;  
247.         while((line = crBR.readLine()) != null){  
248.             s = line.split(" ");  
249.             res.put(s[0], s[1]);      
250.         }  
251.         return res;  
252.     }  
253.   
254.     /** 
255.      * @param args 
256.      * @throws Exception  
257.      */  
258.     public void NaiveBayesianClassifierMain(String[] args) throws Exception {  
259.          //TODO Auto-generated method stub  
260.         //首先创建训练集和测试集  
261.         CreateTrainAndTestSample ctt = new CreateTrainAndTestSample();  
262.         NaiveBayesianClassifier nbClassifier = new NaiveBayesianClassifier();  
263.         ctt.filterSpecialWords();//根据包含非特征词的文档集生成只包含特征词的文档集到processedSampleOnlySpecial目录下  
264.         double[] accuracyOfEveryExp = new double[10];  
265.         double accuracyAvg,sum = 0;  
266.         for(int i = 0; i < 10; i++){//用交叉验证法做十次分类实验，对准确率取平均值   
267.             String TrainDir = "F:/DataMiningSample/TrainSample"+i;  
268.             String TestDir = "F:/DataMiningSample/TestSample"+i;  
269.             String classifyRightCate = "F:/DataMiningSample/classifyRightCate"+i+".txt";  
270.             String classifyResultFileNew = "F:/DataMiningSample/classifyResultNew"+i+".txt";  
271.             ctt.createTestSamples("F:/DataMiningSample/processedSampleOnlySpecial", 0.9, i,classifyRightCate);  
272.             nbClassifier.doProcess(TrainDir,TestDir,classifyResultFileNew);  
273.             accuracyOfEveryExp[i] = nbClassifier.computeAccuracy (classifyRightCate, classifyResultFileNew);  
274.             System.out.println("The accuracy for Naive Bayesian Classifier in "+i+"th Exp is :" + accuracyOfEveryExp[i]);  
275.         }  
276.         for(int i = 0; i < 10; i++){  
277.             sum += accuracyOfEveryExp[i];  
278.         }  
279.         accuracyAvg = sum / 10;  
280.         System.out.println("The average accuracy for Naive Bayesian Classifier in all Exps is :" + accuracyAvg);  
281.           
282.     }  
283. }  

 

 

2.7.4、朴素贝叶斯算法对newsgroup文档集做分类的结果

    在经过一系列Newsgroup文档预处理、特征词的选取、及实现了贝叶斯算法之后，下面用朴素贝叶斯算法那对newsgroup文档集做分类，看看此贝叶斯算法的效果。

    贝叶斯算法分类结果-混淆矩阵表示，以交叉验证的第6次实验结果为例，分类准确率最高达到80.47%。

 

    程序运行硬件环境：Intel Core 2 Duo CPU T5750 2GHZ, 2G内存，实验结果如下：
    取所有词共87554个作为特征词：10次交叉验证实验平均准确率78.19%，用时23min,准确率范围75.65%-80.47%，第6次实验准确率超过80%，取出现次数大于等于4次的词共计30095个作为特征词： 10次交叉验证实验平均准确率77.91%，用时22min，准确率范围75.51%-80.26%，第6次实验准确率超过80%。如下图所示：

 

     结论：朴素贝叶斯算法不必去除出现次数很低的词，因为出现次数很低的词的IDF比较   大，去除后分类准确率下降，而计算时间并没有显著减少

2.7.5、贝叶斯算法的改进

    为了进一步提高贝叶斯算法的分类准确率，可以考虑

1. 优化特征词的选取策略；
2. 改进多项式模型的类条件概率的计算公式，改进为 类条件概率P(tk|c)=(类c下单词tk在各个文档中出现过的次数之和+0.001)/（类c下单词总数+训练样本中不重复特征词总数），分子当tk没有出现时，只加0.001(之前上面2.7.3节是+1)，这样更加精确的描述的词的统计分布规律，

    做此改进后的混淆矩阵如下

 

    可以看到第6次分组实验的准确率提高到84.79%，第7词分组实验的准确率达到85.24%，平均准确率由77.91%提高到了82.23%,优化效果还是很明显的。更多内容，请参考原文：参考文献条目8。谢谢。

 

 

第三部分、从EM算法到隐马可夫模型（HMM）

 

3.1、EM 算法与基于模型的聚类

     在统计计算中，最大期望 （EM，Expectation–Maximization）算法是在概率（probabilistic）模型中寻找参数最大似然估计的算法，其中概率模型依赖于无法观测的隐藏变量（Latent Variabl）。最大期望经常用在机器学习和计算机视觉的数据集聚（Data Clustering）领域。

    通常来说，聚类是一种无指导的机器学习问题，如此问题描述：给你一堆数据点，让你将它们最靠谱地分成一堆一堆的。聚类算法很多，不同的算法适应于不同的问题，这里仅介绍一个基于模型的聚类，该聚类算法对数据点的假设是，这些数据点分别是围绕 K 个核心的 K 个正态分布源所随机生成的，使用 Han JiaWei 的《Data Ming： Concepts and Techniques》中的图：

 

 

 

 

    图中有两个正态分布核心，生成了大致两堆点。我们的聚类算法就是需要根据给出来的那些点，算出这两个正态分布的核心在什么位置，以及分布的参数是多少。这很明显又是一个贝叶斯问题，但这次不同的是，答案是连续的且有无穷多种可能性，更糟的是，只有当我们知道了哪些点属于同一个正态分布圈的时候才能够对这个分布的参数作出靠谱的预测，现在两堆点混在一块我们又不知道哪些点属于第一个正态分布，哪些属于第二个。反过来，只有当我们对分布的参数作出了靠谱的预测时候，才能知道到底哪些点属于第一个分布，那些点属于第二个分布。这就成了一个先有鸡还是先有蛋的问题了。为了解决这个循环依赖，总有一方要先打破僵局，说，不管了，我先随便整一个值出来，看你怎么变，然后我再根据你的变化调整我的变化，然后如此迭代着不断互相推导，最终收敛到一个解。这就是 EM 算法。

    EM 的意思是“Expectation-Maximazation”，在这个聚类问题里面，我们是先随便猜一下这两个正态分布的参数：如核心在什么地方，方差是多少。然后计算出每个数据点更可能属于第一个还是第二个正态分布圈，这个是属于 Expectation 一步。有了每个数据点的归属，我们就可以根据属于第一个分布的数据点来重新评估第一个分布的参数（从蛋再回到鸡），这个是 Maximazation 。如此往复，直到参数基本不再发生变化为止。这个迭代收敛过程中的贝叶斯方法在第二步，根据数据点求分布的参数上面。

3.2、隐马可夫模型（HMM）

    大多的书籍或论文都讲不清楚这个隐马可夫模型(HMM)，包括未鹏兄之原文也讲得不够具体明白。接下来，我尽量用直白易懂的语言阐述这个模型。然在介绍隐马可夫模型之前，有必要先行介绍下单纯的马可夫模型(本节主要引用：统计自然语言处理，宗成庆编著一书上的相关内容)。

3.2.1、马可夫模型

    我们知道，随机过程又称随机函数，是随时间而随机变化的过程。马可夫模型便是描述了一类重要的随机过程。我们常常需要考察一个随机变量序列，这些随机变量并不是相互独立的(注意：理解这个非相互独立，即相互之间有千丝万缕的联系)。

    如果此时，我也搞一大推状态方程式，恐怕我也很难逃脱越讲越复杂的怪圈了。所以，直接举例子吧，如，一段文字中名词、动词、形容词三类词性出现的情况可由三个状态的马尔科夫模型描述如下：

 

状态s1：名词
状态s2：动词
状态s3：形容词

 

假设状态之间的转移矩阵如下：

 

                                s1    s2    s3
                        s1   0.3      0.5    0.2
    A = [aij] =     s2   0.5      0.3    0.2
                        s3   0.4      0.2     0.4

 

    如果在该段文字中某一个句子的第一个词为名词，那么根据这一模型M，在该句子中这三类词出现顺序为O="名动形名”的概率为：

    P(O|M)=P(s1，s2，s3，s1 | M) = P(s1) ×　P(s2 | s1) * P(s3 | s2)*P(s1 | s3)
                =1* a12 * a23 * a31=0.5*0.2*0.4=0.004

    马尔可夫模型又可视为随机的有限状态机。马尔柯夫链可以表示成状态图（转移弧上有概率的非确定的有限状态自动机），如下图所示，

    在上图中，圆圈表示状态，状态之间的转移用带箭头的弧表示，弧上的数字为状态转移的概率，初始状态用标记为start的输入箭头表示，假设任何状态都可作为终止状态。图中零概率的转移弧省略，且每个节点上所有发出弧的概率之和等于1。从上图可以看出，马尔可夫模型可以看做是一个转移弧上有概率的非确定的有限状态自动机。

3.2.2、隐马可夫模型(HMM)

    在上文介绍的马可夫模型中，每个状态代表了一个可观察的事件，所以，马可夫模型有时又称作视马可夫模型(VMM)，这在某种程度上限制了模型的适应性。而在我们的隐马可夫模型(HMM)中，我们不知道模型所经过的状态序列，只知道状态的概率函数，也就是说，观察到的事件是状态的随机函数，因此改模型是一个双重的随机过程。其中，模型的状态转换是不可观察的，即隐蔽的，可观察事件的随机过程是隐蔽的状态过程的随机函数。

    

    理论多说无益，接下来，留个思考题给读者：N 个袋子，每个袋子中有M 种不同颜色的球。一实验员根据某一概率分布选择一个袋子，然后根据袋子中不同颜色球的概率分布随机取出一个球，并报告该球的颜色。对局外人：可观察的过程是不同颜色球的序列，而袋子的序列是不可观察的。每只袋子对应HMM中的一个状态；球的颜色对应于HMM 中状态的输出。

3.2.2、HMM在中文分词、机器翻译等方面的具体应用

    隐马可夫模型在很多方面都有着具体的应用，如由于隐马可夫模型HMM提供了一个可以综合利用多种语言信息的统计框架，因此，我们完全可以讲汉语自动分词与词性标注统一考察，建立基于HMM的分词与词性标注的一体化系统。

    根据上文对HMM的介绍，一个HMM通常可以看做由两部分组成：一个是状态转移模型，一个是状态到观察序列的生成模型。具体到中文分词这一问题中，可以把汉字串或句子S作为输入，单词串Sw为状态的输出，即观察序列，Sw=w1w2w3...wN(N>=1)，词性序列St为状态序列，每个词性标记ct对应HMM中的一个状态qi，Sc=c1c2c3...cn。

    那么，利用HMM处理问题问题恰好对应于解决HMM的三个基本问题：

 

1. 估计模型的参数；
2. 对于一个给定的输入S及其可能的输出序列Sw和模型u=(A，B，*)，快速地计算P(Sw|u)，所有可能的Sw中使概率P(Sw|u)最大的解就是要找的分词效果；
3. 快速地选择最优的状态序列或词性序列，使其最好地解释观察序列。

    除中文分词方面的应用之外，HMM还在统计机器翻译中有应用，如基于HMM的词对位模型，更多请参考：统计自然语言处理，宗成庆编著。

    注：本文着重讲决策树分类和贝叶斯分类算法，后面的EM、HMM都是一笔带过，篇幅有限+懒，未能详尽阐述。日后，有机会，会再讲讲EM和HMM算法的。当然，你还可以先看看一个叫做HMM学习最佳范例的系列，原文写得好，翻译也翻译的精彩，推荐给大家：http://www.52nlp.cn/category/hidden-markov-model/page/4。

原文：http://xiaofeng1982.blog.163.com/blog/static/31572458201210214454770/