欧式距离： $L_{2}(x_{i},x_{j})=\left(\sum_{l=1}^{n}|x_{i}^{(l)}-x_{j}^{(l)}|^{2}\right)^{\frac{1}{2}}$
Lp距离： $L_{p}(x_{i},x_{j})=\left(\sum_{l=1}^{n}\mid x_{i}^{(l)}-x_{j}^{(l)}\mid^{p}\right)^{\frac{1}{p}}$
曼哈顿距离： $L_{1}(x_{i},x_{j})=\sum_{l=1}^{n}|x_{i}^{(l)}-x_{j}^{(l)}|$
L $\infty$ 距离： $L_{\infty}(x_{i},x_{j})=\max_{l}\mid x_{i}^{(l)}-x_{j}^{(l)}\mid$

数据维度归一化

假设所使用的样本特征为 $\{(x_{i1},x_{i2},\ldots,x_{in})\}_{i=1}^m$ ，取每一轴上的最大值减最小值

$M_j=\max_{i=1,\ldots,m}x_{ij}-\min_{i=1,\ldots,m}x_{ij}$

随后在计算距离时将每一个坐标轴除以相应的 $M_j$ 以进行归一化

$d((y_1,\ldots,y_n),(z_1,\ldots,z_n))=\sqrt{\sum_{j=1}^n\left(\frac{y_j}{M_j}-\frac{z_j}{M_j}\right)^2}$

数据维度归一化的必要性

当使用多维度数据计算距离时，数据维度的归一化是及其必要的。

例如，以身高(cm)与脚码（尺码）大小作为特征值，判断男性或者女性。5个训练样本分布如下：

A [(179,42),男]，B [(178,43),男]，C [(165,36)女]，D [(177,42),男]，E [(160,35),女]

可以发现，第一维身高特征是第二维脚码特征的4倍左右，在计算距离度量的时候，如果不进行数据维度的归一化，算法就会偏向于第一维特征，这会造成俩个特征并不是等价重要的，最终可能会导致距离计算错误，从而导致预测错误。

以测试样本 F[(167,43),男]为例，取k=3，分别算出F离训练样本的欧式距离，然后选取最近的3个，多数类别就是我们最终的结果，计算结果如下：

$\begin{gathered} AF=\sqrt{\left(167-179\right)^2+\left(43-42\right)^2}=\sqrt{145} \\ BF=\sqrt{\left(167-178\right)^2+\left(43-43\right)^2}=\sqrt{121} \\ CF=\sqrt{\left(167-165\right)^2+\left(43-36\right)^2}=\sqrt{53} \\ DF=\sqrt{\left(167-177\right)^2+\left(43-42\right)^2}=\sqrt{101} \\ EF=\sqrt{\left(167-160\right)^2+\left(43-35\right)^2}=\sqrt{103} \end{gathered}$

可以得到，最近的前三个分别是C,D,E三个样本，那么由C,E为女性，D为男性，得到预测结果为女性。

女性脚43码的可能性远远小于男性脚43码的可能性，算法却错误地预测F为女性，这不是算法的问题，这是各个特征量纲不同的问题，这里量纲直接导致身高的权重远大于脚码的权重，进而导致预测错误。所以在计算前应该让每个特征同等重要，这就是归一化的必要性。

k值的选择

选择较小的k值
- 噪声敏感
- K值的减小意味着着整体模型会变得复杂，容易发生过拟合情况
- 学习的近似误差(approximation error)会减小，但学习的估计误差(estimation error)会增大

过拟合：在训练集上准确率非常高，而在测试集上准确率低

选择较大的k值
- K值的增大意味着整体的模型会变得简单
- 学习的估计误差(estimation error)会减小，但学习的近似误差(approximation error)会增大

合理的选择方式：一般先选取一个较小的k值，然后采取交叉验证法来选取最优的k值，即实验调参，类似于神经网络通过调整超参数来得到一个较好的层数。

k近邻算法优缺点

优点
- 精度高
- 对异常值不敏感
- 无数据输入假定
缺点
- 计算复杂度高
- 空间复杂度高

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