内容提要：
* 习题 3.1 详解
* 习题 3.2 详解
* 习题 3.3 详解
点击蓝字 ｜关注我们
习题 3.1 详解
「习题 3.1」参照图 3.1，在二维空间中给出实例点，画出 为 1 和 2 时的 近邻法构成的空间划分，并对其进行比较，体会 值选择与模型复杂度及预测准确率的关系。
「解」
根据题意，首先参照《统计学习方法（第 2 版）》中的图 3.1 给出二维空间中的实例点，然后对于 和 ，分别训练 近邻模型并绘制决策边界，最后比较不同 值下的模型复杂度与预测准确率。
1. 给出二维空间中的实例点
在《统计学习方法（第 2 版）》的图 3.1 上添加坐标网格，提取实例点坐标。
以 表示点类实例集合，
以 表示叉类实例集合，
得到数据集 。
2. 训练 近邻模型并绘制决策边界
以 近邻法对数据集 进行空间划分的 Python 代码如下。
# 导入相关模块
import numpy as np
import matplotlib.pyplot as plt
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score
from matplotlib.colors import ListedColormap
# 点类数据集，类别设为 0
T_1 = np.array([[0.8, 2, 0],
[1.8, 5.7, 0],
[2.6, 4.6, 0],
[3, 3.6, 0],
[3.9, 2.4, 0],
[3.9, 3.8, 0],
[4, 5.4, 0],
[5.2, 2.8, 0],
[5.2, 4.2, 0],
[5.9, 3, 0],
[6.6, 4.8, 0]])
# 叉类数据集，类别设为 1
T_2 = np.array([[2.2, 0.8, 1],
[2.4, 1.6, 1],
[1, 3.3, 1],
[2, 3.2, 1],
[3.4, 3, 1],
[4.5, 1.2, 1],
[6, 1.3, 1]])
# 两个类别合并之后的数据集 T
T = np.vstack((T_1, T_2))
# 提取特征和标签
X = T[:, 0:2] # 点坐标
y = T[:, 2] # 类别标签
# 自定义图片颜料池
cmap_light = ListedColormap(['#FFAAAA', '#AAFFAA']) # 浅色系
cmap_bold = ListedColormap(['#FF0000', '#00FF00']) # 深色系
# 创建函数绘制决策边界
def plot_decision_boundary(X, y, model, ax, title):
h = 0.02 # 设置网格的步长， 数值越小，划分空间之间的分隔线越清晰
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
np.arange(y_min, y_max, h))
# 用训练好的模型预测每个点的类别
Z = model.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)
# 绘制决策边界
ax.contourf(xx, yy, Z, alpha=0.8, cmap=cmap_light)
ax.scatter(X[:, 0], X[:, 1], c=y, edgecolors='k', marker='o', s=100, cmap=cmap_bold)
ax.set_title(title)
ax.set_xticks(())
ax.set_yticks(())
# 创建 k 近邻模型并分别设置k=1和k=2
fig, axs = plt.subplots(1, 2, figsize=(12, 6))
# k=1
knn1 = KNeighborsClassifier(n_neighbors=1, n_jobs=-1) # n_jobs 用于指定并行计算时使用的CPU核心数
knn1.fit(X, y)
plot_decision_boundary(X, y, knn1, axs[0], "k=1")
# k=2
knn2 = KNeighborsClassifier(n_neighbors=2, n_jobs=-1)
knn2.fit(X, y)
plot_decision_boundary(X, y, knn2, axs[1], "k=2")
# 显示图形
plt.tight_layout()
plt.show()
# 计算预测准确率
y_pred_1 = knn1.predict(X)
y_pred_2 = knn2.predict(X)
accuracy_1 = accuracy_score(y, y_pred_1)
accuracy_2 = accuracy_score(y, y_pred_2)
print(f"Accuracy for k=1: {accuracy_1:.2f}")
print(f"Accuracy for k=2: {accuracy_2:.2f}")
运行代码，可以得到 分别为 1 和 2 时的分类决策边界，并且预测准确率分别为 100% 和 89%。
)
3. 比较不同 值下的模型复杂度与预测准确率
仔细观察可以发现， 时决策边界较为复杂，呈现更多的锯齿状，这是因为每个测试点都依赖于最近的一个训练点，很容易受到噪声的影响，导致过拟合； 时决策边界略显平滑一些，因为每个测试点的分类依赖于最近的两个训练点，边界变得稍微稳定，且减少了对局部噪声的敏感性。
另外，从输出的预测准确率可以看出， 时的准确率更高，但如果数据中存在噪声或者不均衡，它可能导致过拟合； 时的准确率略低，无法很好地捕捉数据的细节，但因为模型复杂度低一些，可能具有更好的泛化能力。
很明显， 值的选取对模型有一定的影响，具体内容见下表。
习题 3.2 详解
「习题 3.2」 利用例题 3.2 构造的 树求点 的最近邻点。
「解」
1. 寻找“当前最近点”
从根结点开始， 在根结点 的左子区域内，继续探寻，进入 所确定的上子区域内，最终到达 的左子区域中， 就是“当前最近邻点”。
2. 回溯验证
以 为圆心， 与 之间的距离为半径画一个圆，如图所示。
这个区域内有两个结点，分别是 和 。计算 到这两点的距离，发现 与 之间的距离最近，那么 为“当前最近点”。接着，再以 为圆心， 与 之间的距离为半径画一个圆，此时圆里没有其他结点，说明可以确认 就是 的最近邻点，如图所示。
习题 3.3 详解
「习题 3.3」参照算法 3.3，写出输出为 的 近邻的算法。
「解」
先将算法 3.3列出如下：
算法 3.3 （用 树的最近邻搜索）
输入：已构造的 树，目标点 ；
输出： 的最近邻。
（1）在 树中找出包含目标点 的叶结点：从根结点出发，递归地向下访问 树。若目标点 当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶结点为止。
（2）以此叶结点为＂当前最近点＂。
（3）递归地向上回退，在每个结点进行以下操作：
（a）如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为＂当前最近点＂。
（b）当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体地，检查另一子结点对应的区域是否与以目标点为球心，以目标点与＂当前最近点＂间的距离为半径的超球体相交。
如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点。接着，递归地进行最近邻搜索；
如果不相交，向上回退。
（4）当回退到根结点时，搜索结束。最后的＂当前最近点＂即为 的最近邻点。
❞
仿照算法 3.3，得到用 树的 近邻搜索的算法如下。
输入：已构造的 树，目标点 ；
输出： 的 近邻。
(1) 在 树中找出包含目标点 的叶结点：从根结点出发，递归地向下访问 树。若目标点 当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶结点为止。
(2) 以该叶结点作为当前最近邻实例记录在列表中，若 ，确定“当前 近邻”个实例。若 ，先搜索子结点的父结点的另一子结点对应的区域是否有近邻点，若有，记录到列表中，否则退回上一层结点继续寻找。直到列表中满足 个实例点则停止记录，否则继续向上搜索，确定“当前 近邻”个实例。
(3) 递归地向上回退，在每个结点进行以下操作：
(a) 如果目标点与当前结点的距离小于目标点与“当前 近邻”个实例中的最远距离，则将该结点记录到“当前 近邻”中。
(b) 检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体地，检查另一子结点对应的区域是否与以目标实例 为球心，“当前 近邻”中与目标实例 最远的距离为半径的超球体相交。如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点。接着，递归地进行近邻搜索；如果不相交，向上回退。
(4) 当回退到根结点时，搜索结束。最后的“当前 近邻”即为 的 近邻点。
下面以一个例子来试验以上算法。给定数据集
如图所示。
根据构造平衡 树的算法，对数据集进行划分得到如下结果。
接下来，我们以欧式距离为距离度量，搜索目标实例 的 个近邻点。具体的搜索步骤如下。
(1) 寻找当前 近邻：从根结点出发， 在根结点 的左子区域内，接着搜索到深度为 1 的叶子结点 所确定的下子区域内，记录 和 为“当前 近邻点”。
(2) 回溯验证：
(a) 计算 与 和 的欧式距离，分别为 2.91 和 1.63。 ，以 为圆心， 与 之间的距离为半径画圆，这个区域内还包含 1 个父结点 ，则更新 和 为“当前 近邻点”。
(b) 计算 与 和 的距离，分别为 1.80 和 1.63。 ，以 为圆心， 与 之间的距离为半径画圆，这个区域内没有其他结点，说明可以确认 和 为 的 近邻点。
好啦，关于第三章的习题解答就说到这里，希望大家可以耐心看完！
如果这个免费讲义对你的学习有所帮助，请帮助我们推荐给更多的朋友，回复「入群」，也可以加入我们的学习来哦！我们下期不见不散。
欢迎大家关注简博士的B站和公众号，在公众号私信“入群”，可以与小伙伴们一起讨论问题哦。