作业 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降维
图与拉普拉斯矩阵