【机器学习】KNN（k-Nearest Neighbor）算法

K近邻（k-Nearest Neighbor， 简称KNN）算法是一种非常简单的机器学习监督算法。它的主要思想是：给定一个测试数据，如果离它最近的K个训练数据大多都属于某一个类别，则认为该测试数据也属于这个类别。以下图为例，图中的绿色点表示测试数据，现在我们需要判断这个点应该是红色三角形还是蓝色正方形。按照上述思想，如果K取3，则离绿色点最近的点中有两个是红色三角形，一个是蓝色正方形，因此KNN判断绿色点为红色三角形。

可见，KNN的思想确实十分简单，实现也很容易。但是我们思考一下为什么可以判断两个数据之间的“远近”？回到现实中的例子，当你判断是一张桌子理离你近，还是椅子离你近时，我们的衡量标准其实就是看桌子和椅子和我们的距离。回想一下：计算一条直线上两点的距离，我们可以直接将两点的坐标值相减后取绝对值得到；计算一个平面内两个点的距离，我们可以将点的各个坐标值带入欧式距离计算公式得到距离；同样地，计算三维空间中点的距离，也是将点的各个坐标值带入欧式距离计算公式得到。那么推广到d维空间中的点，我们也可以点的各个坐标值带入欧式距离计算公式得到。但是，各个点的坐标是如何确定的呢？其实就是我们引入了一个空间坐标系，d维空间中的一个点其实就是一个向量，这个向量的各个数值就对应了其在各个维度坐标轴上的取值。其实我们也可以将机器学习中的每个样本看作是d维空间中的一个点，这样我们就可以采用空间中的距离计算方法来衡量样本之间的距离，因此才会有所谓的“远近”。也就是说，KNN将每一个数据都看作是d维空间中的一个点，在这个空间中采用了坐标系来描述这个点的位置，再通过某种距离计算公式来表示这两个点之间的距离。

KNN分类

给定一个d维的测试数据 x∈Rd$x /in R^d$，KNN对于x的分类过程如下：

找到距离最小的k个训练数据，采用多数投票的方式得到k个训练数据中出现次数最多的类标签，将x判定为这个类标签。

使用pyhton实现KNN如下：

KNN 回归

在分类任务中，KNN采取多数投票的方法判定测试数据的类别。在回归任务中可以采取多种方法判定。“平均法”将找出的K个最近测试样本的实值输出的平均值作为预测结果；“加权平均”将权重的倒数作为K个样本的权重值，从而计算加权平均，距离越近的样本其权重越大。

距离计算方法

衡量两个样本之间距离除了可以使用欧式距离以外，还可以采用闵可夫斯基距离， 曼哈顿距离，切比雪夫距离，余弦距离等等。

闵可夫斯基距离也叫做明氏距离，计算公式为：(∑ni=1|xi−yi|p)1p$(/sum_{i=1}^n |x_i - y_i|^p)^/frac{1}{p}$。当p=1时，就是曼哈顿距离；当p=2时，就是欧氏距离；当p取无穷时，就是切比雪夫距离： limp→∞(∑ni=1|xi−yi|p)1p=maxni=1|xi−yi|$/lim_{p /to /infty} (/sum_{i=1}^n |x_i - y_i|^p)^/frac{1}{p} = /max_{i=1}^n |x_i - y_i|$

K的取值

k值的不同预测结果也会很不一样，因此选取一个合适的k值是很有必要的。最简单的就是k=1，即只看与测试数据最近的那个训练数据。但是很有可能比这个训练数居远一点点的那些数据，大多数是另外一个分类标签，这样就会导致预测错误。最复杂的就是k=N，即k等于训练样本的总个数。这虽然考虑了所有的文本，大大提高了预测结果的可靠性，但是会带来大量的计算，降低算法的速度。而且，训练数据只是无穷数据中的一部分，训练数据集中样本的标签不能代表所有的数据类别标签分布。还可以将k取不同的值，选定训练错误率最低的k值。但是这种方法同样会花费大量的时间。 一个比较合理的取值是k=(√N)$k=/sqrt(N)$，这样不仅可以提高预测准确率，还可以将时间控制在一个比较合理的范围。