AI 导论4:机器学习导论
1. 决策树学习
例子:在一个水果的分类问题中,采用特征向量为: {颜色,尺寸,形状,味道 },其中:
- 颜色属性的取值范围:红,绿,黄
- 尺寸属性的取值范围:大,中,小
- 味道属性的取值范围:甜,酸
- 形状属性的取值范围:圆,细
样本集:一批水果,知道其特征向量及类别
问 题:一个新的水果,观测到了其特征向量,应该将其分类哪一类?
决策树适合解决的问题
- 实例由 ”属性-值“ 对表示
- 目标函数由离散的输出值
- 训练数据可以包含错误
- 熟练数据可以包含缺少属性值的实例
I. 基础概念
熵
- D:数据集
- Pi:数据集中类别 i 数据的比例
- c:数据集一共有 c 个类别
信息增益
助记:划分前熵 - 划分后熵
- A:属性
- Values(A):属性 A 所有可能值的集合
- Dv:D 中属性 A 值为 v 的子集
II. 决策树的生长
决策树节点划分
对于任意一个结点 n,可以出现以下三种情况:
- n 中的样本属于同一类,不可划分
- n 中样本不属于同一类,但是不存在任何一个划分可以使其子结点的平均熵低于 n 的熵,不可划分
- 其他,可划分
叶子节点的确定
- 测试集方法:根据训练集构建决策树,每展开一层子节点,就用测试集统计一次决策树性能,最终选择性能最好的一层子节点作为叶子节点
- 阈值方法:提前设定一个阈值,只要性能到达该阈值,则将这一层作为叶子节点(比如信息增益小于该阈值)
III. 决策树的实现:ID3 算法
- 创建根节点,根节点数据集为初始数据集,属性包括全体属性
- 当前结点指向根节点,在当前节点的属性集和数据集上,计算所有信息的信息增益,选择信息增益最大的属性 A 作为当前节点的决策属性
- 对属性 A 的每一个可能值生成一个新节点,当前节点数据集中选取属性 A 等于某个值的数据作为新节点的数据集,去除当前节点的属性 A,属性 A 作为新节点的属性集
- 如果新节点数据集 or 属性集为空,则该节点为叶子节点,标记类别,标记该节点为已处理节点
- 标记当前节点为已处理节点
- 如无未处理节点,算法结束;反之,令当前节点指向一个未处理节点,跳转 2
IV. 决策树优化
过拟合的解决
- 及早停止树增长
- 后修剪法:先允许树过度拟合,然后对过拟合的树进行修剪
- 将决策树化位等价的规则集合,从根节点到叶子节点的一条路径就是一条规则
- 评估每条规则,如果删除该规则中的一个前件不会降低该规则的估计精度,则删除此前件
信息增益度量问题的解决
问题:当某个属性 可能值的数量 >> 类别数量 时,该属性信息增益会不正常增大,因为过多可能值将训练数据分分割非常小的空间,小空间内数据非常纯净,熵接近于 0,造成信息增益特别大
解决:增加惩罚项抑制 SplitInformation
然后使用 GainRatio 代替之前的 Gain
2. 贝叶斯学习
在给定训练数据 D 时,确定假设空间 H 中的最优假设,进行分类的问题
I. 贝叶斯公式
- 先验概率:
- 似然度:
- 后验概率:
II. 贝叶斯最优假设分类
极大后验假设(MAP 假设)
在候选假设集合中寻找使后验概率最大的假设
极大似然假设(ML 假设)
在候选假设集合中寻找使似然度最大的假设
由于似然度不需要训练就能知道,所以在更多使用极大似然假设
III. 贝叶斯最优分类器分类
设 V 表示类别集合,vi 表示单一类别,使用 P(vi|d) 作为分类标准
该方法性能最好,开销最大
IV. 分类实例
对数据 d 有假设 h1, h2, h3,先验概率分别为:
且已知:
又已知在分类集合 V = {+, -} 上数据 d 被 h1 分类为 +,被 h2 和 h3 分类为 -。请分别依据 MAP 假设和贝叶斯最优分类器对数据进行分类。
解:
MAP 假设分类
所以使用假设 h1,d 为 +
贝叶斯最优分类器分类
d 为 -
V. 朴素贝叶斯方法
如果一个实例的属性过多,比如,那么使用贝叶斯学习将会非常困难,假设使用 MAP 假设:
如果 n = 10,每个属性有 3 个可能值,目标集合里有 5 个候选目标,那么 项就有 5 * 310 个,计算困难
为了解决这个问题,使用朴素贝叶斯方法:对于目标值,数据各属性之间视为条件独立,这样,,项的数目就减少到了 5 × 3 × 10 个

原文链接:AI 导论4:机器学习导论
nightmorning的博客 版权所有,转载请注明出处。
还没有任何评论,你来说两句吧!