1. KNN

KNN

前言：之所以会有这个文集是因为快要秋招了，想要准备一下，所有的内容都以面试问答的形式体现，以前有人做过类似的内容：深度学习500问，但是里面的内容感觉更适合作为平时学习的参考。

本文集所有的文章与前人工作最大的区别是：有的回答会显得有些口语化，因为是我自己一边嘴里念念有词，一边记下来的（想象你脑海里有两个小人），实际面试的时候，不可能机械的去背诵，那样会感觉怪怪的，但是所有的回答又有一定的内在逻辑。

我在自己有限的几次面试中，发现，对于面试官的很多问题，我知道答案，但是不知道该怎么回答，该从何讲起，没有条例，逻辑不清晰，原因一方面是自己基础不扎实，一方面是没有针对性的准备，所以我想通过这个文集，解决这个问题，换句话说，这个文集里的文章可能只适合我自己，各位看官请仔细甄别。

1. 请详述/介绍/说一下KNN算法？

介绍KNN时至少要答出以下四点：

1. knn的原理，2.k值的选择，3.距离度量，4. 决策规则。
   后三者又称为KNN的三要素

答：KNN是一种基本的分类与回归方法

1. 处理分类问题时，给定一个训练数据集，对新输入的实例，在训练数据集中找到和它最邻近的K个实例，这K个实例的多数属于某个类，就把这个新的实例分为这个类，也就是多数表决投票；如果把最邻近的K个实例的标签均值作为预测值，就可以处理回归问题了。（原理解释完了）

2. 这里面K值的选择会对KNN算法的训练结果产生重要影响，

   • 如果K值比较小，那就相当于用比较小的邻域中的训练样本进行预测，"学习"的偏差减小（优点），只有和输入样本比较近的训练样本才会对预测起作用。缺点是会增大"学习"的方差（波动），预测结果会对近邻的样本点非常敏感。如果这时候近邻的训练样本点刚好是噪声，那预测就会出错。也就是说K 值的减小意味着模型整体变复杂，容易发生过拟合。
   • 反过来如果K值比较大，模型变简单，方差减小，偏差增大，和新样本较远的训练样本也会对预测起作用，会使预测结果偏离预期的结果。
     实际中通常采用交叉验证法来选取最优K值

3. 评判两个样本远近的方法是距离度量，这是特征空间中两个样本点相似程度的反映。K近邻模型（的特征空间一般是N 维实数向量空间）一般使用欧式距离(也就是中学学的空间两个点之间的距离)，（另外还有曼哈顿距离，不用平方，不用开方，直接对应坐标做差，然后取绝对值，再累加做和）。距离度量不同，所确定的最近邻点不同。

4. 决策规则有分类决策规则和回归决策规则两种，

   • 分类决策通常采用多数表决， 回归决策通常采用均值回归，两个都可以基于距离的远近进行加权投票：距离越近的样本权重越大。

注意：如果这是面试官问你的第一个问题，那他下面一定会基于你上面的回答继续提问，所以接下来可能会问到：

1.1 什么是过拟合，什么是欠拟合，该怎么解决呢

这个问题要拆成四个问题去回答：解释过拟合，解释怎么解决过拟合；解释欠拟合，解释怎么解决欠拟合

1. 选择的模型包含的参数过多，模型在训练数据上表现很好，但是在测试数据上表现很差，这种情况叫过拟合（过拟合高 方差）；

2. 过拟合无法避免，只能缓解，可以通过

   • 正则化
   • 数据集增强：通过人工规则产生虚假数据来创造更多的训练数据。
   • 噪声注入：包括输入噪声注入、输出噪声注入、权重噪声注入。将噪声分别注入到输入/输出/权重参数中。
   • 早停（early stop）：当验证集上的误差没有进一步改善时，算法提前终止。
     最好的解决方案是使用更多训练数据。这样得到的模型自然能够更好地泛化。如无法采用这种解决方案，则次优解决方案是使用正则化等技术

3. 与过拟合相对的是欠拟合，模型在训练数据上表现就很差（欠拟合高偏差）。出现这种情况的原因有很多：模型不够强大、过于正则化，或者根本没有训练足够长的时间。

4. 解决欠拟合的方法有：
   - 增加新特征，可以考虑加入进特征组合、高次特征;
   - 更换模型;
   - 选择较小的正则项参数
   - 增加训练时间

1.2 交叉验证是怎么回事儿？/通过交叉验证怎么选择K值

这个问题感觉图文并茂的方式更能讲清楚；选择K值其实就是选择不同的模型，所以交叉验证是常用的模型选择方法之一，另一种是正则化，后面再补充

交叉验证
基本想法是重复的使用数据。一般将数据集随机切分成三个部分：训练集，用来训练模型；验证集，用来选择模型，测试集，用于对最终学习方法的评估。一般使用K-折交叉验证(此K非彼K)，方法是：将训练数据随机的切分成K个不同的子集，其中K-1个做训练集，余下的一个做验证集；把训练数据划分成K个子集是随机的，所以可以重复P次，把P次交叉验证的误差均值作为作为最终的误差估计。（上图中P=5，P也可以等于其他数）

1.3 什么是多数表决规则

这个问题我不太确定是不是一定要写出公式来，但是就是字面意思：在投票的时候，少数服从多数。

参考：

1. 统计学习方法-李航（第二版)
2. 探索过拟合和欠拟合
3. 机器学习防止欠拟合、过拟合方法
4. KNN