Ch02 k近邻法

目录

• k近邻算法
• k近邻模型
• kd树

k近邻算法

k近邻算法比较简单。可以理解为，给定一个未知样本，通过与已有样本之间的距离度量来判断未知样本的类别。k的意思是针对距离最近的k个已知样本对未知样本进行分类决策表决。

k近邻模型

觉得k近邻中最关键的是距离的度量方法与分类表决决策。

距离度量方法

在书中介绍了Lp距离计算方法。
当p=1时为曼哈顿距离，p=2时为欧式距离。
假设一个二维空间中，当p取不同值可得到下图。

分类表决决策

涉及k的取值，与k个样本的使用。
若k取1表示最近零算法。
k的取值越小意味着模型更复杂，容易overfit。
k的取值越大，未知样本的预测可能受噪声影响，对应模型越简单。
一般k取较小的数值，可通过gridsearch得到最优的k。
分类决策规则对应k个样本怎么用。最基本也是常用的规则就是投票表决，此时书中论述，多数投标表决的决策规则等价于经验风险最小化。

kd树

kd树提高了k近邻算法的效率。不再是线性扫描，而是使用特殊的结构存储训练数据，以减少距离计算的次数。
kd树主要分为kd树的构造与搜索。
kd树的构造是在特征维度上划分，构造子区域。我觉得和决策树的思想有一点点的类似。
kd树的搜索设计在子区间与领域子区间的搜索。
实现可参考scipy cookbook。