1. 组合方法（Bagging）

（1）定义：随机从输入样本空间中独立重复抽样出m个子样本空间，利用这m个子样本空间独立训练出m个基分类器，通过组合m个相互独立的基分类器的预测结果来提高整体分类的准确率，例如m个分基分类器的算术平均值（回归）或者投票结果（分类）。基分类器满足两个条件：一个是相互独立，另一个是分类结果好于随机猜测。优点：并行处理，无依赖。

（2）特点：随机采样也会有36.8%的的数据不被采集，我们常常称之为袋外数据(Out Of Bag, 简称OOB)。这些数据没有参与训练集模型的拟合，因此可以用来检测模型的泛化能力。

（3）Bagging算法

① 从原始样本中采用有放回抽样的方法选取n个样本；

②对n个样本选取所有特征，用建立决策树的方法获得最佳分割点；

③重复m次，获得m个决策树或神经网络模型；

④对输入样例进行预测时，每个子树都产生一个结果，采用多数投票机制输出。

（4）随机森林[1]

① 从原始样本中采用有放回抽样的方法选取n个样本组成一个样本子空间；

②对n个样本随机选取所有特征中的k个特征，用建立决策树的方法获得最佳分割点；

③重复m次，获得m个CART决策树或神经网络模型；

④对输入样例进行预测时，每个子树都产生一个结果，采用多数投票机制输出。

2. 提升方法（Boosting）

（1）基本思路：提升方法采用加法模型，即基函数的线性组合，学习算法为前向分步算法的“分而治之”思路。

（2）通俗表述：对于一个复杂的任务，将多个专家的判断进行适当地综合得出的整体结果，这要比其中任何一个专家单独的判断要好。

（3）AdaBoost算法：对输入的样本X进行加权分布，初始化为等概率分布，经过一次模型训练后，根据错误率来更新输入样本X的权值分布，更新的规则是上一次分错的样本Xi权值增加，分对的样本Xj权值下降，同时利用错误率计算本次训练的基分类器的权值，错误率高的权值小，错误率低的权值大。计算结束后，根据本次计算的样本权值分布继续训练模型。最终得到一个模型为加法模型、损失函数为指数函数、学习算法为前向分步算法的AdaBoost学习模型。

（4）提升树模型（GDBT）：以基函数为决策树、损失函数为平方误差函数或指数函数、学习方法为前向分步算法的提升方法称为提升树。拟合当前模型的残差，而不重新输入原始样本数据X。

（5）梯度提升算法：损失函数为一般的Loss Function，有时候不好优化，所以利用一阶梯度下降算法。加法模型和前面的算法都是一样的。基函数也可以是决策树或神经网络。

（6）优点：①低泛化误差；②容易实现，分类准确率较高，没有太多参数可以调；

（7）缺点：对outlier比较敏感；（原因：拟合残差）

（8）XGBoost算法：损失函数为自定义的Loss Function，优化算法为二阶梯度下降算法——牛顿法，即误差函数的二阶泰勒展开[9]。

① 决策树的分裂方法：1.信息增益——遍历所有特征的所有可能的分割点，计算gain值，选取值最大的（feature，value）去分割； 2.近似算法——对于每个特征，只考察分位点，减少计算复杂度

②稀疏值处理：缺失，类别one-hot编码，大量0值，当特征出现缺失值时，XGBoost可以学习出默认的节点分裂方向。

Bagging 与 Boosting的区别

（1）bagging和Adaboost一样，对于弱学习器没有限制，但是最常用的弱学习器一般也是决策树和神经网络。

（2）Bagging算法：由于并行地训练很多不同的基分类器的目的是降低方差(variance),而采用多个相互独立的基分类器以后，h的值自然就会靠近偏差 Ε[h-E(h)] .对于每个基分类器，训练的目标就是降低这个偏差（bias),所以我们会采用深度很深甚至不剪枝的过拟合决策树分类器[3]。

（3）Boosting算法：训练的每一步，我们都会在上一轮的残差（residual）或样本权值基础上拟合数据，所以这可以保证偏差（bias）。对于每个基分类器，训练的目的是选择方差（variance）更小的基分类器，即更简单的基分类器，所以选择深度较浅的决策树。

（4）机器学习算法泛化误差：偏差（bias)和方差(variance)。这个可由下图的式子导出（这里用到了概率论公式D(X)=E(X^2)-[E(X)]^2）。偏差指的是算法的期望预测与真实预测之间的偏差程度，反应了模型本身的拟合能力；方差度量了同等大小的训练集的变动导致学习性能的变化，刻画了数据扰动所导致的影响。

误差率与偏差和方差的关系式

模型复杂度与方差和偏差的关系

3. 朴素贝叶斯

朴素贝叶斯分类是在输入样本X的各个特征A1，A2，....,An为条件独立假设的情况下，利用贝叶斯定理，根据样本X计算相应标签Y的最大似然后验概率及后验条件概率，获得朴素贝叶斯分类模型，即朴素贝叶斯分类器。需要注意条件独立时某项为零的情况，通过拉普拉斯光滑处理。

4. 决策树

（1）本质：决策树学习本质是从训练数据集中归纳出一组分类规则。

（2）ID3（Iterative Dichotomiser 3，迭代二叉树3）算法思路：

①构建根节点。选择信息增益最大的特征（属性）作为根节点，公式：g(D,A) = H(D) - H(D|A)，把数据分割成两个子样本空间。

②递归计算子节点为内部节点（特征属性）还是叶节点（样本标签类别）。内部节点也是根据信息增益最大的特征来实现样本空间的分割，叶节点则是根据此样本全部为一个类别或分类错误率小于一个阈值时停止递归。

（3）CART（Classification and Regression Tree）算法思路：

①回归树：递归地利用平方误差最小的损失函数进行特征属性选取，对输入空间的划分。求解的公式：min[ min∑(yi-c1)² + min∑(yj-c2)²],其中c1和c2为划分的两个空间的平均值，yi和yj分别为两个空间的所有取值。

②分类树：递归地利用基尼指数（Gini index）最小化准则进行特征属性选取，划分输入空间。求解的公式：Gini(p) = ∑pi(1-pi) = 1 - ∑pi²,其中pi表示第i个类别。

（3）优缺点：

①优点：

1.计算量简单，可解释性强.

2.比较适合处理有缺失属性值的样本[4]。（a）选择分裂属性——训练时，去掉此数据，计算去掉后总数据占raw的比例，再乘以计算的熵。（b）验证集时，已经选择了分裂属性，此时导流给左右子树的错误率。（c）训练完成后测试集时，填充缺失值。

3.能够处理不相关的特征

②缺点：1.容易过拟合，但是利用GBDT或随机森林可以缓解

5.K近邻法（K-Nearest Neighbor,KNN）

kd树与决策树的区别[11]

KD树：

提高K近邻法计算效率的一种手段，类似二叉查找树。不过二叉查找树中的数据是一维的，而K近邻的训练样本往往是多维的。所以，在建树的过程中，需要进行特征维度的选择。合理的方式是，每轮递归选择方差最大的特征S作为区分标准，以S的中位数作为根节点。这样能保证寻找最近邻的快速性，构建出均衡的二叉树。

决策树：

① 一种可以直接用来分类的树形结构，这是和KD树单单是为了快速找到最近邻的最大不同。

② 决策树的特征选择，使用了信息论里熵和条件熵的概念，最开始用信息增益（即熵与条件熵之差，信息论里也叫互信息）作为特征S，后来改进为了信息增益比。

③ KD树在建树的过程中会重复使用各维特征，最后树的叶节点最多只会有一个样本；而决策树一般每维度特征只会被用一次，最后树的叶节点就代表类别。

④ 决策树建立后往往要剪枝，防止过拟合。而K近邻法是否过拟合和KD树无关，只和K相关（K越小，越容易过拟合）。

6.支持向量机（Support Vector Machines, SVM）

（1）基本分类器：在特征空间上的间隔最大的线性分类器，使用核技巧可以成为实质性的非线性分类器[5]。

（2）SVM算法思路：

①输入可分训练集T和类别Y；

②构造并带有约束条件【 yi(wx + b) -1 + ξi >=0 】的分离超平面间隔最大的优化问题【 min 1/2·||w||² + C∑ξi】；

③利用数据集代替w和b参数构造第二步中优化问题的对偶问题，利用序列最小优化SMO算法求解仅带有α的最优问题，得到α的解；

④利用α求解w和b的值，得到并输出分离超平面【 wx + b = 0 】和分类决策函数【 f(x) = sign(wx+b) 】

（3）核技巧思路：非线性的输入空间，要通过SVM实现线性分类功能，就需要把非线性的输入空间转化为线性空间；核技巧可以通过一个非线性变换将输入空间对应于一个线性可分的特征空间，从而实现SVM擅长的线性分类问题。

（4）学习算法：

①序列最小优化（Sequential Minimal Optimization, SMO）算法，包括选择变量的启发式方法和求解两个变量的二次规划解析方法。

②算法思路：不断地将原二次规划问题分解为只有两个变量的二次规划问题，并对子问题进行解析求解，知道所有变量满足KKT条件为止。

（5）优缺点：

①优点：（a）有大量的核函数可以使用，从而可以很灵活的来解决各种非线性的分类回归问题[5]；（b）样本量不是海量数据的时候，分类准确率高，泛化能力强。（c）解决高维特征的分类问题和回归问题很有效,在特征维度大于样本数时依然有很好的效果

②缺点：（a）如果特征维度远远大于样本数，则SVM表现一般，（c）SVM在样本量非常大，核函数映射维度非常高时，计算量过大，不太适合使用（d）SVM对缺失数据敏感（f）非线性问题的核函数的选择没有通用标准，难以选择一个合适的核函数

7. 深层神经网络（Deep Neural Networks, DNN）

（1）DNN定义：一种具备至少一个隐藏层的，利用激活函数去线性化，使用交叉熵作损失函数，利用反向传播优化算法（随机梯度下降算法、批量梯度下降算法）进行学习训练（调整并更新神经元之间的权重）的前馈神经网络。

感知器

遇到数据集缺失、漏标签、维数太多、样本不足等问题该如何解决？

特征工程[8]

数据集样本不均衡处理方法：数据的角度和算法的角度[4]

① 数据采样：通过某一种策略改变样本的类别分布，以达到将不平衡分布的样本转化为相对平衡分布的样本的目的，而随机采样是采样算法中最简单也最直观易懂的一种方法。

1.过采样：通过多次有放回随机采样从少数类中抽取数据集E，采样的数量要大于原有少数类的数量，最终的训练集为S_maj+E

2.欠采样：从多数类S_maj中随机选择少量样本E再合并原有少数类样本作为新的训练数据集，新数据集为S_min+E，随机欠采样有两种类型分别为有放回和无放回两种，无放回欠采样在对多数类某样本被采样后不会再被重复采样，有放回采样则有可能

3.过采样和欠采样那个效果好些？

(a). 解决不均衡数据问题的方法中，占主导地位的是过采样，它几乎存在于所有的分析场景中

(b). 过采样应该被用在那些需要完全消除不均衡的情况中，而下采样在只需要从一定程度消除不均衡的情况中的效果可能更好

(c). 与一些传统的机器学习模型不同的是，过采样也不一定会造成卷积神经网络的过拟合

② 代价敏感学习算法：误分类的样本引入不同的权重系数，或者具体地调节先验类别概率。

数据缺失问题

在介绍RF时，Breiman就提出两种解决缺失值的方法[7]：

①(快速简单但效果差)：把数值型变量(numerical variables)中的缺失值用其所对应的类别中(class)的中位数(median)替换。把描述型变量(categorical variables)缺失的部分用所对应类别中出现最多的数值替代(most frequent non-missing value)。以数值型变量为例：