14. 机器学习——kNN

机器学习面试题汇总与解析——kNN

本章讲解知识点

• 1. 什么是 kNN
• 2. k 值选择
• 3. kNN 的优缺点

• 本专栏适合于Python已经入门的学生或人士，有一定的编程基础。

• 本专栏适合于算法工程师、机器学习、图像处理求职的学生或人士。

• 本专栏针对面试题答案进行了优化，尽量做到好记、言简意赅。这才是一份面试题总结的正确打开方式。这样才方便背诵

• 如专栏内容有错漏，欢迎在评论区指出或私聊我更改，一起学习，共同进步。

• 相信大家都有着高尚的灵魂，请尊重我的知识产权，未经允许严禁各类机构和个人转载、传阅本专栏的内容。

  
  

• 关于机器学习算法书籍，我强烈推荐一本《百面机器学习算法工程师带你面试》，这个就很类似面经，还有讲解，写得比较好。

• 关于深度学习算法书籍，我强烈推荐一本《解析神经网络——深度学习实践手册》，简称 CNN book，通俗易懂。

• B站机器学习视频：https://space.bilibili.com/10781175/channel/detail?cid=133301

1. 什么是 kNN

在学习机器学习的时候，接触的第一个算法大都是 kNN。

简言之，kNN 算法计算不同特征值之间的距离对样本进行分类。现在有这么一组数据。

上面 6 个样本（电影）分别给出其特征（打斗镜头、拥抱镜头）和标签（电影类型）信息，现在给定一个新的样本，我们想知道这部电影的类型。由于是 2 维数据，我们可以用平面直角坐标系表示。

绿色的点是未知的，红色的黄色的点是已知的。kNN 要做的就是计算未知的点到所有已知点的距离，根据距离进行排序。

排序后的数据如下，

我们在 kNN 算法中经常会听到说当 k=3 时、当 k=5 时...这里的 k 指的就是样本数。在这个例子中，当 k=3 时，前三个样本出现最多的电影类型是动作片，因此《这个杀手不太冷》样本也应该归为动作片。同样的，当 k=5 时，前 5 个样本出现最多的电影类型也是动作片 ( $\frac{3}{5}\backslash frac\{3\}\{5\}$ > $\frac{2}{5}\backslash frac\{2\}\{5\}$），因此样本也属于动作片。

上面提到的是 2 维数据，但是我们现实中处理的样本可能有 3 个甚至更多特征，我们无法用视觉来抽象这些特征，但是计算方法还是一样的，只不过根号里做差的数变多了而已。

2. k 值选择

我们知道 k 的取值比较重要，那么该如何确定 k 取多少值好呢？答案是通过交叉验证（将样本数据按照一定比例，拆分出训练用的数据和验证用的数据，比如 6：4 拆分出部分训练数据和验证数据），从选取一个较小的 k 值开始，不断增加 k 的值，然后计算验证集合的方差，最终找到一个比较合适的 k 值。

通过交叉验证计算方差后你大致会得到下面这样的图：

这个图其实很好理解，当你增大 k 的时候，一般错误率会先降低，因为有周围更多的样本可以借鉴了，分类效果会变好。但注意，和 K-means 不一样，当 k 值更大的时候，错误率会更高。这也很好理解，比如说你一共就 35 个样本，当你 k 增大到 30 的时候，kNN 基本上就没意义了。

所以选择 k 点的时候可以选择一个较大的临界 k 点，当它继续增大或减小的时候，错误率都会上升，比如图中的 k=10。

3. kNN 的优缺点

k 最近邻（k-Nearest Neighbors，kNN）是一种常用的分类和回归算法，它根据样本之间的距离来进行预测或分类。kNN 的优缺点如下：

优点：

• 简单直观：kNN 算法简单易懂，容易实现和理解。
• 无需训练：kNN 是一种基于实例的学习方法，不需要进行显式的训练过程，只需要存储训练样本即可。
• 对异常值不敏感：kNN 算法对于数据中的异常值不敏感，因为预测时是基于邻居样本的投票或平均值来决定分类或回归结果。

缺点：

• 计算复杂度高：kNN 算法需要计算样本之间的距离，随着样本数量增加，计算复杂度也会增加，尤其是在高维数据集上。
• 内存消耗大：kNN 需要存储训练样本的特征向量，对于大规模数据集，会占用较大的内存空间。
• 预测速度慢：由于需要计算样本之间的距离，预测时的速度相对较慢。
• 需要确定 k 值：kNN 算法需要事先确定 k 值，选择不合适的 k 值可能会影响预测结果。
• 数据不平衡问题：如果训练数据中某个类别的样本数远远多于其他类别，kNN 算法在预测时可能会有偏差。
• 对数据纲量敏感，所以数据要先归一化

面试题

1. kNN 介绍一下⭐⭐⭐⭐

k 最近邻（k-Nearest Neighbors，kNN）是一种基于实例的学习算法，用于分类和回归问题。该算法基于样本之间的相似性进行预测或分类。kNN 算法的原理很简单：对于给定的测试样本，通过计算它与训练集中所有样本的距离，并选取距离最近的 k 个样本，然后根据这 k 个样本的类别（对于分类问题）或平均值（对于回归问题）来预测测试样本的类别或数值。

kNN 算法的主要步骤如下：

1. 计算距离：对于给定的测试样本，计算它与训练集中每个样本之间的距离。常用的距离度量包括欧氏距离、曼哈顿距离。
2. 选择 k 个邻居：根据距离选择与测试样本距离最近的 k 个训练样本。
3. 进行投票或计算平均值：对于分类问题，根据 k 个邻居的类别进行投票，选取票数最多的类别作为测试样本的预测类别；对于回归问题，计算 k 个邻居的数值的平均值作为测试样本的预测数值。
4. 输出预测结果：根据投票结果或平均值，得到测试样本的预测结果。

2. kNN 优缺点⭐⭐⭐⭐

优点：

• 简单直观：kNN 算法简单易懂，容易实现和理解。
• 无需训练：kNN 是一种基于实例的学习方法，不需要进行显式的训练过程，只需要存储训练样本即可。
• 对异常值不敏感：kNN 算法对于数据中的异常值不敏感，因为预测时是基于邻居样本的投票或平均值来决定分类或回归结果。

缺点：

• 计算复杂度高：kNN 算法需要计算样本之间的距离，随着样本数量增加，计算复杂度也会增加，尤其是在高维数据集上。
• 内存消耗大：kNN 需要存储训练样本的特征向量，对于大规模数据集，会占用较大的内存空间。
• 预测速度慢：由于需要计算样本之间的距离，预测时的速度相对较慢。
• 需要确定 k 值：kNN 算法需要事先确定 k 值，选择不合适的 k 值可能会影响预测结果。
• 数据不平衡问题：如果训练数据中某个类别的样本数远远多于其他类别，kNN 算法在预测时可能会有偏差。
• 对数据纲量敏感，所以数据要先归一化

3. kNN 的 k 值怎么选⭐⭐⭐⭐

下面介绍几种常用的选择 k 值的方法：

• 经验法则：根据经验规则选择 k 值。一般来说，较小的 k 值会使模型更具有灵敏性，但容易受到噪声和异常值的干扰；较大的 k 值可以平滑预测结果，但可能导致不同类别之间的边界模糊。常用的经验法则是选择一个较小的 k 值（如 3 或 5），然后通过交叉验证等方法进行调优。

• 考虑类别平衡：如果数据集中的类别不平衡（某些类别的样本数量远远大于其他类别），则选择较小的 k 值可能更合适，以避免预测结果偏向数量较多的类别。

• 交叉验证：可以使用交叉验证来评估不同 k 值下模型的性能，并选择性能最好的 k 值。通过将数据集划分为训练集和验证集，尝试不同的 k 值并计算模型在验证集上的性能指标（如准确率、F1值等），选择表现最好的 k 值。

4. kNN 数据需要归一化吗？⭐⭐⭐⭐

以下是归一化的一些原因：

1. 尺度统一：kNN 算法使用距离度量来计算最近邻，如果特征之间的尺度不一致，即量纲，尺度较大的特征可能会主导