2.9 K近邻算法

摘要

K近邻算法(K-nearest neighbor, k-NN)是一种基本的分类与回归的方法。

k近邻算法：

输入：训练数据集

T=(x1,y1),(x2,y2)...,(xN,yN)T={(x_{1},y_{1}), (x_{2},y_{2})..., (x_{N},y_{N})}

其中

xiϵχ⊆Rnx_{i}\epsilon \chi \subseteq R^{n}

为实例的特征向量

yiϵY=c1,c2......,cK,y_{i} \epsilon Y={c_{1}, c_{2}......, c_{K}, }

为实例的类别,i=1,2,...,N

输出：给定实例x，要能输出新给的特征向量所属y中的类

(1). 根据给定的距离度量，在训练集T中找出与x最邻近的k个点，涵盖这k个点的x的邻域基座 $N_{k} (x)$ ;

(2). 在 $N{k} (x)$ 中根据分类决策规则（如多数表决表，对$N{k} (x)$ 进行排序，然后取出现频率最高的第k个点的类）决定x的类别y：

y=arg max⁡cj ∑xi⊆Nk(x) I(yi=cj)y=arg\, \max_{c_{j}}^{\ } \sum_{x_{i}\subseteq N_{k}(x)}^{\ } I(y_{i}=c_{j})

其中I为指示函数，为yi=cjy_{i}=c_{j}情况下, I = 1 否则I = 0

更通俗的理解可以为如下：

KNN是通过测量不同特征值之间的距离进行分类

  • 它的思路是：

如果选择一个待分类的样本，其在特征空间中有k个最相似的样本值（即特征空间中和这个待分类的点为最邻近点集）。

这k个样本集中的绝大多数属于某一类别，则该待分类的样本也属于这个绝大多数的同一类别。

其中K通常是不大于20的整数。

KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

例子

下面通过一个简单的例子说明一下：如下图，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如下图所示

  • 如果K=3，最小的圆, 由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形那个类。

  • 如果K=5，虚线内，由于蓝色四方形比例为3/5，因此绿色圆被赋予蓝色四方形类。

由此也说明了KNN算法的结果很大程度取决于K的选择。

在KNN中，通过计算对象间距离来作为各个对象之间的非相似性指标，避免了对象之间的匹配问题，在这里距离一般使用欧氏距离或曼哈顿距离：

欧氏距离：

d(x,y)=∑k=1n(xk−yk)2d(x,y)=\sqrt{\sum_{k=1}^{n}(x_{k}-y_{k})^{2}}

曼哈顿距离：

d(x,y)=∑k=1n∣xk−yk∣d(x,y)=\sqrt{\sum_{k=1}^{n}|x_{k}-y_{k}|}

同时，KNN通过依据k个对象中占优的类别进行决策，而不是单一的对象类别决策。这两点就是KNN算法的优势。

接下来对KNN算法的思想总结一下

就是在训练集中数据和标签已知的情况下，输入测试数据，将测试数据的特征与训练集中对应的特征进行相互比较，找到训练集中与之最为相似的前K个数据，则该测试数据对应的类别就是K个数据中出现次数最多的那个分类，其算法的描述为：

  • 1）计算测试数据与各个训练数据之间的距离；

  • 2）按照距离的递增关系进行排序；

  • 3）选取距离最小的K个点；

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

  • 5）返回前K个点中出现频率最高的类别作为测试数据的预测分类。

python 代码实现：

#coding:utf-8

from numpy import *
import operator

##给出训练数据以及对应的类别
def createDataSet():
    group = array([[1.0,2.0],[1.2,0.1],[0.1,1.4],[0.3,3.5]])
    labels = ['A','A','B','B']
    return group,labels

###通过KNN进行分类
def classify(input,dataSe t,label,k):
    dataSize = dataSet.shape[0]
    ####计算欧式距离
    diff = tile(input,(dataSize,1)) - dataSet
    sqdiff = diff ** 2
    squareDist = sum(sqdiff,axis = 1)###行向量分别相加，从而得到新的一个行向量
    dist = squareDist ** 0.5

    ##对距离进行排序
    sortedDistIndex = argsort(dist)##argsort()根据元素的值从大到小对元素进行排序，返回下标

    classCount={}
    for i in range(k):
        voteLabel = label[sortedDistIndex[i]]
        ###对选取的K个样本所属的类别个数进行统计
        classCount[voteLabel] = classCount.get(voteLabel,0) + 1
    ###选取出现的类别次数最多的类别
    maxCount = 0
    for key,value in classCount.items():
        if value > maxCount:
            maxCount = value
            classes = key

    return classes

测试代码如下：

#-*-coding:utf-8 -*-
import sys
sys.path.append("...文件路径...")
import KNN
from numpy import *
dataSet,labels = KNN.createDataSet()
input = array([1.1,0.3])
K = 3
output = KNN.classify(input,dataSet,labels,K)
print("测试数据为:",input,"分类结果为：",output)

回车之后的结果为：

测试数据为： [ 1.1 0.3] 分类为： A

答案符合我们的预期，要证明算法的准确性，势必还需要通过处理复杂问题进行验证，之后另行说明。

【提示】python版本为3.7

具体的KNN视频教程地址为：

参考

参考文档来源1:Yabea-博客

参考文档来源2:李航-统计学习方法

Previous2.8 强化学习经验回放Next2.10 朴素贝叶斯法

Last updated