贝叶斯分类器(上)

1. 背景

在很多应用中,属性集和类变量之间的关系是不确定的。也就是说,尽管测试记录的属性集和某些训练样例相同,但是也不能正确地预测它的类标号。这种情况产生的原因可能是噪声,或者出现了某些影响分类的因素却没有包含在分析中。

这篇博文将介绍一种对属性集和类变量的概率关系建模的方法—贝叶斯分类器(bayesian classifier)。首先将介绍贝叶斯定理;然后解释贝叶斯定理在分类问题中的应用;接下来描述贝叶斯分类器的两种实现:朴素贝叶斯(naive bayesian classifier)和贝叶斯信念网络(bayesian belief networks),考虑到篇幅的问题,这篇博文只介绍朴素贝叶斯,贝叶斯信念网将在下篇博文介绍;最后将通过例子说明朴素贝叶斯分类的应用。

2. 贝叶斯定理

假设$X,Y$是一对随机变量,它们的联合概率$P(X=x,Y=y)$是指$X$取值$x$且$Y$取值$y$的概率,条件概率是指一随机变量在另一随机变量取值已知的情况下某一特定值的概率。例如,条件概率$P(Y=y|X=x)$是指在变量$X$取值$x$的情况下,变量$Y$取值$y$的概率。

$X$和$Y$的联合概率和条件概率满足如下关系:
$$
P(X,Y) = P(Y|X) \cdot P(X) = P(X|Y) \cdot P(Y)
$$
由上面的公式可以得到下面公式,称为贝叶斯定理
$$
P(Y|X) = \frac{P(X|Y)P(Y)}{P(X)}
$$

3. 贝叶斯定理在分类中的应用

在描述贝叶斯定理怎样应用于分类之前,我们先从统计学的角度对分类问题加以形式化。设$X$表示特征属性集,$Y$表示类变量。如果类变量和属性之间的关系不确定,那么我们可以把$X$和$Y$看作随机变量,用$P(Y|X)$以概率的方式捕捉二者之间的关系。这个条件概率又称为$Y$的后验概率(posterior-probability),与之相对地,$P(Y)$称为$Y$的先验概率(prior probability)。

在训练阶段,我们要根据从训练数据中收集的信息,对$X$和$Y$的每一种组合学习后验概率$P(Y|X)$。知道这些概率后,通过找出使后验概率$P(Y’|X’)$最大的类$Y’$对测试记录$X’$进行分类。

准确估计类标号和属性值的每一种可能组合的后验概率非常困难,因为即便数目不是很大,仍然需要很大的训练集。此时,贝叶斯定理很有用,它允许我们用先验概率$P(Y)$,类条件概率$P(X|Y)$和证据$P(X)$来表示后验概率
$$
P(Y|X) = \frac{P(X|Y)P(Y)}{P(X)}
$$

在比较不同$Y$值的后验概率时,分母$P(X)$总是常数,因此可以忽略。先验概率$P(Y)$可以通过计算训练集中属于每个类的训练记录所占的比例进行估计。对类条件概率$P(X|Y)$的估计,则有两种实现方法:[朴素贝叶斯分类器]和[贝叶斯信念网络],本篇博文介绍朴素贝叶斯分类器。

4. 朴素贝叶斯分类器

朴素贝叶斯的基本思想是:对于给定的待分类项,求出在此项出现的条件下各个类别出现的概率,哪个最大,就认为此待分类项属于哪个类别

朴素贝叶斯分类器有一个假设:给定类标号$y_k$,各属性之间条件独立。条件独立假设表述如下:
$$
P(X|Y=y_k) = \prod_{i=1}^m P(x_i|Y=y_k)
$$
其中,每个属性集$X=\{x_1,x_2,\cdots,x_m\}$包含$m$个属性。

朴素贝叶斯分类器的工作流程如下:

  1. 设$X=\{x_1,x_2,\cdots,x_m\}$是一个待分类项,而$x_i$为$X$的一个特征属性集;
  2. 设类别集合$C=\{y_1,y_2,\cdots,y_n\}$;
  3. 计算$P(y_1|X),P(y_2|X),\cdots,P(y_n|X)$;
  4. 如果$P(y_k|X)=max\{P(y_1|X),P(y_2|X),\cdots,P(y_n|X)\}$,则$X \in y_k$。

其中,最关键的是如何计算第三步中的各个条件概率,方法如下:

  1. 给定一个训练样本集,统计在各类别下各个特征属性的条件概率,即
    $$
    P(x_1|y_1),P(x_2|y_1),\cdots,P(x_m|y_1) \\
    P(x_1|y_2),P(x_2|y_2),\cdots,P(x_m|y_2) \\
    \vdots \\
    P(x_1|y_n),P(x_2|y_n),\cdots,P(x_m|y_n) \\
    $$

  2. 根据朴素贝叶斯分类器的假设,以及贝叶斯定理有:
    $$
    \begin{split}
    P(y_k|X) &= \frac{P(X|y_k)P(y_k)}{P(X)} \\
    \end{split}
    $$

其中,
$$
P(X|y_k) = \left[\prod_{i=1}^m P(x_i|y_k)\right]
$$

由于对于所有的$Y$,$P(X)$是固定的,因此只要找出使分子$\prod_{i=1}^m P(x_i|y_k)$最大的类就够了。

由上文可以看出,计算在各个类别下特征属性的条件概率$P(X=x_i|Y=y_k)$是朴素贝叶斯分类的关键性步骤:

  • 当特征属性为离散值时,可以通过统计训练样本中各个划分在每个类别中出现的频率来估计;
  • 当特征属性为连续属性时,可以假设连续变量服从某种概率分布,然后使用训练数据估计分布的参数。高斯分布(也称正态分布)常被用来表示连续属性的类条件概率分布。该分布有两个参数,均值$\mu$和方差$\sigma^2$。对每个类,属性$x_i$的类条件概率等于:

$$
P(X=x_i|Y=y_k) = \frac{1}{\sqrt{2\pi}\sigma_{ik}} \exp\left[-\frac{(x_i-\mu_{ik})^2}{2\sigma_{ik}^2}\right]
$$

参数$\mu_{ik}$可以用类$y_k$的所有训练记录关于$x_i$的样本均值$\bar{x}$来估计,参数$\sigma_{ik}^2$可以用这些训练记录的样本方差$s^2$来估计。

5. 朴素贝叶斯分类器例子

这里我们以之前博文中的产品购买案例来说明朴素贝叶斯分类的工作流程。训练样本的属性集为$X=\{性别,年龄,婚姻\}$,类标为$Y=\{Yes,No\}$,表示是否购买产品,训练样本共有10条记录,购买记录有4条,不购买记录有6条。

现在给定一个测试样本$X’$为性别=F,年龄=中,婚姻=离异,预测该用户是否会购买公司的产品。因此,我们需要计算概率

$$
\left \{
\begin{split}
& P(Y=Yes|性别=F,年龄=中,婚姻=离异) \\
& P(Y=No|性别=F,年龄=中,婚姻=离异)
\end{split}
\right.
$$

计算过程如下:
$$
\left\{
\begin{split}
& P(Y=Yes) = 4/10 \\
& P(性别=F|Yes) = 1/4 \\
& P(年龄=中|Yes) = 1/4 \\
& P(婚姻=离异|Yes) = 0 \\
\end{split}
\right.
$$

$$
\left\{
\begin{split}
& P(Y=No) = 6/10 \\
& P(性别=F|No) = 4/6 \\
& P(年龄=中|No) = 3/6 \\
& P(婚姻=离异|No) = 1/6 \\
\end{split}
\right.
$$


$$
\begin{split}
P(Y=Yes|性别=F,年龄=中,婚姻=离异)
&= 4/10 \times 1/4 \times 1/4 \times 0 \cdot \alpha \\
& = 0
\end{split}
$$
同理可得,
$$
\begin{split}
P(Y=No|性别=F,年龄=中,婚姻=离异)
&= 6/10 \times 4/6 \times 3/6 \times 1/6 \cdot \alpha \\
&= 0.033
\end{split}
$$
其中$\alpha = 1/P(性别=F,年龄=中,婚姻=离异)$

取概率值最大的类,为$Y=No$,因此,对于给定的测试样本,我们预测它属于不够买的一类。

6. 条件概率的 m 估计

前面的例子体现了从训练数据估计后验概率时的一个潜在问题:如果有一个属性的类条件概率等于0,则整个类的后验概率就等于0。因此,仅使用记录比例来估计类条件概率的方法并不是很可靠,尤其是当训练样例很少而属性数目又很大时。

解决该问题的途径是使用$m$估计(m-estimate)方法来估计条件概率:
$$
P(x_i|y_j) = \frac{n_c+mp}{n+m}
$$
其中,$n$是类$y_j$中的实例总数,$n_c$是类$y_j$的训练样例中取值$x_i$的样例数,$m$是称为等价样本大小的参数,而$p$是用户指定的参数。如果没有训练集(即$n=0$),则$P(x_i|y_j)=p$。因此$p$可以看作是在类$y_j$的记录中观察属性值$x_i$的先验概率。等价样本大小决定先验概率$p$和观测概率$n_c/n$之间的平衡。

在前面的例子中,条件概率$P(婚姻=离异|Yes) = 0$,因为类中没有训练样例含有该属性值。使用$m$估计方法,$m=4,p=1/4$,则条件概率不再是0:
$$
P(婚姻=离异|Yes) = (0 + 4 \times 1/4) / (4 + 4) = 1/8
$$

7. 参考资料