S 贝叶斯分类器考虑属性间关系

• 在求解 $P(\boldsymbol x \ | \ c)$ 的分布时，留意到对 $\boldsymbol x$ 而言是所有属性上的联合分布，因而比较困难。对于各个属性间的关系不同，因而产生了不同的方式。
• 比如下面三个就根据对属性间依赖的涉及程度，形成了一个「谱 (spectrum)」：
  • 朴素 (naive) 贝叶斯分类器：认为各个类别下，属性均为相互独立的。
  • 半朴素 (semi-naive) 贝叶斯分类器：适当考虑一部分属性间的相互依赖信息，一般具有一定的结构，比如下面要介绍的 SPODE、TAN、AODE、kDE。
  • 贝叶斯网 (Bayesian network)（信念网 belief network）：能够表示任意属性间的依赖性。

A 朴素贝叶斯分类器

A1 朴素贝叶斯分类器

i. 朴素贝叶斯分类器

• 朴素的贝叶斯分类器认为各个类别下属性均为相互独立，对于任一 $\boldsymbol x$，有：

  $$ P(\boldsymbol x \ | \ c) = \prod_{d=1}^{N} P(x_d \ | \ c) $$

• 因而能最小化分类错误率的朴素贝叶斯最优分类器为：

  $$ h^*(\boldsymbol x) = \argmax_{c \in [1, C] \cap \Z} P(c) P(\boldsymbol x \ | \ c) = \argmax_{c \in [1, C] \cap \Z} P(c) \prod_{d=1}^{N} P(x_d \ | \ c) $$

ii. $P(c)$ 的求法

• 如果有充足的独立同分布样本，根据大数定律， 有 $P(c) = \frac {|D_c|}{|D|}$。

iii. $P(x_d \ | \ c)$ 的求法

1. 对离散属性 $d$ 的任意值 $x_d$ 而言，可以继续用大数定律 $P(x_d \ | \ c) = \frac {|D_{c} \cap D_{[d:x_d]}|}{|D_c|}$。（$D_{[d:x_d]}$ 为在属性 $d$ 下取值为 $x_d$ 的样例构成的集合）
2. 对连续属性或者样本不足的离散属性 $d$ 的任意值 $x_d$ 而言，可以考虑用概率密度函数 $f(x_d \ | \ c)$ 代替 $P(x_d \ | \ c)$。通常的方法是高斯分布。

iv. 朴素贝叶斯分类器的使用方法

• 下面的「估值」是指 $P(c)$ 和 $P(x_d \ | \ c)$（离散值，或是概率密度分布）。
  • 可以先行计算所有的估值，存储起来，之后实际使用时进行查询；
  • 可以懒惰学习，收到查询请求时相应进行计算；
  • 可以增量学习，只需对新增样本属性值涉及的估值进行更新。

v. 朴素贝叶斯分类器的使用效果

• 其实非常好，有的时候属性间依赖关系是一致的、或者存在相互抵消的现象，这时朴素假设也会有很好的效果。

A2 朴素贝叶斯分类器缺失离散属性样本时的处理

i. 缺失离散属性样本的影响

• 如果某个离散属性 $d$ 的某值 $x_d$ 没有与某个类 $c$ 同时出现过，那么 $P(x_d \ | \ c) = 0$。
• **影响：**求各维度概率连乘时，无论其他维度的概率有多大，都会被这个 0 给「抹去」，导致不可能出现这个类别 $c$ 的结果。显然会带来泛化性能的降低。

ii. 修正方法：拉普拉斯修正

• 一个解决方法是对数据进行「拉普拉斯修正」，即：

  1. 对 $P(c)$ 的求法，为每个类别增加一个样本：

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

  2. 对 $P(x_d \ | \ c)$ 的求法，为当前离散属性 $d$ 的每个取值增加一个样本（$V_d$ 为离散属性 $d$ 的各个可能取值构成的集合）：

     $$ P(x_d \ | \ c) = \frac {|D_{c} \cap D_{[d:x_d]}| + 1}{|D_c| + |V_d|} $$

A3 对于连续值缺失样本时的处理

i. 缺失连续属性样本的影响

• 当对某个属性 $d$ 用 PDF 模型 $f(x_d \ | \ c)$ 进行 $P(x_d \ | \ c)$ 替代的时候，可能会遇到某值 $x_d$，其在某类别 $c$ 下：
  1. 要么完全不存在例子，使得 PDF 恒为 0。
  2. 要么虽存在例子但太少，使得 PDF 模型产生部分 0 或在某点无穷大。
     • 比如高斯模型在只有一个样本的时候方差为 0，导致 PDF 是一个位移后的冲激函数 $\delta(x_d)$，取值绝大部分为 0，除了均值点上取值无穷大。
• **影响：**无论是 0 还是 +∞，都会「抹去」其他维度的存在，影响同离散属性情况。

ii. 修正方法

• 我看没有人讨论。

B 半朴素贝叶斯分类器

B0 半朴素贝叶斯分类器

i. 独依赖估计（ODE）

• 独依赖估计 (One-Dependent Estimator, ODE) 是半朴素贝叶斯分类器最常用的一种策略，其假设每个属性 $d$ 在类别之外，最多依赖于一个其他属性（记作 $pa_d$）：

  $$ P(\boldsymbol x \ | \ c) \propto \prod_{d=1}^{N} P(x_d \ | \ c, x_{pa_d}) $$

• 换句话说，如果把类别本身都算成一个节点，半朴素的依赖关系就构成了类似网络的结构，如下图（NB = Naive Bayesian）。