k 近邻算法（K-Nearest Neighbors，简称 KNN）是一种常用的监督学习算法，可以用于分类和回归问题。在 OpenCV 中，KNN 算法的函数为 cv.ml.KNearest_create()。
距离度量的选择
k 近邻算法中需要按照距离递增次序排序，通常选取以下类型的距离：
样本特征表示为： $$x_{i}=\left(x_{i}^{(1)},x_{i}^{(2)},\cdots,x_{i}^{(n)}\right)^{\mathrm{T}}$$
L∞距离： $$L_{\infty}(x_{i},x_{j})=\max_{l}\mid x_{i}^{(l)}-x_{j}^{(l)}\mid$$
曼哈顿距离： $$L_{1}(x_{i},x_{j})=\sum_{l=1}^{n}|x_{i}^{(l)}-x_{j}^{(l)}|$$
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_{2}(x_{i},x_{j})=\left(\sum_{l=1}^{n}|x_{i}^{(l)}-x_{j}^{(l)}|^{2}\right)^{\frac{1}{2}}$$
数据维度归一化
假设所使用的样本特征为 ${(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 个，多数类别就是我们最终的结果，计算结果如下： $$AF=\sqrt{(167-179)^2+(43-42)^2}=\sqrt{145}$$ $$BF=\sqrt{(167-178)^2+(43-43)^2}=\sqrt{121}$$ $$CF=\sqrt{(167-165)^2+(43-36)^2}=\sqrt{53}$$ $$DF=\sqrt{(167-177)^2+(43-42)^2}=\sqrt{101}$$ $$EF=\sqrt{(167-160)^2+(43-35)^2}=\sqrt{103}$$
可以得到，最近的前三个分别是 C,D,E 三个样本，那么由 C,E 为女性，D 为男性，得到预测结果为女性。
女性脚 43 码的可能性远远小于男性脚 43 码的可能性，算法却错误地预测 F 为女性，这不是算法的问题，这是各个特征量纲不同的问题，这里量纲直接导致身高的权重远大于脚码的权重，进而导致预测错误。所以在计算前应该让每个特征同等重要，这就是归一化的必要性。
