读书笔记：k近邻

宏观层面

k近邻(k nearest neighbor, knn)算是一种简单的分类和回归算法，利用元素最近的k个值来决定自身的类别或回归值。

• 分类问题，对新的样本，通过寻找离样本最近的k个样本，基于少数服从多数的原则确定当前样本的label
• 回归问题，对新样本，通过寻找离样本最近的k个样本，计算k个样本对应值的平均值作为预测值

算法基本思想和原理是什么？

knn算法主要用于解决分类问题，属于非参数模型，没有显示的学习过程，k只是超参数。该算法主要关注三个问题，

• k值的选择
  在knn算法中k是一个超参数，需要根据期望来进行不断调整.一般k值越小，意味着只寻找较少的样本值作为参考，极端情况下$k=1$，为最近邻算法，k值越小，偏差越小(只跟最近的几个值有关系)，方差越大(受波动影响越大)，模型越复杂，容易造成过拟合。预测值只跟最近的几个点有关系，如果最近点是噪声，则预测值很容易受到影响。如果k值增大，则预测结果偏差增大(预测值参考范围扩大)(增大学习的偏差)，方差越小（波动变下），泛华能力提高。在实际使用中k值通常会选取一个很小的值，通过交叉验证法确定k值。

• 距离度量方式
  度量方式是用来寻找k个最近邻的计算方式，常见的距离度量方式有公式为

  $$L_p(x_{i}^{\rightarrow},x_j^{\rightarrow})=(\sum_{l}^n|x_{i,l} - x_{i,l}|^p)^{1/p}$$

  $x$为输入样本特征向量，共有$n$个维度。

  • $p=1$, 时为曼哈顿距离(Manhattan distance)， $$L_p=\sum_l^n|x_{i,l}-x_{j,l}|$$
  • $p=2$, 欧几里得距离(Euclidean distance) $$L_p=\sum_l^n(x_{i,l}-x_{j,l})^{1/2}$$
  • $p=\infty$,为各个坐标距离的最大值 $$L_p=max|x_{i,l}-x_{j,l}|$$

• 分类决策规则
  决策规则是指在寻找到最近k个样本之后，如何利用这些样本点的信息来预测当前样本的标签或值。

  • 少数服从多数，根据k个样本中出现类别数最都的类别作为预测类别，等价于经验风险最小化，$argmax\sum{I(y_i=c_i)}$
  • 少数服从多数，也可以根据距离远近对样本权重进行加权计算
• 回归决策规则
  • 回归决策通常采用均值回归，也可以根据距离远近进行加权，距离近的权重高
  • 均值回归等价于经验风险最小化

个人理解是什么？

knn算法是最简单的分类和回归算法，没有显示的训练过程，只需要准备训练样本集，在预测时全部载入，根据预测样本进行搜索k个最近邻点，来觉得预测值。如果样本集特别大，这就存在搜索时间的问题，需要构建一个$M \times N$ 的矩阵，时间复杂度为$O(N^2)$, 当样本数据量为百万级别是，这个计算成本相当高，难易接受。因此需要对算法做一些优化。如下文所述kdtree。

微观层面：

公式详细推导过程是否领会和记忆？

• k近邻分类算法

  输入：训练集

  $$T={(x_1, y_1),(x_2, y_2),\cdots,(x_N, y_N)}$$

  其中，$x_i$为输入特征向量，维度为$d$, 类别$y = \{c_1, c_2,\cdots, c_M\}$，
  输出：给定待预测样本$x$，输出其对应类别
  步骤：
  (1) 根据给定的度量方式，在训练集$T$中，寻找k个最近点集$N_k(x)$
  (2) 在点集合中统计各个类别出现的次数，选择具有最多次数的类别$c$作为预测结果$y$返回，即

  $$y=argmax\sum_{x_i\in N_k}I(y_i=c_j)$$

• k近邻回归算法

  输入：训练集

  $$T={(x_1, y_1),(x_2, y_2),\cdots,(x_N, y_N)}$$

  其中，$x_i$为输入特征向量，维度为$d$, 类别$y = \{c_1, c_2,\cdots, c_M\}$，
  输出：给定待预测样本$x$，输出其对应类别
  步骤：
  (1) 根据给定的度量方式，在训练集$T$中，寻找k个最近点集$N_k(x)$
  (2) 在点集合中计算样本y的均值，作为预测结果$y$返回，即

  $$y=\frac{1}{k}\sum_{x_i\in N_k}y_i$$

KDTree 算法实现

k近邻算法关键点是如何对训练集进行快速k近邻搜索。为了提高搜索效率，对训练集采用特殊结构进行存储，即kdtree.

• kd tree 是一个二叉树，表示k维空间的一个划分
• kd tree的构造等价不断的用垂直于坐标轴的超平面将k维空间切分

kd tree 构造

输入：k维空间数据集$T=\{x_1, x_2, \cdots, x_N\}$,其中$x_i=(x_1^{(1)}, x_1^{(2)}, \cdots, x_1^{(k)})$
输出： kd tree
(1) 开始构造跟节点
选择$x_1^{(1)}$所在坐标轴的中位数$x_1^{(1*)}$为切分点划分超平面，生成深度为1的左、右子节点

- 左子节点对应于$x_i^{(1)} < x_1^{(1*)}$的区域
- 右子节点对应于$x_i^{(1)} > x_1^{(1*)}$的区域

(2) 重复，对于深度为j的节点，选择$x^{(l)}$为切分坐标轴， $l=j (mod k) + 1$,以该坐标中位数作为切分点，切分之后树的深度变为j+1。这里之所以不用$l=j+1$来选择坐标轴，是因为树的深度j可能超过空间维度k，这样就轮转坐标轴进行切分。
(3) 递归直到左右两个子区域没有实例存在时停止。
备注：这种按照中坐标位数为切分点，构造出来的树为平衡二叉树，但搜索时的效率未必是最优的。

kd tree 搜索

输入：已构造的kd tree， 目标点$x$
输出：$x$的最近邻点(k近邻类似)
(1) 初始化，当前最近点$x_{nst}=null $, 最近点距离$d_{nst}= +\infty$
(2) 在kd树中找到包含目标点的叶子节点，
从根节点出发，递归向下访问kdtree，执行二叉树搜索

- 目标点x当前维度的坐标小于切分点坐标，则移动到左子节点
- 目标点x当前维度的坐标大于切分点坐标，则移动到右子节点

(这里访问节点时是按照切分维度进行比较，因此需要记录下切分维度？)
在访问过程中记录下访问各节点的顺序，存放在先进后出$Queue$中，便于后面的回退。
(3) 递归向上回退，结束条件$Queue$为空
(a) 从$Queue$中弹出一个节点，记作$x_q$,计算$x \rightarrow x_q$的距离，记作$d_q$
(b) 如果$d_q < d_{nst}$, 则更新最近点和最近距离

$$x_{nst}=x_q, d_{nst}=d_q$$
(c) 如果$x_q$ 为节点(超平面上的点)，则考察以$x$为球心，$d_{nst}$为半径的超球体是否与$x_q$所在超平面相交，如果相交
- 若$Queue$中已经访问过$x_q$的左子树，则继续二叉搜索$x_q$右子树
- 若$Queue$中已经访问过$x_q$右子树，则继续二叉搜索其左子树
将搜索记录依然存放在$Queue$,循环结束时，$x_{nst}$就是最近邻点

备注：1) 训练集中的点是随机分布是，搜索时间复杂度是$O(logN)$ 2) 当训练集大小和特征空间维度接近是，搜索效率下降，接近于线性扫描

优缺点是什么？

优点：

• 模型简单，可以快速构建baseline
• 不需要显示训练过程，操作简便

缺点:

• 模型过于简单，准确率很难达到最优
• 如果训练集大，则搜索效率下降
• k值选择，和样本特征选择很关键，需要不断的验证

应用层面

算法的使用场景或任务有哪些？

knn最早是在2015年实习时接触，对商品类目预测，采用的方式是，对商品title,descrption文本进行关键词提取，筛选为特征，将每个商品表示为一个固定长度的特征向量，通过余弦距离，对新商品通过knn算法确定商品类别。
knn算法效果很高，但准确率只能到85%+，最终效果依赖数据集、特征构造，度量方式选择。

问题思考

参考文献

1. 统计机器学习方法 第二版
2. AI算法工程师手册