[机器学习][理论知识][实践]KNN算法

电玩女神 2023-06-16 07:46 21阅读 0赞

### 文章目录 ###

*  1KNN算法原理
 *  2KNN三要素
 *  3KNN分类预测规则
 *  4KNN算法实现方式
 *   *  4.1KD Tree
     *  4.2KD Tree构建方式
     *  4.3KD tree查找最近邻
 *  5KNN参数说明

# 1KNN算法原理 #

*  K近邻(K-nearst neighbors, KNN)是一种基本的机器学习算法，所谓k近邻，就 是k个最近的邻居的意思，说的是每个样本都可以用它最接近的k个邻居来代表。 比如:判断一个人的人品，只需要观察与他来往最密切的几个人的人品好坏就可 以得出，即“近朱者赤，近墨者黑”;KNN算法既可以应用于分类应用中，也可 以应用在回归应用中。
 *  KNN在做回归和分类的主要区别在于最后做预测的时候的决策方式不同。KNN 在分类预测时，一般采用多数表决法;而在做回归预测时，一般采用平均值法。

1.  从训练集合中获取K个离待预测样本距离最近的样本数据;
2.  根据获取得到的K个样本数据来预测当前待预测样本的目标属性值。

# 2KNN三要素 #

*  K值的选择:对于K值的选择，一般根据样本分布选择一个较小的值，然后通过交叉 验证来选择一个比较合适的最终值;当选择比较小的K值的时候，表示使用较小领域 中的样本进行预测，训练误差会减小，但是会导致模型变得复杂，容易过拟合;当 选择较大的K值的时候，表示使用较大领域中的样本进行预测，训练误差会增大，同 时会使模型变得简单，容易导致欠拟合;
 *  距离的度量:一般使用欧氏距离(欧几里得距离);
 *  决策规则:在分类模型中，主要使用多数表决法或者加权多数表决法;在回归模型 中，主要使用平均值法或者加权平均值法。

# 3KNN分类预测规则 #

*  在KNN分类应用中，一般采用多数表决法或者加权多数表决法。
 *  多数表决法:每个邻近样本的权重是一样的，也就是说最终预 测的结果为出现类别最多的那个类
 *  加权多数表决法:每个邻近样本的权重是不一样的，一般情况 下采用权重和距离成反比的方式来计算，也就是说最终预测结 果是出现权重最大的那个类别

在KNN回归应用中，一般采用平均值法或者加权平均值法。

*  平均值法:每个邻近样本的权重是一样的，也就是说最终预测 的结果为所有邻近样本的目标属性值的均值;比如右图中，蓝 色圆圈的最终预测值为:2.6;
 *  加权平均值法:每个邻近样本的权重是不一样的，一般情况下 采用权重和距离成反比的方式来计算，也就是说在计算均值的 时候进行加权操作;比如右图中，假设上面三个点到待预测样 本点的距离均为2，下面两个点到待预测样本点距离为1，那么 蓝色圆圈的最终预测值为:2.43。(权重分别为: 1/7和2/7)  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3Njk1NjU5_size_16_color_FFFFFF_t_70]

# 4KNN算法实现方式 #

*  蛮力实现(brute):计算预测样本到所有训练集样本的距离，然后选择最小的k个距 离即可得到K个最邻近点。缺点在于当特征数比较多、样本数比较多的时候，算法的 执行效率比较低;
 *  KD树(kd\_tree):KD树算法中，首先是对训练数据进行建模，构建KD树，然后再 根据建好的模型来获取邻近样本数据。

## 4.1KD Tree ##

*  KD Tree是KNN算法中用于计算最近邻的快速、便捷构建方式。
 *  当样本数据量少的时候，我们可以使用brute这种暴力的方式进行求解最近邻， 即计算到所有样本的距离。但是当样本量比较大的时候，直接计算所有样本的距 离，工作量有点大，所以在这种情况下，我们可以使用kd tree来快速的计算。

## 4.2KD Tree构建方式 ##

KD树采用从m个样本的n维特征中，分别计算n个特征取值的方差，用方差最大 的第k维特征 n k n\_k nk作为根节点。对于这个特征，选择取值的中位数 n k v n\_\{kv\} nkv作为样本的划 分点，对于小于该值的样本划分到左子树，对于大于等于该值的样本划分到右子 树，对左右子树采用同样的方式找方差最大的特征作为根节点，递归即可产生 KD树。

## 4.3KD tree查找最近邻 ##

当我们生成KD树以后，就可以去预测测试集里面的样本目标点了。对于一个目 标点，我们首先在KD树里面找到包含目标点的叶子节点。以目标点为圆心，以 目标点到叶子节点样本实例的距离为半径，得到一个超球体，最近邻的点一定在 这个超球体内部。然后返回叶子节点的父节点，检查另一个子节点包含的超矩形 体是否和超球体相交，如果相交就到这个子节点寻找是否有更加近的近邻,有的话 就更新最近邻。如果不相交那就简单了，我们直接返回父节点的父节点，在另一 个子树继续搜索最近邻。当回溯到根节点时，算法结束，此时保存的最近邻节点 就是最终的最近邻。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3Njk1NjU5_size_16_color_FFFFFF_t_70 1]

# 5KNN参数说明 #

<table> 
 <thead> 
  <tr> 
   <th>参数</th> 
   <th>KNeighborsClassifier ----- KNeighborsRegressor</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>weights</td> 
   <td>样本权重，可选参数: uniform(等权重)、distance(权重和距离成反比，越近影响越强);默认为uniform</td> 
  </tr> 
  <tr> 
   <td>n_neighbors</td> 
   <td>邻近数目，默认为5</td> 
  </tr> 
  <tr> 
   <td>algorithm</td> 
   <td>计算方式，默认为auto，可选参数: auto、ball_tree、kd_tree、brute;推荐选择kd_tree</td> 
  </tr> 
  <tr> 
   <td>leaf_size</td> 
   <td>在使用KD_Tree的时候，叶子数量，默认为30</td> 
  </tr> 
  <tr> 
   <td>metric</td> 
   <td>样本之间距离度量公式，默认为minkowski(闵可夫斯基);当参数p为2的时候，其实就是欧几里得距离</td> 
  </tr> 
  <tr> 
   <td>p</td> 
   <td>给定minkowski距离中的p值，默认为2</td> 
  </tr> 
 </tbody> 
</table>

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3Njk1NjU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191125003943768.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3Njk1NjU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3Njk1NjU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191125004228699.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI3Njk1NjU5,size_16,color_FFFFFF,t_70