K最近邻（k-Nearest Neighbor，KNN）分类算法

以你之姓@ 2022-05-04 01:30 252阅读 0赞

### 概述 ###

K最近邻（k-Nearest Neighbor，KNN）分类算法是最简单的机器学习算法。  
  
它没有训练的过程，它的学习阶段仅仅是把样本保存起来，等收到测试集之后再进行处理，属于“懒惰学习”。反之，在训练阶段就对样本进行学习的算法属于“急切学习”。  
  
它本质上是衡量样本之间的相似度。

### 口头描述 ###

给定测试集里某个点，基于某种距离度量计算它与训练集中每个点的距离，按照距离递增依次排序，选取与当前点距离最小的K个点，确定K个点的所在类别的出现频率，频率最高的类别作为当前点的label

### 计算步骤 ###

计算步骤如下：

*  算距离：给定测试对象，计算它与训练集中的每个对象的距离
 *  找邻居：对训练集的每个对象根据距离排序，选取最近的K个
 *  做分类：根据这k个近邻归属的主要类别进行投票，以确定测试对象的分类

### 相似度的衡量 ###

距离越近应该意味着这两个点属于一个分类的可能性越大。  
但，距离不能代表一切，有些数据的相似度衡量并不适合用距离  
相似度衡量方法：包括欧式距离、夹角余弦等。

（简单应用中，一般使用欧氏距离，但对于文本分类来说，使用余弦(cosine)来计算相似度就比欧式(Euclidean)距离更合适）

### 类别的判定 ###

*  简单投票法：少数服从多数，近邻中哪个类别的点最多就分为该类。
 *  加权投票法：根据距离的远近，对近邻的投票进行加权，距离越近则权重越大（权重为距离平方的倒数）

### 算法不足之处 ###

*  样本不平衡容易导致结果错误  
    如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。  
      
    改善方法：对此可以采用权值的方法（和该样本距离小的邻居权值大）来改进。
 *  计算量较大  
    因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。  
      
    改善方法：事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。  
    该方法比较适用于样本容量比较大的类域的分类，而那些样本容量较小的类域采用这种算法比较容易产生误分。

### k值设定为多大？ ###

k太小，分类结果易受噪声点影响；k太大，近邻中又可能包含太多的其它类别的点。  
（对距离加权，可以降低k值设定的影响）  
k值通常是采用交叉检验来确定（以k=1为基准）  
经验规则：k一般低于训练样本数的平方根

### 类别如何判定最合适？ ###

投票法没有考虑近邻的距离的远近，距离更近的近邻也许更应该决定最终的分类，所以加权投票法更恰当一些。而具体如何加权，需要根据具体的业务和数据特性来探索

### 如何选择合适的距离衡量？ ###

高维度对距离衡量的影响：众所周知当变量数越多，欧式距离的区分能力就越差。  
变量值域对距离的影响：值域越大的变量常常会在距离计算中占据主导作用，因此应先对变量进行标准化。

### 训练样本是否要一视同仁？ ###

在训练集中，有些样本可能是更值得依赖的。  
也可以说是样本数据质量的问题  
可以给不同的样本施加不同的权重，加强依赖样本的权重，降低不可信赖样本的影响。

### 性能问题？ ###

kNN是一种懒惰算法，平时不好好学习，考试（对测试样本分类）时才临阵磨枪（临时去找k个近邻）。  
  
懒惰的后果：构造模型很简单，但在对测试样本分类地的系统开销大，因为要扫描全部训练样本并计算距离。  
已经有一些方法提高计算的效率，例如压缩训练样本量等。

### 距离计算方法 ###

假设使用欧氏距离，有两个向量  A ( a 1 , a 2 , . . . , a n ) , &ThickSpace; B ( b 1 , b 2 , . . . , b n ) A(a\_1,a\_2,...,a\_n),\\; B(b\_1,b\_2,...,b\_n) A(a1,a2,...,an),B(b1,b2,...,bn) ,则他们之间的欧氏距离为：  
 D A , B = ∑ i = 1 n ( a i − b i ) 2 D\_\{A,B\}=\\sqrt\{\\sum\_\{i=1\}^\{n\}(a\_i-b\_i)^2\} DA,B=i=1∑n(ai−bi)2

### Python代码 ###

""" 测试集 inX 训练样本集 dataSet 标签向量 labels 最近邻数目 k """
    def KNN(inX,dataSet,labels,k):
        dataSetSize=dataSet.shape[0]
        diffMat=tile(inX,(dataSetSize,1))-dataSet
        sqDiffMat=diffMat**2
        sqDistance=sqDiffMat.sum(axis=1)
        distances=sqDistance**0.5
        sortedDistIndicies=distances.argsort()
        classCount={ }
        for i in range(k):
            voteIlabel=labels[sortedDistIndicies[i]]
            classCount[voteIlabel]=classCount.get(voteIlabel,0)+1
        sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
        return sortedClassCount[0][0]