《统计学习方法》三：手推“k近邻法”

一时失言乱红尘 2023-06-25 02:29 51阅读 0赞

## 第三章  k k k近邻法 ##

k-NN是一种基本的分类和回归方法，没有显式的表达过程。

**3.1. k k k近邻算法**  
 k k k近邻算法是给定一个训练数据集，对于新的输入实例，在训练数据集中找到与该实例最近的 k k k个实例。将这 k k k个实例中多数属于的类别作为输入实例的类别预测值。具体算法如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1MTcxMzI_size_16_color_FFFFFF_t_70]  
**3.2. k k k近邻模型**  
决定 k k k近邻模型的三要素：距离度量、 k k k值的选和分类决策规则  
**3.2.1.模型**  
通过每个实例的邻域将特征空间进行划分。  
**3.2.2.距离度量**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1MTcxMzI_size_16_color_FFFFFF_t_70 1]  
**3.2.3. k k k值的选择**  
可知较小的 k k k使实例的预测的近似误差减小，但由于 k k k小，会对邻近的 k k k个实例更加敏感，容易过拟合，增大估计误差。  
 k k k值过大会减小估计误差，增大近似误差。当 k k k等于训练集样本个数是，总是使用训练集中样本最多的一类进行预测。

**3.2.4.分类决策规则**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1MTcxMzI_size_16_color_FFFFFF_t_70 2]  
**3.3. k k k近邻法的实现： k d kd kd树**  
**3.3.1.构造 k d kd kd树**  
 k d kd kd树是一颗二叉树，构造 k d kd kd树相当于不断的用垂直于坐标轴的场平面将 k k k维空间切分，构成一系列的 k k k维超矩形区域（注意：此处的 k k k代表维度，与 k k k近邻法的 k k k无关）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1MTcxMzI_size_16_color_FFFFFF_t_70 3]  
**3.3.2.搜索kd树**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1MTcxMzI_size_16_color_FFFFFF_t_70 4]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1MTcxMzI_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2019123019112115.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1MTcxMzI=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1MTcxMzI_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191230194133765.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1MTcxMzI=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1MTcxMzI_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191230194523633.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1MTcxMzI=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1MTcxMzI_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191230194543622.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1MTcxMzI=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1MTcxMzI_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191230200908619.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE1MTcxMzI=,size_16,color_FFFFFF,t_70