k近邻法

待我称王封你为后i 2022-08-14 05:39 145阅读 0赞

k近邻法是一种基本的分类与回归方法。k近邻法的输入为实例的特征向量，对应于特征空间的点；输出为实例的类别，可以取多值。k近邻法思想：1. 根据给定的距离度量方法，找出训练数据集中与实例x最相邻的k个点；2. 在k 个点中，根据分类决策规则，决定x 的类别。  
k近邻法中，当训练数据集、距离度量、k值、分类决策规则确定后，对于任何一个新的输入实例，它所属的类唯一的确定；这相当于将特征空间划分为一些子空间，确定子空间里每一个点所属的类。  
在距离度量为欧式距离、分类决策规则为投票表决的情况下，K近邻法代码设计：

import numpy as np
    def classify(X,traindata,trainlabel,k)
        m,n=np.shape(traindata) #m,n为行列数
        distances = np.power(np.sum((np.tile(X,(m,1))-traindata)**2,1),0.5) # 实例X与训练数据集所有点的欧式距离
        distancesort = np.argsort(distances) #返回的是下标，例如[5,2,3]，排序之后是[1,2,0]
        topK = dict()
        for i in xrange(k):
            label = trainlabel[distancesort[i]]# 得到的前k个相邻的的类别
            topK[label] = topK.get(label,0)+1 # 求得前k个相邻类别的数量
        topKsort = sorted(topK.iteritems(),key=lambda x:x[1],reverse=True)
        return topKsort[0][0] #返回实例X的类别

由上述可知，K近邻法有四个关键元素：训练数据集、k值、距离度量、分类决策规则。

### k值 ###

*  若k值较小，就相当于用较小的邻域的训练数据集进行预测。优点是学习的近似误差会减小，只有与输入实例相近的点才会对预测起作用。缺点是学习的估计误差会增大，预测结果对近邻的实例点非常敏感，如果实例点恰巧是噪声，预测就很可能出错。即，k值越小，整体模型越复杂，易过拟合。
 *  若k值较大，就相当于用较大的邻域的训练数据集进行预测。优点是学习的估计误差会减小。缺点是学习的近似误差会增大，与输入实例不相似的点也会对预测起作用。
 *  在实际中，k 值一般取一个较小的值。可以通过逐步增大k值的方法来观察最小误差率，选择合适的k值。

### 距离度量 ###

*  欧式距离，实例点与训练数据点各特征的差的平方和，再开根号；
 *  曼哈顿距离，实例点与训练数据点各特征的差的绝对值的和。  
    在距离度量的计算中，需要注意每个特征的值的范围。如果相差很大，应该进行规范化。有助于防止较大初始值域的特征比较小值域特征的权值过大。规范化公式为：  
    
    
    *v*=*v*−*m**i**n**m**a**x*−*m**i**n*

### 分类决策规则 ###

k近邻的分类决策规则往往是多数表决，即由输入实例的k个临近的训练实例的多数类决定输入实例的类。

### 总结 ###

<table> 
 <thead> 
  <tr> 
   <th>优点</th> 
   <th align="center">缺点</th> 
   <th align="right">适用范围</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>精度高、对异常点不敏感、无数据输入假设</td> 
   <td align="center">计算复杂度高、空间复杂度高</td> 
   <td align="right">数值型、标称型</td> 
  </tr> 
 </tbody> 
</table>