贝叶斯分类器

一、贝叶斯定理

1.1 贝叶斯定理

  1. 为试验 的样本空间; 的一组事件。若 :

    则称 为样本空间 的一个划分。

  2. 如果 为样本空间 的一个划分,则对于每次试验,事件 中有且仅有一个事件发生。

  3. 全概率公式 :设试验 的样本空间为 的事件, 为样本空间 的一个划分,且 。则有:

  4. 贝叶斯定理 :设试验 的的样本空间为 的事件, 为样本空间 的一个划分,且 ,则有:

1.2 先验概率、后验概率

  1. 先验概率:根据以往经验和分析得到的概率。

    后验概率:根据已经发生的事件来分析得到的概率。

  2. 例:假设山洞中有熊出现的事件为 ,山洞中传来一阵熊吼的事件为

    • 山洞中有熊的概率为 。它是先验概率,根据以往的数据分析或者经验得到的概率。
    • 听到熊吼之后认为山洞中有熊的概率为 。它是后验概率,得到本次试验的信息从而重新修正的概率。

二、朴素贝叶斯法

  1. 朴素贝叶斯法是基于贝叶斯定理与特征条件独立假设的分类方法。

    对给定的训练集:

    • 首先基于特征条件独立假设学习输入、输出的联合概率分布。
    • 然后基于此模型,对给定的输入 ,利用贝叶斯定理求出后验概率最大的输出
  2. 朴素贝叶斯法不是贝叶斯估计,贝叶斯估计是最大后验估计。

2.1 原理

  1. 设输入空间 维向量的集合 ,输出空间为类标记集合

    为定义在 上的随机向量, 为定义在 上的随机变量。

    的联合概率分布,假设训练数据集 独立同分布产生。

    朴素贝叶斯法通过训练数据集学习联合概率分布 。具体的学习下列概率分布:

    • 先验概率分布:
    • 条件概率分布:
  2. 朴素贝叶斯法对条件概率做了特征独立性假设:

    • 这意味着在分类确定的条件下,用于分类的特征是条件独立的。
    • 该假设使得朴素贝叶斯法变得简单,但是可能牺牲一定的分类准确率。
  3. 根据贝叶斯定理:

    考虑分类特征的条件独立假设有:

    则朴素贝叶斯分类器表示为:

    由于上式的分母 的取值无关,则分类器重写为:

2.2 期望风险最小化

  1. 朴素贝叶斯分类器是后验概率最大化,等价于期望风险最小化。

  2. 令损失函数为:

  3. 根据 有:

    为了使得期望风险最小化,只需要对 中的元素极小化。

    ,则有:

    即:期望风险最小化,等价于后验概率最大化。

2.3 算法

  1. 在朴素贝叶斯法中,学习意味着估计概率:

  2. 可以用极大似然估计相应概率。

    • 先验概率 的极大似然估计为:

    • 设第 个特征 可能的取值为 ,则条件概率 的极大似然估计为:

      其中: 为示性函数, 表示第 个样本的第 个特征。

  3. 朴素贝叶斯算法 :

    • 输入 :

      • 训练集

        , 为第 个样本的第 个特征。其中 为第 个特征可能取到的第 个值。

      • 实例

    • 输出 :实例 的分类

    • 算法步骤:

      • 计算先验概率以及条件概率:
      • 对于给定的实例 ,计算:
      • 确定实例 的分类:

2.4 贝叶斯估计

  1. 在估计概率 的过程中,分母 可能为 0 。这是由于训练样本太少才导致 的样本数为 0 。而真实的分布中, 的样本并不为 0 。

    解决的方案是采用贝叶斯估计(最大后验估计)。

  2. 假设第 个特征 可能的取值为 ,贝叶斯估计假设在每个取值上都有一个先验的计数 。即:

    它等价于在 的各个取值的频数上赋予了一个正数

    的样本数为0,则它假设特征 每个取值的概率为 ,即等可能的。

  3. 采用贝叶斯估计后, 的贝叶斯估计调整为:

    • 时,为极大似然估计当 时,为拉普拉斯平滑
    • 的样本数为 0,则假设赋予它一个非零的概率

三、半朴素贝叶斯分类器

  1. 朴素贝叶斯法对条件概率做了特征的独立性假设:

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

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

3.1 独依赖估计 OED

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

    其中 为特征 所依赖的特征,称作的 父特征。

  2. 如果父属性已知,那么可以用贝叶斯估计来估计概率值 。现在的问题是:如何确定每个特征的父特征?

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

3.1.1 SPODE

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

    假设节点 Y 代表输出变量 ,节点 Xj 代表属性 。下图给出了超父特征为 时的 SPODE

    SPODE

3.1.2 TAN

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

    • 计算任意两个特征之间的条件互信息。记第 个特征 代表的结点为 ,标记代表的节点为 则有:

      如果两个特征 相互条件独立,则 。则有条件互信息 ,则在图中这两个特征代表的结点没有边相连。

    • 以特征为结点构建完全图,任意两个结点之间边的权重设为条件互信息

    • 构建此完全图的最大带权生成树,挑选根结点(下图中根节点为节点 ),将边置为有向边。

    • 加入类别结点 ,增加 到每个特征的有向边。因为所有的条件概率都是以 为条件的。 TAN

四、其它讨论

  1. 朴素贝叶斯分类器的优点:

    • 性能相当好,它速度快,可以避免维度灾难。
    • 支持大规模数据的并行学习,且天然的支持增量学习。
  2. 朴素贝叶斯分类器的缺点:

    • 无法给出分类概率,因此难以应用于需要分类概率的场景。