Question

1. 朴素贝叶斯法对条件概率做了特征的独立性假设： $ MathJax-Element-113 $ 。

   但是现实任务中这个假设有时候很难成立。若对特征独立性假设进行一定程度上的放松，这就是半朴素贝叶斯分类器semi-naive Bayes classifiers 。

2. 半朴素贝叶斯分类器原理：适当考虑一部分特征之间的相互依赖信息，从而既不需要进行完全联合概率计算，又不至于彻底忽略了比较强的特征依赖关系。

3.1 独依赖估计 OED

1. 独依赖估计One-Dependent Estimator:OED是半朴素贝叶斯分类器最常用的一种策略。它假设每个特征在类别之外最多依赖于一个其他特征，即：

   $ p( \mathbf{\vec x}\mid y)=p(x_1,x_2,\cdots, x_n\mid y) =\prod_{j=1}^{n}p(x_j\mid y,x_j^P) $

   其中 $ MathJax-Element-114 $ 为特征 $ MathJax-Element-119 $ 所依赖的特征，称作的 $ MathJax-Element-119 $ 父特征。

2. 如果父属性已知，那么可以用贝叶斯估计来估计概率值 $ MathJax-Element-117 $ 。现在的问题是：如何确定每个特征的父特征？

   不同的做法产生不同的独依赖分类器。

3.1.1 SPODE

1. 最简单的做法是：假设所有的特征都依赖于同一个特征，该特征称作超父。然后通过交叉验证等模型选择方法来确定超父特征。这就是SPODE:Super-Parent ODE方法。

   假设节点 Y 代表输出变量 $ MathJax-Element-132 $ ，节点 Xj 代表属性 $ MathJax-Element-119 $ 。下图给出了超父特征为 $ MathJax-Element-120 $ 时的 SPODE 。

   

3.1.2 TAN

1. TAN:Tree Augmented naive Bayes是在最大带权生成树算法基础上，通过下列步骤将特征之间依赖关系简化为如下图所示的树型结构：

   • 计算任意两个特征之间的条件互信息。记第 $ MathJax-Element-121 $ 个特征 $ MathJax-Element-122 $ 代表的结点为 $ MathJax-Element-123 $ ，标记代表的节点为 $ MathJax-Element-124 $ 则有:

     $ I(\mathbf X_i,\mathbf X_j\mid \mathbf Y)=\sum_y\sum_{x_i}\sum_{x_j} p(x_i,x_j\mid y)\log \frac{p(x_i,x_j\mid y)}{p(x_i\mid y)p(x_j\mid y)} $

     如果两个特征 $ MathJax-Element-125 $ 相互条件独立，则 $ MathJax-Element-126 $ 。则有条件互信息 $ MathJax-Element-127 $ ，则在图中这两个特征代表的结点没有边相连。

   • 以特征为结点构建完全图，任意两个结点之间边的权重设为条件互信息 $ MathJax-Element-128 $ 。

   • 构建此完全图的最大带权生成树，挑选根结点（下图中根节点为节点 $ MathJax-Element-129 $ )，将边置为有向边。

   • 加入类别结点 $ MathJax-Element-131 $ ，增加 $ MathJax-Element-131 $ 到每个特征的有向边。因为所有的条件概率都是以 $ MathJax-Element-132 $ 为条件的。