k近邻法

k近邻法(k-nearest neighbor,k-NN)是一种基本分类与回归方法。书中只讨论了分类问题中的k近邻法。

k近邻法用较为通俗的语言描述为:根据距离x最近的k个点的类别来将x进行分类。

可以从上面描述中看出k近邻法的几个关键因素:

  • 距离:怎么定义点与点的距离
  • k:最近的k个点,k的值如何确定
  • 分类:怎么根据附近点的类别情况进行分类,分类规则是什么

先给出书中的定义,再来看这几个关键因素。

定义

输入:训练数据集$$T={ (x_{ 1 },y_{ 1 }),(x_{ 2 },y_{ 2 }),\cdots ,(x_{ N },y_{ N })} $$ 其中$x_i \in X \subseteq R^n$为实例的特征向量,$y_i \in Y \subseteq { c_1, c_2, \cdots, c_K} $为实例的类别, $i=1,2,\cdots ,N$;实例特征向量x;
输出:实例x所属的类y。

  • 根据给定的距离度量,在训练集T中找出与x最邻近的k个点,涵盖这k个点的x的邻域记作$N_{ k }(x)$;
  • 在$N_{ k }(x)$中根据分类决策规则(如多数表决)决定x的类别y:$$y=arg\max _{ c_j }{ \quad I(y_i=c_j), } \quad i=1,2,\cdots ,N;\quad j=1,2,\cdots ,K$$I为指示函数,即当$y_i=c_j$时I为1,否则I为0。

距离度量

k近邻法的特征空间一般是n维实数空间$R^n$,使用的距离是欧式距离,但也可以用其他距离,选择不同距离计算出但结果可能是不同但。

k值的选择

k值的选择会对k近邻法对结果产生重大影响。
k值若选择较小,则会对近邻点非常敏感,容易过拟合。
k值若选择较大,学习对近似误差会增大,模型较简单。

分类决策规则

k近邻法对分类规则往往是多数表决,即由k个近邻对训练实例中对多数类决定输入类对实例。