表示得知特征X的信息而使得类Y的信息的不确定性减少的程度
大致步骤：
给定训练数据集D和特征A，经验熵H(D)表示对数据集D进行分类的不确定性。而经验条件熵H(D|A)表示在特征A给定的条件下对数据集D进行分类的不确定性。那么它们的差，即信息增益，就表示由于特征A而使得对数据集D的分类的不确定性减少的程度。显然，对于数据集D而言，信息增益依赖于特征，不同的特征往往具有不同的信息增益。信息增益大的特征具有更强的分类能力。
-
决策树
是什么？
描述对实例进行分类的树形结构
本质是：从训练数据集种归纳出一组分类规则，与训练数据集不想矛盾的决策树（即能对训练数据进行正确分类的决策树）可能有多个，也可能一个也没有。
决策树的生成只考虑局部最优，剪枝考虑全局最优
损失函数：通常是正则化的极大似然函数。
学习步骤
特征选择
选择的准则是：信息增益或信息增益比
信息增益
熵
条件熵
经验熵和经验条件熵
互信息
熵：表示随机变量不确定性的度量
条件熵：在已知随机变量X的条件下随机变量Y的不确定性
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵和经验条件熵
熵与条件熵之差称为互信息。决策树学习中的信息增益等价于训练数据集中类与特征的互信息
信息增益比
利用信息增益作准则存在偏向于“偏向于选择取值较多的特征”问题
定义
信息增益g（D，A）与训练数据集D关于特征A的值的熵Ha（D）之比
HA(D)为训练集D关于特征A的值的熵，n是特征A的取值个数。
决策树的生成
ID3：ID3的核心是在各个结点上应用“信息增益”准则选择特征。
从根结点出发，选择信息增益最大的特征作为结点特征，由该特征的不同取值建立子结点，对子结点递归调用以上方法。直到所有特征的信息增益均很小（设一个阈值ε）或没有特征可选为止。
C4.5：对ID3算法进行了改进，生成过程中用信息增益比来选择特征。
ID3:信息增益
C4.5:信息增益比
决策树的剪枝
剪枝
学习时过多地考虑如何提高对训练数据的正确分类，从而构建出过于复杂的决策树（过拟合）。
解决办法是考虑决策树的复杂度，对已生成的树进行简化，这一过程称为剪枝（pruning）。
具体地，从树上裁掉一些子树或叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型。
决策树的损失函数
“决策树生成”只考虑了通过提高信息增益（或信息增益比）对训练数据进行更好的拟合。而“决策树剪枝”通过优化损失函数，还考虑了减小模型复杂度。“决策树生成”学习局部的模型，而“决策树剪枝”学习整体的模型。
CART
CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布。CART算法分为两步：
（1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大。
（2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。
生成树
回归树：平方误差最小化，分类树：基尼指数
Gini值越大，样本集合的不确定性也越大（与熵类似）
剪枝
形成一个子树序列
通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。