互联网算法高频面试题汇总
机器学习一、聚类（1）Kmeans（2）DBSCAN（3）处理有序变量 二、分类（1）SVM（2）AUC和PR曲线 三、集成学习（1）bagging（2）boosting（3）stacking（4）树类别（5）缺失值处理 四、自然语言处理（1）HMM（2）MEMM（3）CRF 神经网络一、训练（1）dropout（2）batchnorm（3）ADAM（4）欠拟合和过拟合（5）分类为什么用MSE 二、模型（1）卷积（2）LSTM（3）TCN（4）图神经网络 数据结构一、Dijaska二、topk算法机器学习
一、聚类
（1）Kmeans
KMeans 聚类算法有三个缺点：
第一个就是对簇的数量的选择，我们希望指定一个簇数K，以使每个点和其最近的簇的距离之和最小。但是在实际情况中，我们很难找到一个合适的K值，因为我们不知道应该将数据分为几类。（解决：手肘法，类内误差平方和SSE；ISODATA，可以分裂和合并）Kmeans 算法会把所有的数据点都进行分类，但是很多情况下，会有一些离群点，这些点应该被剔除的，但是 Kmeans 算法还是会把它们归为某一类。k均值聚类假设对每个簇来说，所有的方向都同等重要。这也就意味着k均值聚类主要适用于球形分布的数据，对于其他分布的数据分类可能不好。（解决：核函数）对类中心的初始值敏感。（解决：Kmeans++，初始的聚类中心之间的相互距离要尽可能的远）
（2）DBSCAN
DBSCAN 算法是基于密度对数据点进行处理的，主要是将特征空间中足够密集的点划分为同一个簇，簇的形状可以是任意的，而且数据点中有噪声点的话，不会将这些点划分给某个簇。这个算法有几个值得一提的地方：
不需要我们指定数据集中簇的个数K。前面说K均值聚类通常只在球形分布的数据集上分类效果比较好，而 DBSCAN 聚类则可以用于各种复杂形状的数据集。可以识别出不属于任何簇的离群点，非常适合用来检测离群点。
DBSCAN 算法也不是万能的，它也有一些缺点：
DBSCAN 算法的运行速度要比 KMeans 算法慢一些。DBSCAN 算法的两个参数eps和min_samples也是要根据具体的数据情况进行多次尝试。对于具有不同密度的簇，DBSCAN 算法的效果可能不是很好。
（3）处理有序变量
二元变量/分类变量：相异度 {00011}{11000}=4/5
序数变量：秩，或者拆成哑变量
神经网络：embedding
二、分类
（1）SVM
如果特征维数很高，往往线性可分（SVM解决非线性分类问题的思路就是将样本映射到更高维的特征空间中），可以采用LR或者线性核的SVM；
如果样本数量很多，由于求解最优化问题的时候，目标函数涉及两两样本计算内积，使用高斯核明显计算量会大于线性核，所以手动添加一些特征，使得线性可分，然后可以用LR或者线性核的SVM；
如果不满足上述两点，即特征维数少，样本数量正常，可以使用高斯核的SVM。
RBF vs poly
polynomial kernel的参数比RBF多，而参数越多模型越复杂
RBF kernel更方便计算，取值在[0,1]；而用polynomial kernel取值范围是(0,inf)，在阶数高的情况下更凸显出劣势，计算复杂度很高
但是经过试验在数据变化剧烈的情况下poly要更好些，因此还是要进行调参尝试
（2）AUC和PR曲线
AUC曲线的横轴是FPR（被分错的白样本/白样本），纵轴是Recall（被分对的黑样本/黑样本）
PR曲线的横轴是Recall，纵轴是精准率（被分对的黑样本/分为黑样本）
一般PR曲线和AUC低分段更适合样本不平衡问题
三、集成学习
（1）bagging
随机森林，特征和input都抽样
（2）boosting
Adaboost（分类）提高那些被前一轮弱分类器错误分类的样本的权值，而降低那些被正确分类样本的权值。GBDT（分类和回归）
每一棵决策树学习的是之前所有树结点loss和的负梯度，当使用常见的均方误差时，负梯度即为残差。XGBoost（分类和回归）
GBDT将目标函数泰勒展开到一阶，而xgboost将目标函数泰勒展开到了二阶；
xgboost加入了和叶子权重的L2正则化项，因而有利于模型获得更低的方差。 XGBoost的importance计算
gain增益：特征在每个树的贡献占比求平均，默认计算方式
cover覆盖度：特征观测到的相对数量，即叶节点中观测值的占比
freq频率：特征在树中发生的分裂次数占比lightgbm
速度快：
遍历样本转变为遍历直方图
采用单边梯度算法过滤掉梯度小的样本
基于Leaf-wise算法的增长策略构建树，并限制深度
优化特征并行、数据并行，缓存优化
内存小：
直方图和互斥特征捆绑
（3）stacking
N个模型，原始训练数据len1*emb，原始测试数据len2*emb
每个模型做K折交叉验证，得到预测的训练特征len1*1，和预测的测试特征len2*1
新的训练数据len1*N，新的测试数据len2*N
（4）树类别
决策树有CART（基尼系数），ID3（信息增益），C4.5（信息增益比）
回归树只有CART
（5）缺失值处理
中位数
数据相似性作为权重（时间复杂度高，O(n*d)）
决策树：训练时忽略缺失值，但是增益会乘上非缺失值占比，计算score时赋给训练缺失值分到左右的比例，进行全概率计算；测试时遇到缺失值就选择概率大的那个方向
XGBoost：分别计算在某一特征下所有缺失值往左和往右的增益，选择增益最大的那个方向并初始化方向；如果在训练中没有缺失值而在预测中出现缺失，自动将缺失值的划分方向放到右子树
四、自然语言处理
（1）HMM
HMM模型是概率生成模型，存在两个假设： 一是输出观察值之间严格独立，二是状态的转移过程中当前状态只与前一状态有关(一阶马尔可夫模型)。
维特比算法为何有效？
因为HMM的马尔科夫性，保证了如果知道当前概率最大的词性，就一定能知道上一个词性。
（2）MEMM
MEMM模型是概率判别模型克服了观察值之间严格独立产生的问题（给定yt，xt和xt-1是有关的），但是由于局部归一化，使得该模型存在标注偏置问题。
（3）CRF
CRF是概率判别模型，概率无向图模型，通过全局归一化解决了标注偏置问题，且模仿最大熵模型融入更多特征，取得了更好的效果。
神经网络
一、训练
（1）dropout
当相对于网络的复杂程度（即网络的表达能力、拟合能力）而言数据量过小时，出现过拟合，显然这时各神经元表示的特征相互之间存在许多重复和冗余。dropout的直接作用是减少中间特征的数量，从而减少冗余，即增加每层各个特征之间的正交性。
让某个神经元以概率p停止工作；预测模型的时候，每一个神经单元的权重参数要乘以概率p。
为什么有效：
取平均的作用：dropout掉不同的隐藏神经元就类似在训练不同的网络，随机删掉一半隐藏神经元导致网络结构已经不同，整个dropout过程就相当于对很多个不同的神经网络取平均。而不同的网络产生不同的过拟合，一些互为“反向”的拟合相互抵消就可以达到整体上减少过拟合。减少神经元之间复杂的共适应关系： 弱化了各个特征之间由于数据量太小导致产生的过多的相互作用。换句话说假如我们的神经网络是在做出某种预测，即使丢失特定的特征，它也应该可以从众多其它特征中学习一些共同的特征。因此使得网络对丢失特定神经元连接的鲁棒性提高。Dropout类似于性别在生物进化中的角色：物种为了生存往往会倾向于适应这种环境，环境突变则会导致物种难以做出及时反应，性别的出现可以繁衍出适应新环境的变种，有效的阻止过拟合，即避免环境改变时物种可能面临的灭绝。
（2）batchnorm
缺点：小batch下学习到的mu和sigma没有代表性
（3）ADAM
RMSprop加上平滑版梯度和偏置矫正。
m是平滑版的梯度，需要偏置矫正；
v是二阶矩的滑动平均，基于梯度大小来自适应调整学习率（梯度变化大则减小学习率）。
ADAMW：保证L2 regularization与weight decay等价
（4）欠拟合和过拟合
欠拟合使用复杂模型（增加变量、分段函数），数据增强；（DL）增加epoch和网络层数过拟合
正则项，集成学习，优化器（学习率），label smoothing，验证集；（DL）layernorm，batchnorm，dropout
（5）分类为什么用MSE
MSE让正确分类变大（靠近1）的同时，也让错误分类变得平均（接近0），而交叉熵只对正确分类的结果看重
分类问题有激活函数这个非线性单元，比如sigmoid，因此MSE非凸，有多个极值点
MSE求导，越接近真实值越导致梯度消失
二、模型
（1）卷积
1×1卷积
对于图像来说，1x1卷积实际上是对每个像素点，在不同的channels上进行线性组合，且保留了图片的原有平面结构，调控filter的个数，从而完成升维或降维的功能。
1×1卷积和全连接的区别
N1*N2*C转为N1*N2*k，1×1卷积是在通道级别的操作，全连接是在像素级别的操作
（2）LSTM
梯度消失Ct-1从遗忘门到Ct，如果遗忘门接近1，则这条路径梯度不会消失
其他路径依旧会发生梯度消失，但是总的远距离梯度=各条路径的远距离梯度之和，LSTM通过改善一条路径上的梯度问题拯救了总体的远距离梯度梯度爆炸
经过多次sigmoid（小于1）后，其他路径发生梯度爆炸的频率会低得多
实践中梯度爆炸一般通过梯度裁剪来解决
（3）TCN
训练集900个，测试集200个
LSTM的输入输出格式：（batch_size, seq_len, input_dim）–>（batch_size, output_dim）
TCN的输入输出格式：（batch_size, seq_len），一维卷积，但是seq_len可以比LSTM更长
TCN优点：
（1）并行性：TCN可以对每一层的卷积并行处理（梯度一起计算），而不需要像RNN那样顺序的处理（层数小于seq_len）
（2）灵活的感受野：TCN的感受野的大小受层数、卷积核大小、扩张系数等决定
（3）稳定的梯度：RNN经常存在梯度消失和梯度爆炸的问题，TCN不太存在梯度消失和爆炸问题
（4）内存更低：RNN在使用时需要将每步的信息都保存下来，这会占据大量的内存，TCN在一层里面卷积核是共享的，内存使用更低
（4）图神经网络
GNN vs GCNGNN：图神经网络，由于传统的DNN网络无法表示顶点和边这种关系型数据，便出现了图神经网络解决这种图数据的表示问题，这属于DNN往图方向的应用扩展GCN；
图卷积神经网络，GNN在训练过程中，有将attention引入图结构的，有将门控机制引入图结构的，还有将卷积引入图结构的，引入卷积的GNN就是GCN，通过提取空间特征来进行学习。CNN vs GCN
GCN能够处理任意拓扑图；GCN借助图的拉普拉斯矩阵的特征值和特征向量。
数据结构
一、Dijaska
V个点，E个邻居，使用优先队列后复杂度是O(VlogV+VE)，不使用时是O(EV^2)。
空间复杂度都是O(V)。
二、topk算法
冒泡排序，得到有序的最大k个数，O(nk)
堆排序，得到无序的最大k个数，O(nlogk)
快速排序，得到第k大的数，O(n)
