k-近邻（k-Nearest Neighbor）

一. k-NN算法【有监督】

1. 概念

(1) 原理：K近邻是一种多类划分的模型，基于实例，不需要训练。当一个样本与数据集中的k个样本最相近时， 若这k个样本中的大多数属于某一个类别， 则该样本也应该属于这个类别。

(2) 两类问题

在分类问题中，KNN用来预测种类。使用“投票法”，选择这k个样本中出现最多的类别来作为测试样本的类别。

在回归问题中，KNN用来预测一个值。使用“平均法”，将k个样本的实值输出的平均值作为测试样本的输出。

2. 算法流程

(1) 输入：载入数据，并初始化k值

(2) 计算测试数据到每一个训练数据的距离

(3) 按距离排序，取 TOP k 个最近的训练数据

(4) 取频率最高的类作为测试数据的预测类别

3. 算法的泛化误差

给定测试样本x，设其最近邻样本为z，最近邻（1-NN）出错率就是x与z类别标记不同的概率

即，1NN的泛化错误率≤2倍的贝叶斯最优分类器错误率

c*=argmax P(c*|x)    为贝叶斯最优分类器的结果

二. 距离度量

1. 欧氏距离（Euclidean Distance）

两点间的最短距离，它将样本的不同属性（即各指标或各变量量纲）之间的差别等同看待，这一点有时不能满足实际要求。

                                                

2. 曼哈顿距离（Manhattan Distance）

也叫L1距离，指在曼哈顿从一个十字路口开车到另外一个十字路口的实际距离。依赖座标系统的转度，当坐标轴变动时，点间的距离就会不同。

                                           

绿色为欧氏距离，其余为曼哈顿距离

3. 切比雪夫距离（Chebyshev Distance）

又叫“棋盘距离”，“轴上最长距离”，指“王”在棋盘上移动的距离（可以朝任意方向走）

                                                       

4.闵可夫斯基距离（Minkowski Distance）

不是一种距离，而是距离的定义。

定义两点：   以及  

则                    （p是一个变参数）

(1) p=1时，曼哈顿距离（对应L1-范数）

(2) p=2时，欧氏距离（对应L2-范数）

(3) p→∞ 时，切比雪夫距离

5. 标准化欧氏距离（Standardized Euclidean distance）

(1) 闵氏距离的缺点：

① 将各个分量的量纲(scale)，也就是“单位”当作相同的看待了

② 没有考虑各个分量的分布（期望、方差等）可能是不同的。

③ 各个维度必须是互相独立的，也就是“正交”的

(2) 改进：标准化欧氏距离

① 设样本集X的均值为μ，标准差为σ

    标准化：            （数学期望为0，方差为1）

②加权欧式距离：    （将方差的倒数看成是一个权重）

三. k值选取

1. 随着k值增大，分类界面更加平滑

(1) k值小：学习的近似误差会减小，模型复杂，对近邻的实例点分类敏感，容易过拟合。

(2) k值大，学习的估计误差会减小，模型简单，对输入实例预测不准确

2. 误差

(1) 近似误差：关注训练集，如果k值小了会出现过拟合的现象，对现有的训练集能有很好的预测，但是对未知的测试样本将会出现较大偏差的预测。模型本身不是最接近最佳模型。

(2) 估计误差：关注测试集，估计误差小了说明对未知数据的预测能力好。模型本身最接近最佳模型。但K取太大并不能提高正确率，而且算法效率会低。

(3) 在应用中，K值一般取一个比较小的数值，通常采用交叉验证法来选取最优的K值。

四. kd树（K-dimension tree）

1. kNN的缺点

K近邻在高维情况下时，待预测样本需要与依次与所有样本求距离，则对于n个m维的样本，复杂度为O(mn)，成为测试阶段的严重瓶颈。

2. 使用kd树优化

(1) 定义：是一种以二叉树的形式存储数据的方法，表示对k维空间的一个划分。用于高维空间中的搜索，比如范围搜索和最近邻搜索。

(2) 原理：不断用垂直于坐标轴的超平面将K维空间划分为两部分，分别记作左子树(<)、右子树(≥)，构成一系列的K维超矩形区域。

(3) 优势：kd树的每个结点对应于一个k维超矩形区域。 利用kd树可以省去对大部分数据点的搜索， 从而减少搜索的计算量。

(4) 构造方法

① 建立根节点； 

② 选取方差最大的特征作为分割特征； （选择较为分散的一维）

③ 选择该特征的中位数作为分割点； （交替x轴、y轴）

④ 将数据集中，该特征小于中位数的给左子树，大于中位数的传递给根节点的右子树； 

⑤ 重复②-④，直到所有数据都被建立到KD Tree的节点上为止。

(5) 搜索方法

① 利用kd树，从根节点开始向下访问，根据目标★在分割特征中小于(大于)当前节点，选择向左(向右)移动

② 递归：当到达叶节点，就将其保存为 “当前最近点”❶ 

③ 回溯，从叶节点再返回到根节点，若当前节点更接近，那么它就更新为 “当前最近点” ❷

④ 检查：作为父节点❷是否有另一子树更近，若有则更新为 “当前最近点” ❸

（以❷到★的距离为半径画超球体，若与另一超平面空间相交，寻找该空间是否有更近点❸）

⑤ 回溯：以❸到★的距离为半径画超球体，若与节点❸的父节点❷被分割的超平面相交，说明当前节点的兄弟节点所在子树有可能含更近的点，则需要对这个兄弟节点递归执行①-④。若不相交，则无需更新，继续回溯。

⑥ 结束：当回退到根节点时，停止搜索。

参考：

[1] 机器学习之KNN（k近邻）算法详解——CSDN

[2] 样本相似性度量_描绘自己的王国……—CSDN

[3] KD Tree的原理及Python实现 - 李小文的文章 - 知乎