knn算法k值确定（【机器学习】KNN算法及K值的选取）

KNN算法是有监督学习中的分类算法    
    
    
，它看起来和另一个机器学习算法K-means有点像（K-means是无监督学习算法）    


     


     


   ，但却是有本质区别的    
    
    
。

KNN的原理就是：当预测一个新的值x的时候




 




 




 

，根据它距离最近的K个点是什么类别   

   

   

，来判断x属于哪个类别    


     


     


   。

图中绿色的点就是我们要预测的那个点     

     

     

  ，假设K=3




 




 




 

。那么KNN算法就会找到与它距离最近的三个点（这里用圆圈把它圈起来了）




  




  




  
，看看哪种类别多一些
  


  


  


，比如这个例子中是蓝色三角形多一些     
     
     
 ，新来的绿色点就归类到蓝三角了   

   

   

。

但是 




   




   




   ，当K=5的时候

 



 



 



，判定就变成不一样了     

     

     

  。这次变成红圆多一些               ，所以新来的绿点被归类成红圆




  




  




  
。从这个例子中  




    




    




    ，我们就能看得出K的取值是很重要的
  


  


  


。

KNN的两个核心点：K值的选取和点之间距离的计算方式

距离计算公式就不多说了
















，是欧氏距离：

d

(

x

,

y

)

:

=

∑

i

=

1

n

(

x

i

−

y

i

)

2

d(x,y):=\sqrt{\sum_{i=1}^n(x_i-y_i)^2}

d(x,y):=∑i=1n​(xi​−yi​)2​

（对于高维特征               ，曼哈顿距离（即p更低）更能避免维度灾难的影响   



     



     



    ，效果更优     
     
     
 。欧几里得距离（次数更高）更能关注大差异较大的特征的情况）

最简单粗暴的就是将预测点与所有点距离进行计算
















，然后保存并排序    
    
    
，选出前面K个值看看哪些类别比较多 




   




   




   。但其实也可以通过一些数据结构来辅助    


     


     


   ，比如最大堆

如何确定K值？答案是通过网格搜索




 




 




 

，交叉验证（将样本数据按照一定比例   

   

   

，拆分出训练用的数据和验证用的数据     

     

     

  ，比如6：4拆分出部分训练数据和验证数据）




  




  




  
，从选取一个较小的K值开始
  


  


  


，不断增加K的值     
     
     
 ，然后计算验证集合的方差 




   




   




   ，最终找到一个比较合适的K值

 



 



 



。

有个反直觉的现象

 



 



 



，K取值较小时               ，模型复杂度（容量）高  




    




    




    ，训练误差会减小
















，泛化能力减弱；K取值较大时               ，模型复杂度低   



     



     



    ，训练误差会增大
















，泛化能力有一定的提高               。原因是K取值小的时候（如k=1）    
    
    
，仅用较小的领域中的训练样本进行预测    


     


     


   ，模型拟合能力比较强




 




 




 

，决策就是只要紧跟着最近的训练样本（邻居）的结果  




    




    




    。但是   

   

   

，当训练集包含   
    
    
   ”噪声样本“时     

     

     

  ，模型也很容易受这些噪声样本的影响（如图 过拟合情况




  




  




  
，噪声样本在哪个位置
  


  


  


，决策边界就会画到哪）     
     
     
 ，这样会增大"学习"的方差 




   




   




   ，也就是容易过拟合
















。这时

 



 



 



，多听听其他邻居训练样本的观点就能尽量减少这些噪声的影响               。K值取值太大时               ，情况相反  




    




    




    ，容易欠拟合   



     



     



    。

KNN是一种非参的
















，惰性的算法模型：

非参的意思并不是说这个算法不需要参数               ，而是意味着这个模型不会对数据做出任何的假设   



     



     



    ，与之相对的是线性回归（我们总会假设线性回归是一条直线）
















。也就是说KNN建立的模型结构是根据数据来决定的
















，这也比较符合现实的情况    
    
    
，毕竟在现实中的情况往往与理论上的假设是不相符的    
    
    
。

此处的非参数似乎不太正确

惰性又是什么意思呢？想想看    


     


     


   ，同样是分类算法




 




 




 

，逻辑回归需要先对数据进行大量训练   

   

   

，最后才会得到一个算法模型    


     


     


   。而KNN算法却不需要     

     

     

  ，它没有明确的训练数据的过程




  




  




  
，或者说这个过程很快




 




 




 

。

KNN算法优点

算法简单直观
  


  


  


，易于应用于回归及多分类任务 对数据没有假设     
     
     
 ，准确度高 




   




   




   ，对异常点较不敏感 由于KNN方法主要靠周围有限的邻近的样本

 



 



 



，而不是靠判别类域的方法来确定所属类别的               ，因此适用于类域的交叉或非线性可分的样本集   

   

   

。

KNN算法缺点

计算量大  




    




    




    ，尤其是样本量    
    
    
、特征数非常多的时候     

     

     

  。另外KD树    


     


     


   、球树之类的模型建立也需要大量的内存 只与少量的k相邻样本有关
















，样本不平衡的时候               ，对稀有类别的预测准确率低 使用懒散学习方法   



     



     



    ，导致预测时速度比起逻辑回归之类的算法慢




  




  




  
。当要预测时
















，就临时进行 计算处理
  


  


  


。需要计算待分样本与训练样本库中每一个样本的相似度    
    
    
，才能求得与 其最近的K个样本进行决策     
     
     
 。 与决策树等方法相比    


     


     


   ，KNN考虑不到不同的特征重要性




 




 




 

，各个归一化的特征的影响都是相同的 




   




   




   。 相比决策树




 




 




 

、逻辑回归模型   

   

   

，KNN模型可解释性弱一些 差异性小     

     

     

  ，不太适合KNN集成进一步提高性能

 



 



 



。