1.二叉树前、中、后、层次非递归写法
2.排序算法(尤其是快排)
3.100000个数中找出最大的k个数
算法:
1.模型的评价指标计算公式
精确率:判黑真正为黑的占判黑总数的比例
召回率:正确判黑的占黑样本总数的比例
ROC曲线:在各个阈值下模型以FPR为横坐标、TPR为纵坐标,画的曲线
AUC:ROC曲线线下面积
2.AUC指标详解
计算公式:ROC曲线的线下面积
概率解释:在正负样本中随机取一对正负样本,其中正样本得分大于负样本得分的概率
AUC是否受正负样本比例的影响?
AUC不受正负样本比例的影响,用正负采样过后的测试集和用不进行采样的测试集AUC基本不变
AUC和其他评价指标相比的优势在哪里?为什么?
改评价指标不受测试集正负样本比例的影响,相比于其他评估指标,例如准确率、召回率和F1值,负样本下采样相当于只将一部分真实的负例排除掉了,然而模型并不能准确地识别出这些负例,所以用下采样后的样本来评估会高估准确率;因为采样只对负样本采样,正样本都在,所以采样对召回率并没什么影响。这两者结合起来,最终导致高估F1值!
3.word2vec介绍,如何进行训练?有那两种区别是什么?大数据情况下那种更适合?
a.介绍
一种词向量的表达,能使词的表达具有一定的上下文信息,原始的word2vec是一个浅层神经网络,首先把全部词进行one-hot,那么每个词将对应着一个特征向量,
(1).首先是一个线性的Embedding层。在word2vec进行训练的时候,将输入2k个词的词向量,通过一个共享的D*V(V是词典大小,D是Embebdding的向量维度)的矩阵C,映射为2k个分布式的词向量。C矩阵例存储了要学习的word2cev向量
(2).忽略上下文的序列信息:输入所有的词向量都汇总到一个Embedding layer(加和取平均)
(3).用softmax进行映射,得到这个词是各个词的概率
(4).然后根据这个词本身的情况来进行更新
c.有那几种?区别是什么?
Cbow:每次用前后k个词词来预测中间的1个词 词向量更新n词,时间复杂度较低
Skip-gram:用1个词预测前后k个词 词向量更新kn词,时间复杂度较高 更适合数据较少的情况
d.大数据情况下更适合哪种?为什么?
更适合适用Cbow,因为效率较高
e.有哪几种优化方式?具体讲一下哈弗曼树方式如何进行训练和预测
分层softmax:
负采样:
f.局限性
(1).只能考虑局部的词之间的关联性
(2).没有考虑词之间的内在联系
g.实质
计算输入向量和输出向量的余弦相似度
4.SVM
1.公式推导
2.损失函数
hinge(折页损失函数)+正则
3.映射到的核函数空间有什么要求(核函数要求)?
过某非线性变换 φ( x) ,将输入空间映射到高维特征空间,在低维输入空间存在某个函数 K(x, x′) ,恰好等于在高维空间中这个内积,即K( x, x′) =<φ( x) ⋅φ( x′) > (这样的函数K被称作核函数)
4.点到向量距离公式推导
5..生成模型和判别模型
1.定义
生成模型:学习得到数据的联合分布P(x,y),然后求联合分布。能够学习到数据的生成机制。
判别模型:学习的到概率的条件分布P(y|x)
2.区别
数据量和准确率:生成模型的数据量需求比较大,在数据量足够多的时一般生成模型效果较好,因为联合分布能够提供更多的有效信息;而判别模型需要的数据量较小,引起直接面向预测在小数据条件下一般效果比生成模型效果好
速度:生成模型收敛速度较快
隐变量情况:生成模型能够应付(高斯混合模型就是生成模型的隐变量形式)
3.常见的生成模型和判别模型
生成模型:隐马尔科夫链、朴素贝叶斯
判别模型:csrf
6.xgboost
XGBoost的损失函数是什么,节点划分准则是什么?
损失函数:
节点划分准则:
分类树:信息增益获信息增益比
回归树:最大均方误差
整体流程:
Xgboost和GBDT算法时间复杂度是多少?
针对每个特征,把属于该节点的训练样本根据该特征值升序排列,通过线性扫描的方式来决定该特征的最佳分裂点,并记录该特征的最大收益(采用最佳分裂点时的收益)
时间复杂度:O(nlogn d m)(n是样本个数,d是特征个数,m是树的深度)
xgboost是如何进行剪枝的?
xgboost采用后剪枝的方式进行剪枝,即 从顶到底建立所有可以建立的子树,再从底到顶反向进行剪枝,这样不容易陷入局部最优解。
xgboost和gbdt的区别:
1.xgboost是gbdt的工程化实现
2.xgboost加入了正则化信息
3.xgboost允许使用自定义的损失函数
4.xgboost损失函数加入了二阶导数信息,下降的更快更准
5.xgboost支持和随机森林一样的列抽样
6.xgboost支持并行化,但是并不是树与树之间的并行化,而是在最费时的特征排序截断进行并行化,将排序结果进行分桶保存,各个树生成时复用
7.xgboost基模型除了支持gbdt支持的CART树外还支持其他的基模型
7.样本不平衡问题处理办法
8.L1正则化和L2正则化
极大似然和最大熵