04. 半朴素贝叶斯分类器

来源：原始 Jupyter Notebook。内容已转换为网页阅读格式；下载原文件。

我们回顾一下朴素贝叶斯分类器，它的表达式如下：

\begin{align} y = f(x) &= \mathop{\arg\max}_{c_k} P(Y=c_k|X=x) \\ &= \mathop{\arg\max}_{c_k} P(Y=c_k)P(X=x|Y=c_k) \\ &= \mathop{\arg\max}_{c_k} P(Y=c_k) \prod_i P(X=x^{(i)}|Y=c_k) \end{align}

可以看出在使用贝叶斯公式计算后验概率 $P(Y=c_k|X=x)$ 时，类条件概率 $P(X=x|Y=c_k)$ 很难计算，它是所有属性上的联合概率，难以从有限的训练样本直接估计出来。所以，朴素贝叶斯分类器采用了一个很简单的假设：属性条件独立性假设，也就是说所有的属性相互独立，这样类条件概率可以写成每个属性的条件概率的乘积。

不过在现实任务中，这个独立性假设往往很难成立，于是便有了 半朴素贝叶斯分类器（semi-naive Bayes classifiers），它的基本思想是适当的考虑一部分属性间的相互依赖信息，既不需要计算完全联合概率，又不至于彻底忽略了比较强的属性依赖关系。

独依赖估计（One-Dependent Estimator，简称 ODE）是半朴素贝叶斯分类器最常用的一种策略，它假设每个属性在类别之外最多仅依赖于一个其他属性：

y = f(x) = \mathop{\arg\max}_{c_k} P(Y=c_k) \prod_i P(X=x^{(i)}|Y=c_k, X=pa^{(i)})

其中 $pa^{(i)}$ 为属性 $x^{(i)}$ 所依赖的属性，称为 $x^{(i)}$ 的父属性，若父属性 $pa^{(i)}$ 已知，概率 $P(X=x^{(i)}|Y=c_k, X=pa^{(i)})$ 也就很容易计算，所以问题也就转化为如何确定每个属性的父属性。常见的方法有：

SPODE（Super-Parent ODE），它假设所有属性都依赖于同一个属性，称为超父（super-parent），然后通过交叉验证等模型选择方法来确定超父属性
AODE（Averaged ODE），它尝试将每个属性作为超父来构建 SPODE，然后将那些具有足够训练数据支撑的 SPODE 通过集成学习汇聚起来得到结果
TAN（Tree Augmented naive Bayes）通过计算任意两个属性之间的 条件互信息（conditional mutual information）构建完全图，再根据 最大带权生成树（maximum weighted spanning tree）算法保留强相关属性之间的依赖性

将 属性条件独立性假设 放松为 独依赖假设 可能获得泛化性能的提升，那么将 独依赖假设（ODE）再放松到 k依赖假设（kDE），是否能进一步提升泛化性能呢？要注意的是，随着 k 的增加，准确估计概率 $P(X=x^{(i)}|Y=c_k, X=pa^{(i)})$ 所需的训练样本数量将以指数级增加，因此，如果训练数据非常充分，泛化性能有可能提升，但是在有限样本条件下，效果不一定好。