一、KNN概述

        在所有的机器学习算法中，K近邻（KNN）几乎是最简单的，而且它既可用于分类（预测离散的类别标签），也可用于回归（预测连续的实数值）。尽管简单，但事实证明在某些任务中KNN非常有效。因为KNN需要存储所有的训练样本，占用内存很大，所以速度相对较慢。因此在使用KNN之前，常常需要通过聚类降低训练集大小。        

        KNN是最简单的分类算法，也可以用于回归。对于待分类的样本，计算待预测样本和训练集中所有数据点的距离，将距离从小到大取前K个，哪个类别在前K个数据点中的数据最多，就认为待预测样本属于该类别。

1、样本的特征空间

        在训练样本集中，每个样本x都是一个由nx个特征值构成的特征向量x=(x1, …,xnx)，因此可以认为每个样本都在一个nx维特征空间内分布。例如，日常生活中所说的三维空间，通常是指由长、宽、高三个维度所构成的空间。三维空间中的每个样本x都可以用包含长、宽、高三个特征的特征向量x=(x1, x2, x3)来唯一描述，显然样本x的分布就是在长、宽、高三个维度的特征空间内的分布。

        对于监督学习来说，每个样本都有一个标签y, 分类算法或回归算法的目的就是找到一个函数f，y=f(x)，使得以足够高的精度逼近y。这样，当有一个新样本x-test时，就可以使用该函数确定其标签了。

2、向量之间的距离

        样本在特征空间中的分布是用特征向量描述的，因此可以使用向量之间的距离来衡量样本与样本之间的相似程度。两个向量之间距离的计算，在数学上称为向量距离（Distance），