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?0），算法的查找效率很高，然而当Kd-tree用于对高维数据（例如：K?00）进行索引和查找时，就面临着维数灾难（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树种距离查找点最近的点以及最近的距离
1. 若kd树为空，则设定两者距离为无穷大，返回；如果kd树非空，则将kd树的根节点加入到优先级队列中?
2. 从优先级队列中出队当前优先级最大的结点，计算当前的该点到查找点的距离是否比最近邻距离小，如果是则更新最近邻点和最近邻距离。如果查找点在切分维坐标小于当前点的切分维坐标，则把他的右孩子加入到队列中，同时检索它的左孩子，否则就把他的左孩子加入到队列中，同时检索它的右孩子。这样一直重复检索，并加入队列，直到检索到叶子节点。然后在从优先级队列中出队优先级最大的结点?
3. 重复1?中的操作，直到优先级队列为空，或者超出规定的时间，返回当前的最近邻结点和距离?

参?