【机器学习】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集成进一步提高性能。