KNN面试题
1.简述一下KNN算法的原理
KNN算法利用训练数据集对特征向量空间进行划分。KNN算法的核心思想是在一个含未知样本的空间,可以根据样本最近的k个样本的数据类型来确定未知样本的数据类型。
该算法涉及的3个主要因素是:k值选择,距离度量,分类决策。
2. 如何理解kNN中的k的取值?
在应用中,k值一般取比较小的值,并采用交叉验证法进行调优。
3. 在kNN的样本搜索中,如何进行高效的匹配查找?
线性扫描(数据多时,效率低)
构建数据索引——Clipping和Overlapping两种。前者划分的空间没有重叠,如k-d树;后者划分的空间相互交叠,如R树。(对R树了解很少,可以之后再去了解)
4. KNN算法有哪些优点和缺点?
-
优点:
算法思想较简单,既可以做分类也可以做回归;可以用于非线性分类/回归;训练时间复杂度为O(n);准确率高,对数据没有假设,对离群点不敏感。
-
缺点:
计算量大;存在类别不平衡问题;需要大量的内存,空间复杂度高。
5. 不平衡的样本可以给KNN的预测结果造成哪些问题,有没有什么好的解决方式?
输入实例的K邻近点中,大数量类别的点会比较多,但其实可能都离实例较远,这样会影响最后的分类。 可以使用权值来改进,距实例较近的点赋予较高的权值,较远的赋予较低的权值。
6. 为了解决KNN算法计算量过大的问题,可以使用分组的方式进行计算,简述一下该方式的原理。
先将样本按距离分解成组,获得质心,然后计算未知样本到各质心的距离,选出距离最近的一组或几组,再在这些组内引用KNN。 本质上就是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本,该方法比较适用于样本容量比较大时的情况。
##7. K-Means与KNN有什么区别
-
KNN
- KNN是分类算法
- 监督学习
- 喂给它的数据集是带label的数据,已经是完全正确的数据
- 没有明显的前期训练过程,属于memory-based learning
- K的含义:来了一个样本x,要给它分类,即求出它的y,就从数据集中,在x附近找离它最近的K个数据点,这K个数据点,类别c占的个数最多,就把x的label设为c
-
K-Means
- 1.K-Means是聚类算法
- 2.非监督学习
- 3.喂给它的数据集是无label的数据,是杂乱无章的,经过聚类后才变得有点顺序,先无序,后有序
- 有明显的前期训练过程
- K的含义:K是人工固定好的数字,假设数据集合可以分为K个簇,由于是依靠人工定好,需要一点先验知识
-
相似点
- 都包含这样的过程,给定一个点,在数据集中找离它最近的点。即二者都用到了NN(Nears Neighbor)算法,一般用KD树来实现NN。
##9. KD树改进
-
Kd-tree在维度较小时(例如:K≤30),算法的查找效率很高,然而当Kd-tree用于对高维数据(例如:K≥100)进行索引和查找时,就面临着维数灾难(curse of dimension)问题,查找效率会随着维度的增加而迅速下降。通常,实际应用中,我们常常处理的数据都具有高维的特点,例如在图像检索和识别中,每张图像通常用一个几百维的向量来表示,每个特征点的局部特征用一个高维向量来表征(例如:128维的SIFT特征)。因此,为了能够让Kd-tree满足对高维数据的索引,Jeffrey S. Beis和David G. Lowe提出了一种改进算法——Kd-tree with BBF(Best Bin First),该算法能够实现近似K近邻的快速搜索,在保证一定查找精度的前提下使得查找速度较快。
-
在介绍BBF算法前,我们先来看一下原始Kd-tree是为什么在低维空间中有效而到了高维空间后查找效率就会下降。在原始kd-tree的最近邻查找算法中(第一节中介绍的算法),为了能够找到查询点Q在数据集合中的最近邻点,有一个重要的操作步骤:回溯,该步骤是在未被访问过的且与Q的超球面相交的子树分支中查找可能存在的最近邻点。随着维度K的增大,与Q的超球面相交的超矩形(子树分支所在的区域)就会增加,这就意味着需要回溯判断的树分支就会更多,从而算法的查找效率便会下降很大。
-
从上述标准的kd树查询过程可以看出其搜索过程中的“回溯”是由“查询路径”决定的,并没有考虑查询路径上一些数据点本身的一些性质。一个简单的改进思路就是将“查询路径”上的结点进行排序,如按各自分割超平面(也称bin)与查询点的距离排序,也就是说,回溯检查总是从优先级最高(Best Bin)的树结点开始。
bbf的算法:
输入:kd树,查找点x.
输出:kd树种距离查找点最近的点以及最近的距离-
若kd树为空,则设定两者距离为无穷大,返回;如果kd树非空,则将kd树的根节点加入到优先级队列中;
-
从优先级队列中出队当前优先级最大的结点,计算当前的该点到查找点的距离是否比最近邻距离小,如果是则更新最近邻点和最近邻距离。如果查找点在切分维坐标小于当前点的切分维坐标,则把他的右孩子加入到队列中,同时检索它的左孩子,否则就把他的左孩子加入到队列中,同时检索它的右孩子。这样一直重复检索,并加入队列,直到检索到叶子节点。然后在从优先级队列中出队优先级最大的结点;
-
重复1和1中的操作,直到优先级队列为空,或者超出规定的时间,返回当前的最近邻结点和距离。
-