Naive Bayes Classifier

Table of Contents

1 朴素贝叶斯分类器简介

朴素贝叶斯分类器(Naive Bayes classifier)是一种基于贝叶斯定理的常用分类方法,它的实现比较简单。

参考:
统计学习方法,李航,第四章

1.1 贝叶斯定理(贝叶斯公式)

设 \(A,B\) 是两个事件,\(P(B|A)\) 表示事件 \(A\) 已经发生的前提下,事件 \(B\) 发生的概率(称为条件概率)。贝叶斯公式为:
\[P(B|A) = \frac{P(A|B)P(B)}{P(A)} = \frac{P(A|B)}{P(A)}P(B)\]

上式中, \(P(B)\) 往往由历史数据可以得到,叫做 先验概率(Priori Probability)\(P(B|A)\) 称为 后验概率(Posteriori Probability)

2 朴素贝叶斯分类器

朴素贝叶斯分类器的思想很简单: 将实例分到后验概率最大的类中。

朴素贝叶斯分类的正式描述如下:
假设有 \(N\) 条训练数据 \(T = \{(\boldsymbol{x_1}, y_1), (\boldsymbol{x_2}, y_2), \cdots, (\boldsymbol{x_N}, y_N)\}\) ,其中 \(y_i \in \mathcal{Y} = \{ c_1, c_2, \cdots, c_k\}\) ,即数据共分为 \(k\) 类。

假设给定的待分类数据为: \(\boldsymbol{x} = (x^{(1)}, x^{(2)}, \cdots, x^{(N)})^{\mathsf{T}}\) ,如何求它所属的分类 \(y\) 呢?
朴素贝叶斯分类器采用的方法是先计算下面所有条件概率(后验概率):
\[P(c_1 \mid \boldsymbol{x}), P(c_2 \mid \boldsymbol{x}), \cdots, P(c_k \mid \boldsymbol{x})\]
然后,把待分类数据 \(\boldsymbol{x}\) 分到上面 \(k\) 个概率中较大的那个对应的分类:
\[y = \operatorname{arg} \underset{c_i \in \mathcal{Y} }{\max} P(c_i \mid \boldsymbol{x})\]
上式就是朴素贝叶斯分类器的决策函数的原始形式,后文将对它进行化简。

2.1 求解决策函数(用“特征条件独立”的假设来简化计算)

如何求 \(y = \operatorname{arg} \underset{c_i \in \mathcal{Y} }{\max} P(c_i \mid \boldsymbol{x})\) 呢?
由贝叶斯公式有: \(P(c_i \mid \boldsymbol{x}) = \dfrac{P(\boldsymbol{x} \mid c_i) P(c_i)}{P(\boldsymbol{x})}\) ,由于分母 \(P(\boldsymbol{x})\) 对于所有类别是不变的,不影响比较大小,所以无需理会它。式中, \(P(c_i)\) 往往是历史已知数据,或者由训练数据集可直接统计出来(即训练数据中出现 \(c_i\) 的次数除以训练数据的总数 \(N\) 即可),

剩下 \(P(\boldsymbol{x} \mid c_i) = P(x^{(1)}, x^{(2)}, \cdots, x^{(N)} \mid c_i)\) 需要计算,它比较难计算。如果假设 分类的特征在类确定的条件下都是条件独立的 ,那么有:
\[\begin{aligned} P(\boldsymbol{x} \mid c_i) & = P(x^{(1)}, x^{(2)}, \cdots, x^{(N)} \mid c_i) \\ & = \prod_{j=1}^{N}P(x^{(j)} \mid c_i) \end{aligned}\]

上面这个假设是比较强的假设(所以认为它是朴素的,称为朴素贝叶斯分类器),这可能会牺牲分类的准确性,但它大大简化了计算。

所以,朴素贝叶斯分类器的决策函数可以写为:
\[y = \operatorname{arg} \underset{c_i \in \mathcal{Y} }{\max} P(c_i) \prod_{j=1}^{N}P(x^{(j)} \mid c_i)\]

2.2 简单实例

这个例子摘自:统计学习方法,李航,第四章

有表 1 所示训练数据。

Table 1: 一些训练数据
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
\(X^{(1)}\) 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3
\(X^{(2)}\) S M M S S S M M L L L M M L L
\(Y\) -1 -1 1 1 -1 -1 -1 1 1 1 1 1 1 1 -1

其中, \(X^{(1)}\) 和 \(X^{(2)}\) 为数据的两个特征(都是离散值), \(Y\) 为类标记。求数据 \((2, S)^{\mathsf{T}}\) 的分类。

解:
我们直接按照公式 \(y = \operatorname{arg} \underset{c_i \in \mathcal{Y} }{\max} P(c_i) \prod_{j=1}^{N}P(x^{(j)} \mid c_i)\) 来对数据进行分类。为表述更清晰,我们把 \(P(c_i)\) 完整地写为 \(P(Y=c_i)\) ,把 \(P(x^{(j)} \mid c_i)\) 完整地写为 \(P(X^{(j)} \mid Y=c_i)\) 。由于给定的训练数据都是一些离散的值,直接统计出现的次数,可得到:
\[\begin{aligned} & P(Y=1) = \frac{9}{15}, \; P(Y=-1) = \frac{6}{15} \\ & P(X^{(1)} = 1 \mid Y=1) = \frac{2}{9}, \; P(X^{(1)} = 2 \mid Y=1) = \frac{3}{9}, \; P(X^{(1)} = 3 \mid Y=1) = \frac{4}{9} \\ & P(X^{(2)} = S \mid Y=1) = \frac{1}{9}, \; P(X^{(2)} = M \mid Y=1) = \frac{4}{9}, \; P(X^{(2)} = L \mid Y=1) = \frac{4}{9} \\ & P(X^{(1)} = 1 \mid Y=-1) = \frac{3}{6}, \; (X^{(1)} = 2 \mid Y=-1) = \frac{2}{6}, \; P(X^{(1)} = 3 \mid Y=-1) = \frac{1}{6} \\ & P(X^{(2)} = S \mid Y=-1) = \frac{3}{6}, \; P(X^{(2)} = M \mid Y=-1) = \frac{2}{6}, \; P(X^{(2)} = L \mid Y=-1) = \frac{1}{6} \\ \end{aligned}\]
对于给定的数据 \(\boldsymbol{x} = (2, S)^{\mathsf{T}}\) ,计算:
\[\begin{aligned} & P(Y=1)P(X^{(1)} = 2 \mid Y=1) P(X^{(2)} = S \mid Y=1) = \frac{9}{15} \cdot \frac{3}{9} \cdot \frac{1}{9} = \frac{1}{45} \\ & P(Y=-1)P(X^{(1)} = 2 \mid Y=-1) P(X^{(2)} = S \mid Y=-1) = \frac{6}{15} \cdot \frac{2}{6} \cdot \frac{3}{6} = \frac{1}{15} \\ \end{aligned}\]
由于 \(\frac{1}{15} > \frac{1}{45}\) ,所以 \(y = -1\)

说明:这个例子不太好,没有指定例子的真实生活背景,且待分类的数据存在于训练数据中;但它很简单,足够说明朴素贝叶斯分类器的基本原理。

3 处理“特征连续”的情况

前面的例子中,由于特征都是离散值,可以方便地从训练数据中计算出相应的概率。但如果特征是连续值时,怎么办呢?
有两种常用技巧,一是把连续值划分为几个区间,计算区间的概率,从而离散化连续值;另一种技巧是假设是这些连续数值为正态分布,通过样本计算出均值和方差,从而得到正态分布的密度函数,把值代入密度函数从而可以算出某一点的密度函数的值。

训练数据集大时,采用计算区间的概率,从而离散化连续值的技巧更好,因为它可以体现训练数据的分布;当样本很小时,可以采用假设是这些连续数值为正态分布的技巧。

下面通过两个实例分别演示这些技巧。

3.1 实例:检测“社交网站不真实账号”

这个例子摘自:算法杂货铺——分类算法之朴素贝叶斯分类(Naive Bayesian classification)

我们选取下面三个特征属性来判断社交网站的账号是否真实:
\(X^{(1)}\) :日志数量/注册天数, \(X^{(2)}\) :好友数量/注册天数, \(X^{(3)}\) :是否使用真实头像。

运维人员曾经人工检测过的10000个账号作为训练样本,得到该站10000个账号中有8900个为真实账号(记为 \(c_0\) ),1100个为虚假账号(记为 \(c_1\) )。从而有: \(P(Y=c_0) = 0.89, \; P(Y=c_1) = 0.11\)
对于 \(X^{(3)}\) 可以用0和1表示“没有使用/使用”了真实头像。但在这里 \(X^{(1)}\) 和 \(X^{(2)}\) 是连续变量,无法按照某个特定值计算概率。一个技巧是将连续值变为离散值,计算区间的概率。比如将 \(X^{(1)}\) 分解成 \([0, 0.05), [0.05, 0.2), [0.2, + \infty)\) 三个区间,将 \(X^{(2)}\) 分解成 \([0, 0.1), [0.1, 0.8), [0.8, + \infty)\) 三个区间 ,然后计算每个区间的概率。

从10000个样本中,运维人员统计得到每个类别条件下各个特征属性划分的频率:
\[\begin{aligned} & P(X^{(1)} < 0.05 \mid Y = c_0) = 0.3, \; P(0.05 \le X^{(1)} < 0.2 \mid Y = c_0) = 0.5, \; P(X^{(1)} \ge 0.2 \mid Y = c_0) = 0.2 \\ & P(X^{(1)} < 0.05 \mid Y = c_1) = 0.8, \; P(0.05 \le X^{(1)} < 0.2 \mid Y = c_1) = 0.1, \; P(X^{(1)} \ge 0.2 \mid Y = c_1) = 0.1 \\ & P(X^{(2)} < 0.1 \mid Y = c_0) = 0.1, \; P(0.1 \le X^{(2)} < 0.8 \mid Y = c_0) = 0.7, \; P(X^{(2)} \ge 0.8 \mid Y = c_0) = 0.2 \\ & P(X^{(2)} < 0.1 \mid Y = c_1) = 0.7, \; P(0.1 \le X^{(2)} < 0.8 \mid Y = c_1) = 0.2, \; P(X^{(2)} \ge 0.8 \mid Y = c_0) = 0.1 \\ & P(X^{(3)} = 0 \mid Y = c_0) = 0.2, \; P(X^{(3)} = 1 \mid Y = c_0) = 0.8 \\ & P(X^{(3)} = 0 \mid Y = c_1) = 0.9, \; P(X^{(3)} = 1 \mid Y = c_1) = 0.1 \\ \end{aligned}\]

现在有一个账号的这三个属性为: \((X^{(1)}, X^{(2)}, X^{(3)})^{\mathsf{T}} = (0.1, 0.2, 0)^{\mathsf{T}}\) ,那么它是真实账号还是虚假账号呢?
\(X^{(1)} = 0.1\) 属于区间 \([0.05, 0.2)\) , \(X^{(2)} = 0.2\) 属于 \([0.1, 0.8)\) ,我们计算:
\[\begin{aligned} & P(Y=c_0) P(0.05 \le X^{(1)} < 0.2 \mid Y=c_0) P(0.1 \le X^{(2)} < 0.8 \mid Y = c_0) P(X^{(3)} = 0 \mid Y = c_0) \\ & = 0.89 \times 0.5 \times 0.7 \times 0.2 = 0.0623 \\ & P(Y=c_1) P(0.05 \le X^{(1)} < 0.2 \mid Y=c_1) P(0.1 \le X^{(2)} < 0.8 \mid Y = c_1) P(X^{(3)} = 0 \mid Y = c_1) \\ & = 0.11 \times 0.1 \times 0.2 \times 0.9 = 0.00198 \\ \end{aligned}\]

由于 \(0.0623 > 0.00198\) ,所以归为 \(c_0\) 类。可以看到,虽然这个用户没有使用真实头像,但是通过朴素贝叶斯分类器的鉴别,更倾向于将此账号归入真实账号类别。

3.2 实例:预测性别

下面例子摘自:https://zh.wikipedia.org/wiki/朴素贝叶斯分类器

假设有下面统计数据:

Table 2: 关于“性别/身高/体重/脚掌大小”的一些统计数据
性别 身高(英尺)  体重(磅)  脚掌(英寸)
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英寸,请问该人是男还是女?

身高、体重、脚掌都是连续变量,不能采用离散变量的方法计算概率。而且由于样本太少,所以也无法分成区间计算。怎么办?
这时,可以假设男性和女性的身高、体重、脚掌都是正态分布,通过样本计算出均值和方差,也就是得到正态分布的密度函数。有了密度函数,就可以把值代入,算出某一点的密度函数的值。

我们假设训练集样本的特征满足高斯分布,从训练集可以得到下表:

Table 3: 假设前面样本的特征满足高斯分布
性别 均值(身高) 方差(身高) 均值(体重) 方差(体重) 均值(脚的尺寸) 方差(脚的尺寸)
男性 5.855 3.5033e-02 176.25 1.2292e+02 11.25 9.1667e-01
女性 5.4175 9.7225e-02 132.5 5.5833e+02 7.5 1.6667e+00

从上表知,男性的身高是均值5.855、方差0.035的正态分布。所以,男性身高为6英尺的概率的相对值等于:
\[P(height \mid male) = \frac{1}{\sqrt{2 \pi \sigma^2}} e^{\frac{-(6 - \mu)^2}{2 \sigma^2}} \approx 1.5789, \quad \mu = 5.855, \sigma^2 = 0.035\]
说明:大于1并没有关系,因为这里是密度函数的值,只用来反映各个值的相对可能性。

类似地,我们可以计算出:
男性体重130磅的概率的相对值为 \(5.9881 e^{-6}\)
男性脚掌8英寸的概率的相对值为 \(1.3113 e^{-3}\)
女性身高为6英尺的概率的相对值为 \(2.2346 e^{-1}\)
女性体重130磅的概率的相对值为 \(1.6789 e^{-2}\)
女性脚掌8英寸的概率的相对值为 \(2.8669 e^{-1}\)

可以假设 \(P(\text{男}) = P(\text{女}) = 0.5\)

计算:
\[\begin{aligned} & P(\text{男}) \times P(\text{身高}=6|\text{男}) \times P(\text{体重}=130|\text{男}) \times P(\text{脚掌}=8|\text{男}) = 6.1984 e^{-9} \\ & P(\text{女}) \times P(\text{身高}=6|\text{女}) \times P(\text{体重}=130|\text{女}) \times P(\text{脚掌}=8|\text{女}) = 5.3778 e^{-4} \end{aligned}\]

由于女性后验概率的分子比较大,所以我们预计这个样本是女性。

4 Laplace校准

如果当某个类别下某个特征没有出现时,可能会出现概率为0的情况,这会令分类器质量大大降低。
为了解决这个问题,我们引入Laplace校准,它的思想很简单:就是对每个类别下所有特征的计数加1,这样如果训练样本集数量充分大时,并不会对结果产生影响(可称为“加一”平滑)。

参考:https://en.wikipedia.org/wiki/Laplacian_smoothing

5 下一步:贝叶斯信念网络

朴素贝叶斯分类器中假设输入变量都是条件独立的,如果假设它们之间存在概率依存关系,则模型就变成了贝叶斯信念网络(Bayesian network)。


Author: cig01

Created: <2015-05-30 Sat 00:00>

Last updated: <2018-01-02 Tue 15:19>

Creator: Emacs 25.3.1 (Org mode 9.1.4)