KNN(K-nearest Nerbor)算法

Posted on

KNN(K-NearestNerborhood)学习

特点

  • 懒惰学习(LazyLearning):

    1. 在训练阶段仅仅是把样本保存起来，训练时间开销为零(没有显式的训练过程)
    2. 待收到测试样本后再进行处理
    3. 预测阶段较慢

  • 对$K$值敏感：增大$K$值，一般来说准确率先上升后下降

    讨论1NN在二分类问题的性能：泛化错误率不超过贝叶斯最优分类器的错误率的两倍
    • $K=1$时目标是找到最近邻的1个点，给定测试样本$x$ ,最近邻训练样本为$z$，标签集为$\mathcal{Y}$,抽样的样本独立同分布
    • 对任意测试样本，总能在任意近的范围的范围内找到一个训练样本
    • 令$c^*=arg \max_{c \in \mathcal{Y} } P(c|x) $表示Bayes最优分类器的结果,计算分类出错的概率

    $$
    \begin{aligned}
    P(err)& =1-\sum_{c\in\mathcal{Y} }P(c\mid\boldsymbol{x})P(c\mid\boldsymbol{z}) \
    &\simeq1-\sum_{c\in\mathcal{Y} }P^2(c\mid\boldsymbol{x}) \
    &\leqslant1-P^2(c^\mid\boldsymbol{x}) \
    &=\left(1+P\left(c^    \mid\boldsymbol{x}\right)\right)\left(1-P\left(c^\mid\boldsymbol{x}\right)\right) \
    &\leqslant2\times\left(1-P\left(c^    \mid\boldsymbol{x}\right)\right).
    \end{aligned}
    $$

  • 高维诅咒：在高维空间中近邻的点都变得差不多远，而且KDtree优化难以进行

  • 其他：

    • 非参数化parameter-free：不对数据分布做出任何假设
    • 简单，易于实现，内存消耗大，计算成本高，解释性差，预测慢

基本思想

根据距离函数计算待分类样本X和每个训练样本的距离（作为相似度），选择与待分类样本距离最小的K个样本作为X的K个最近邻，最后以X的K个最近邻中的大多数所属的类别作为X的类别。

分类原理

  1. 导入划分训练集和测试集

    • 每条属性应该有若干属性和一个标签
    • 由于KNN是懒惰学习，对于测试集的每一个样本，KNN通过样本的若干属性和训练集的样本的属性的距离

  2. 设置算法的K值

    • $K$为超参数，需要人为设置
    • 算法实现后可通过交叉验证的方式选取最好的$K$

  3. 设置算法的距离指标

    Minkowski距离
    • 对数据对象 $i=(x_{i1},x_{i2},…,x_{ip}),j=(x_{j1},x_{j2},…,x_{jp})$,各维权重为 $\omega=(\omega_1,\omega_2,…,\omega_p)$
    • Minkowski距离：$d_{\omega}(i,j)=\left({\sum_{k=1}^{p}{w_i|x_{ik}-x_{jk}|^q}}\right)^{\frac 1 q}$
    • 注意，各维等价时，$p=1$称为Manhattan距离 $d(i,j)={\sum_{k=1}^{p}{|x_{ik}-x_{jk}|^q}}$，$p=2$称为Euclidean距离 $d(i,j)=\sqrt{\sum_{k=1}^{p}{|x_{ik}-x_{jk}|^2}}$

  4. 遍历所有的测试样本，对每一个样本进行预测

    • 当前的样本为 sample，计算 sample与训练集中的样本(标签为 lb)的距离 d,
    • 把所有距离-标签元组((d, lb))按照 d升序排序
    • 投票：对前 K个元组，找到出现次数最多的标签，这个标签就是预测的结果(平局的情况：我们选择数据点中第一个出现的数据点的标签作为结果，这在python也是很好实现的。)

  5. 记录所有预测的标签，计算准确率

  6. 对所有的可能的$K$​值，交叉验证

注意

  1. K值设定
  • K值选择过小：得到的近邻数过少，会降低分类精度，同时会放大噪声的干扰
  • K值选择过大：k个近邻并不相似的数据亦被包含进来，造成噪声增加而导致分类效果的降低。
  1. 类别的判定方式
  • 投票法没有考虑近邻的距离的远近，距离更近的近邻也许更应该决定最终的分类，所以加权投票法更恰当一些。
  1. 距离度量方式的选择

当变量越多（高维诅咒问题），欧式距离的区分能力越差。

  1. 性能问题

KNN是一种懒惰算法，构造模型很简单但在对测试样本分类地的系统开销大。

策略：采样训练样本量减少训练集的大小；或通过聚类，将聚类所产生的中心点作为新的训练样本。