没有合适的资源?快使用搜索试试~ 我知道了~
171840708_张逸凯1
需积分: 0 0 下载量 51 浏览量
2022-08-03
13:43:00
上传
评论
收藏 1.14MB PDF 举报
温馨提示
试读
13页
注意:佰佤佦、预测结果命名为“学号 姓名”伨例如“伱伸伱伲伲伱估估伱 张三伮佰佤佦”伩,源码、压缩文件命名为“学号”,例如“伱伸伱伲伲伱估估伱伮佺佩佰”伻伨伳伩
资源详情
资源评论
资源推荐
机器学习导论
习题三
171840708, 张逸凯, zykhelloha@gmail.com
2020 年 4 月 25 日
学术诚信
本课程非常重视学术诚信规范,助教老师和助教同学将不遗余力地维护作业中的学术诚信
规范的建立。希望所有选课学生能够对此予以重视。
1
伨伱伩 允许同学之间的相互讨论,但是署你名字的工作必须由你完成,不允许直接照搬
任何已有的材料,必须独立完成作业的书写过程伻
伨伲伩 在完成作业过程中,对他人工作(出版物、互联网资料)中文本的直接照搬(包括
原文的直接复制粘贴及语句的简单修改等)都将视为剽窃,剽窃者成绩将被取消。
对于完成作业中有关键作用的公开资料,应予以明显引用;
伨伳伩 如果发现作业之间高度相似将被判定为互相 抄袭行为,抄袭和被抄袭双方 的成绩
都将被取消。因此请主动防止自己的作业被他人抄袭。
作业提交注意事项
伨伱伩 请在佌佡佔佥佘模板中第一页填写个人的学号、姓名、邮箱;
伨伲伩 本次作业需提交该佰佤佦文件、 问题伴可直接运行的源码伨伮佰佹文件伩、 问题伴的预测结
果伨伮佣佳佶文件伩,将以上三个文件压缩成佺佩佰文件后上传。注意:佰佤佦、 预测结 果命名
为“学号 姓名”伨例如“伱伸伱伲伲伱估估伱 张三伮佰佤佦”伩,源码、压缩文件命名为“学号”,
例如“伱伸伱伲伲伱估估伱伮佺佩佰”伻
伨伳伩 未按照要求提交作业,提交作业格式不正确,作业命名不规范,将会被扣除部分作
业分数;
伨伴伩 本次作业提交截止时间为4月23日23:55:00。除非有特殊情况(如因病缓交),否
则截止时间后不接收作业,本次作业记零分。
1
参考尹一通老师高级算法课程中对学术诚信的说明。
伱
伲估伲估年春季 机器学习导论 作业三
1 [20pts] Decision Tree I
伨伱伩 [5pts] 试分析使用“最小训练误差”作为决策树划分选择的缺陷。
伨伲伩 [5pts] 树也是一种线性模型,考虑图伨伱伩所示回归决策树,X
1
, X
2
均在单位区间上取值,t
1
, t
2
, t
3
, t
4
满
足估 < t
1
< t
3
< 伱, 估 < t
2
, t
4
< 伱,试绘制出该决策树对于特征空间的划分。假设区域R
i
上
模型的输出值为c
i
,试用线性模型表示该决策树。
图 伱伺 回归决策树
伨伳伩 [10pts] 对于回归树,我们常采用平方误差来表示回归树对于训练数据的预测误差。但是
找出平方误 差最小化准则下的最优回归树在计算上一般是不可行的,通常我们采用贪心的
算法计算切分变量j和分离点s。佃佁佒佔回归树在每一步求解如下优化问题
佭佩佮
j,s
佭佩佮
c
1
X
x
i
∈R
1
(j,s)
伨y
i
− c
1
伩
2
伫 佭佩佮
c
2
X
x
i
∈R
2
(j,s)
伨y
i
− c
2
伩
2
其中R
1
伨j, s伩 伽 {x|x
j
≤ s}, R
2
伨j, s伩 伽 {x|x
j
> s}。试分析该优化问题表达的含义并给出变
量j, s的求解思路。
Solution. (1)
依据最小训练误差划分伬 也就是当前划分的依据伨属性伩可以带来最相似于训练集 标签的结
果伮 这样得到的决策树可以说是对训练集拟合最优的决策树伮
对比 其他方法伨以佉佄伳为例伩伬 依据信息增益划分伬 信息增 益是表示已知一个随机变量的信息
后使得另一个随机变量的不确定性减少的程度伬 信息增益最大意味着 对当前属性来进行划分所
获得的伢纯度提升伢越大伮 所期望的是每个分支尽可能属于同一类别伬 这与分类问题中尽量提取数
据的所有特征(信息)是一致的伮
综上所述伬 依据最小训练误差划分可能使模型太伢依赖伢训练集了伬 也就是过拟合伬 导致模型
对于测试集的泛化能力下降伮
(2)
伲
伲估伲估年春季 机器学习导论 作业三
图 伲伺 绘制决策树对于特征空间的划分
线性模型表达伺 f伨x伩 伽
5
X
i=1
c
i
I伨x ∈ R
i
伩, 其中 I伨x ∈ R
i
伩 伽
伱, 伨x ∈ R
i
伩
估, 伨x /∈ R
i
伩
(3)
不妨令数据点x ∈ R
d
伬 d个属性构成了d维的特征空间伬 x对应了d维特征空间一个数据点伬
佃佁佒佔 回归树的目标是将特征空间在每一维度划分成若干个子空间伬 在树上叶节点 ∈ 某个子空
间伮
就像上题一样伬 如果x ∈ R
i
伬 那么就输出R
i
内对应的数值伮
题中所给优化问题伺
佭佩佮
j,s
佭佩佮
c
1
X
x
i
∈R
1
(j,s)
伨y
i
− c
1
伩
2
伫 佭佩佮
c
2
X
x
i
∈R
2
(j,s)
伨y
i
− c
2
伩
2
下面我们来解释这个优化问题的含义伺
优化问题中R
1
伨j, s伩 伽 {x|x
j
≤ s}, R
2
伨j, s伩 伽 {x|x
j
> s}伬 也就是在第j个特征空间关于s的
一个划分伬 R
1
, R
2
是互补的 两个区域伬 我们可以发现上述优化问题就是遍历所有的划分属性j伬
然后递归地找到最优的划分点s伬 不断把当前特征空间划分成子空间直到满足终止条件伮
下面给出变量j, s的求解思路:
• 求解内层佭佩佮
c
t
, t ∈ {伱, 伲}伨佴只有两个值表示不断把当前迭代步的特征空间按照划分点分
成两个伩伺
伳
剩余12页未读,继续阅读
爱吃番茄great
- 粉丝: 20
- 资源: 298
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0