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集成进一步提高性能

 



 



 



。