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)
预测值为f(X),真实值为Y
即预测正确则没有损失(损失为 0),预测错误损失为 1
预测是否正确的标准是:预测值是否等于目标值
(2)平方损失函数(quadratic loss functon)
(3)绝对损失函数(absolute loss function)
(4)对数损失函数(logarithmic loss function)
3)分类决策规则
k邻近法中的分类决策规则往往是多数表决,即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。
说得通俗一点,就是等权重投票选出最多票数的!
多数表决规则有着如下解释:
如果分类的损失函数为0-1损失,分类函数为
(即通过f分类模型能将输入分类为c1,c2,...,cK)
则错误分类的概率为:
上式左边是误分类概率,右边是1减去正确分类的概率
因为两概率之和为 1
这就是KNN算法的原理,你学会了么?
【人工智能社群】已经成立,旨在打造真正有价值,能交流,一起学习成长的社群,并且每月送书不断!现备注城市+昵称+研究方向,扫码添加好友后立即进群。
▲长按扫码