朴素贝叶斯分类器的应用

原文：http://www.ruanyifeng.com/blog/2013/12/naive_bayes_classifier.html

生活中很多场合需要用到分类，比如新闻分类、病人分类等等。

本文介绍朴素贝叶斯分类器（Naive Bayes classifier），它是一种简单有效的常用分类算法。

分类法

一、病人分类的例子

让我从一个例子开始讲起，你会看到贝叶斯分类器很好懂，一点都不难。

某个医院早上收了六个门诊病人，如下表。

　　症状　　职业　　　疾病

　　打喷嚏　护士　　　感冒
　　打喷嚏　农夫　　　过敏
　　头痛　　建筑工人　脑震荡
　　头痛　　建筑工人　感冒
　　打喷嚏　教师　　　感冒
　　头痛　　教师　　　脑震荡

现在又来了第七个病人，是一个打喷嚏的建筑工人。请问他患上感冒的概率有多大？

根据贝叶斯定理：

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

可得

　　　P(感冒|打喷嚏x建筑工人)
　　　　= P(打喷嚏x建筑工人|感冒) x P(感冒)
　　　　/ P(打喷嚏x建筑工人)

假定"打喷嚏"和"建筑工人"这两个特征是独立的，因此，上面的等式就变成了

　　　P(感冒|打喷嚏x建筑工人)
　　　　= P(打喷嚏|感冒) x P(建筑工人|感冒) x P(感冒)
　　　　/ P(打喷嚏) x P(建筑工人)

这是可以计算的。

　　P(感冒|打喷嚏x建筑工人)
　　　　= 0.66 x 0.33 x 0.5 / 0.5 x 0.33
　　　　= 0.66

因此，这个打喷嚏的建筑工人，有66%的概率是得了感冒。同理，可以计算这个病人患上过敏或脑震荡的概率。比较这几个概率，就可以知道他最可能得什么病。

这就是贝叶斯分类器的基本方法：在统计资料的基础上，依据某些特征，计算各个类别的概率，从而实现分类。

二、朴素贝叶斯分类器的公式

假设某个体有n项特征（Feature），分别为F₁、F₂、...、F_n。现有m个类别（Category），分别为C₁、C₂、...、C_m。贝叶斯分类器就是计算出概率最大的那个分类，也就是求下面这个算式的最大值：

　P(C|F1F2...Fn)
　　= P(F1F2...Fn|C)P(C) / P(F1F2...Fn)

由于 P(F1F2...Fn) 对于所有的类别都是相同的，可以省略，问题就变成了求

　P(F1F2...Fn|C)P(C)

的最大值。

朴素贝叶斯分类器则是更进一步，假设所有特征都彼此独立，因此

　P(F1F2...Fn|C)P(C)
　　= P(F1|C)P(F2|C) ... P(Fn|C)P(C)

上式等号右边的每一项，都可以从统计资料中得到，由此就可以计算出每个类别对应的概率，从而找出最大概率的那个类。

虽然"所有特征彼此独立"这个假设，在现实中不太可能成立，但是它可以大大简化计算，而且有研究表明对分类结果的准确性影响不大。

下面再通过两个例子，来看如何使用朴素贝叶斯分类器。

三、账号分类的例子

本例摘自张洋的《算法杂货铺----分类算法之朴素贝叶斯分类》。

根据某社区网站的抽样统计，该站10000个账号中有89%为真实账号（设为C₀），11%为虚假账号（设为C₁）。

　　C0 = 0.89

　　C1 = 0.11

接下来，就要用统计资料判断一个账号的真实性。假定某一个账号有以下三个特征：

　　　　F1: 日志数量/注册天数
　　　　F2: 好友数量/注册天数
　　　　F3: 是否使用真实头像（真实头像为1，非真实头像为0）

　　　　F1 = 0.1
　　　　F2 = 0.2
　　　　F3 = 0

请问该账号是真实账号还是虚假账号？

方法是使用朴素贝叶斯分类器，计算下面这个计算式的值。

　　　　P(F1|C)P(F2|C)P(F3|C)P(C)

虽然上面这些值可以从统计资料得到，但是这里有一个问题：F1和F2是连续变量，不适宜按照某个特定值计算概率。

一个技巧是将连续值变为离散值，计算区间的概率。比如将F1分解成[0, 0.05]、(0.05, 0.2)、[0.2, +∞]三个区间，然后计算每个区间的概率。在我们这个例子中，F1等于0.1，落在第二个区间，所以计算的时候，就使用第二个区间的发生概率。

根据统计资料，可得：

　　P(F1|C0) = 0.5, P(F1|C1) = 0.1
　　P(F2|C0) = 0.7, P(F2|C1) = 0.2
　　P(F3|C0) = 0.2, P(F3|C1) = 0.9

因此，

　　P(F1|C0) P(F2|C0) P(F3|C0) P(C0)
　　　　= 0.5 x 0.7 x 0.2 x 0.89
　　　　= 0.0623

　　P(F1|C1) P(F2|C1) P(F3|C1) P(C1)
　　　　= 0.1 x 0.2 x 0.9 x 0.11
　　　　= 0.00198

可以看到，虽然这个用户没有使用真实头像，但是他是真实账号的概率，比虚假账号高出30多倍，因此判断这个账号为真。

四、性别分类的例子

本例摘自维基百科，关于处理连续变量的另一种方法。

下面是一组人类身体特征的统计资料。

　　性别　　身高（英尺）　体重（磅）　　脚掌（英寸）

　　男　　　6 　　　　　　180　　　　　12
　　男　　　5.92　　　　　190　　　　　11
　　男　　　5.58　　　　　170　　　　　12
　　男　　　5.92　　　　　165　　　　　10
　　女　　　5 　　　　　　100　　　　　6
　　女　　　5.5 　　　　　150　　　　　8
　　女　　　5.42　　　　　130　　　　　7
　　女　　　5.75　　　　　150　　　　　9

已知某人身高6英尺、体重130磅，脚掌8英寸，请问该人是男是女？

根据朴素贝叶斯分类器，计算下面这个式子的值。

P(身高|性别) x P(体重|性别) x P(脚掌|性别) x P(性别)

这里的困难在于，由于身高、体重、脚掌都是连续变量，不能采用离散变量的方法计算概率。而且由于样本太少，所以也无法分成区间计算。怎么办？

这时，可以假设男性和女性的身高、体重、脚掌都是正态分布，通过样本计算出均值和方差，也就是得到正态分布的密度函数。有了密度函数，就可以把值代入，算出某一点的密度函数的值。

比如，男性的身高是均值5.855、方差0.035的正态分布。所以，男性的身高为6英尺的概率的相对值等于1.5789（大于1并没有关系，因为这里是密度函数的值，只用来反映各个值的相对可能性）。

有了这些数据以后，就可以计算性别的分类了。

　　P(身高=6|男) x P(体重=130|男) x P(脚掌=8|男) x P(男)
　　　　= 6.1984 x e^-9

　　P(身高=6|女) x P(体重=130|女) x P(脚掌=8|女) x P(女)
　　　　= 5.3778 x e^-4

可以看到，女性的概率比男性要高出将近10000倍，所以判断该人为女性。

（完）

一、什么是贝叶斯推断

贝叶斯推断（Bayesian inference）是一种统计学方法，用来估计统计量的某种性质。

它是贝叶斯定理（Bayes' theorem）的应用。英国数学家托马斯·贝叶斯（Thomas Bayes）在1763年发表的一篇论文中，首先提出了这个定理。

贝叶斯推断与其他统计学推断方法截然不同。它建立在主观判断的基础上，也就是说，你可以不需要客观证据，先估计一个值，然后根据实际结果不断修正。正是因为它的主观性太强，曾经遭到许多统计学家的诟病。

贝叶斯推断需要大量的计算，因此历史上很长一段时间，无法得到广泛应用。只有计算机诞生以后，它才获得真正的重视。人们发现，许多统计量是无法事先进行客观判断的，而互联网时代出现的大型数据集，再加上高速运算能力，为验证这些统计量提供了方便，也为应用贝叶斯推断创造了条件，它的威力正在日益显现。

二、贝叶斯定理

要理解贝叶斯推断，必须先理解贝叶斯定理。后者实际上就是计算"条件概率"的公式。

所谓"条件概率"（Conditional probability），就是指在事件B发生的情况下，事件A发生的概率，用P(A|B)来表示。

根据文氏图，可以很清楚地看到在事件B发生的情况下，事件A发生的概率就是P(A∩B)除以P(B)。

$P(A|B)=\frac{P(A\cap B)}{P(B)}$

因此，

$P(A\cap B)=P(A|B){P(B)}$

同理可得，

$P(A\cap B)=P(B|A){P(A)}$

所以，

$P(A|B){P(B)}=P(B|A){P(A)}$

即

$P(A|B)=\frac{P(B|A){P(A)}}{{P(B)}}$

这就是条件概率的计算公式。

三、全概率公式

由于后面要用到，所以除了条件概率以外，这里还要推导全概率公式。

假定样本空间S，是两个事件A与A'的和。

上图中，红色部分是事件A，绿色部分是事件A'，它们共同构成了样本空间S。

在这种情况下，事件B可以划分成两个部分。

即

$P(B)=P(B\cap A)+P(B\cap A')$

在上一节的推导当中，我们已知

$P(B\cap A)=P(B|A)P(A)$

所以，

$P(B)=P(B|A)P(A)+P(B|A')P(A')$

这就是全概率公式。它的含义是，如果A和A'构成样本空间的一个划分，那么事件B的概率，就等于A和A'的概率分别乘以B对这两个事件的条件概率之和。

将这个公式代入上一节的条件概率公式，就得到了条件概率的另一种写法：

$P(A|B)=\frac{P(B|A)P(A)}{P(B|A)P(A)+P(B|A')P(A')}$

四、贝叶斯推断的含义

对条件概率公式进行变形，可以得到如下形式：

$P(A|B)=P(A)\frac{P(B|A)}{P(B)}$

我们把P(A)称为"先验概率"（Prior probability），即在B事件发生之前，我们对A事件概率的一个判断。P(A|B)称为"后验概率"（Posterior probability），即在B事件发生之后，我们对A事件概率的重新评估。P(B|A)/P(B)称为"可能性函数"（Likelyhood），这是一个调整因子，使得预估概率更接近真实概率。

所以，条件概率可以理解成下面的式子：

　　后验概率　＝　先验概率ｘ调整因子

这就是贝叶斯推断的含义。我们先预估一个"先验概率"，然后加入实验结果，看这个实验到底是增强还是削弱了"先验概率"，由此得到更接近事实的"后验概率"。

在这里，如果"可能性函数"P(B|A)/P(B)>1，意味着"先验概率"被增强，事件A的发生的可能性变大；如果"可能性函数"=1，意味着B事件无助于判断事件A的可能性；如果"可能性函数"<1，意味着"先验概率"被削弱，事件A的可能性变小。

五、【例子】水果糖问题

为了加深对贝叶斯推断的理解，我们看两个例子。

第一个例子。两个一模一样的碗，一号碗有30颗水果糖和10颗巧克力糖，二号碗有水果糖和巧克力糖各20颗。现在随机选择一个碗，从中摸出一颗糖，发现是水果糖。请问这颗水果糖来自一号碗的概率有多大？

我们假定，H1表示一号碗，H2表示二号碗。由于这两个碗是一样的，所以P(H1)=P(H2)，也就是说，在取出水果糖之前，这两个碗被选中的概率相同。因此，P(H1)=0.5，我们把这个概率就叫做"先验概率"，即没有做实验之前，来自一号碗的概率是0.5。

再假定，E表示水果糖，所以问题就变成了在已知E的情况下，来自一号碗的概率有多大，即求P(H1|E)。我们把这个概率叫做"后验概率"，即在E事件发生之后，对P(H1)的修正。

根据条件概率公式，得到

$P(H_{1}|E)=P(H_{1})\frac{P(E|H_{1})}{P(E)}$

已知，P(H1)等于0.5，P(E|H1)为一号碗中取出水果糖的概率，等于0.75，那么求出P(E)就可以得到答案。根据全概率公式，

$P(E)=P(E|H_{1})P(H_{1})+P(E|H_{2})P(H_{2})$

所以，

$P(E)=0.75\times 0.5+0.5\times 0.5=0.625$

将数字代入原方程，得到

$P(H1|E)=0.5\times \frac{0.75}{0.625}=0.6$

这表明，来自一号碗的概率是0.6。也就是说，取出水果糖之后，H1事件的可能性得到了增强。

六、【例子】假阳性问题

第二个例子是一个医学的常见问题，与现实生活关系紧密。

已知某种疾病的发病率是0.001，即1000人中会有1个人得病。现有一种试剂可以检验患者是否得病，它的准确率是0.99，即在患者确实得病的情况下，它有99%的可能呈现阳性。它的误报率是5%，即在患者没有得病的情况下，它有5%的可能呈现阳性。现有一个病人的检验结果为阳性，请问他确实得病的可能性有多大？

假定A事件表示得病，那么P(A)为0.001。这就是"先验概率"，即没有做试验之前，我们预计的发病率。再假定B事件表示阳性，那么要计算的就是P(A|B)。这就是"后验概率"，即做了试验以后，对发病率的估计。

根据条件概率公式，

$P(A|B)=P(A) \frac{P(B|A)}{P(B)}$

用全概率公式改写分母，

$P(A|B)=P(A) \frac{P(B|A)}{P(B|A)P(A)+P(B|\bar{A})P(\bar{A})}$

将数字代入，

$P(A|B)=0.001\times \frac{0.99}{0.99\times 0.001+0.05\times 0.999}\approx 0.019$

我们得到了一个惊人的结果，P(A|B)约等于0.019。也就是说，即使检验呈现阳性，病人得病的概率，也只是从0.1%增加到了2%左右。这就是所谓的"假阳性"，即阳性结果完全不足以说明病人得病。

为什么会这样？为什么这种检验的准确率高达99%，但是可信度却不到2%？答案是与它的误报率太高有关。（【习题】如果误报率从5%降为1%，请问病人得病的概率会变成多少？）

有兴趣的朋友，还可以算一下"假阴性"问题，即检验结果为阴性，但是病人确实得病的概率有多大。然后问自己，"假阳性"和"假阴性"，哪一个才是医学检验的主要风险？

===================================

关于贝叶斯推断的原理部分，今天就讲到这里。下一次，将介绍如何使用贝叶斯推断过滤垃圾邮件。

七、什么是贝叶斯过滤器？

垃圾邮件是一种令人头痛的顽症，困扰着所有的互联网用户。

正确识别垃圾邮件的技术难度非常大。传统的垃圾邮件过滤方法，主要有"关键词法"和"校验码法"等。前者的过滤依据是特定的词语；后者则是计算邮件文本的校验码，再与已知的垃圾邮件进行对比。它们的识别效果都不理想，而且很容易规避。

2002年，Paul Graham提出使用"贝叶斯推断"过滤垃圾邮件。他说，这样做的效果，好得不可思议。1000封垃圾邮件可以过滤掉995封，且没有一个误判。

另外，这种过滤器还具有自我学习的功能，会根据新收到的邮件，不断调整。收到的垃圾邮件越多，它的准确率就越高。

八、建立历史资料库

贝叶斯过滤器是一种统计学过滤器，建立在已有的统计结果之上。所以，我们必须预先提供两组已经识别好的邮件，一组是正常邮件，另一组是垃圾邮件。

我们用这两组邮件，对过滤器进行"训练"。这两组邮件的规模越大，训练效果就越好。Paul Graham使用的邮件规模，是正常邮件和垃圾邮件各4000封。

"训练"过程很简单。首先，解析所有邮件，提取每一个词。然后，计算每个词语在正常邮件和垃圾邮件中的出现频率。比如，我们假定"sex"这个词，在4000封垃圾邮件中，有200封包含这个词，那么它的出现频率就是5%；而在4000封正常邮件中，只有2封包含这个词，那么出现频率就是0.05%。（【注释】如果某个词只出现在垃圾邮件中，Paul Graham就假定，它在正常邮件的出现频率是1%，反之亦然。这样做是为了避免概率为0。随着邮件数量的增加，计算结果会自动调整。）

有了这个初步的统计结果，过滤器就可以投入使用了。

九、贝叶斯过滤器的使用过程

现在，我们收到了一封新邮件。在未经统计分析之前，我们假定它是垃圾邮件的概率为50%。（【注释】有研究表明，用户收到的电子邮件中，80%是垃圾邮件。但是，这里仍然假定垃圾邮件的"先验概率"为50%。）

我们用S表示垃圾邮件（spam），H表示正常邮件（healthy）。因此，P(S)和P(H)的先验概率，都是50%。

$P(S)=P(H)=50%$

然后，对这封邮件进行解析，发现其中包含了sex这个词，请问这封邮件属于垃圾邮件的概率有多高？

我们用W表示"sex"这个词，那么问题就变成了如何计算P(S|W)的值，即在某个词语（W）已经存在的条件下，垃圾邮件（S）的概率有多大。

根据条件概率公式，马上可以写出

$P(S|W)=\frac{P(W|S)P(S)}{P(W|S)P(S)+P(W|H)P(H)}$

公式中，P(W|S)和P(W|H)的含义是，这个词语在垃圾邮件和正常邮件中，分别出现的概率。这两个值可以从历史资料库中得到，对sex这个词来说，上文假定它们分别等于5%和0.05%。另外，P(S)和P(H)的值，前面说过都等于50%。所以，马上可以计算P(S|W)的值：

$P(S|W)=\frac{5%\times 50%}{5%\times 50%+0.05%\times 50%}=99.0%$

因此，这封新邮件是垃圾邮件的概率等于99%。这说明，sex这个词的推断能力很强，将50%的"先验概率"一下子提高到了99%的"后验概率"。

十、联合概率的计算

做完上面一步，请问我们能否得出结论，这封新邮件就是垃圾邮件？

回答是不能。因为一封邮件包含很多词语，一些词语（比如sex）说这是垃圾邮件，另一些说这不是。你怎么知道以哪个词为准？

Paul Graham的做法是，选出这封信中P(S|W)最高的15个词，计算它们的联合概率。（【注释】如果有的词是第一次出现，无法计算P(S|W)，Paul Graham就假定这个值等于0.4。因为垃圾邮件用的往往都是某些固定的词语，所以如果你从来没见过某个词，它多半是一个正常的词。）

所谓联合概率，就是指在多个事件发生的情况下，另一个事件发生概率有多大。比如，已知W1和W2是两个不同的词语，它们都出现在某封电子邮件之中，那么这封邮件是垃圾邮件的概率，就是联合概率。

在已知W1和W2的情况下，无非就是两种结果：垃圾邮件（事件E1）或正常邮件（事件E2）。

其中，W1、W2和垃圾邮件的概率分别如下：

如果假定所有事件都是独立事件（【注释】严格地说，这个假定不成立，但是这里可以忽略），那么就可以计算P(E1)和P(E2)：

$P(E_{1})=P(S|W_{1})P(S|W_{2})P(S)$

$P(E_{2})=(1-P(S|W_{1}))(1-P(S|W_{2}))(1-P(S))$

又由于在W1和W2已经发生的情况下，垃圾邮件的概率等于下面的式子：

$P=\frac{P(E_{1})}{P(E_{1})+P(E_{2})}$

即

$P=\frac{P(S|W_{1})P(S|W_{2})P(S)}{P(S|W_{1})P(S|W_{2})P(S)+(1-P(S|W_{1}))(1-P(S|W_{2}))(1-P(S))}$

将P(S)等于0.5代入，得到

$P=\frac{P(S|W_{1})P(S|W_{2})}{P(S|W_{1})P(S|W_{2})+(1-P(S|W_{1}))(1-P(S|W_{2}))}$

将P(S|W1)记为P1，P(S|W2)记为P2，公式就变成

$P=\frac{P_{1}P_{2}}{P_{1}P_{2}+(1-P_{1})(1-P_{2})}$

这就是联合概率的计算公式。如果你不是很理解，点击这里查看更多的解释。

十一、最终的计算公式

将上面的公式扩展到15个词的情况，就得到了最终的概率计算公式：

$P=\frac{P_{1}P_{2}\cdot \cdot \cdot P_{15}}{P_{1}P_{2}\cdot \cdot \cdot P_{15}+(1-P_{1})(1-P_{2})\cdot \cdot \cdot (1-P_{15})}$

一封邮件是不是垃圾邮件，就用这个式子进行计算。这时我们还需要一个用于比较的门槛值。Paul Graham的门槛值是0.9，概率大于0.9，表示15个词联合认定，这封邮件有90%以上的可能属于垃圾邮件；概率小于0.9，就表示是正常邮件。

有了这个公式以后，一封正常的信件即使出现sex这个词，也不会被认定为垃圾邮件了。

（完）