一、模型介绍

贝叶斯分类器是一类分类算法的总称，贝叶斯定理是这类算法的核心，因此统称为贝叶斯分类。下面，我们将会从贝叶斯决策论、极大似然估计、朴素贝叶斯分类器、半朴素贝叶斯分类器、贝叶斯网络来进行讲解。

1、贝叶斯决策论

贝叶斯决策论(Bayesian decision theory)是概率框架下实施决策的基本方法。机器学习所要实现的是基于有限的训练样本尽可能准确地估计出后验概率 $ p(c|x)$ 。而估计后验概率的方式有两种：

判别式模型(discriminative models)，通过直接建模$ P(c|x)$ 来预测，其中决策树，BP神经网络，支持向量机都属于判别式模型
生成式模型(generative models)，通过对联合概率模型$ P(x，c)$进行建模，然后再获得$ P(c|x)$ 。贝叶斯方法就是基于生成式模型构建的。

我们可以知道贝叶斯公式如下：
$p(c|x) = \frac{p(x,c)}{p(x)} = \frac{p(c)p(x|c)}{p(x)}$
其中$ p(c|x)$ 是样本$ x$ 相对于标签$ c$ 的条件概率，也称为似然，在这里是后验概率（指在得到样本$ x$ 时，我们对结果$ c$ 的估计）。 $ p(c)$ 是先验概率（在进行建模前就已知的概率），这里指标签$ c$ 出现的概率。$ p(x|c)$ 指的是在已知标签$ c$ 时，样本$ x$ 出现的概率。$ p(x)$ 表示样本$ x$ 出现的概率

对于二分类而言，我们使用贝叶斯模型要做的就是，计算$ p(1|x)$ 与$ p(0|x)$ 的大小，选择较大的那个作为分类结果。即：贝叶斯决策论是基于最小风险的

贝叶斯决策理论的“最优”性

贝叶斯决策论选择后验概率中最大的哪一个作为预测结果，这保证了我们预测的错误概率是最小的，这就是其“最优”性。

贝叶斯决策论的最小误分概率

我们定义最小误分概率如下：

$R^* = \sum_Xp(X)·min(p(y=0|X),p(y=1|X))$

易知$ \sum_Xp(X) = 1$ 且$ 0\le min(p(y=0|X),p(y=1|X))\le 0.5$ ，我们可以得到$ 0 \le R^* \le 0.5$ 。因此贝叶斯决策论保证了我们我们的预测的正确率是大于50%的。

上面的情况还只是随机情况，当我们建模比较好时，或许我们可以得到$ min(p(y=0|X),p(y=1|X))\le 0.2$ 那么该决策的误分概率就低于20%。

贝叶斯公式的另一个优点时，其能够维持先验和观测对象之间的平衡，即不会出现在数据集上有99%的正例时，模型将所有的结果都预测为正例的情况，贝叶斯公式有机地通过$ p(X)$对于先验进行调节，保证结果不会完全被先验概率所决定。

缺点

贝叶斯决策论的假设性比较强，实际操作太难。我们无法活得真实的先验概率，只能通过统计学的方法进行估计
在计算概率时，会面临维度灾难，即当$ X$ 的特征较多时，我们要将这些概率相乘，可能会使得其趋近于0，数值很不稳定

我们的模型就是上面的贝叶斯模型，但是$ p(x|c),p(x),p(c)$ 这些参数是未知的，我们怎么样通过观测结果（训练集）来得到这些参数（不只是上面的三个参数，还包括某个特征/样本在训练集中出现的概率，是个统称，这里可以记为$ \theta$ ），以及我们需要的概率呢？

极大似然估计（Maximum Likelihood Estimation，MLE）和贝叶斯估计（Bayesian Estimation）是统计推断中两种最常用的参数估计方法，这两种方法，也分别是频率派和贝叶斯派的观点

2、极大似然估计MLE

假设我们有训练集$ X$，共有n个独立同分布的样本$ x_1,x_2,……$ ，$ \theta$ 表示模型的参数，也可以说是整个模型。那么，我们可以得到，在这个模型中，出现这个n个样本的概率为：

其中$ f(x_i|\theta)$ 表示在这个模型中，样本$ x_i$ 出现的概率。

当概率$ p(x_1,x_2,……|\theta)$ 最大时，我们就能够得到最符合这个模型的参数$ \theta$ 。

需要注意的是，连乘容易造成下溢，我们一般将其转换成对数的形式$ ln L(X|\theta) = \sum_{x_i \in X} ln f(x_i|\theta)$

我们可以得到我们要的参数$ \theta_{MLE} = argmax_{\theta} ln L(X|\theta)$

举例

假设有一个袋子，里面有黑白两种颜色的球，我们不知道里面黑球和白球的比例。我们从袋子中拿球，然后放回，进行了100次的拿球操作，总过拿到了70个白球，问白球的比例是多少。

我们使用极大似然估计的思想，对上面的参数$ \theta$ （也就是白球的比例$ p$）进行估计。

$L(X|\theta) = p(x_1|\theta)·p(x_2|\theta)····p(x_{100}|\theta) \\ =p^{70}(1-p)^{30}$

于是：

$ln\ L(X|\theta) = 70ln\ p + 30ln(1-p)$

求导取最大值

$ln'L(X|\theta) = \frac{70}{p} - \frac{30}{1-p}$

于是得到$ p=0.7$

优缺点

这种方法比较简单，但是假设条件非常严格，要求训练集符合真实的数据分布

3、朴素贝叶斯分类器

贝叶斯估计法，是如何得到上面的参数呢？其采用了一个很重要的假设，假设所有的属性都是互相独立的(属性条件独立性假设），即：对于联合概率有$ p(x,y) = p(x)p(y)$

此时，我们假设样本$ x=(x_1,x_2,……x_d)$，样本$ x$ 共有$ d$ 个特征，则贝叶斯公式可以改写为：

$P(c|x) = \frac{P(c)P(x|c)}{P(x)} = \frac{P(c)}{P(x)}\prod_{i=1}^dP(x_i|c)$

因此，朴素贝叶斯分类器的训练过程，就是基于训练集D来估计类先验概率$ P(c)$ ，并为每个属性估计条件概率$ P(x_i|c)$ 。

估计类先验概率$ P(c)$

令$ D_c$ 表示训练集$ D$ 中第$ c$ 类样本组成的集合，若有充足的独立同分布样本，则可容易地估计出类先验概率：

$P(c) = \frac{|D_c|}{|D|}$

估计属性条件概率$ P(x_i|c)$

对离散属性而言，令$ D_{c,x_i}$ 表示$ D_c$ 中在第$ i$ 个属性上取值为$ x_i$ 的样本组成的集合，则条件概率可估计为：

$P(x_i|c) =\frac{|D_{c,x_i}|}{|D_c|}$

对连续属性而言，我们可以考虑概率密度函数，假定$ p(x_i|c) \thicksim \mathcal{N}(\mu_{c,i},\sigma_{c,i}^2)$ ，其中$ \mu_{c,i}$ 和$ \sigma_{c,i}$ 分别是第$ c$ 类样本在第$ i$ 个属性上取值的均值和方差，则有：

$p(x_i|c) = \frac{1}{\sqrt{2\pi}\sigma_{c,i}}exp(-\frac{(x_i-\mu_{c,i})^2}{2\sigma_{c,i}^2})$

拉普拉斯修正

为了避免其他属性携带的信息被训练集中未出现的属性值”抹去”，在估计概率时通常要进行”平滑”，令$ N$ 表示训练集$ D$ 中可能的类别数，$ N_i$ 表示第$ i$ 个属性可能的取值数，则上面的公式修改为：

$P(c) = \frac{|D_c|+1}{|D|+N} \\ P(x_i|c) =\frac{|D_{c,x_i}|+1}{|D_c|+N_i}$

缺点

朴素贝叶斯分类器所进行的属性条件独立假设在现实生活中很难成立

4、半朴素贝叶斯分类器

半朴素贝叶斯分类器对属性条件独立性假设进行了一定程度的放松。半朴素贝叶斯分类器适当考虑一部分属性间的相互依赖信息，从而既不需要进行完全联合概率计算，又不彻底忽略了比较强的属性依赖关系。

独依赖估计(ODE)

独依赖估计是半朴素贝叶斯分类器最常用的策略，就是假设每个属性在类别之外最多只依赖一个其他属性，即：

$P(c|x) \varpropto P(c)\prod_{i=1}^dP(x_i|c,pa_i)$

其中$ pa_i$ 为属性$ x_i$ 所依赖的属性，称为$ x_i$ 的父属性。

若$ pa_i$ 已知，那么我们可以得到其概率值：

$P(x_i|c,pa_i) = \frac{|D_{x_i,c,pa_i}|+1}{|D_c,pa_i|+N_i}$

那么，我们的问题就是，如何确定这个父属性？

最直接的方法，就是假设所有的属性都依赖于同一个属性，称为“超父”，通过交叉验证等模型选择方法来确定超父属性，即：“SPODE”方法

TAN

TAN(Tree Augmented naive Bayes)是在最大带权生成树算法的基础上，通过下列步骤将属性间依赖关系约简为树形结构的：

计算两个属性之间的条件互信息

$I(x_i,x_j|y) = \sum_{x_i,x_j;c\in \mathcal{Y}} P(x_i,x_j|c) log\frac{P(x_i,x_j|c)}{P(x_i|c)P(x_j|c)}$

以属性为节点，构建完全图，任意两个结点之间的权重设为$ I(x_i,x_j|y)$
构建此完全图的最大带权生成树，挑选根变量，将边置为有向
加入类别节点$ y$ ，增加从$ y$ 到每个属性的有向边

条件互信息$ I(x_i,x_j|y)$ 刻画了属性$ x_i$ 和属性$ x_j$ 在已知类别情况下的相关性。因此，TAN通过最大生成树算法，仅保留了强相互属性之间的关系。

AODE

AODE(Averaged One-Dependent Estimator)是基于集成学习机制，更为强大的独依赖分类器，与SPODE通过模型选择超父属性不同，AODE尝试将每个属性作为超父来构建SPODE,然后将那些具有足够训练数据支撑的SPODE集成起来作为最终结果，即：

$P(c|x) \varpropto \sum_{i=1\\|D_{x_i}| \ge m'}^d P(c,x_i)\prod_{j=1}^dP(x_j|c,x_i)$

其中$ D_{x_i}$ 是在第$ i$ 个属性上取值为$ x_i$ 的样本的集合，$ m’$ 为阈值常数。

AODE需要估计$ P(c,x_i)$ 和$ P(x_j|c,x_i)$ ，我们可以得到：

$P(c,x_i) = \frac{|D_{c,x_i}|+1}{|D|+N_i} \\ P(x_j|c,x_i) = \frac{|D_{c,x_i,x_j}|+1}{|D_{c,x_i}|+N_i}$

与朴素贝叶斯分类器相似，AODE无需进行模型选择，能够节省预测时间，易于实现增量学习。

5、贝叶斯网

半朴素贝叶斯分类器是将属性条件独立假设放松为独依赖假设来得到泛化性能的提升，那么我们可以通过可考虑属性间的高阶依赖来进一步提升泛化性能，即，我们要考虑属性的多个依赖关系，将ODE中的$ pa_i$ 替换成包含$ k$ 个属性的集合$ pa_i$

贝叶斯网(Bayesian network)也称信念网(belief network),它借助有向无环图(Directed Acyclic Graph,简称DAG)来刻画属性之间的依赖关系，并使用条件概率表(Conditional Probability Table,简称CPT)来描述属性的联合概率分布。

一个贝叶斯网$ B$ 由结构$ G$ 和参数$ \Theta$ 两部分构成，即$ B=$ < $ G,\Theta$ > ，网络结构$ G$ 是一个有向无环图，其每个节点对应了一个属性，若两个属性有直接依赖关系，则它们由一条边连接起来；参数$ \Theta$ 定量描述了这种依赖关系，假设属性$ x_i$ 在$ G$ 中的父节点集为$ \pi_i$ ，$ \Theta$ 包含了每个属性的条件概率，$ \theta_{x_i|\pi_i} = P_B(x_i|\pi_i)$ 。

结构

贝叶斯网络结构有效的表达了属性间的条件独立性。给父节点集，贝叶斯假设每个属性与他的非后裔属性独立，于是$ B=$ 将属性$ x_1,x_2,······$ 的联合概率分布定义为：

$P_B(x_1,x_2,...,x_d) = \prod_{i=1}^dP_B(x_i|\pi_i) = \prod_{i=1}^d \theta_{x_i|\pi_i}$

以上图7.2为例，其联合概率密度定义为：

$P(x_1,x_2,x_3,x_4,x_5) = P(x_1)P(x_2)P(x_3|x_1)P(x_4|x_1,x_2)P(x_5|x_2)$

从上面的贝叶斯网我们可以得到，$ x_3$ 和$ x_4$ 在$ x_1$ 已知的情况下独立，$ x_4$ 和$ x_5$ 在$ x_2$ 已知的情况下独立，即：$ x_3 \bot x_4|x_1$ ，$ x_4 \bot x_5|x_2$

贝叶斯网的三种典型依赖关系如下：

我们可以借助这些结构，来分析贝叶斯网中各个属性节点的独立性。

在同父结构下，给定$ x_1$ 的取值，$ x_3$ 与 $ x_4$ 独立

在V型结构下，给定$ x_4$ 的取值，$ x_1$ 与 $ x_2$ 必不独立，在$ x_4$ 未知时，$ x_1$ 与 $ x_2$ 独立

在顺序结构下，给定$ x$ 的取值，$ y$ 与 $ z$ 独立

我们可以借助这些结构，将贝叶斯网络转换成”道德图”来进行独立性的分析

找出有向图中的所有V型结构，在V型结构的两个父节点之间加一条无向边
将所有有向边改为无向边，由此产生的图，就叫道德图

图7.2的道德图如下：

学习

根据上一节的知识，我们已经知道了关于贝叶斯网结构的一些知识，那么我们该怎么构建一个贝叶斯网络呢？贝叶斯网络学习的首要任务就是根据训练数据集找出最”恰当”的贝叶斯网，”评分搜索“是求解这一问题的常用办法

“评分搜索”：定义个一个评分函数，以此来评估贝叶斯网与训练数据的契合程度，然后基于评分函数来寻找结构最优的贝叶斯网。

评分函数决定了贝叶斯网络的归纳偏好。

常用评分函数基于信息论准则，将学习问题看作一个数据压缩任务，学习的目标是能找到一个能以最短编码长度描述训练数据的模型。

对于贝叶斯网络学习而言，模型就是一个贝叶斯网，同时，每个贝叶斯网描述了一个在训练数据上的概率分布，自有一套编码机制能使那些经常出现的样本有更短的编码。于是，我们应选择那个综合编码长度（包括描述网络和编码数据）最短的贝叶斯网，这就是“最小描述长度准则”(Minimal Description Length,简称MDL)。

给定训练集$ D = {x_1,x_2,…,x_m}$ ，贝叶斯网在$ B=$ < $ G,\Theta$ > 上的评分函数可写为：

$s(B|D) = f(\theta)|B| - LL(B|D)$

其中,$ |B|$ 是贝叶斯网的参数($ \theta_{x_i|\pi_i}$)的个数，$ f(\theta)$ 表示每个参数$ \theta$ 所需的字节数，且：

$LL(B|D) = \sum_{i=1}^m log \ P_B(x_i)$

是贝叶斯网$ B$ 的对数似然。

因此，学习任务转换成了一个优化任务，即寻找一个贝叶斯网$ B$ 使评分函数最小。

除了上面的评分函数，我们还有：

AIC(Akaike Information Criterion)评分函数：$ AIC(B|D) = |B| - LL(B|D)$

BIC(Bayesian Information Criterion)评分函数：$ BIC(B|D) = \frac{log m}{2}|B| - LL(B|D)$

我们可以发现，当评分函数第一项为0或常数时，评分函数退化为负对数对然。当结构$ G$ 固定时，评分函数第一项为常数，此时，最小化评分函数，等价于对参数$ \Theta$ 的极大似然估计。当然，我们的参数$ \theta_{x_i|\pi_i}$ 可以直接通过训练数据集$ D$ 通过经验估计获得，即：

$\theta_{x_i|\pi_i} = \hat{P_D}(x_i|\pi_i)$

不过，在网络结构空间中搜索最优贝叶斯网络是一个NP难问题，很难快速求解。我们可以借助以下两种方法来进行搜索：

贪心法。从某个网络结构出发，每次调整一条边（增加、删除、调整方向）直到评分函数值不再降低
通过给网络结构施加约束来削减搜索空间，例如将网络结构限定为树形结构等

推断

当贝叶斯网络训练好之后，我们就可以利用这个网络来进行分类等问题的解决了。通过已知变量观测值来推测待查询变量的过程称为推断(inference)，已知变量观测值称为证据(evidence)。

最理想的是直接根据贝叶斯网定义的联合概率分布来精确计算后验概率，但是这是NP难的，当网络结点较多，连接稠密时，难以进行精确判断，此时需借助近似判断。现实应用中，贝叶斯网的近似推断通常使用吉布森采样(Gibbs sampling)来完成。

以下是吉布森采样的工作过程：

二、模型分析

1、模型应用

贝叶斯网络适用于由离散变量构成的数据集合，变量之间满足一定的条件独立关系，且此条件独立关系能够用一个有向无环图来描述。贝叶斯网络可以针对给定的任务实现预测、分类、诊断、聚类、因果分析等数据挖掘的功能。根据初始条件和推理目标的不同，贝叶斯网络的应用类型各不相同。

可以应用于多分类任务
比较适合文本处理问题，比如敏感邮件的检测等

2、模型优缺点

优点

朴素贝叶斯模型（NBC）发源于古典数学理论，有着坚实的数学基础，以及稳定的分类效率。
朴素贝叶斯模型（NBC）所需估计的参数很少，对缺失数据不太敏感，算法也比较简单。

缺点

理论上，朴素贝叶斯模型（NBC）与其他分类方法相比具有最小的误差率。但是实际上并非总是如此，这是因为NBC模型假设属性之间相互独立，这个假设在实际应用中往往是不成立的（可以考虑用聚类算法先将相关性较大的属性聚类），这给NBC模型的正确分类带来了一定影响。在属性个数比较多或者属性之间相关性较大时，NBC模型的分类效率比不上决策树模型。而在属性相关性较小时，NBC模型的性能最为良好。
需要知道先验概率。
分类决策存在错误率

参考链接