-
任务：
给定训练数据集：$D={(x_1, y_1), (x_2, y_2),...,(x_n,y_n)}$，其中$x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^T$为输入实例特征向量，n为特征个数，$y_i\in{1,2...K}$为类标记，给这些数据通过建立决策树模型进行分类
-
特征选择：选取对训练数据具有分类能力的特征
(1).信息增益算法：
熵：用于度量随机变量不确定性，假定有随机变量$X$以及概率分布$P(X=x_i)=p_i,\qquad i=1,2,...n$ $$ H(X)=-\sum_{i=1}^np_i\log{p_i} $$ 假设某个服从伯努利分布的随机变量X，其概率分布如下： $$ P(X=0)=p\ P(X=1)=1-p $$ 这个分布的熵为： $$ H(X)=-p\log{p}-(1-p)\log{(1-p)} $$ 可以算出，当p=0或者1时，随机变量X没有不确定性；当p=0.5时，不确定性最大。
条件熵：给定随机变量X的条件下随机变量Y的不确定性，用$H(Y|X)$表示，定义为给定X的条件下Y的条件概率分布的熵对X的数学期望。 $$ H(Y|X)=\sum_{i=1}^np_iH(Y|X=x_i)，其中p_i=P(X=x_i),\qquad i=1,2,...n $$ 推导： $$ \begin{aligned} H(Y|X)&=\sum_{x\in X}P(x)H(Y|X=x)\ &=-\sum_{x\in X}P(x)\sum_{y\in Y}P(y|x)\log P(y|x)\ &=-\sum_{x\in X}\sum_{y\in Y}P(x, y)\log{p(y|x)} \end{aligned} $$ 当概率分布是从数据中估计得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵。
信息增益：表示得特征X的信息而使得Y信息的不确定性减少的程度 $$ g(D, A)=H(D)-H(D|A) $$
信息增益比：信息增益偏向于划分特征较多的特征值，信息增益比可以校正这一问题。 $$ g_R(D, A)=\frac{g(D, A)}{H_A(D)} $$ 其中，$H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{D}\log_2{\frac{|D_i|}{D}}$
-
决策树生成(ID3算法)：
给定训练集D，特征集A和阈值$\epsilon$，输出决策树T
- 若D中所有实例属于同一类$C_k$，则T为单节点树，并将类$C_k$作为该结点的类标记，返回T
- 若A为空集，则T为单节点树，并将D中实例数最大的类$C_k$作为该结点的类标记，返回T
- 否则计算A中各特征的信息增益，选择信息增益最大的特征$A_g$
- 如果$A_g$的信息增益小于阈值$\epsilon$,则置T为单节点树，并将D中实例最大的类$C_k$作为该结点的类标记，返回T
- 否则对$A_g$的每一可能值$a_i$，依$A_g=a_i$将D分隔为若干非空子集$D_i$，将$D_i$中实例数最大的类作为标记，构建子节点，由节点及其子节点构成树T，返回T
- 对第i个子节点，以$D_i$为训练集，以$A-{A_g}$为特征集，递归调用上面步骤得到子树$T_i$，返回$T_i$
-
除此之外还有C4.5算法，是ID3算法的升级版，与ID3算法不同的是，C4.5算法采用的是信息增益比
-
决策树剪枝算法：
由于决策树生成算法过多地考虑如何提高对训练数据的正确分类，从而构建过于复杂的决策树，这样产生的决策树往往对训练数据的分类很准确，却对未知的测试数据的分类没有那么准确，即出现过拟合现象。我们需要对已生成的决策树进行简化，这个简化的过程我们称之为**剪枝(pruning)。**具体就是剪掉一些不重要的子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型。剪枝的目的就是得到最优的决策树模型。这个模型不仅对训练训练数据有很好的分类，对预测数据也能很好地预测。
-
简单决策树剪枝算法：
-
设树T的叶节点个数为|T|，t是树T的叶节点，该叶节点有$N_t$个样本点，其中k类的样本点有$N_{tk}$个，$H_t(T)$为叶节点t上的经验熵，$\alpha\geq0$是参数，则决策树学习的损失函数为： $$ C_{\alpha}(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T| $$ 其中叶节点的经验熵$H_t(T)=-\sum_k\frac{N_{tk}}{N_t}\log{\frac{N_{tk}}{N_t}}$，记损失函数第一项为：$C(T)=\sum_{t=1}^TN_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^KN_{tk}\log{\frac{N_{tk}}{N_t}}$，这样损失函数可以表示为： $$ C_{\alpha}(T)=C(T)+\alpha|T| $$
-
这样求损失的基本想法：每个叶节点所分的类别不都相同，求每个叶节点的经验熵是想保持每个叶节点的纯度，尽量保证每个被分类的集合中，都是同一类数据
-
算法流程：
-
计算每个节点的经验熵
-
递归地从叶节点向上回缩，
设一组叶节点回缩到其父节点之前和之后的树为$T_B$和$T_A$，若剪枝后的损失更小，则剪枝；否则不剪枝
-
重复上述步骤直至不能继续为止
-
-
-
-
CART算法：
注意CART算法生成的二叉树
-
基尼系数： $$ \begin{aligned} Gini(D)&=\sum_{i=1}^nP(x_i)(1-P(x_i))\ &=1-\sum_{i=1}^nP(x_i)^2 \end{aligned} $$ 对于样本集合D，根据特征A是否可能是a将集合D分成两部分$D_1, D_2$，在属性A的条件下，样本集合D的基尼系数为： $$ Gini(D|A=a)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2) $$
-
回归树的生成：
-
假设X与Y分别是输入和输出变量，Y是连续变量，给定训练数据集 $$ D={(x_1, y_1), (x_2, y_2),...,(x_n, y_n)} $$ 一颗回归树对应着输入空间的一个划分单元上的输出值，假设已经将输入空间划分成M个单元$R_1,R_2,...R_M$，并且在每个单元上固定输出值$c_m$，于是回归树模型可以表示为： $$ f(x)=\sum_{m=1}^Mc_mI(x\in R_m) $$ 当输入空间固定时，可以用平方误差$\sum_{x_i\in R_m}(y_i-f(x_i))^2$来表示回归树对预训练数据的预测误差，用平方误差最小准则求解每个单元上最优的输出值，单元$R_m$上的$c_m$的最优值为所有输入实例$x_i$对应的输出均值： $$ c_m=ave(y_i|x_i\in R_m) $$ 对输入空间的划分采用启发式方法，选择第j个变量$x^{(j)}$和它的取值s，作为切分变量和切分点，并定义两个区域： $$ R_1(j,s)={x|x^{(j)}\leq s}和R_2(j,s)={x|x^{(j)}>s} $$ 具体求解： $$ \min_{j,s}[\min_{c_1}\sum_{x_i\in R_1(j, s)}(y_i-c_1)^2+\min_{c_2}\sum_{x_i\in R_2(j, s)}(y_i-c_1)^2] $$ 其中： $$ \hat{c_1}=ave(y_i|x_i\in R_1(j,s ))和\hat{c_2}=ave(y_i|x_i\in R_2(j,s)) $$ 即遍历特征j和切分点s，找到使得上面式子成立的(j, s)
然后求出当前最优切分点的输出值$c_m$，继续对两个子区域继续调用上述步骤，直至不能再切分了，即可得到决策树。
-
-
分类树的生成：
- 对于数据集D和特征A，通过遍历A的每个可能的取值a，将数据集D划分成两部分$D_1$和$D_2$
- 计算每一个特征的每一个取值的基尼指数，选取最优特征和最优切分点，从现节点生成两个子节点，将训练数据依特征分配到两个子节点中去
- 递归调用上述步骤，直至不能继续切分，然后生成决策树
-
CART树剪枝：
-
决策树的损失函数为： $$ C_\alpha(T)=C(T)+\alpha|T| $$ 参数$\alpha$衡量训练数据的拟合程度与复杂度，当$\alpha$固定时一定存在使得损失函数$C_\alpha$最小的最优子树
-
当$\alpha$取值越大时，最优子树偏向于越简单(叶节点少)；当$\alpha$取值越小时，最优子树偏向于越复杂；极端情况：$\alpha=0$时最优子树就是本身；$\alpha=\infty$时，最优子树就是根节点构成的单节点树
-
剪枝是对决策树的非叶节点剪枝的，对于每个非叶节点来说，需要将剪枝前后子树的损失进行对比，为了便于计算，其实不用将整棵树剪枝前后的损失函数对比，而是以当前剪枝的非叶节点t为根的子树和将该结点剪枝后即合并后的单节点树来进行对比，记以t为根节点的子树为$T_t$和单节点树为t，其损失分别是：$C_\alpha(t)=C(t)+\alpha$和$C_\alpha(T_t)=C(T_t)+\alpha|T_t|$然后它们进行比较：
- 当$\alpha$为0时，$C_\alpha(T_t)<C_\alpha(t)$
- 当$\alpha$增大到一定程度时，某一$\alpha$满足$C_\alpha(T_t)=C_\alpha(t)$
- 当$\alpha$再增大时，不等式反向，$C_\alpha(T_t)>C_\alpha(t)$
对两个损失作差，$g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}$对应着剪枝后$\alpha$减少的程度，上面提到，当$\alpha$增大到某一程度时$C_\alpha(T_t)=C_\alpha(t)$，此时到达阈值，即剪不剪枝损失都一样
剪枝的主要思路是，对于原始决策树$T_0$，先剪枝一棵子树，生成子树$T_1$，然后再从$T_1$中剪去子树得到$T_2$，直到最后只剩下根节点，然后再从${T_0,T_1,...T_n}$中挑选最优子树$T_i$，一般采用交叉验证，使用预测验证集效果最好的树作为最终模型；然而每棵树怎么剪，剪哪个节点如何决定呢？首先遍历决策树中所有非叶节点，计算它们的g(t)，也就是假设剪去这些节点之后，决策树总体的损失减少的程度，也就是g(t)，g(t)是个临界值，当$\alpha$取值为g(t)时损失函数不变，然后从这些非叶节点中挑选一个损失减少最小的节点剪枝得到$T_i$。
-
剪枝算法：
-
设k=0,$T=T_0$
-
设$\alpha=\infty$
-
遍历决策树叶节点计算内部的g(t) $$ g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}\ \alpha=min(\alpha, g(t)) $$
-
遍历内部节点，如果有$\alpha=g(t)$的节点t，则进行剪枝，得到新的树T
-
设k=k+1，$\alpha_k=\alpha,T_k=T$
-
如果T不是由根节点单独构成的树，则回到步骤2
-
采用交叉验证法在子树序列中选取最优子树
-
-
-
-
主要思想：根据数据集不同的划分，独立训练多个基分类器，然后利用(投票法、平均法)集成起来
Bagging是Bootstrap aggregating的缩写，名副其实，这两字也就代表了Bagging方法的主要步骤：
- Bootstrap意为自助法，它是一种统计学上的数据抽样方法，指从一个给定的数据集合中有放回的均匀抽样。Bagging通过在原始训练集上进行自助法抽样构造出一系列子训练集，并在这些子训练集上训练原始的弱模型。在比较理想的条件下，即原始训练集不仅独立同分布，而且足够大以至于能够捕获足够多的的真实数据的复杂性，那么自助法抽样而来的子训练集也就同样可以看做是真实分布的良好近似。其中一种比较有意思的抽样方法是632自助法，即从含d个样本的原始数据集合中有放回地抽样d次产生同样含d个样本的子数据集，那么一个原始数据集中的样本在子数据集中不出现的概率就是
$(1-\frac{1}{d})^d$ ，当d足够大时，借助重要极限$\lim_{x\rightarrow\infty}(1+\frac{1}{x})^x=e$ ，有概率为$e^{-1}=0.368$ ，即子数据集中的去重样本约占原始数据集合中的$63.2%$ 。 - Aggregation，在每个子训练集上学习得到的一批弱模型通过确定性的平均过程来得到最终的输出，如对分类问题的多数投票，或概率性的输出，回归问题的取平均。
我们可以看到Bagging方法的重点就在于通过自助法抽样构造数据子集，这使得每个弱模型看到的数据几乎都是不一样的，如果我们能在此之上继续控制每个弱模型的过拟合程度，那么可想而知这些弱模型聚集得到的强模型的过拟合程度只会更低。这里需要注意的一点是，如果我们把之前在原始训练集上学习得到的单个弱模型预测错误的样本分为两类：一类是因为模型不认识当前的数据而犯的错（可以理解为方差），另一类是模型本身能力所限，处理不了这样的数据而犯的错（可以理解为偏差），那么Bagging方法得到的强模型之所以强，只是因为它改善了第一种情形，使集成模型在面对没见到过的数据的时候犯错的时候少了，换言之也就是鲁棒性更强了，方差更小了，第二种情形不是它的初衷也不是它所能解决的。
Random Forest随机森林：
- 从原始样本中采取有放回抽样的方法选取n个样本；
- 对n个样本选取a个特征中的随机k个，用建立决策树的方法获得最佳分割点；
- 重复m次，获得m个决策树；
- 对输入样例进行预测时，每个子树都产生一个结果，采用多数投票机制输出。
随机森林的随机性主要体现在两个方面：
- 数据集的随机选取：从原始的数据集中采取有放回的抽样（bagging），构造子数据集，子数据集的数据量是和原始数据集相同的。不同子数据集的元素可以重复，同一个子数据集中的元素也可以重复。
- 待选特征的随机选取：与数据集的随机选取类似，随机森林中的子树的每一个分裂过程并未用到所有的待选特征，而是从所有的待选特征中随机选取一定的特征，之后再在随机选取的特征中选取最优的特征。
以上两个随机性能够使得随机森林中的决策树都能够彼此不同，提升系统的多样性，从而提升分类性能。
随机森林的优点：
- 实现简单，训练速度快，可以并行实现，因为训练时树与树之间是相互独立的；
- 相比单一决策树，能学习到特征之间的相互影响，且不容易过拟合；
- 能处理高维数据（即特征很多），并且不用做特征选择，因为特征子集是随机选取的；
- 对于不平衡的数据集，可以平衡误差；
- 相比SVM，对特征缺失不敏感，因为待选特征也是随机选取；
- 训练完成后可以给出哪些特征比较重要。
随机森林的缺点：
- 在噪声过大的分类和回归问题还是容易过拟合；
- 相比于单一决策树，它的随机性让我们难以对模型进行解释。
主要思想：串行训练基分类器，基分类器之间相互依赖，每训练完一个分类器之后，调整权重然后训练下一个。
同样地，如果说在原始数据集上学习到的单个模型地预测错误分为两类：方差和偏差，Bagging着力解决的是第一点，方法是自助法构造出不同的子数据集，那么Boosting则将目光放在了降低偏差上，它是怎么做的呢？
我们先来看一下偏差是如何产生的，如果我们把目光放到训练数据上，可以粗略的这么认为：训练误差所代表的的就是因模型能力所限，无法处理样本，训练得到的模型在进行预测时，遇见与引入训练误差相似的样本同样无法处理，这部分错误就可以近似地看做偏差。理解了偏差的来源，那么可以理解只要在保证方差的约束下尽可能地降低训练误差，偏差就会自然地降低，Boosting的方法就是如此。
Boosting又是如何降低训练误差呢？那就是“因材施教，重点辅导”，逐步把更多的注意力放到之前没处理好的样本上。也就是顺序地学习一系列模型，在学习当前模型时把重点放在解决之前模型所没解决好的样本上，以更大的可能性解决好之前错误的样本，具体来看有两种常用方法：
- 自适应提升AdaBoost(Adaptive Boosting)，它通过增加错误样本点的权重系数，同时减小正确样本点的权重系数来对误差函数进行影响，从而使得模型将学习重点放到权重系数更大的样本数据上。不仅如此，AdaBoost采用加权多数表决，为顺序学得的每个弱模型赋上一个与误差负相关的模型权重系数，让误差率更低的弱模型表达更多的意见，然后将模型输出的加权和作为集成模型的输出。
- 梯度提升Gradient Boosting，不同于AdaBoost通过改变样本的权重系数来分配注意力，Gradient Boosting则是通过改变样本的目标值来实现同样的目的。Gradient Boosting可以形象地看做“接力赛”，通过顺序地学习出一系列的模型来逐步地逼近真实目标值。我们知道，在给定任意可微误差函数的条件下，有一种简单的优化方法，即最速下降法：沿着负梯度的方向更新参数，那么对于可微损失函数
$L(y, f(x))$ 来说，我们欲逐步逼近真实目标值等价于逐步使得经验损失函数最小化，那么怎么是它逐步减小呢，就需要使得$f(x)$ 沿着$L(y, f(x))$ 负梯度的方向变化，这样得到的新模型$f'(x)$ 才能使得经验损失函数更小。归纳来看，Gradient Boosting的关键点在于每次针对损失函数的负梯度来构建弱模型（也就是对该样本的负梯度值为新的目标值），然后将这个学习到的弱模型作为加法模型的最新一项集成到加法模型中来，顺序地构造弱模型，直到满足阈值或其它停止条件。
Adaboost算法：
-
每个样本都有各自的权重，首先各个样本点的权重初始化为$\frac{1}{N}$，其中N表示样本数量
- 初始化权重分布为：$D_1=[\frac{1}{n},\frac{1}{n},...,\frac{1}{n}]$
-
循环M次
-
使用第m次的权重分布$D_m$来学习一个基分类器：$G_m(x)$
- 利用现有数据集和数据权重构造误差率最小的分类器，误差率是用来计算误差率的
-
计算本次基分类器在训练集X和权重$D_m$上的误差率$e_m$，也就是分类错误的权值之和 $$ e_m=\sum_{i=1}^NP(G_m(x_i\not=y_i))=\sum_{i=1}^Nw_{mi}I(G_m(x_i)\not=y_i) $$
-
计算$G_m(x)$的系数： $$ \alpha_m=\frac{1}{2}\log{\frac{1-e_m}{e_m}} $$
-
更新训练集的权值分布： $$ w_{(m+1),i}=\frac{w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i)) $$ 其中$Z_m$是归一化因子： $$ Z_m=\sum_{i=1}^Nw_{mi}exp(-\alpha_my_iG_m(x_i)) $$
-
-
最终的分类器为：$G(x)=sign(\sum_{m=1}^M\alpha_mG_m(x)$
-
Adaboost可以看做是加法模型，采取的损失函数为指数损失函数，通过前向分步算法推导出来的；0-1损失函数可以使用数学性质更好的指数损失函数来替代
BDT：Boosting Decision Tree(提升树)，即采用加法模型，前向分步算法，并且以决策树为基分类器的模型
GBDT:Gradient Boosting Decision Tree(梯度提升树)，即采用梯度下降法的提升树模型
Stacking堆叠法的组合方式是通过训练一个新的元模型来将一系列弱模型组合起来，这个元模型以弱模型的输出为输入，以样本的真实值为目标值，它输出即为最终输出。为了训练这样一个元模型，通常还需要将训练集分成不同的两份，在其中一份上训练原始的弱模型，在另一份上训练元模型，当然可以借鉴k-折交叉验证的方法，在k-1折数据上训练弱模型，在剩余数据上训练元模型。在实际应用中，考虑到数据量和模型类别，通常堆叠的层数不会太多。