精读西瓜书(第七章-贝叶斯分类器)-半朴素贝叶斯分类器

写在前面

  • 昨天, 我们学习了贝叶斯分类器中的朴素贝叶斯分类器; 今天, 我们继续学习贝叶斯分类器中的半朴素贝叶斯分类器.

半朴素贝叶斯分类器

  • 为了降低贝叶斯公式中估计后延概率 \(P(c|x)\) 的困难, 朴素贝叶斯分类器采用了属性条件独立性假设, 但在现实任务中这个假设旺旺很难成立. 于是, 人们尝试对属性条件独立性假设进行一定程度的放松, 由此产生了一类称为’半朴素贝叶斯分类器’(Semi-Naive Bayes Classifiers)的学习方法. 半朴素贝叶斯分类器的基本想法是适当考虑一部分属性间的相互依赖信息, 从而不需进行完全联合概率计算, 又不至于彻底忽略了比较强的属性依赖关系. ‘独依赖估计’(One-Dependent Estimator, 简称ODE)是半朴素贝叶斯分类器最常用的一种策略. 顾名思义, 所谓’独依赖’就是假设每个属性在类别之外最多仅依赖于一个其他属性, 即:

  • 其中 \(pa_{i}\) 为属性 \(x_{i}\) 的父属性. 此时, 对每个属性 \(x_{i}\) , 若其父属性 \(pa_{i}\) 已知, 则可采用类似的方法来估计概率值 \(P(x_{i}|c, pa_{i})\) . 于是, 问题的关键就转化为如何确定每个属性的父属性, 不同的做法产生不同的独依赖分类器. 最直接的做法是假设所有属性都依赖于同一个属性, 称为’超父’(Super Parent), 然后通过交叉验证等模型选择方法来确定超父属性, 由此形成了SPODE(Super-Parent ODE)方法. 如下图, \(x_{1}\) 是超父属性:

  • TAN(Tree Augmented Naive Bayes)则是在最大带权生成树(Maximum Weighted Spanning Tree)算法的基础上, 通过以下步骤将属性建依赖关系约简为上图的树状结构:

  • 容易看出, 条件互信息 \(I(x_{i}, x_{j} | y)\) 刻画了属性 \(x_{i}\) 和 \(x_{j}\) 在已知类别的情况下的相关性, 因此, 通过最大生成树算法. TAN实际上仅保留了强相关属性之间的依赖性. AODE(Averaged One-Dependent Estimator)是一种基于集成学习机制, 更为强大的独依赖分类器. 与SPODE通过模型选择确定超父属性不同, AODE尝试将每个属性作为超父来构建SPODE, 然后将那些具有足够训练数据支撑的SPODE集成起来作为最终结果, 即:

  • 其中 \(D_{x_{i}}\) 是在第 \(i\) 个属性上取值为 \(x_{i}\) 的样本的集合, \(m’\) 为阈值常数. 显然, AODE需估计 \(P(c, x_{i})\) 和 \(P(x_{j}|c, x_{i})\) . 则有:

  • 其中 \(N_{i}\) 是第 \(i\) 个属性可能的取值数, \(D_{c, x_{i}}\) 是类别为 \(c\) 且在第 \(i\) 个属性上取值为 \(x_{i}\) 的样本集合, \(D_{c, x_{i}, x_{j}}\) 是类别为 \(c\) 且在第 \(i\) 和第 \(j\) 个属性上取值分别为 \(x_{i}\) 和 \(x_{j}\) 的样本集合.
  • 不难看出, 与朴素贝叶斯分类器想死, AODE的训练过程也是’计数’, 即在训练数据集上对符合条件的样本进行计数的过程. 与朴素贝叶斯分类器相似, AODE无需模型选择, 既能通过预计算节省预测时间, 也能采取懒惰学习方式在与测试再进行计数, 并且易于实现增强学习. 若训练数据非常充分, 泛化性能有可能提升; 但在有限样本条件下, 则有陷入估计高阶联合概率的泥沼.

写在后面

  • 今天, 我们学习了贝叶斯分类器中的半朴素贝叶斯分类器; 明天, 我们将继续学习贝叶斯分类器中的贝叶斯网.