K-近邻（KNN）算法_knn距离度量

作者：Gausst松鼠会 | 2024-06-11 12:07:12

踩

knn距离度量

前言

kNN是一种基本的分类和回归方法，本文探讨的是KNN的分类方法。kNN可以理解为给定训练样本，对于新的测试数据，在训练样本中找到与测试数据最临近的k个训练样本，根据最近的k个训练样本的类别，通过多数投票的方式进行预测。

假设如下图，有两类不同的样本数据，分别用蓝色的小正方形和红色的小三角形表示，而图正中间的那个绿色的圆所标示的数据则是待分类的数据。

如上图：

输入：

训练数据集 $T=\left \{ (x_1,y_1),(x_2,y_2),...,(x_n,y_n) \right \}$ ，其中 $x_i\epsilon R^n, y_i\epsilon \left\{c_1, c_2, ..., c_k \right\}$
测试数据x

输出：

根据给定的距离度量，在训练集T中找到与x距离最近的k个样本，涵盖这k个点的x的邻域记作 $N_k(x)$
在N_k(x)中根据分类规则(如多数表决)确定x的类别y， $y=arg max_j \sum_{x_i\epsilon N_k(x)}I\left \{y_i=c_j\right \},i=1,2,...,n; j=1,2,...,k$

从kNN的算法描述中可以发现，在KNN算法中有三个要素很重要，分别是距离度量，k的大小和分类规则。

距离度量有很多种方式，要根据具体情况选择合适的距离度量方式。常用的是闵可夫斯基距离：

$D(x, y)=(\sum_{i=1}^{m}|x_i-y_i|^p)^{1/p}, p\geq 1$

如果k值较小，就相当于用较小邻域中的训练实例进行预测，极端情况下k=1，测试实例只和最接近的一个样本有关，训练误差很小(0)，但是如果这个样本恰好是噪声，预测就会出错，测试误差很大。也就是当k值较小的，会产生过拟合的现象。

如果k值较大，就相当于用很大邻域中的训练实例进行预测，极端情况是k=n，测试实例的结果是训练数据集中实例最多的类，这样会产生欠拟合。

在应用中，一般选择较小k并且k是奇数。通常采用交叉验证的方法来选取合适的k值。（选取k值很重要的关键是实验调参，通过调整超参数来得到一个较好的结果）

kNN中的分类决策规则通常是多数表决，即由测试样本的k个临近样本的多数类决定测试样本的类别。

举例：对人的性别进行分类，特征分别为身高（单位cm）和鞋码（尺码）。假设数据集如表：

看出问题了吗？

身高特征的数值是脚码特征的4倍左右，那么在进行距离度量的时候，算法就会偏向于身高特征，对于距离的计算结果受身高特征的影响较大，这样造成俩个特征并不是等价重要的，最终可能会导致距离计算错误，从而导致预测错误。

这就是特征量纲（简单理解为取值范围或者衡量单位）的问题，因为特征量纲的不同导致了身高的重要性已经远远大于脚码了，这是不客观的。

一般来说，在进行KNN分类使用的样本特征时，都会对特征进行归一化处理，减少由于特征本身属性和取值问题带入的先验的影响，导致特征权重的偏移。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/703099