关于KNN的问题整理。

KNN简介？

k近邻算法(k-nearest neighbor)是一种有监督的分类算法，是通过测量不同特征向量之间的距离来进行分类的。它的思想是如果一个样本在特征空间中最邻近的k个样本大多数属于某个类别，则该样本也属于这个类别。算法过程为

  • 计算测试样本特征向量和其他每个样本的特征向量之间的距离；
  • 对距离进行递增排序，选择距离最小的k个点；
  • 确定这k个点所在类别出现频率；
  • 返回这k个点出现频率最高的类别作为当前测试样本的预测类别。

KNN数据需要归一化么？

数据是否归一化取决于模型是关注变量的取值还是变量之间的分布。KNN中有计算两个特征向量的距离操作，因此需要进行数据归一化，来削弱不同特征之间数量级的差异性。

KNN优缺点？

  • 优点：
    • 思想简单，既可以做分类，也可以做回归；
    • 可用于非线性的分类；
    • 适用于样本容量比较大的类域进行分类。
  • 缺点：
    • 当特征空间中样本数量和样本特征维度比较大时，计算量大，分类速度慢；
    • k值难以确定，一般多次交叉验证实验调整k值；
    • 对不均衡的样本集敏感，当少数类的样本进行测试时，由于k近邻的样本属于多数类而导致分类错误。

KNN的k值怎么选？

一般通过多次实验以交叉验证的方式给k值打分，寻找分数最高的k值。

KNN中k值的设置对模型有什么影响？

  • 如果k值设置过小，会导致结果对近邻的样本点非常敏感，此时如果有噪声(样本打错标签)的影响，会导致预测错误，过小的k值会使得模型变复杂，容易过拟合到噪声；
  • 如果k值设置过大，会导致某些其他类别的样本点也贡献了作用，会导致预测错误，过大的k值会使得模型变简单，容易欠拟合，模式倾向于输出类别数多的类；
  • 如果k值设置等于样本数，此时无论测试输入是什么，模型只会输出类别数最多的类。

KNN三要素？

  • 距离度量：可以使用欧氏距离或者曼哈顿距离($L_p$距离的特例)进行度量；
  • k值的选择：一般通过多次交叉验证选择最优的k值；
  • 分类决策规则：常用的是多数表决的规则。

在K-means或KNN中，用欧氏距离和曼哈顿距离度量有什么区别？

曼哈顿距离和欧式距离的用途不一样。
对于$(x_1, y_1), (x_2, y_2)$，

欧式距离定义为
$$d(x,y):=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2}$$

曼哈顿距离定义为
$$d(x,y):=|x_1-y_1|+|x_2-y_2|$$

曼哈顿距离是在直接坐标系中两点所形成的线段对坐标轴的投影。曼哈顿距离只能计算水平或垂直的距离，有维度限制。而欧式距离可用于任何空间距离的计算。一般来说，数据点会存在于任何空间中，用欧氏距离更好点。

kd树的结构？kd树的构建？KNN如何使用kd树？

关于kd树的详解。

  • kd树的结构是一个二叉树的结构，它的每一个节点记录【特征坐标，切分轴，指向左孩子的指针，指向右孩子的指针】，特征坐标是在线性空间$\R^n$中的一个点$(x_1,x_2,…,x_n)$，切分轴是指沿着第$r$轴$(1≤r≤n)$的一次切分，左右孩子仍是kd树，并且左孩子的特征点在特征空间上在根节点的左边，右孩子的特征点在根节点的右边。

  • kd树的构建，给定数据集$S\subseteq \R^n$和切分轴$r$，使用递归算法构建一个基于数据集的二叉树；

    • 如果集合$S$中的元素个数大于1，那么将所有点按第$r$个坐标进行排序，然后选出中位元素作为当前点的特征坐标(即切分为止)，并记录切分轴$r$；
    • 再对中位元素之前的子集合$S_L$和之后的子集合$S_R$，更新$r$轴($r \leftarrow(r+1)\mod n$)，以第$r$轴为切分轴递归创建kd子树；
    • 如果集合$S$中的元素个数等于1，那么当前特征点就是该处节点的特征数据。

  • kd树的使用。任务是寻找距离测试点$p$最近的$k$个样本，记录在长度为$k$的列表$L$中。

    • 从根节点出发，根据$p$在第$r$轴的坐标值与当前特征节点的相应坐标值的大小比较，小于则会往左枝向下遍历，否则往右枝向下遍历；
    • 到达叶节点后，如果$L$不满，把当前叶节点的特征坐标加入$L$，如果满了，计算当前叶节点和$p$的欧氏距离，同时找到$L$中的距离$p$最长的节点，如果当前距离小于最长距离，则当前节点替换最长距离节点，同时标记为已访问。
    • 从叶节点向上回溯访问未访问过的节点，如果$L$不满，把当前节点的特征坐标加入$L$，如果满了，计算距离看是否进行节点的替换。(可通过计算$p$和切分面的距离看是否需要剪掉右子树，提升遍历效率)