《机器学习高频面试题详解》1.5：K近邻（KNN）算法

大家好，我是鬼仔，今天带来《机器学习高频面试题详解》专栏的第1.5节：K近邻（KNN）算法。这是鬼仔第一次开设专栏，每篇文章鬼仔都会用心认真编写，希望能将每个知识点讲透、讲深，帮助同学们系统性地学习和掌握机器学习中的基础知识，希望大家能多多支持鬼仔的专栏～

目前这篇是试读，后续的文章需要订阅才能查看哦（每周一更/两更），专栏预计更新30+篇文章（只增不减），具体内容可以看专栏介绍，大家的支持是鬼仔更新的动力！

K近邻法（k-nearest neighbors，KNN）是一种很朴素的机器学习算法，用样本库中距离最近的K个样本来预测新数据，预测任务可以是分类，也可以是回归，区别在于最后的决策方式不同。

KNN算法有三个重要的考虑因素：K值的选择、距离度量方式和分类决策规则，这三个因素决定了KNN算法的性能。

k值的选择很重要，过大过小都不适合。（近似误差：可以理解为对现有训练集的训练误差；估计误差：可以理解为对测试集的测试误差、泛化误差。）

在实际应用中，k值一般先取一个比较小的值，然后逐渐增大，通常交叉验证法来选取最优的K值。

常用的有欧氏距离、曼哈顿距离、切比雪夫距离和闵可夫斯基距离等，定义如下：

KNN的分类决策规则前面已经讲过了，分类任务一般为投票法，回归任务一般为平均值法。

了解完KNN算法的原理后，我们可以很清楚地知道：KNN算法的实现等价于向量相似性检索问题，即给定一个查询点（可能是高纬向量），如何快速且准确地找到该点的最近邻点（通过特定的距离度量方式计算）。

具体来说，有两类解决方法：暴力实现和构建索引。

最直接暴力的方法就是线性扫描，即穷举搜索，依次计算预测样本到样本集里每个样本的距离，然后取出距离最近的前k个样本点即可。但这种方式在实际应用中是不可行的，因为现实中无论是样本数量，还是特征数量，可能都会达到几万以上，线性扫描法很低效。

除了暴力法，我们还可以通过构建索引的方法来高效查询最近邻数据。大家在学习数据结构的时候，应该都有学过AVL树（平衡二叉树），索引树就是其中一种，通过对搜索空间进行有序的层次划分，根据划分空间是否存在重叠可以进一步分为Clipping树和Overlapping树。Clipping树划分空间互相独立，没有重叠，比如kd树；Overlapping树划分空间相互有交叠，比如R树。

KNN算

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

专栏作者曾在校招期间拿到包括字节、微信和华为等多家大厂的SSP offer，该专栏主要是为了帮助同学们系统性地学习和掌握机器学习中的基础知识。专栏详细地整理了各大厂的算法岗面经，力争深入浅出地讲解重要知识点，适合人群为准备校招或者实习，且目标岗位为算法岗、数据挖掘岗或者数据分析岗的同学。