关于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$和切分面的距离看是否需要剪掉右子树,提升遍历效率)