雅乐网

kNN 是 k-NearestNeighbor 的缩写，中文叫做k-临近算法。它的思想是通过一个点最邻接的k个点的分类来预测这个点的分类。

如下图所示，k=3时，预测问号是属于○还是△ 。在距离要预测样本最近的三个点中，有2个是三角，1个时圆，由此预测该样本属于三角分类。

距离有很多种定义，最常用的是欧氏距离：

有n个维度的两个点A和B之间的欧氏距离是

$$d = \sqrt {\sum_{i=0}^{n-1} {(A_i – B_i)^2}}$$

如果不使用特殊的优化方法，计算时需要针对新的样本和每一个训练样本计算距离，然后选出距离最近的top k个，这样时间复杂度非常大。

python代码

testVec 是一个 测试数据，大小为 1行 n列。

trainMat是所有的训练数据，m行表示m个样本，n列是n个特征。labels共m个元素对应m个样本所属的分类。

k是对测试数据选择k个最相近的训练样本来进行预测。

先使用tile函数把测试数据的向量复制m份，构成一个m*n的矩阵，这样两个矩阵相乘可以得到测试样本和每个训练样本的距离。