第 4 章 朴素贝叶斯法

1.1 本章概要

1. 朴素贝叶斯法是生成学习方法

   利用训练数据学习 $P(X|Y)$ 和 $P(Y)$ 的估计，得到联合概率分布：

   $$P(X, Y) = P(X|Y)P(Y)$$

2. 条件独立性

   $$P(X = x | Y= c_k) = P(X^{(1)} = x^{(1)}, X^{(2)} = x^{(2)}, ..., X^{(n)} = x^{(n)} | Y = c_k) = \prod\limits_{j=1}^{n}P(X^{(j)} = x^{(j)} | Y =c_k)$$

   此假设使朴素贝叶斯的学习与预测大为简化，易于实现，但分类性能不一定高

3. 利用联合概率模型进行分类预测

   $$P(Y|X) = \dfrac{P(X, Y)}{P(X)} = \dfrac{P(Y)P(X|Y)}{\sum\limits_YP(Y)P(X|Y)}$$

   将输入 $x$ 分给后验概率最大的类 $y$：

   $$y = arg\max\limits_{c_k} P(Y=c_k) \prod\limits_{j=1}^{n} P(X_j = x^{(j)} | Y = c_k)$$

4. 后验概率最大等价于 0-1 损失函数时的期望风险最小化

1.2 目录

1. 朴素贝叶斯法的学习与分类

   1.1 基本方法

   1.2 后验概率最大化的含义

2. 朴素贝叶斯的参数估计

   2.1 极大似然估计

   2.2 学习与分类算法

   2.3 贝叶斯估计

---

2.1 朴素贝叶斯法的学习与分类

思路：

1. 假设输入特征是条件独立的
2. 学习输入和输出的联合概率分布
3. 对于给定的输入，利用贝叶斯定理求出后验概率最大的输出

2.1.1 基本方法

1. 输入与输出

   输入特征向量 $x \in \chi$ ，输出类标记 $y \in \Upsilon$，令 $X$ 是定义在 $\chi$ 上的随机变量，$Y$ 是定义在输出空间 $\Upsilon$ 上的随机变量，则 $P(X, Y)$ 是 $X$ 和 $Y$ 的联合概率分布

2. 训练数据集

   $ T = { (x_1, y_1), (x_2, y_2), …, (x_n, y_n) }$ 由 $P(X, Y)$ 独立同分布产生

3. 通过训练数据集 $T$ 学习联合概率分布 $P(X, Y)$

   • 学习先验概率分布

     $$P(Y = c_k), k = 1, 2, ..., K$$

   • 学习条件概率分布

     $$P(X = x| Y= c_k) = P(X^{(1)} = x^{(1)}, X^{(2)} = x^{(2)}, ..., X^{(n)} = x^{(n)} | Y = c_k)$$

     强力假设：条件独立，朴素贝叶斯得名于此

     $$P(X = x| Y = c_k) = \prod\limits_{j=1}^{n}P(X^{(j)} = x^{(j)} | Y =c_k)$$

   • 得到联合概率分布

     $$P(X, Y) = P(X = x|Y= c_k)P(Y=c_k)$$

4. 对新输入 $x$ 分类，计算后验概率分布 $P(Y=c_k|X=x)$

   $$P(Y = c_k | X = x) = \dfrac{P(X=x|Y=c_k)P(Y=c_k)}{P(X)} = \dfrac{P(X=x|Y=c_k)P(Y=c_k)}{\sum_kP(X=x|Y=c_k)P(Y=c_k)}$$

5. 朴素贝叶斯分类器

   $$y = f(x) = arg\max\limits_{c_k} \dfrac{P(X=x|Y=c_k)P(Y=c_k)}{P(X)} = arg\max\limits_{c_k} \prod\limits_j P(X^{(j)} = x^{(j)} | Y =c_k)$$

2.1.2 后验概率最大化的含义

等价于期望风险最小化

2.2 朴素贝叶斯的参数估计

2.2.1 极大似然估计

朴素贝叶斯的学习即从训练数据集 $T$ 中估计 $P(Y = c_k)$ 和 $P(X^{(j)} = x^{(j)} | Y = c_k)$

1. 先验概率 $P(Y = c_k)$ 的极大似然估计：

   $$P(Y = c_k) = \dfrac{\sum\limits_{i=1}^N I(y_i = c_k)} {N} = \dfrac{\#\{y_i = c_k\}}{N}$$

   其中：$ k = 1, 2, …, K $

2. 条件概率 $P(X^{(j)} = x^{(j)} | Y = c_k)$

   假如第 $j$ 个特征 $x^{(j)}$ 可以取 ${a_{j1}, a_{j2}, … a_{jS_j} }$ 这些值，则

   $$P(X^{(j)} = a_{jl} | Y = c_k) = \dfrac{ \#\{ X^{(j)} = a_{jl}, Y=c_k \} }{ \#\{ Y = c_k\}}$$

2.2.2 学习与分类算法

算法 4.1 (朴素贝叶斯算法)

• 输入

  训练数据 $ T = { (x_1, y_1), (x_2, y_2), …, (x_n, y_n) }$，

  其中:

  $x_i = (x^{(1)}_i, x^{(2)}_i, …, x^{(n)}_i)^T$ ，$x^{(j)}_i$ 是第 $i$ 个样本的第 $j$ 个特征

  $x^{(j)}i \in { a{j1}, a_{j2}, …, a_{jS_j} }$， $a_{jl}$ 是第 $j$ 个特征的第 $l$ 个取值

• 输出

  实例 $x$ 的分类

• 过程

  1. 计算先验概率 $P(Y = c_k)$

     $$P(Y = c_k) = \dfrac{\sum\limits_{i=1}^N I(y_i = c_k)} {N} = \dfrac{\#\{y_i = c_k\}}{N}$$

  2. 计算条件概率 </span>$ P(X^{(j)} = x^{(j)}

     Y = c_k) $</span>

     $$P(X^{(j)} = a_{jl} | Y = c_k) = \dfrac{ \#\{ X^{(j)} = a_{jl}, Y=c_k \} }{ \#\{ Y = c_k\}}$$

  3. 对于实例 $x$ 计算

     $$P(Y=c_k)\prod\limits_j P(X^{(j)} = x^{(j)} | Y =c_k)$$

  4. 确定实例 $x$ 的类

     $$arg\max\limits_{c_k} \prod\limits_j P(X^{(j)} = x^{(j)} | Y =c_k)$$

2.2.3 贝叶斯估计

当训练数据集 $T$ 数量少，但类别多时，可能某个类别没有收集到实例，这地极大似然估计会遇到要估计的概率值为0的情况。这时采用贝叶斯估计来处理。

1. 条件概率 $P(X^{(j)} = x^{(j)} | Y = c_k)$ 的贝叶斯估计为

   $$P(X^{(j)} = a_{jl} | Y = c_k) = \dfrac{ \#\{ X^{(j)} = a_{jl}, Y=c_k \} + \lambda}{ \#\{ Y = c_k\} + S_j \lambda}$$

   其中 $S_j$ 是第 $j$ 个特征可能取值的总数

2. 先验概率 $P(Y = c_k)$ 的贝叶斯估计

   $$P(Y = c_k) = \dfrac{\sum\limits_{i=1}^N I(y_i = c_k)+\lambda} {N+K\lambda} = \dfrac{\#\{y_i = c_k\} + \lambda}{N + K\lambda}$$

---

第 5 章 决策树

决策树是基本的分类和回归方法。在分类问题中，基于特征对实例进行分类，相当于 if-else 规则的集合。主要优点是模型具有可读性、分类速度快。学习通常包括3个步骤：特征选择、决策树的生成和决策树的修剪本意介绍三个算法：ID3、C4.5 和 CART 算法

1.1 本章概要

1. 决策树的学习，旨在构建一个拟合训练数据，且复杂度小的决策树。现实中采用启发式方法学习

2. 决策树学习算法包括 3 个部分：特征选择、树的生成和树的剪枝。常用的方法有：ID3、C4.5 和 CART

3. 特征选择目标在于选择给训练数据 $T$ 分类的特征。常用准则如下：

   • 信息增益（ID3）

     样本集合 D 对特征 A 的 信息增益

     $$g(D, A) = H(D) - H(D|A)$$

     • 数据集 D 的熵：$ H(D) = - \sum\limits_{k=1}^K \dfrac{|C_k|}{|D|} log_2 \dfrac{|C_k|}{|D|}$

     • 给定特征 A 时数据集 D 的条件熵：$ H(D|A) = \sum\limits_{i=1}^{n} \dfrac{|D_i|}{|D|} H(D_i)$

     • $D_i$ 是 D 中特征 A 取第 $i$ 个值时的样本子集

     • $C_k$ 是 D 中属于第 $k$ 类的样本子集
     • $n$ 是特征 A 的取值个数
     • $K$ 是类的个数

   • 信息增益率（C4.5）

     $$g_R(D, A) = \dfrac{g(D, a)}{H_A(D)}$$
     • $H_A(D)$ 是 D 关于特征 A 的值的熵

   • 基尼指数（CART）

     $$Gini(D) = 1 - \sum\limits_{k=1}{K} \left( \dfrac{|C_k|}{|D|}\right)^2$$

     特征 A 下集合 D 的基尼指数：

     $$Gini\_index(D, A) = \sum\limits_{v=1}^{V} \dfrac{|D^v|}{|D|} Gini(D^v)$$

     上式摘自《西瓜书》

4. 决策树的生成

   以信息增益最大、信息增益率最大或基尼指数最小为准则，从根结点开始，不断选择最优特征，用特征分割当前集合

5. 决策树的剪枝

   解决过拟合问题。从已生成的树上剪掉一些叶结点或子树，将其父结点设为新的叶结点

1.2 本章目录

1. 决策树模型与学习

   1.1 决策树模型

   1.2 决策树与 if-then 规则

   1.3 决策树与条件概率分布

   1.4 决策树学习

2. 特征选择

   2.1 特征选择问题

   2.2 信息增益

   2.3 信息增益率

3. 决策树的生成

   3.1 ID3 算法

   3.2 C4.5 算法

4. 决策树的剪枝

5. CART 算法

   5.1 CART 生成

   5.2 CART 剪枝

---

2.1 决策树模型与学习

2.1.1 模型

决策树由结点和有向边组成，结点分成内结点和叶结点，内结点表一个特征或属性，叶结点表类别

分类的过程：从根结点开始，根据实例 $x$ 的某个特征将 $x$ 分配到根结点下一级的子结点，下一级的每个子结点对应着此特征的一个取值。继续考察 $x$ 剩余的特征，直到将 $x$ 分配到叶结点中，此叶结点的类别就是 $x$ 的类别

2.2.2 学习

1. 学习的目标

   通过训练集构建一套决策树模型，能对实例进行正确的分类。本质是从训练集中归纳出一组分类规则，既适应训练集又具有泛化能力。

2. 学习策略

   我们用损失函数表示目标，学习策略（方案）是以损失函数为目标函数的最小化

3. 学习算法

   学习算法是递归选择最优特征，用特征对当前数据进行分割，使子数据集有一个最好的分类

4. 剪枝

   对生成的树从下而上剪枝，将树变简单，去年过于细分的叶结点

2.2 特征选择

2.2.1 特征选择问题

若一个特征分类结果与随机分类结果没有差异，这个特征无分类能力。分类的好坏用信息增益或信息增益率来衡量

2.2.1.1 信息增益