决策树
决策树（decision tree）是一种分类与回归方法，本文主要讨论用于分类的决策树，决策树的结构呈树形结构，在分类问题中，其代表基于特征对数据进行分类的过程，通常可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型可读性好并且分类速度快。训练的时候，利用训练数据根据损失函数最小化的原则建立决策树模型。
预测时对于新的数据，利用决策树进行分类。决策树的学习通常包括三个步骤：特征选择，生成决策树，对决策树进行剪枝。这些决策树的思想主要来自Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法，以及Breiman等人在1984年提出的CART算法。
用于分类的决策树是一种对数据进行分类的树形结构。决策树主要由节点（node）和有向边（directed edge）组成。节点有两种类型：内部节点（internal node）以及叶节点（leaf node）。内部节点表示一个特征或者属性，叶节点表示一个类。其结构如图所示：
决策树学习采用的是自顶向下的递归方法, 其基本思想是以信息熵为度量构造一棵熵值 下降最快的树,到叶子节点处的熵值为零, 此时每个叶节点中的实例都属于同一类。
- 最大优点: 可以自学习。在学习的过程中,不需要使用者了解过多背景知识,只需要对训练实例进行较好的标注,就能够进行学习。
- 显然,属于有监督学习。
决策树三种生成算法
ID3 — 信息增益 最大的准则
ID3算法的核心是在决策树各个节点上使用信息增益作为特征选择的依据，递归的构建决策树。 从根节点开始，对节点计算所有可能的特征的信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点；再对子节点递归的调用以上方法，构建决策树；知道所有特征的信息增益均很小或没有特征可以选择为止，得到最后一个决策树。ID3相当于用最大似然法进行概率模型的选择。
C4.5 — 信息增益比 最大的准则
C4.5算法使用信息增益率作为特征选择的依据，算法的流程与ID3相似。
CART
- 回归树: 平方误差 最小 的准则
- 分类树: 基尼系数 最小的准则
CART树的名字其实非常有意思，Classification And Regression Tree（分类回归树），它使用基尼系数(Gini Index)作为特征的划分依据。顾名思义，CART既可以用来做分类也可以用来做回归。它是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。 CART树假设我么的决策树是二叉树，内部节点特征的取值为是或否。
CART算法为：
1. 决策树的生成：基于训练数据集生成决策树，生成的决策树要尽量大； 2.决策树剪枝：用验证数据集对已经生成的巨额额数进行剪枝并选择最优子树。
信息熵
信息熵（information entropy） 是度量样本集合纯度的最常用的一种指标。
熵：$H(X)=-\sum_{x \in X} p(x,y)logp(x)$
联合熵：$H(X，Y)=-\sum_{x \in X,y \in Y} p(x,y)logp(x,y)$
条件熵：$H(X|Y)=-\sum_{x \in X,y \in Y} p(x,y)logp(x|y)$
相对熵：$D(p||q)=\sum_x p(x)log\frac{p(x)}{q(x)}$
互信息：$I(x,y)=\sum_{x\in X, y \in Y} p(x,y )log\frac{p(x,y)}{p(x)p(y)}$
决策树学习基本算法
信息增益—$g(D,A)$
信息增益(Information Gain)：表示得知特征A的信息而使得类X的信息的不确定性减少的程度。
定义：特征A对训练数据集D的信息增益g(D, A)，定义为集合D的经验熵H(D)与经验条件熵H(D|A)的差值。
$g(D,A)=H(D)−H(D|A)$
而这又是互信息的定义。所以决策树中的信息增益等价于训练集中类与特征的互信息。
总结：一般而言，信息增益g(D, A)越大，就意味着使用特征A来进行划分所获得的“纯度提升”就越大。著名的ID3决策树学习算法就是以信息增益为准则来学习划分属性的。
增益率
信息率(Information Gain Ratio)： 用信息增益作为划分特征的依据时，会存在一些问题。例如，如果使用数据的ID作为特征，这样，每个数据点相当于均匀分布，所以得到的信息增益一定是最大的，但是我们都知道ID是不能作为特征的。这样如果单纯的使用信息增益作为划分特征的依据的话，会导致我们生成的树比较矮胖，容易过拟合。
定义：特征A对训练数据集D的信息增益率$$gR(D,A)$$定义为其信息增益$$g(D,A)$$与训练数据集D关于特征A的值得信息熵$$IV(D)$$之比：
$ gR(D,A)=\frac {g(D,A)}{IV(D)} $
总结：信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的C4.5决策树算法就不直接使用信息增益而是使用“增益率” 。
Gini系数：
数据集P的纯度可以用Gini值来度量。
$Gini(P)=\sum_{k=1}^K p_k(1-p_k)=1-\sum_{k=1}^Kp_k^2$
总结：CART决策树使用Gini指数来选择划分属性。$Gini(P)$反映了从数据集D中随机抽取了两个样本，其类别标记不一致的概率，因此，$Gini（D）$越小，则数据集P的纯度就越高。
决策树的评价 —— loss function：
假定样本的总类别数为$K$个；树T的叶节点个数为$\mid T \mid$，t是树T的叶节点，叶节点有$N_t$个样本点，其中$k$类的样本点有$N_{ik}$个，$H_t(T)$为叶节点t上的经验熵，则决策树的loss function可以定义为：
$C_a(T)=\sum_{t\in Leaf}N_tH_t(T)+a|T|$
决策树种避免过拟合的方法——剪枝
- 预剪枝：在决策树生成过程中，对每个结点在划分前先进行估计，如果当前的结点划分不能带来决策树泛化性能提升，则停止划分并将当前的结点标记为叶节点。
- 后剪枝：先从训练集生成一个完整的决策树，然后自底向上的对非叶节点进行考察，若将该结点对应的子树替换为叶节点能带来决策树泛化能力性能提升，则就把该子树替换为叶结点。
在上面决策树的评价指标loss function ：$C_a(T)=\sum_{t\in Leaf}N_tH_t(T)+a|T|$中，
C(T)表示模型对训练数据集的预测误差，即模型与训练数据的拟合程度，
$\mid T \mid$表示模型复杂度，由参数α控制两者之间的影响。
当α确定时：
- 子树越大，与训练集的拟合越好，但模型的复杂度就越高；
- 子树越小，模型简单，但与训练集的拟合度不好。
决策树生成学习局部的模型，而剪枝学习整体的模型!
剪枝的过程为：
- 计算每个节点的经验熵；
- 递归的从树的叶节点向上回缩，设一组叶节点回缩到其父节点之前和之后的整体树分别为$T_B$和$T_A$，对应的损失函数值分别为$C_α(T_B)$和$C_α(T_A),$如果$C_α(T_A)<=C_α(T_B)$，则进行剪枝。
决策树的优缺点
- 优点: 决策树对训练属于有很好的分类能力
- 缺点: 但对未知的测试数据未必有好的分类能力,泛化 能力弱,即可能发生过拟合现象。
Bagging（套袋法）
bagging的算法过程如下：
- 从原始样本集中使用Bootstraping方法随机抽取n个训练样本，共进行k轮抽取，得到k个训练集。（k个训练集之间相互独立，元素可以有重复）
- 对于k个训练集，我们训练k个模型（这k个模型可以根据具体问题而定，比如决策树，knn等）
- 对于分类问题：由投票表决产生分类结果；对于回归问题：由k个模型预测结果的均值作为最后预测结果。（所有模型的重要性相同）
Boosting（提升法）
boosting的算法过程如下：
- 对于训练集中的每个样本建立权值wi，表示对每个样本的关注度。当某个样本被误分类的概率很高时，需要加大对该样本的权值。
- 进行迭代的过程中，每一步迭代都是一个弱分类器。我们需要用某种策略将其组合，作为最终模型。（例如AdaBoost给每个弱分类器一个权值，将其线性组合最为最终分类器。误差越小的弱分类器，权值越大）
Bagging，Boosting的主要区别
样本选择上：
Bagging采用的是Bootstrap随机有放回抽样；
Boosting每一轮的训练集是不变的，改变的只是每一个样本的权重。
样本权重：
Bagging使用的是均匀取样，每个样本权重相等；
Boosting根据错误率调整样本权重，错误率越大的样本权重越大。
预测函数：
Bagging所有的预测函数的权重相等；
Boosting中误差越小的预测函数其权重越大。
并行计算：
Bagging各个预测函数可以并行生成；
Boosting各个预测函数必须按顺序迭代生成。
决策树与这些算法框架进行结合所得到的新的算法：
1）Bagging + 决策树 = 随机森林
2）AdaBoost + 决策树 = 提升树
3）Gradient Boosting + 决策树 = GBDT
随机森林（Random Forests）
随机森林是一种重要的基于Bagging的集成学习方法，可以用来做分类、回归等问题。
随机森林有许多优点：
- 具有极高的准确率
- 随机性的引入，使得随机森林不容易过拟合
- 随机性的引入，使得随机森林有很好的抗噪声能力
- 能处理很高维度的数据，并且不用做特征选择
- 既能处理离散型数据，也能处理连续型数据，数据集无需规范化
- 训练速度快，可以得到变量重要性排序
- 容易实现并行化
随机森林的缺点：
- 当随机森林中的决策树个数很多时，训练时需要的空间和时间会较大
- 随机森林模型还有许多不好解释的地方，有点算个黑盒模型
随机森林构建过程
与上面介绍的Bagging过程相似，随机森林的构建过程大致如下：
- 从原始训练集中使用Bootstraping方法随机有放回采样选出m个样本，共进行n_tree次采样，生成n_tree个训练集
- 对于n_tree个训练集，我们分别训练n_tree个决策树模型
- 对于单个决策树模型，假设训练样本特征的个数为n，那么每次分裂时根据信息增益/信息增益比/基尼指数选择最好的特征进行分裂
- 每棵树都一直这样分裂下去，直到该节点的所有训练样例都属于同一类。在决策树的分裂过程中不需要剪枝
- 将生成的多棵决策树组成随机森林。对于分类问题，按多棵树分类器投票决定最终分类结果；对于回归问题，由多棵树预测值的均值决定最终预测结果
