CS计算机代考程序代写 作业 3:决策树、提升算法与无监督学习

作业 3:决策树、提升算法与无监督学习

1 介绍

本次作业需要提交说明文档(PDF 形式)。注意事项如下:

• 本次作业总分值为 110 分,若得分超过 100 分,则按照 100 分截断。

• 作业按点给分,因此请在说明文档中按点回答,方便助教批改。

• 友情提示:每个算法的主要代码已经实现,因此每一小题的代码都不大(不超过 10 行)。

• 只有“求证”,“证明”这种题需要过程。

• 不要使用他人的作业,也不要向他人公开自己的作业,否则处罚很严厉,会扣至-100(倒扣
本次作业的全部分值)。

• 统一文件的命名:{学号}_{姓名}_hw3.zip

2 决策树(25pt)

在本题中,你将使用决策树解决二分类问题和回归问题。

1. 补全 tree.py 中 DecisionTree 类的 fit 函数。提示:递归调用决策树的构造与 fit 函数。(5pt)

2. 完成 tree.py 中 compute_entropy 函数。(5pt)

3. 完成 tree.py 中 compute_gini 函数。(5pt)

4. 完成 tree.py 中 mean_absolute_deviation_around_median 函数。(5pt)

5. 运行 tree.py,在实验文档中记录决策树在不同数据集上运行的结果,包括

(a) DT_entropy.pdf,使用决策树在二分类问题上的结果。

(b) DT_regression.pdf,使用决策树在回归问题上的结果。

并简要描述实验现象(例如超参数对于决策树的影响)。(5pt)

1

3 提升算法(45pt)

3.1 AdaBoost 的训练误差

给定包含 m 条数据的训练集,假设 AdaBoost 算法中,基分类器 ht 的误差 ϵt 的上界为
1/2− γ, 其中 γ > 0。请证明当 T >

logm
2γ2

时,AdaBoost 的训练误差可以达到 0。(10pt)

3.2 Gradient Boosting Machines

总结课件中的 Gradient Boosting Machine 的算法流程如下:

1. 令 f0(x) = 0。

2. For t=1 to T:

(a) 计算在各个数据点上的梯度 gt =
( ∂
∂ŷi

ℓ(yi, ŷi)|ŷi=ft−1(xi)
)n
i=1

(b) 根据 −gt 拟合一个回归模型,ht = arg minh∈F 。

(c) 选择合适的步长 αt, 最简单的选择是固定步长 η ∈ (0, 1]。

(d) 更新模型,ft(x) = ft−1(x) + αtht(x)。

请完成以下题目:

1. 完成上述算法中的填空。(5pt)

2. 考虑回归问题,假设损失函数 ℓ(y, ŷ) =
1

2
(y − ŷ)2。直接给出第 t 轮迭代时的 gt 以及 ht 的

表达式。(使用 ft−1 表达)。(5pt)

3. 考虑二分类问题,假设损失函数 ℓ(y, ŷ) = log(1 + exp(−yŷ))。直接给出第 t 轮迭代时的 gt
以及 ht 的表达式。(使用 ft−1 表达)。(5pt)

2

4. 完成 boosting.py 中 GradientBoosting 类的 fit 函数。(5pt)

5. 完成 boosting.py 中 GradientBoosting 类的 predict 函数。(5pt)

6. 完成 boosting.py 中函数 gradient_logistic。(5pt)

7. 运行 boosting.py,在实验文档中记录 GBM 在不同数据集上运行的结果,包括

(a) GBM_l2.pdf,使用 L2 loss 在二分类问题上的结果。

(b) GBM_logistic.pdf,使用 logistic loss 在二分类问题上的结果。

(c) GBM_regression.pdf),使用 L2 loss 在回归问题上的结果。

并简要描述实验现象(例如超参数对于 GBM的影响、损失函数对于 GBM的影响等)。(5pt)

4 无监督学习(40pt)

4.1 聚类

本题中,你将使用 K-Means 算法对数据进行聚类分析。

1. 完成 clustering.py 中 KMeans 类的 close_centeroid 函数。(5pt)

2. 补全 clustering.py 中 KMeans 类的 fit 函数。(5pt)

3. 运行 clustering.py,在实验文档中记录实验结果,包括

(a) clustering_1.pdf,当 k = 3 时的聚类结果。

(b) clustering_2.pdf,当 k 取不同值时的 loss 变化。

并简要描述实验现象(例如如何选择合适的 k)。(5pt)

4.2 PCA 降维

令 X 是一个均值中心化的数据矩阵,即 X 的样本均值 x =
1

n


i xi = 0。

1. 证明数据到一个任意向量 u 一维投影的方差等于 uT Cu,其中 C =
1

n


i xix

T
i 是样本协方差

矩阵。(5pt)

3

2. 证明 k = 1 的 PCA 将数据投影到最大方差的方向。(5pt)

4.3 图与拉普拉斯矩阵

拉普拉斯特征映射算法目的是找到一种低维表示,用来最好地保持通过权重矩阵 W 衡量的近
邻关系,该算法工作原理如下:

1. 找到每个数据点的 t 个最近邻点。

2. 构造W,1个m×m的稀疏对称矩阵,其中如果 (xi, xj)是近邻,则Wij = exp (−||xi − xj ||22/σ2),
否则等于 0。

3. 构造对角矩阵 D 使得 Dii = ΣjWij。

4. 通过最小化近邻点之间的加权距离,找到 k 维表示:

Y = arg min
Y′


i,j

Wij ||y

i − y

j ||
2
2 (1)

下面我们假定 k = 1,我们想要寻找一个一维表示 y。证明式子等价于 y = arg miny′ y′
T Ly′,其中

L = D − W 是图的拉普拉斯矩阵。(15pt)

4

介绍
决策树(25pt)
提升算法(45pt)
AdaBoost的训练误差
Gradient Boosting Machines

无监督学习(40pt)
聚类
PCA降维
图与拉普拉斯矩阵