CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In
jackfrued

CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!

GitHub Repository: jackfrued/Python-100-Days
 Path: blob/master/Day81-90/82.k最近邻算法.md
Views: 729

k最近邻分类

kk最近邻（简称kNN，k-Nearest Neighbor）是Cover和Hart在1968年提出的一种简单的监督学习算法，可用于字符识别、文本分类、图像识别等领域。kNN的工作机制非常简单：给定测试样本，基于某种距离度量（如：欧式距离、曼哈顿距离等）找出训练集中与其最接近的kk个训练样本，然后基于这kk个“最近邻居”的信息来进行预测。对于分类任务，可以在kk个最近邻居中选择出现次数最多的类别标签作为预测的结果；对于回归任务，可以使用kk个最近邻居实际输出（目标值）的平均值作为预测的结果，当然也可以根据距离的远近进行加权平均，距离越近的样本权重值就越大。

距离的度量

  1. 欧氏距离

d=∑k=1n(x1k−x2k)2d = \sqrt{\sum_{k=1}^n(x_{1k}-x_{2k})^2}

  1. 曼哈顿距离

d=∑k=1n∣x1k−x2k∣d = \sum_{k=1}^n \mid {x_{1k}-x_{2k}} \mid

  1. 切比雪夫距离

d=max(∣x1k−x2k∣)d = max(\mid x_{1k}-x_{2k} \mid)

  1. 闵可夫斯基距离

    • 当p=1p=1时，就是曼哈顿距离

    • 当p=2p=2时，就是欧式距离

    • 当p→∞p \to \infty时，就是切比雪夫距离

d=∑k=1n∣x1k−x2k∣ppd = \sqrt[p]{\sum_{k=1}^n \mid x_{1k}-x_{2k} \mid ^p}

  1. 余弦距离 cos(θ)=∑k=1nx1kx2k∑k=1nx1k2∑k=1nx2k2 cos(\theta) = \frac{\sum_{k=1}^n x_{1k}x_{2k}}{\sqrt{\sum_{k=1}^n x_{1k}^2} \sqrt{\sum_{k=1}^n x_{2k}^2}}

鸢尾花数据集介绍

kNN算法实现

###使用Scikit-learn实现kNN

算法优缺点

优点：

  1. 简单有效

  2. 重新训练代价低

  3. 适合类域交叉样本

  4. 适合大样本分类

缺点：

  1. 惰性学习

  2. 输出的可解释性不强

  3. 不擅长处理不均衡样本

  4. 计算量比较大

k值的选择和交叉检验

k值的选择对于kNN算法的结果有非常显著的影响。下面用李航博士的《统计学习方法》一书中的叙述，来对k值的选择加以说明。

如果选择较小的kk值，就相当于用较小的邻域中的训练实例进行预测，“学习”的近似误差会减小，只有与输入实例较近（相似的）训练实例才会对预测结果起作用；但缺点是“学习”的估计误差会增大，预测结果会对近邻的实例点非常敏感，如果近邻的实例点刚好是噪声，预测就会出错。换句话说，kk值的减小就意味着整体模型变得复杂，容易发生过拟合。

如果选择较大的kk值，就相当于用较大的邻域中的训练实例进行预测，其优点是可以减少学习的估计误差，但缺点是学习的近似误差会增大。这时候，与输入实例较远（不相似的）训练实例也会对预测起作用，使预测发生错误。对于k=Nk=N的极端情况（其中NN代表所有的训练实例的数量），那么无论输入实例是什么，都会预测它属于训练实例中最多的类，很显然，这样的模型完全忽略了训练实例中大量的有用信息，是不可取的。

实际应用中，kk的取值通常都比较小，可以通过交叉检验的方式来选择较好的kk值。