AI 导论4：机器学习导论

正文索引 [隐藏]

1. 决策树学习

例子：在一个水果的分类问题中，采用特征向量为： {颜色，尺寸，形状，味道 }，其中：

  • 颜色属性的取值范围：红，绿，黄
  • 尺寸属性的取值范围：大，中，小
  • 味道属性的取值范围：甜，酸
  • 形状属性的取值范围：圆，细

样本集：一批水果，知道其特征向量及类别

问 题：一个新的水果，观测到了其特征向量，应该将其分类哪一类？

image-20191211083814433

决策树适合解决的问题

  • 实例由 ”属性-值“ 对表示
  • 目标函数由离散的输出值
  • 训练数据可以包含错误
  • 熟练数据可以包含缺少属性值的实例

I. 基础概念

熵

image-20191211084304307

  • D：数据集
  • Pi：数据集中类别 i 数据的比例
  • c：数据集一共有 c 个类别

信息增益

助记：划分前熵 - 划分后熵

image-20191211084452330

  • A：属性
  • Values(A)：属性 A 所有可能值的集合
  • Dv：D 中属性 A 值为 v 的子集

II. 决策树的生长

决策树节点划分

对于任意一个结点 n，可以出现以下三种情况：

  • n 中的样本属于同一类，不可划分
  • n 中样本不属于同一类，但是不存在任何一个划分可以使其子结点的平均熵低于 n 的熵，不可划分
  • 其他，可划分

叶子节点的确定

  • 测试集方法：根据训练集构建决策树，每展开一层子节点，就用测试集统计一次决策树性能，最终选择性能最好的一层子节点作为叶子节点
  • 阈值方法：提前设定一个阈值，只要性能到达该阈值，则将这一层作为叶子节点（比如信息增益小于该阈值）

III. 决策树的实现：ID3 算法

  1. 创建根节点，根节点数据集为初始数据集，属性包括全体属性
  2. 当前结点指向根节点，在当前节点的属性集和数据集上，计算所有信息的信息增益，选择信息增益最大的属性 A 作为当前节点的决策属性
  3. 对属性 A 的每一个可能值生成一个新节点，当前节点数据集中选取属性 A 等于某个值的数据作为新节点的数据集，去除当前节点的属性 A，属性 A 作为新节点的属性集
    • 如果新节点数据集 or 属性集为空，则该节点为叶子节点，标记类别，标记该节点为已处理节点
  4. 标记当前节点为已处理节点
  5. 如无未处理节点，算法结束；反之，令当前节点指向一个未处理节点，跳转 2

IV. 决策树优化

过拟合的解决

  • 及早停止树增长
  • 后修剪法：先允许树过度拟合，然后对过拟合的树进行修剪
    • 将决策树化位等价的规则集合，从根节点到叶子节点的一条路径就是一条规则
    • 评估每条规则，如果删除该规则中的一个前件不会降低该规则的估计精度，则删除此前件

信息增益度量问题的解决

问题：当某个属性 可能值的数量 >> 类别数量 时，该属性信息增益会不正常增大，因为过多可能值将训练数据分分割非常小的空间，小空间内数据非常纯净，熵接近于 0，造成信息增益特别大

解决：增加惩罚项抑制 SplitInformation

image-20191211091605973

然后使用 GainRatio 代替之前的 Gain

image-20191211091550027

2. 贝叶斯学习

在给定训练数据 D 时，确定假设空间 H 中的最优假设，进行分类的问题

I. 贝叶斯公式

image-20191211093418943

  • 先验概率：image-20191211092550071
  • 似然度：image-20191211092653289
  • 后验概率：image-20191211092714018

II. 贝叶斯最优假设分类

极大后验假设（MAP 假设）

在候选假设集合中寻找使后验概率最大的假设

    \[h_{MAP} = \arg\max P(h|d)\]

极大似然假设（ML 假设）

在候选假设集合中寻找使似然度最大的假设

image-20191211093602443

由于似然度不需要训练就能知道，所以在更多使用极大似然假设

III. 贝叶斯最优分类器分类

设 V 表示类别集合，vi 表示单一类别，使用 P(vi|d) 作为分类标准

image-20191211100006360

该方法性能最好，开销最大

IV. 分类实例

对数据 d 有假设 h1, h2, h3，先验概率分别为：

    \[P(h_1) = 0.3,\ P(h_2) = 0.3,\ P(h_3) = 0.4\]

且已知：

    \[P(d|h_1) = 0.5,\ P(d|h_2) = 0.3, P(d|h3) = 0.2\]

又已知在分类集合 V = {+, -} 上数据 d 被 h1 分类为 +，被 h2 和 h3 分类为 -。请分别依据 MAP 假设和贝叶斯最优分类器对数据进行分类。

解：

MAP 假设分类

image-20191211095222124

所以使用假设 h1，d 为 +

贝叶斯最优分类器分类

image-20191211095438021

d 为 -

V. 朴素贝叶斯方法

如果一个实例的属性过多，比如image-20191211101309461，那么使用贝叶斯学习将会非常困难，假设使用 MAP 假设：

image-20191211101400108

如果 n = 10，每个属性有 3 个可能值，目标集合里有 5 个候选目标，那么image-20191211101427721 项就有 5 * 310 个，计算困难

为了解决这个问题，使用朴素贝叶斯方法：对于目标值，数据各属性之间视为条件独立，这样，image-20191211101704042，项的数目就减少到了 5 × 3 × 10 个