【面试】面试常见问题整理

1. LR和SVM的区别

相同点：
1、都是监督、分类算法，且一般处理二分类问题
2、两个方法都可以增加不同的正则化项，如l1、l2等等
3、都是判别模型
3、如果不考虑核函数，LR和SVM都是线性分类算法。也就是说他们的分类决策面都是线性的。

不同点：
1、损失函数不同：LR用似然函数；SVM用合页损失函数。
这两个损失函数的目的都是增加对分类影响较大的数据点的权重，减少与分类关系较小的数据点的权重
2、SVM只考虑支持向量，也就是和分类最相关的少数点。而逻辑回归通过非线性映射，大大减小了离分类平面较远的点的权重，相对提升了与分类最相关的数据点的权重。所以， 线性SVM不直接依赖于数据分布，分类平面不受一类点影响；LR则受所有数据点的影响，如果数据不同类别strongly unbalance，一般需要先对数据做balancing。
3、在解决非线性问题时，支持向量机采用核函数的机制，而LR通常不采用核函数的方法，做特征。因为SVM只有少数几个点运算，LR要全部(计算量)
4、Linear SVM依赖数据表达的距离测度，所以需要对数据先做归一化；LR不受其影响，但是如果要正则的话也要归一化
5、SVM不能产生概率，LR可以产生概率
6、SVM的目标函数就自带正则（目标函数中的1/2||w||^2项），这就是为什么SVM是结构风险最小化算法的原因。而LR必须另外在损失函数上添加正则项。

2. 正则化；L1正则和L2正则的区别
   http://blog.csdn.net/jinping_shi/article/details/52433975

正则化是针对过拟合而提出的。在模型的经验风险上加入正则化项作为结构风险，并使用一个比例来权衡模型复杂度与经验风险的权重。

范数
L0范数：不为0的元素个数
L1范数: 为x向量各个元素绝对值之和。
L2范数: 为x向量各个元素平方和的1/2次方
Lp范数: 为x向量各个元素绝对值p次方和的1/p次方.

作用
L1正则化可以产生稀疏模型，可以用于特征选择
L2正则化可以防止模型过拟合
一定程度上，L1也可以防止过拟合

奥卡姆剃刀原理，能够很好的解释已知数据并且十分简单才是最好的模型。

L1和L2正则先验分别服从什么分布，L1是拉普拉斯分布，L2是高斯分布

3. 简单介绍一下SVM，哪些核函数，哪些参数
   https://www.zhihu.com/question/37928831?sort=created

基本认知：支持向量机(support vector machine，SVM)是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器。模型为分离超平面，策略为间隔最大化，学习算法为凸二次优化。

核函数有线性核、高斯核、多项式核等，一般使用线性核核高斯核。多项式核有参数p表达p次多项式。高斯核参数高斯径向基的sigma

使用SVM要做归一化处理；RBF核耗时

下面是吴恩达的见解：
1.如果Feature的数量很大，跟样本数量差不多，这时候选用LR或者是Linear Kernel的SVM
2.如果Feature的数量比较小，样本数量一般，不算大也不算小，选用SVM+Gaussian Kernel
3.如果Feature的数量比较小，而样本数量很多，需要手工添加一些feature变第一种情况

4. 过拟合和解决方法

过度拟合训练数据，使得模型过于复杂导致的。表现为对训练数据效果良好，对测试数据效果很差。
处理方法有：
1、更多数据：数据量、数据增强、加噪声
2、正则化：约束模型复杂度
3、减少特征
4、早停止
5、交叉验证
6、使用多个模型：如集成方法的Boosting、Bagging；或神经网络的dropout

5. 分类问题的评价标准

准确率、精确率、召回率、F1值、AUC值；PR曲线、ROC曲线

(实际，猜测) TP:真，真；FP:假真；TN:真，假；FN:假假
准确率acc=TP+TN/TP+TN+FP+FN
精确率P=TP/TP+FP
召回率R=TP/TP+FN
F1值=2PR/P+R
AUC值=ROC曲线下的面积

PR曲线，y轴为精确率，x轴为召回率，越偏右上越好(都很高)
ROC曲线，y轴为真正例率，x轴为假正例率，越偏左上越好
真正例率TPR=TP/TP+FP;假正例率FPR=FP/TN+FP

AUC表示正例排在负例前面的概率。
AUC表示，随机抽取一个正样本和一个负样本，分类器正确给出正样本的score高于负样本的概率。

另外，为什么取AUC较好？因为一个二分类问题，如果你取P或R的话，那么你的评价结果和你阈值的选取关系很大。AUC能很好描述模型整体性能的高低。

6. 熵、信息增益、信息增益比、基尼指数

   
   
   
   
   
   

7. 介绍LR，为啥用的是似然函数不用最小二乘？

   
   

8. 梯度下降法和拟牛顿法

梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法“。
批量梯度下降、随机梯度下降、小批量梯度下降。
最速下降法越接近目标值，步长越小，前进越慢。

从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。
牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。
从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。
牛顿法的优缺点总结：
　　优点：二阶收敛，收敛速度快；
　　缺点：牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。

拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。

9. 数据不平衡问题

采样：过采样、欠采样
合成数据：SMOTE
模型中的样本权重
异常点检测
AUC：因为ROC曲线有个很好的特性：当测试集中的正负样本的分布变换的时候，ROC曲线能够保持不变。在实际的数据集中经常会出现样本类不平衡，即正负样本比例差距较大，而且测试数据中的正负样本也可能随着时间变化。

10. 特征选择

Filter：过滤法，按照发散性或者相关性对各个特征进行评分，设定阈值或者待选择阈值的个数，选择特征。
Wrapper：包装法，根据目标函数（通常是预测效果评分），每次选择若干特征，或者排除若干特征。
Embedded：集成法，先使用某些机器学习的算法和模型进行训练，得到各个特征的权值系数，根据系数从大到小选择特征。类似于Filter方法，但是是通过训练来确定特征的优劣。

Filter：【自变量、目标变量的联系】
方差选择法，使用方差选择法，先要计算各个特征的方差，然后根据阈值，选择方差大于阈值的特征。
相关系数法，使用相关系数法，先要计算各个特征对目标值的相关系数以及相关系数的P值。
卡方检验、互信息法
变量间的相关系数

Wrapper：【目标函数判断】
递归特征消除法，递归消除特征法使用一个基模型来进行多轮训练，每轮训练后，消除若干权值系数的特征，再基于新的特征集进行下一轮训练。【多轮训练寻优，RFE】

Embedded：【学习模型自身评价】
正则化：使用带惩罚项的基模型，除了筛选出特征外，同时也进行了降维。Lasso、Ridge
基于树模型的特征选择法：树模型中GBDT也可用来作为基模型进行特征选择

降维

PCA
LDA

11. 数据预处理
    唯一值：删除
    缺失值：直接使用，如决策树
       ： 删除特征，对于大量缺失的
       ： 缺失值补全
    缺失值补全：均值插补、同类均值插补、建模预测、高维映射(one-hot)、多重插补(估计+噪声)、压缩感知和矩阵补全
    特征编码：二元化、独热编码（可处理非数值属性，扩充特征，属性稀疏）
    数据标准化：使样本数据缩放到某个指定范围。原因：数量级大的属性占主导，收敛速度慢，所有依赖于样本距离的算法对数据的数量级都比较敏感。方法：min-max,z-score,
    数据正则化：正则化过程针对单个样本，对核方法计算样本相似性有效

12. RF、GBDT、XGBoost调参

GBDT：
Boosting相关：
n_estimators：最大迭代次数，和learning_rate一起考虑.>100
learning_rate：权重缩减系数ν，也称作步长。作为正则化项。0.01~0.1。小learning_rate，CV合适的n_estimators
subsample：正则化方式(防止过拟合)中的子采样，不放回抽样，推荐在[0.5, 0.8]
CART相关：
max_features:特征太多可用
max_depth:常用的可以取值10-100之间。样本多可用。
min_samples_split：看样本数量
min_samples_leaf：看样本数量
min_weight_fraction_leaf：一般来说，如果我们有较多样本有缺失值，或者分类树样本的分布类别偏差很大，就会引入样本权重，这时我们就要注意这个值了。
max_leaf_nodes：与max_depth二选一
min_impurity_split：一般不改
random_state

RF：
Bagging相关：
n_estimators：迭代次数，重要！
oob_score：是否采用袋外样本来评估模型的好坏，建议True，泛化。
criterion：评价标准，默认分类Gini，可以信息增益；回归mse，可以mae
CART相关：
max_features：重要
max_depth：重要
min_samples_split：重要
min_samples_leaf：重要
min_weight_fraction_leaf
max_leaf_nodes
min_impurity_split

XGBoost:
'booster':'gbtree',
'objective': 'multi:softmax', #多分类的问题
'num_class':10, # 类别数，与 multisoftmax 并用
'gamma':0.1, # 用于控制是否后剪枝的参数,越大越保守，一般0.1、0.2这样子。
'max_depth':12, # 构建树的深度，越大越容易过拟合
'lambda':2, # 控制模型复杂度的权重值的L2正则化项参数，参数越大，模型越不容易过拟合。
'subsample':0.7, # 随机采样训练样本
'colsample_bytree':0.7, # 生成树时进行的列采样
'min_child_weight':3,
这个参数默认是 1，是每个叶子里面 h 的和至少是多少，对正负样本不均衡时的 0-1 分类而言,假设 h 在 0.01 附近，min_child_weight 为 1 意味着叶子节点中最少需要包含 100 个样本。
这个参数非常影响结果，控制叶子节点中二阶导的和的最小值，该参数值越小，越容易 overfitting。
'silent':0 ,#设置成1则没有运行信息输出，最好是设置为0.
'eta': 0.007, # 如同学习率
'seed':1000,
'nthread':7,# cpu 线程数
'eval_metric': 'auc'

13. LR、SVM调参
    https://www.cnblogs.com/pinard/p/6035872.html
    LR：
    penalty:l1/l2
    solver:liblinear、lbfgs拟牛顿法、newton-cg牛顿法、sag随机平均梯度下降
    multi_class/class_weight/sample_weight

SVM：
C表示模型对误差的惩罚系数；gamma反映了数据映射到高维特征空间后的分布，gamma越大，支持向量越多，gamma值越小，支持向量越少。C越大，模型越容易过拟合；C越小，模型越容易欠拟合。gamma越小，模型的泛化性变好，但过小，模型实际上会退化为线性模型；gamma越大，理论上SVM可以拟合任何非线性数据。
GridSearchCV
1）一般推荐在做训练之前对数据进行归一化，当然测试集中的数据也需要归一化。。
2）在特征数非常多的情况下，或者样本数远小于特征数的时候，使用线性核，效果已经很好，并且只需要选择惩罚系数C即可。
3）在选择核函数时，如果线性拟合不好，一般推荐使用默认的高斯核'rbf'。这时我们主要需要对惩罚系数C和核函数参数γ进行艰苦的调参，通过多轮的交叉验证选择合适的惩罚系数C和核函数参数γ。
4）理论上高斯核不会比线性核差，但是这个理论却建立在要花费更多的时间来调参上。所以实际上能用线性核解决问题我们尽量使用线性核。

14. RF、GBDT、XGBoost评分
    XGBoost:特征评分可以看成是被用来分离决策树的次数
    RF：Gini
    GBDT：平方损失

RF计算某个特征X的重要性时，具体步骤如下：
1）对每一颗决策树，选择相应的袋外数据（out of bag，OOB）​计算袋外数据误差，记为errOOB1.
所谓袋外数据是指，每次建立决策树时，通过重复抽样得到一个数据用于训练​决策树，这时还有大约1/3的数据没有被利用，没有参与决策树的建立。这部分数据可以用于对决策树的性能进行评估，计算模型的预测错误率，称为袋外数据误差。
​这已经经过证明是无偏估计的,所以在随机森林算法中不需要再进行交叉验证或者单独的测试集来获取测试集误差的无偏估计。
​2）随机对袋外数据OOB所有样本的特征X加入噪声干扰（可以随机改变样本在特征X处的值），再次计算袋外数据误差，记为errOOB2。
3）​假设森林中有N棵树，则特征X的重要性=∑（errOOB2-errOOB1）/N。这个数值之所以能够说明特征的重要性是因为，如果加入随机噪声后，袋外数据准确率大幅度下降（即errOOB2上升），说明这个特征对于样本的预测结果有很大影响，进而说明重要程度比较高。

15. 距离度量
    闵可夫斯基距离（欧式、曼哈顿）
    马氏距离：马氏距离的计算中考虑了在不同方向上尺度单位。例：判断未知样本归属哪个样本集，考虑了不同维度方差信息。
    互信息
    余弦相似度
    相关系数

KL散度

16. 逻辑回归LR的特征为什么要先离散化
    http://blog.csdn.net/yang090510118/article/details/39478033

在工业界，很少直接将连续值作为特征喂给逻辑回归模型，而是将连续特征离散化为一系列0、1特征交给逻辑回归模型，这样做的优势有以下几点：

1. 稀疏向量内积乘法运算速度快，计算结果方便存储，容易scalable（扩展）。

2. 离散化后的特征对异常数据有很强的鲁棒性：比如一个特征是年龄>30是1，否则0。如果特征没有离散化，一个异常数据“年龄300岁”会给模型造成很大的干扰。

3. 逻辑回归属于广义线性模型，表达能力受限；单变量离散化为N个后，每个变量有单独的权重，相当于为模型引入了非线性，能够提升模型表达能力，加大拟合。

4. 离散化后可以进行特征交叉，由M+N个变量变为M*N个变量，进一步引入非线性，提升表达能力。

5. 特征离散化后，模型会更稳定，比如如果对用户年龄离散化，20-30作为一个区间，不会因为一个用户年龄长了一岁就变成一个完全不同的人。当然处于区间相邻处的样本会刚好相反，所以怎么划分区间是门学问。
   李沐少帅指出，模型是使用离散特征还是连续特征，其实是一个“海量离散特征+简单模型” 同 “少量连续特征+复杂模型”的权衡。既可以离散化用线性模型，也可以用连续特征加深度学习。就看是喜欢折腾特征还是折腾模型了。通常来说，前者容易，而且可以n个人一起并行做，有成功经验；后者目前看很赞，能走多远还须拭目以待。
   大概的理解：
   1）计算简单
   2）简化模型
   3）增强模型的泛化能力，不易受噪声的影响

6. LR并行化

由逻辑回归问题的求解方法中可以看出，无论是梯度下降法、牛顿法、拟牛顿法，计算梯度都是其最基本的步骤，并且L-BFGS通过两步循环计算牛顿方向的方法，避免了计算海森矩阵。因此逻辑回归的并行化最主要的就是对目标函数梯度计算的并行化。
目标函数的梯度向量计算中只需要进行向量间的点乘和相加，可以很容易将每个迭代过程拆分成相互独立的计算步骤，由不同的节点进行独立计算，然后归并计算结果。

18. LR与线性回归

逻辑回归和线性回归首先都是广义的线性回归，
其次经典线性模型的优化目标函数是最小二乘，而逻辑回归则是似然函数，
另外线性回归在整个实数域范围内进行预测，敏感度一致，而分类范围，需要在[0,1]。逻辑回归就是一种减小预测范围，将预测值限定为[0,1]间的一种回归模型，因而对于这类问题来说，逻辑回归的鲁棒性比线性回归的要好。

19. FM/FFM
    FM解决的问题：大规模稀疏数据下的特征组合问题。
    在传统的线性模型如LR中，每个特征都是独立的，如果需要考虑特征与特征直接的交互作用，可能需要人工对特征进行交叉组合；

    
    image.png
    

    这是因为在稀疏条件下，这样的表示方法打破了特征的独立性，能够更好地挖掘特征之间的相关性。以上述电影为例，我们要估计用户A和电影ST的关系w(A&ST)以更好地预测y，如果是简单地考虑特征之间的共现情况来估计w(A&ST)，从已有的训练样本来看，这两者并没有共现，因此学习出来的w(A&ST)=0。而实际上，A和ST应该是存在某种联系的，从用户角度来看，A和B都看过SW，而B还看过ST，说明A也可能喜欢ST，说明A很有可能也喜欢ST。而通过向量v来表示用户和电影，任意两两之间的交互都会影响v的更新，从前面举的例子就可以看过，A和B看过SW，这样的交互关系就会导致v(ST)的学习更新，因此通过向量v的学习方式能够更好的挖掘特征间的相互关系，尤其在稀疏条件下。
    FM 对比 SVM
    看到上面的式子，是不是觉得跟FM特别像？SVM和FM的主要区别在于，SVM的二元特征交叉参数是独立的，如wij，而FM的二元特征交叉参数是两个k维的向量vi、vj，这样子的话，<vi,vj>和<vi,vk>就不是独立的，而是相互影响的。
    为什么线性SVM在和多项式SVM在稀疏条件下效果会比较差呢？线性svm只有一维特征，不能挖掘深层次的组合特征在实际预测中并没有很好的表现；而多项式svn正如前面提到的，交叉的多个特征需要在训练集上共现才能被学习到，否则该对应的参数就为0，这样对于测试集上的case而言这样的特征就失去了意义，因此在稀疏条件下，SVM表现并不能让人满意。而FM不一样，通过向量化的交叉，可以学习到不同特征之间的交互，进行提取到更深层次的抽象意义。
    此外，FM和SVM的区别还体现在：1）FM可以在原始形式下进行优化学习，而基于kernel的非线性SVM通常需要在对偶形式下进行；2）FM的模型预测是与训练样本独立，而SVM则与部分训练样本有关，即支持向量。
    FFM在FM的基础上，增加了特征与场(特征类型)的交叉关系，

20. AdaBoost
    　　　　这里对Adaboost算法的优缺点做一个总结。
    　　　　Adaboost的主要优点有：
    　　　　1）Adaboost作为分类器时，分类精度很高
    　　　　2）在Adaboost的框架下，可以使用各种回归分类模型来构建弱学习器，非常灵活。
    　　　　3）作为简单的二元分类器时，构造简单，结果可理解。
    　　　　4）不容易发生过拟合
    　　　　Adaboost的主要缺点有：
    　　　　1）对异常样本敏感，异常样本在迭代中可能会获得较高的权重，影响最终的强学习器的预测准确性。

21. 介绍GBDT

22. 介绍RF

23. 介绍XGBoost
    xgboost相比传统gbdt有何不同？xgboost为什么快？xgboost如何支持并行？
    看了陈天奇大神的文章和slides，略抒己见，没有面面俱到，不恰当的地方欢迎讨论：
    传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。
    传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。
    xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。
    Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）
    列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
    对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。
    xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
    可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。

xgboost使用经验总结

• 多类别分类时，类别需要从0开始编码
• Watchlist不会影响模型训练。
• 类别特征必须编码，因为xgboost把特征默认都当成数值型的
• 调参：Notes on Parameter Tuning 以及 Complete Guide to Parameter Tuning in XGBoost (with codes in Python)
• 训练的时候，为了结果可复现，记得设置随机数种子。
• XGBoost的特征重要性是如何得到的？某个特征的重要性（feature score），等于它被选中为树节点分裂特征的次数的和，比如特征A在第一次迭代中（即第一棵树）被选中了1次去分裂树节点，在第二次迭代被选中2次…..那么最终特征A的feature score就是 1+2+….

24. GBDT、RF、XGBoost的区别

25. XGBoost和lightGBM

26. 数据倾斜
    在计算数据的时候，数据的分散度不够，导致大量的数据集中到了一台或者几台机器上计算，这些数据的计算速度远远低于平均计算速度，导致整个计算过程过慢。
    如：表Join的Key集中；groupby的维度太小；count distinct的某特殊值太多；
    三个方面解决：
    业务：特殊的，有大数据量的部分单独计算；
    程序：做好剪裁后
    参数：Hive防倾斜的参数；hive.groupby.skewindata
    例子：
    采用sum() group by的方式来替换count(distinct)完成计算。
    空值过多导致倾斜的，Join时不考虑空值，或者加随机数打散
    不同类型数据关联导致倾斜的，统一数据类型
    做好剪裁工作Join

27. MapReduce

    
    
    

    Input 代表的是需要处理的原始数据，一共有3行。
    Splitting 表示分配任务，这里把任务分给3台机器同时处理，每台机器只负责处理一行的数据。
    Mapping 表示这3台机器具体要做的事情。在这里每台机器要做的就是统计一行文字里的单词频率。这里就涉及到比较重要的一个概念，就是key和value。这里key就是单词，value就是这个单词在这一行出现的次数。
    Shuffling 表示对Mapping步骤产生的9行数据，按照key进行分组。这里分成了4组，每组交给一台电脑去处理。
    Reducing 表示把相同key对应的value相加，每个key最终只输出一行，依然是key,value的形式输出。
    Final result 表示把Reducing的输出合并。

Mapper每次只处理一行数据。即Mapper的Input是数据库中的一条记录。
Reducer每次要处理的是相同key下的所有记录，通常会是多行的。