机器学习实战（3）—— KNN原理部分

k近邻（k-Nearest Neighbor，简称kNN）学习是一种监督学习方法。

原理：

给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本，然后基于这k个“邻居”的信息来进行预测。

在分类任务中，可使用“投票法”，即选择这k个样本中出现次数最多的类别标记作为预测结果。还可以基于距离远近加权平均或加权投票，距离越近的样本权重越大。

k近邻是一种“懒惰学习”，没有显式的训练过程！

只是把样本保存起来，当有需要预测的样本时，直接根据距离等预测。

下图中，绿色样本应该预测到哪一类中呢？

当 k = 1，预测为红色三角形一类

当 k = 3，预测为红色三角形一类

当 k = 5，预测为蓝色矩形一类

显然，k是一个重要参数，当k选择不同值时，分类结果可能不同。

如果采用不同的距离计算方式，“邻近”的样本可能有显著差异。

k邻近法的3个基本要素：

（1）距离度量（2）k值的选择（3）分类决策规则

k邻近算法的数学描述：

输入：训练数据集 T={（x1，y1），（x2，y2），...，（xN , yN) }

其中，x为实例的特征向量，y为实例的类别

输出：实例 x 所属的类 y

（1）根据给定的距离度量，在训练集 T 中找出与 x 最邻近的 k 个点，涵盖这 k 个点的 x 的邻域记作Nk（x）

（2）在Nk（x）中根据分类决策规则（如多类表决）决定 x 的类别 y：

argument of the maximum/minimum

arg max f(x): 当f(x)取最大值时，x的取值

arg min f(x)：当f(x)取最小值时，x的取值

I 为指示函数，即当 yi=cj 时 I 为 1，否则 I 为 0，即多数表决，找出最多的类别。

k邻近法的特殊情况是k=1的情形，称为最近邻法，最近邻法将训练数据集中与 x 最邻近点的类作为 x 的类。

（1 )距离度量：

距离在某种程度上是一种相似程度的反映

比如上海距离苏州很近，距离哈尔滨较远，从某种程度上认为上海和苏州的相似性大于上海和哈尔滨的相似性。

k近邻模型一般使用的是欧氏距离（小学初中就学过了）

其实还有其他距离：

如Lp距离、Minkowski（闵可夫斯基）距离

（1）距离度量：

设特征空间X是n维实数向量空间Rn， xi，xjX，

xi=（xi（1）xi（2），..., xi（n）)T

xj=（xi（1）xi（2），..., xi（n）)T,

xi , xj的Lp距离定义为：

当 p=2 时，为欧氏距离：

其实就是大家超级熟悉的：

就是常说的，两点之间的直线段长度（3维以上图形无法表示！）

当 p=1 时，为曼哈顿距离：

曼哈顿距离的由来：

曼哈顿距离的命名原因是从规划为方型建筑区块的城市（如曼哈顿）间，最短的行车路径而来，红色、蓝色、黄色三者的曼哈顿距离相等，绿色为欧氏距离。

如果图中一个白色正方形的边长为1

左下角坐标为（0,0），往右、上是正向

则红色路线的曼哈顿距离为：

|6-0| + |6-0| = 12

当 p=时，为各个坐标距离的最大值，即：

（小提示：为无穷大）

近似误差：可以理解为对现有训练集的训练误差。

估计误差：可以理解为对测试集的测试误差。

近似误差关注训练集，如果近似误差小了会出现过拟合的现象，对现有的训练集能有很好的预测，但是对未知的测试样本将会出现较大偏差的预测。模型本身不是最接近最佳模型。

估计误差关注测试集，估计误差小了说明对未知数据的预测能力好。模型本身最接近最佳模型。

( 2 ) k值选择

k值的选择会对k近邻的结果产生重大影响。

如果k选的较小，相当于用较小的邻域中的训练实例进行预测，预测结果会对邻近的实例点非常敏感，如果邻近的点是噪声预测就会错，k减小意味着模型变得复杂，容易发生过拟合，即近似误差小，估计误差大。

如果k选择较大，相当于用较大的邻域中的训练实例进行预测，近似误差大，估计误差小，意味着模型变得简单，较远处（不相似的）训练实例也会起着预测作用，可能会欠拟合。

k一般取一个较小的数值，通常采用交叉验证法选取最佳的k值。

监督学习是选择模型 f 作为作为决策函数，对于给定的输入X，由 f（X）给出相应的输出 Y ，这个输出的预测值f（X）和真实值 Y 可能一致也可能不一致，用一个损失函数（loss function）来度量预测错误的程度，损失函数是f（X )和 Y 的非负实值函数，记作 L ( Y , f（X ) )

机器学习中常见的损失函数：

（1）0-1损失函数（0-1 loss function）