机器学习面试002—kNN

1. 如何理解kNN中的k的取值？

Ans ：①选取较小的k值时，相当于用较小的领域中的训练实例进行预测，“学习”近似误差会减小，只有与输入实例很相近的样本才会对预测结果起作用。但是，“学习”的估计误差会增大，整体模型会变得复杂，容易过拟合。
②选取较大的k值是，相当于用较大的领域中的训练实例进行预测，可以减少学习的估计误差，但是近似误差会增大，因为离输入实例较远的样本也对预测结果起作用，容易使预测发生错误。k过大导致模型变得简单。
③在选取k上，一般取比较小的值，并采用交叉验证法进行调优。

2. 在kNN的样本搜索中，如何进行高效的匹配查找？

Ans ：①线性扫描(数据多时，效率低)
②构建数据索引——Clipping和Overlapping两种。前者划分的空间没有重叠，如k-d树；后者划分的空间相互交叠，如R树。

3. 那什么是KD树？怎么构建的？

Ans：kd树是对数据点在k维空间中划分的一种数据结构，主要用于多维空间关键数据的搜索。本质上，kd树就是一种平衡二叉树。
思想：先对计算各个维度的方差，选取最大方差的维度作为候选划分维度(方差越大，表示此维度上数据越分散)；对split维度上的值进行排序，选取中间的点为node-data；按照split维度的node-data对空间进行一次划分；对上述子空间递归以上操作，直到空间只包含一个数据点。分而治之，且循环选取坐标轴

4. 能简单介绍一下KD树的查找，以及增、删、改的实现流程吗？

Ans：先二叉查找，找到候选最近点；沿着路径进行回溯，画圆，是否父节点平面交割，以判断是否需要进入另一个平面进行查找；依次回溯，画圆，寻找最近点。
KD树更适合用于训练实例数远大于空间维数时的k近邻搜索。当维数超过20维时，KD数的检索效率急剧下降，几乎接近贪婪的线性扫描。因此出现对KD树的改进——BBF算法，M树，VP树，MVP树等高维空间索引树。