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树种距离查找点最近的点以及最近的距离
  1. 若kd树为空，则设定两者距离为无穷大，返回；如果kd树非空，则将kd树的根节点加入到优先级队列中；
  2. 从优先级队列中出队当前优先级最大的结点，计算当前的该点到查找点的距离是否比最近邻距离小，如果是则更新最近邻点和最近邻距离。如果查找点在切分维坐标小于当前点的切分维坐标，则把他的右孩子加入到队列中，同时检索它的左孩子，否则就把他的左孩子加入到队列中，同时检索它的右孩子。这样一直重复检索，并加入队列，直到检索到叶子节点。然后在从优先级队列中出队优先级最大的结点；
  3. 重复1和1中的操作，直到优先级队列为空，或者超出规定的时间，返回当前的最近邻结点和距离。

参考

1. https://blog.csdn.net/weixin_44915167/article/details/89315734
2. https://www.cnblogs.com/nucdy/p/6349172.html
3. https://blog.csdn.net/v_july_v/article/details/8203674
4. https://blog.csdn.net/junshen1314/article/details/51121582
5. https://blog.csdn.net/lhanchao/article/details/52535694
6. https://blog.csdn.net/fool_ran/article/details/85246432
7. 李航 统计学习方法