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 个