51随机森林RF通过对训练数据样本以及属性进行有放回的抽样（针对某一个属性随机选择样本）这里有两种，一种是每次都是有放回的采样，有些样本是重复的，组成和原始数据集样本个数一样的数据集；另外一种是不放回的抽样，抽取出大约60%的训练信息。由此生成一颗CART树，剩下的样本信息作为袋外数据，用来当作验证集计算袋外误差测试模型；把抽取出的样本信息再放回到原数据集中，再重新抽取一组训练信息，再以此训练数据集生成一颗CART树。这样依次生成多颗CART树，多颗树组成森林，并且他们的生成都是通过随机采样的训练数据生成，因此叫随机森林。RF可以用于数据的回归，也可以用于数据的分类。回归时是由多颗树的预测结果求均值；分类是由多棵树的预测结果进行投票。正式由于它的随机性，RF有极强的防止过拟合的特性。由于他是由CART组成，因此它的训练数据不需要进行归一化，因为每课的建立过程都是通过选择一个能最好的对数据样本进行选择的属性来建立分叉，因此有以上好处的同时也带来了一个缺点，那就是忽略了属性与属性之间的关系。52KMeans讲讲，KMeans有什么缺点，K怎么确定1初始化常数K，随机选取初始点为质心2计算样本与每个质心之间的相似度，将样本归类到最相似的类中3重新计算质心4重复计算一下过程，直到质心不再改变5输出最终的质心以及每个类k-means存在缺点：1）k-means是局部最优的，容易受到初始质心的影响；比如在下图中，因选择初始质心不恰当而造成次优的聚类结果。2）同时，k值的选取也会直接影响聚类结果，最优聚类的k值应与样本数据本身的结构信息相吻合，而这种结构信息是很难去掌握，因此选取最优k值是非常困难的。3）由于每次都要计算所有的样本与每一个质心之间的相似度，故在大规模的数据集上，K-Means算法的收敛速度比较慢。K值得确定：法1：通过枚举，令k从2到一个固定值如10，在每个k值上重复运行数次kmeans(避免局部最优解)，并计算当前k的平均轮廓系数，最后选取轮廓系数最大的值对应的k作为最终的集群数目。时间复杂度：O(N)轮廓系数取值范围为[-1,1]，取值越接近1则说明聚类性能越好，相反，取值越接近-1则说明聚类性能越差。轮廓系数不应该用来评估不同聚类算法之间的优劣，比如Kmeans聚类结果与DBSCAN聚类结果之间的比较。缺点：不适合基高密度的聚类算法DBSCAN53DBSCAN原理和算法伪代码，与kmeans，OPTICS区别DBSCAN聚类算法原理DBSCAN（Density-Based Spatial Clustering of Applications with Noise）聚类算法，它是一种基于高密度连通区域的、基于密度的聚类算法，能够将具有足够高密度的区域划分为簇，并在具有噪声的数据中发现任意形状的簇。我们总结一下DBSCAN聚类算法原理的基本要点：https://blog.csdn.net/hansome_hong/article/details/107596543DBSCAN 算法是一种基于密度的聚类算法：  1.聚类的时候不需要预先指定簇的个数  2.最终的簇的个数不确定2个算法参数：邻域半径R和最少点数目minpointsDBSCAN算法将数据点分为三类：  1.核心点：在半径Eps内含有超过MinPts数目的点。  2.边界点：在半径Eps内点的数量小于MinPts,但是落在核心点的邻域内的点。  3.噪音点：既不是核心点也不是边界点的点4种点的关系：密度直达，密度可达，密度相连，非密度相连在这里插入图片描述，而DBSCAN的时间复杂度是O(m^2)，3．K均值一般聚类所有对象，而DBSCAN丢弃被它识别为噪声的对象。4.K均值使用簇的基于原型的概念，而DBSCAN使用基于密度的概念5.K均值很难处理非球形的簇和不同大小的簇。DBSCAN可以处理不同大小或形状的簇，并且不太受噪声和离群点的影响6. 基本K均值算法等价于一种统计聚类方法（混合模型），假定所有的簇都来自球形高斯分布，具有不同的均值，但具有相同的协方差矩阵。DBSCAN不对数据的分布做任何假定7. K均值可以发现不是明显分离的簇，即便簇有重叠也可以发现，但是DBSCAN会合并有重叠的簇。OPTICS：链接DBSCAN算法中，有两个初始参数Eps（邻域半径）和minPts(Eps邻域最小点数)需要手动设置，并且聚类的结果对这两个参数的取值非常敏感，不同的取值将产生不同的聚类结果。为了克服DBSCAN算法这一缺点，提出了OPTICS算法，该算法可以让算法对半径Eps不再敏感。只要确定minPts的值，半径Eps的轻微变化，并不会影响聚类结果2个新的定义：核心距离：一个对象p的核心距离是使得其成为核心点的最小半径，如果p不是核心点，其可达距离没有定义。可达距离：对于核心点x的邻点x1、x2、…xn 而言，如果他们到点x的距离大于点x’的核心距离，则其可达距离为该点到点x的实际距离；如果他们到点x的距离核心距离小于点x’的核心距离的话，则其可达距离就是点x的核心距离，54OPTICS算法描述输入：样本集D, 邻域半径ε, 给定点在ε领域内成为核心对象的最小领域点数MinPts输出：具有可达距离信息的样本点输出排序55层次聚类两种方式层次聚类：层次聚类就是一层一层的进行聚类，可以由上向下把大的类别（cluster）分割，叫作分裂法；也可以由下向上对小的类别进行聚合，叫作凝聚法；但是一般用的比较多的是由下向上的凝聚方法  1、分裂法：  分裂法指的是初始时将所有的样本归为一个类簇，然后依据某种准则进行逐渐的分裂，直到达到某种条件或者达到设定的分类数目。用算法描述：  输入：样本集合D，聚类数目或者某个条件（一般是样本距离的阈值，这样就可不设置聚类数目）   输出：聚类结果   1.将样本集中的所有的样本归为一个类簇；  repeat：2.在同一个类簇（计为c）中计算两两样本之间的距离，找出距离最远的两个样本a,b；3.将样本a，b分配到不同的类簇c1和c2中；4.计算原类簇（c）中剩余的其他样本点和a，b的距离，若是dis(a)<dis(b)，则将样本点归到c1中，否则归到c2中；   util： 达到聚类的数目或者达到设定的条件  2、凝聚法：凝聚法指的是初始时将每个样本点当做一个类簇，所以原始类簇的大小等于样本点的个数，然后依据某种准则合并这些初始的类簇，直到达到某种条件或者达到设定的分类数目。用算法描述：输入：样本集合D，聚类数目或者某个条件（一般是样本距离的阈值，这样就可不设置聚类数目）输出：聚类结果1.将样本集中的所有的样本点都当做一个独立的类簇；repeat：2.计算两两类簇之间的距离（后边会做介绍），找到距离最小的两个类簇c1和c2；3.合并类簇c1和c2为一个类簇；util： 达到聚类的数目或者达到设定的条件56bagging和boosting的区别Bagging是从训练集中进行子抽样组成每个基模型所需要的子训练集,然后对所有基模型预测的结果进行综合操作产生最终的预测结果。Boosting中基模型按次序进行训练,而基模型的训练集按照某种策略每次都进行一定的转化,最后以一定的方式将基分类器组合成一个强分类器。1）样本选择上：Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。2）样例权重：Bagging：使用均匀取样，每个样例的权重相等。Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。3）预测函数：Bagging：所有预测函数的权重相等。Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。4）并行计算：Bagging：各个预测函数可以并行生成。Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。5)Bagging中的基模型为强模型,Boosting中的基模型为弱模型。57XGBOOST和GDBT的区别GDBT在函数空间中利用梯度下降法进行优化而XGBoost在函数空间中使用了牛顿法进行优化。即GDBT在优化中使用了一阶导数信息,而XGB对损失函数进行了二阶泰勒展开,用到了一阶和二阶倒数信息。XGB在损失函数中加入了正则项(树叶子节点个数,每个叶子节点上输出score的L2模平方和。对于缺失的样本,XGB可以自动学习出它的分裂方向。GDBT的节点分裂方式使用的是gini系数,XGB通过优化推导出分裂前后的增益来选择分裂节点。XGB在处理每个特征列时可以做到并行。58GDBT的原理,以及常用的调参参数先用一个初始值去学习一棵树,然后在叶子处得到预测值以及预测后的残差,之后的树则基于之前树的残差不断的拟合得到,从而训练出一系列的树作为模型。n_estimators基学习器的最大迭代次数,learning_rate学习率，max_lead_nodes最大叶子节点数,max_depth树的最大深度min_samples_leaf叶子节点上最少样本数。59stacking和blending的区别?Stacking和blending的区别在于数据的划分,blending用不相交的数据训练不同的基模型,并将其输出取加权平均。而stacking是将数据集划分为两个不相交的集合,在第一个集合的数据集中训练多个模型,在第二个数据集中测试这些模型,将预测结果作为输入,将正确的标签作为输出,再训练一个高层的模型。60AdaBoost和GBDT的区别,AdaBoost通过调整错分的数据点的权重来改进模型,而GBDT是从负梯度的方向去拟合改进模型AdaBoost改变了训练数据的权值,即样本的概率分布,减少上一轮被正确分类的样本权值,提高被错误分类的样本权值,而随机森林在训练每棵树的时候,随机挑选部分训练集进行训练。在对新数据进行预测时,AdaBoost中所有树加权投票进行预测,每棵树的权重和错误率有关,而随机森林对所有树的结果按照少数服从多数的原则进行预测。随机森林，它属于 Bagging 类的算法。使用随机森林解决回归问题，只需要将所有回归决策树的预测值取平均即可。Boosting 类算法在解决回归问题时，只需要将个体学习器的预测值加权求和即可61gbdt推导链接是一种基于boosting集成学习思想的加法模型，是一种用于回归的机器学习算法，该算法由多棵回归决策树组成，所有树的结论累加起来做最终答案。训练时采用前向分布算法进行贪婪的学习，每次迭代都学习一棵CART树来拟合之前 t-1 棵树的预测结果与训练样本真实值的残差。GBDT中的决策树是个弱模型，深度较小一般不会超过5，叶子节点的数量也不会超过10，GBDT:应用：：：二分类，多分类，特征组合，所有回归问题GBDT和随机森林的相同点：1）都是由多棵树组成；2）最终的结果都是由多棵树一起决定GBDT和随机森林的不同点随机森林对异常值不敏感，GBDT对异常值非常敏感；随机森林对训练集一视同仁，GBDT是基于权值的弱分类器的集成；随机森林是通过减少模型方差提高性能，GBDT是通过减少模型偏差提高性能决策树模型的优点如下。1）容易理解和解释，树可以被可视化。2）不需要太多的数据预处理工作，即不需要进行数据归一化，创造哑变量等操作。3）隐含地创造了多个联合特征，并能够解决非线性问题62xgboost的特征重要性计算特征重要性可以用来做模型可解释性 xgboost实现中Booster类get_score方法输出特征重要性，其中importance_type参数支持三种特征重要性的计算方法：1.importance_type=weight（默认值），特征重要性使用特征在所有树中作为划分属性的次数。2.importance_type=gain，特征重要性使用特征在作为划分属性时loss平均的降低量。3.importance_type=cover，特征重要性使用特征在作为划分属性时对样本的覆盖度63xgboost原理，怎么防过拟合XGBoost 属于加法模型，其基函数为回归决策树；XGBoost 的目标函数为损失函数+正则化项，且损失函数使用了二阶泰勒展开；XGBoost 使用前向分步算法，通过最小化目标函数来进行模型的优化与学习。在xgboost调中，一般有两种方式用于控制过拟合：1）直接控制参数的复杂度：包括max_depth， min_child_weight， gamma；2）add randomness来使得对训练对噪声鲁棒。包括subsample colsample_bytree，或者也可以减小步长 eta，但是需要增加num_round，来平衡步长因子的减小。64xgboost，rf，lr优缺点场景xgb优缺点：1）在寻找最佳分割点时，考虑传统的枚举每个特征的所有可能分割点的贪心法效率太低，xgboost实现了一种近似的算法。大致的思想是根据百分位法列举几个可能成为分割点的候选者，然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。2）xgboost考虑了训练数据为稀疏值的情况，可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率，paper提到50倍。3）特征列排序后以块的形式存储在内存中，在迭代中可以重复使用；虽然boosting算法迭代必须串行，但是在处理每个特征列时可以做到并行。4）按照特征列方式存储能优化寻找最佳的分割点，但是当以行计算梯度数据时会导致内存的不连续访问，严重时会导致cache miss，降低算法效率。paper中提到，可先将数据收集到线程内部的buffer，然后再计算，提高算法的效率。5）xgboost 还考虑了当数据量比较大，内存不够时怎么有效的使用磁盘，主要是结合多线程、数据压缩、分片的方法，尽可能的提高算法的效率。适用场景：分类回归问题都可以。Rf：优点：2）随机森林能处理很高维度的数据（也就是很多特征的数据），并且不用做特征选择。3）在训练完之后，随机森林能给出哪些特征比较重要。4）训练速度快，容易做成并行化方法(训练时，树与树之间是相互独立的)。5）在训练过程中，能够检测到feature之间的影响。6）对于不平衡数据集来说，随机森林可以平衡误差。当存在分类不平衡的情况时，随机森林能提供平衡数据集误差的有效方法。7）如果有很大一部分的特征遗失，用RF算法仍然可以维持准确度。8）随机森林算法有很强的抗干扰能力（具体体现在6,7点）。所以当数据存在大量的数据缺失，用RF也是不错的。9）随机森林抗过拟合能力比较强（虽然理论上说随机森林不会产生过拟合现象，但是在现实中噪声是不能忽略的，增加树虽然能够减小过拟合，但没有办法完全消除过拟合，无论怎么增加树都不行，再说树的数目也不可能无限增加的）。10）随机森林能够解决分类与回归两种类型的问题，并在这两方面都有相当好的估计表现。（虽然RF能做回归问题，但通常都用RF来解决分类问题）。11）在创建随机森林时候，对generlization error(泛化误差)使用的是无偏估计模型，泛化能力强。缺点：1）随机森林在解决回归问题时，并没有像它在分类中表现的那么好，这是因为它并不能给出一个连续的输出。当进行回归时，随机森林不能够做出超越训练集数据范围的预测，这可能导致在某些特定噪声的数据进行建模时出现过度拟合。2）对于许多统计建模者来说，随机森林给人的感觉就像一个黑盒子，你无法控制模型内部的运行。只能在不同的参数和随机种子之间进行尝试。4）对于小数据或者低维数据（特征较少的数据），可能不能产生很好的分类。（处理高维数据，处理特征遗失数据，处理不平衡数据是随机森林的长处）。5）执行数据虽然比boosting等快（随机森林属于bagging），但比单只决策树慢多了。适用场景：数据维度相对低（几十维），同时对准确性有较高要求时。因为不需要很多参数调整就可以达到不错的效果，基本上不知道用什么方法的时候都可以先试一下随机森林。Lr：优点：实现简单，广泛的应用于工业问题上；分类时计算量非常小，速度很快，存储资源低；便利的观测样本概率分数；缺点：当特征空间很大时，逻辑回归的性能不是很好；容易欠拟合，一般准确度不太高不能很好地处理大量多类特征或变量；只能处理两分类问题（在此基础上衍生出来的softmax可以用于多分类），且必须线性可分；对于非线性特征，需要进行转换。适用场景：LR同样是很多分类算法的基础组件，它的好处是输出值自然地落在0到1之间，并且有概率意义。因为它本质上是一个线性的分类器，所以处理不好特征之间相关的情况。虽然效果一般，却胜在模型清晰，背后的概率学经得住推敲。它拟合出来的参数就代表了每一个特征(feature)对结果的影响。也是一个理解数据的好工具。65xgboost特征并行化怎么做的决策树的学习最耗时的一个步骤就是对特征值进行排序,在进行节点分裂时需要计算每个特征的增益,最终选增益大的特征做分裂,各个特征的增益计算就可开启多线程进行。而且可以采用并行化的近似直方图算法进行节点分裂。66xgboost和lightgbm的区别和适用场景（1）xgboost采用的是level-wise的分裂策略，而lightGBM采用了leaf-wise的策略，区别是xgboost对每一层所有节点做无差别分裂，可能有些节点的增益非常小，对结果影响不大，但是xgboost也进行了分裂，带来了无必要的开销。 leaf-wise的做法是在当前所有叶子节点中选择分裂收益最大的节点进行分裂，如此递归进行，很明显leaf-wise这种做法容易过拟合，因为容易陷入比较高的深度中，因此需要对最大深度做限制，从而避免过拟合。（2）lightgbm使用了基于histogram的决策树算法，这一点不同与xgboost中的 exact 算法，histogram算法在内存和计算代价上都有不小优势。1）内存上优势：很明显，直方图算法的内存消耗为(#data* #features * 1Bytes)(因为对特征分桶后只需保存特征离散化之后的值)，而xgboost的exact算法内存消耗为：(2 * #data * #features* 4Bytes)，因为xgboost既要保存原始feature的值，也要保存这个值的顺序索引，这些值需要32位的浮点数来保存。2）计算上的优势，预排序算法在选择好分裂特征计算分裂收益时需要遍历所有样本的特征值，时间为(#data),而直方图算法只需要遍历桶就行了，时间为(#bin)（3）直方图做差加速，一个子节点的直方图可以通过父节点的直方图减去兄弟节点的直方图得到，从而加速计算。（4）lightgbm支持直接输入categorical 的feature，在对离散特征分裂时，每个取值都当作一个桶，分裂时的增益算的是”是否属于某个category“的gain。类似于one-hot编码。（5）xgboost在每一层都动态构建直方图，因为xgboost的直方图算法不是针对某个特定的feature，而是所有feature共享一个直方图(每个样本的权重是二阶导),所以每一层都要重新构建直方图，而lightgbm中对每个特征都有一个直方图，所以构建一次直方图就够了。67HMM隐马尔可夫模型的参数估计方法是？期望最大化（Expectation-Maximum,EM）算法68Bootstrap方法是什么？从一个数据集中有放回的抽取N次，每次抽M个。Bagging算法基于bootstrap。面试时结合Bagging算法讲述会更好。69如何防止过拟合？1.早停法；2.l1和l2正则化；3.神经网络的dropout；4.决策树剪枝；5.SVM的松弛变量；6.集成学习，扩增数据集,特征的筛选,在训练和建立模型的时候，从相对简单的模型开始，不要一开始就把特征做的非常多，模型参数跳的非常复杂。70EM算法推导EM算法是否一定收敛？EM算法可以保证收敛到一个稳定点，即EM算法是一定收敛的。更多校园招聘常见面试问题（开发、算法、编程题目）参见CSDN博客：http://t.csdn.cn/V4qbH欢迎关注、收藏、点赞后进行问题咨询及秋招建议！！