前言
此为本人学习《百面机器学习——算法工程师带你去面试》的学习笔记
经典算法
1、支持向量机
1、在空间上线性可分的两类点，分别向SVM超平面上做投影，这些点在超平面上的投影仍然是线性可分的吗？
答：是，对于任意线性可分的两组点，他们在SVM分类超平面上的投影都是线性不可分的。
2、是否存在一组参数使SVM训练误差为0？
答：是，一个使用高斯核()训练的SVM中，若训练集中不存在两个点在同一个位置，则存在一组参数{
,...,
,b}以及参数
使得该SVM的训练误差为0.
3、训练误差为0的SVM分类器一定存在吗？
答：一定存在
4、加入松弛变量的SVM的训练误差可以为0吗？
答：是，并不一定能得到训练误差为0的模型。如果使用SMO算大来训练一个参加松弛变量的SVM模型，则我们的优化目标改变了，并不再是是训练误差最小。考虑到松弛变量的SVM模型优化的目标函数所包含的两项：和
。当我们的参数C选取较小值时，后面的正则项将占据优化的较大比重。这样，一个该有训练误差，但是参数较小的点将成为更优的结果。当C取0时，w也取0时即可达到优化目标。
2、逻辑回归
1、逻辑回归和线性回归的异同：
区别：最本质的区别，逻辑回归处理的是分类任务，线性回归处理的是回归任务。逻辑回归中，因变量取值是一个二元分布，模型学习得出的是,即给定自变量和超参数后，得到因变量的期望，并基于此期望来处理预测分类问题。而现行回归中实际上求解的是
'=
，是对我们假设的真是关系
=
的一个近似，其中
代表误差项，我们使用这个近似项来处理回归问题。
还有一个区别是，逻辑回归中的因变量是离散的，线性回归中的因变量是连续的。并且在自变量x与超参数确定的情况下，逻辑回归可以看做广义线性模型在因变量y服从二元分布时的一个特殊情况；而使用最小二乘法求解线性回归时，我们认定因变量y服从正态分布。
相同：两者都使用了极大似然估计来对训练样本进行建模。线性回归使用最小二乘法，实际上就是自变量x和超参数确定。因变量y服从正态分布的假设下，使用极大似然估计的一个化简；二逻辑回归中对似然函数
的学习，得到最佳参数
。
在求解参数过程中，都可以使用梯度下降的方法
2、多项逻辑将回归：
一个样本只对应一个标签时，可以假设每个样本属于不同标签的概率服从几何分布，使用多项逻辑回归(Softmax Regression)来进行分类(存在一个Softmax)。
一个样本可能属于多个标签时，可以训练k个二分类的逻辑回归分类器第k个分类器用以区分每个样本是否可以归为第i类。
3、决策树
1、决策树常用的启发函数：
ID3：最大信息增益
C4.5：最大信息增益比
CART树：最大基尼指数（Gini）
2、三种决策树构造准则的比较：
ID3采用信息增益作为评价标准，会倾向于取值较多的特征。因为信息增益反映的是给定条件以后不确定性减少的程度。C4.5实际上是对ID3的优化，通过引入信息增益比，一定程度上对取值比较多的特征进行惩罚，避免ID3出现过拟合，提升决策树的泛化能力。
从样本类型的角度，ID3只能处理离散型变量，而C4.5和CART树都可以处理连续型变量。C4.5会排序找到切分点，将连续变量转换为多个取值区间的离散型变量，CART每次会对特征进行二值划分，适用于连续变量。
从应用角度，ID3和C4.5只能用于分类，CART树可以用于分类和回归。
从实现细节、优化过程等角度，ID3对样本特征缺失值比较敏感，而C4.5和CART树都可以对缺失值进行不同方式的处理。
ID3和C4.5可以产生多叉分支，且每个特征在层级之间不会复用。CART树是二叉树，每个特征可以被重复利用。
ID3和C4.5通过剪枝来权衡树的准确性和泛化性能，CART树枝节利用全部数据发现所有可能的树结构进行对比。
3、前剪枝：在生成决策树的过程中提前停止树的增长。核心思想是在树中节点进行扩展之前，先计算当前的划分是否能带来模型泛化性能的提升，如果不能则不再继续生成子树。
前剪枝停止决策树生长的几种方法：
(1) 当树达到一定深度时停止生长。
(2) 当到达当前节点的样本数量小于某个阈值时停止生长。
(3) 计算每次分类对测试集的准确率提升，当小于某个阈值时停止生长。
前剪枝的优缺点：
优点：简单高效，适合解决大规模问题。
缺点：
(1) 深度和阈值这些值很难准确估计，针对不同问题会有很大差别。
(2) 前剪枝存在一定局限性，有欠拟合的风险，虽然当前的划分会导致测试集准确率下降，可能在后面会有显著上升。
4、后剪枝：在已生成的过拟合决策树上进行剪枝。核心思想是让算法生成一棵完全生长的决策树，然后从底层向上计算是否剪枝。(剪枝是将子树删除，用一个叶子节点代替，节点类别按多数投票)如果剪枝之后准确率有提升，则剪枝。
后剪枝的优缺点：
优点：通常可以得到泛化能力更强的决策树。
缺点：时间开销大。
常用的后剪枝方法：
(1) 错误率降低剪枝(Reduced Error Pruning，REP)
(2) 悲观剪枝(Pessimistic Error Pruning，PEP)
(3)代价复杂度剪枝(Cost Complexity Pruning，CCP)
(4)最小误差剪枝(Minimum Error Pruning，MEP)
(5)CVP(Critical Value Pruning)
(6)OOP(Optimal Pruning)
代价复杂度剪枝CCP的步骤。
(1) 从完整决策树开始，生成一个子树序列{
}，其中
由
生成，
为根节点。(也就是说计算剪枝之后误差增加率，选最小的节点剪枝代替，一直剪枝，直到最后只剩下根节点，记录下这个过程中所有的树的样子)
(2)在子树序列中，根据真实误差选择最佳的决策树。CCP对于从子树序列中选最优树有两种方法：1.从子树序列中选择最佳决策树。由于不是在所有可能的子树中寻找，性能上会有一定不足。2.基于 k 折交叉验证，将数据集分成k份，前k-1份用于生成决策树，最后一份用于剪枝。重复进行N次，再从N个子树中选择最优子树。
