2、K近邻算法(KNN)

约定不等于承诺〃 2022-08-19 13:10 254阅读 0赞

## 2、K近邻算法(KNN) ##

### 2.1、K-近邻算法概述 ###

简单的说，K-近邻算法采用测量不同特征值之间的距离方法进行分类。

K-近邻算法（KNN），它的工作原理是：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即知道每个数据与所属分类对应关系。输入没有标签新数据后，将新数据的特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。

一般来说，我们只选择样本数据集中前K个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数。最后选择k个最相似的数据中出现次数最多的数据，作为新数据的分类。

举一个简单的例子：

下图中蓝色方块和红色三角块代表两类不同的训练样本数据，绿色圆圈是待分类的数据

当k=3时，绿色圆圈属于红色小三角形类

当k=5时，绿色圆圈属于蓝色方块类

![Center][]

### 2.2、KNN算法 ###

K近邻使用的模型实际上对应于对特征空间的划分。

模型三要素：1）、距离度量

2）、k值的选择

3）、分类决策规则

当训练集、距离度量、K值选择和决策规则决定后，对于任何一个新来的样本输入，它所属的类就唯一确定。

**距离度**量：

估计不同样本之间的相似性，通常采用的方法是计算样本间的距离，相似性度量方法有欧氏距离、余弦夹角、曼哈顿距离、切比雪夫距离等。

设二维平面两点：a(x1,x2)  ,b(y1,y2)

**欧氏距离：**

![Center 1][]

**曼哈顿距离：**

![Center 2][]

**切比雪夫距离：**

![Center 3][]

设二维平面两点：a(x1,y1)  ,b(x2,y2)

**余弦夹角：**

![Center 4][]

**K值选择：**

**若K值较小**，只有对输入实例较近的训练实例才会对预测结果起作用，预测结果会对近邻实例点非常敏感。如果近邻的实例点恰巧是噪声，预测就会出错。容易发生过拟合。

**若K较大**，与输入实例较远（不相似）训练实例也会对预测结果起作用，容易是预测结果出错。K值得增大意味着整体的模型变简单。

**若K=N**，那么无论输入实例是什么，都将简单的预测它属于在训练实例中最多的类。这时，模型过于简单，完全忽略训练实例中大量有用的信息，是不可取的。

在应用中，K值一般取较小的值，通常通过经验或交叉验证法来选取最优的K值。

**分类决策规则：**

**投票表决**：

少数服从多数，输入实例的K个近邻中哪个类的实例点最多，就分为该类。

**加权投票法**：

根据距离的远近，对K个近邻的投票进行加权，距离越近则权重越大（比如权重为距离的倒数）

**K近邻算法的伪代码：**

对未知类别属性的数据集中每个点依次执行以下操作

1）、计算已知类别数据集中的点与当前点的距离；

2）、按照距离递增次序排序；

3）、选取与当前点距离最小的k个点；

4）、确定前k个点所在类别出现的频率；

5）、返回前k个点出现频率最高的类别作为当前点的预测分类。

使用算法的一般流程：

1）、数据处理：准备，分析数据，进行归一化等。

2）、训练算法：利用训练样本训练分类器。

3）、测试算法：利用训练好的分类器预测测试样本，并计算错误率。

4）、使用算法：对于未知类别的样本，预测其类别。

测试K近邻分类器性能的留存：

1）、数据处理：归一化等（具体情况可以具体的对待）

2）、测试算法：根据K近邻分类算法预测测试样本类别，并计算错误率

3）、使用算法：当输入新的未知类别样本，利用算法预测结果

**分类错误率：**

如何测试分类器的性能呢？

一个分类器的性能的好坏最简单的评估方法就是，计算其分类错误率。错误率即为测试数据中分类错误的数据个数除以测试数据总数。

错误率越低，分类性能就越好。

### 2.3、k近邻算法的思想 ###

![Center 5][]

![Center 6][]

### 2.4、具体代码实现 ###

注意数组array导入的是这个包：

<table> 
 <tbody> 
  <tr> 
   <td> <p><strong><u><span style="color:#0066CC">multiarray.array</span></u></strong> Found at: <strong><u><span style="color:#0066CC">numpy.core.numeric</span></u></strong></p> <p>array = multiarray.array</p> </td> 
  </tr> 
 </tbody> 
</table>

<span style="font-family: Arial, Helvetica, sans-serif; background-color: rgb(255, 255, 255);">
    代码测试结果：</span>#-*- coding=utf-8 -*-
    from numpy import *
    import operator
    
    def createDataSet():
        #训练集特征
        group = array([[1.0, 0.9], [1.0, 1.0], [0.1, 0.2], [0.0, 0.1]])  
        #训练集对应类别
        labels=['A','A','B','B']
        return group,labels
    
    #待预测数据，训练数据特征、训练数据标签、K值
    def knnclassfy(inx,dataSet,labels,k):
        #训练数据个数
        dataSetSize=dataSet.shape[0]
        #step1：求距离
        #tile重复inx数据，共(dataSetSize,1)次
        diffMat=tile(inx,(dataSetSize,1))- dataSet
        #每个维度距离平方
        sqDiffMat=diffMat**2
        #按行求和
        sqDistances=sqDiffMat.sum(axis=1)
        #开方
        distances=sqDistances**0.5
        #step2：对距离从小到大排序
        sortedDistIndicies=distances.argsort();
        classCount={}
        for i in range(k):
            #step3：选择k个近邻样本
            #得到升序排序后的距离所对应的标签
            voteIlabel=labels[sortedDistIndicies[i]]
            #step4：统计k个近邻样本的各个类别数
            classCount[voteIlabel]=classCount.get(voteIlabel,0)+1
        #step5：返回类别数最多的类别作为待分类数据的类别标签
        #reverse=True对标签的个数进行降序排序
        sortedClassCount=sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
        #排序后第一个标签的个数最多，即认为待分类的向量归属于此标签
        return sortedClassCount[0][0]
    
    
    dataSet, labels = createDataSet()  
    testX = array([1.1, 1.0])  
    k = 3  
    outputLabel = knnclassfy(testX, dataSet, labels, k)  
    print "The first Your input is:", testX, "and classified to class: ", outputLabel  
    
    testX = array([0.2, 0.3])  
    outputLabel = knnclassfy(testX, dataSet, labels, k)  
    print "The second Your input is:", testX, "and classified to class: ", outputLabel

代码测试结果：

<table> 
 <tbody> 
  <tr> 
   <td> <p>The first Your input is: [ 1.1&nbsp; 1. ] and classified to class:&nbsp; A</p> <p>The second Your input is: [ 0.2&nbsp; 0.3] and classified to class:&nbsp; B</p> </td> 
  </tr> 
 </tbody> 
</table>

![Center 7][]

[Center]: /images/20220731/e5cc4a4510a94f2cb9bced0d004e55b4.png
[Center 1]: /images/20220731/b2f31811abe34b628ffdfd0902eca73b.png
[Center 2]: /images/20220731/e3494f525dab4397a9291972ec8dd204.png
[Center 3]: /images/20220731/73475a0ae87b49d088d518ed3abe36eb.png
[Center 4]: /images/20220731/9706fe008e4e42deb0cb9eb512e2b92c.png
[Center 5]: /images/20220731/4781053dcaca4f97a0b17056d819bcb0.png
[Center 6]: /images/20220731/cb990c40a74b4e83b08b8705c9ca36b2.png
[Center 7]: /images/20220731/31e515efeee547b8ae62b1dcec3eaabc.png