决策树（decision tree）是一种基本的分类与回归方法。

其表示的树型结构，能够觉得是if-else规则的集合。基本的长处是分类可读性好，速度快。

一般会有三个步骤：特征选择、决策树的生成和决策树的修剪。

决策树由结点(node)和有向边(directed edge)组成。结点有两类：内部结点（表示一个特征或者属性）和叶节点（表示一个类或者决策结果）。决策树学习样本集，学习的目标是依据给定的训练数据集构建决策树模型。可以对測试集以及实例进行正确的分类。通常默认。训练集和測试集拥有同样或近似的分布概率模型。

从全部可能的决策树中选取最优决策树是NP全然问题，所以通常採用启示式方法。近似求解这一最优问题。得到的决策树是次最优（sub-optimal）。

因为决策树表示一个条件概率分布，所以深浅不同的决策树相应复杂度不同的概率模型。决策树的生成仅仅考虑局部最优（贪心算法），决策树的剪枝则考虑全局最优。

信息增益和信息增益率

特征选取在于选择对训练数据集具有分类能力的特征，这样能够提高决策树的学习效率。

假设一个特征进行分类的结果与随机分类的结果没有非常大的差别，那这个特征的分类能力非常差或者差点儿没有。

1）信息熵

信息熵是信息论中的基本概念。信息论由Shannon于1948年提出并发展起来，用于解决信息传递过程中的问题，也称统计通信理论。它觉得：

1、信息传递由信源、信道和信宿组成。

2、传递系统存在于一个随机干扰环境中，因此传递系统对信息的传递是随机误差的。假设把发送信息记为U而接收到信息记 V，由信道可记为通信模型。为P(U|V)。

信道模型是一个条件概率矩阵P(U|V)。

在实际通信前。信宿信源会发出什么信息不可能知道。称为信宿对信源状态具有不确定性，因为这样的不确定性是发生在通信之前的。故称为先验不确定性。

在收到信息后的不确定性。称为后验不确定性。

信息是指对不确定性的消除。

Shannon 借鉴了热力学的概念，把信息中排除了冗余后的平均信息量称为“信息熵”。并给出了计算信息熵的数学表达式。变量的不确定性越大，熵也就越大，把它搞清楚所须要的信息量也就越大。

信息熵是信息论中度量信息量的一个概念。

一个系统越有序，它的信息熵越小；反之。一个混乱的系统信息熵越大。能够觉得，信息熵是系统有序化程度的一个度量。

2）信息增益

信息熵又称为先验熵，是在信息发送前信息量的数学期望。后验熵指在信息发送后，从信宿角度对信息量的数学期望。一般先验熵大于后验熵，先验熵与后验熵估差，即所谓的信息增益，反映的是信息消除随机不确定性的程度。

决策树学习中的信息增益等价于训练集中类与特征的互信息。

表示因为特征A而导致训练集不确定性的降低量。信息增益也。特征A对训练集D的信息增益g(D, A)。定义为集合D的经验熵H(D)与特征A给定条件下的经验条件熵H(D|A)之差：

3）信息增益率

信息增益值得大小是相对训练集而言。并没有绝对的意义。

举一个样例。火车的速度能在9s内从10m/s加速到100m/s，可是如今有一辆摩托车能在1s内从1m/s加速到11m/s，尽管加速后摩托车的速度不如火车，可是它拥有和火车等同的加速能力！

在训练集的经验熵大的时候，信息增益值也会偏大，反之信息增益值会偏小。不能反映真实的不确定改善能力。使用信息增益率（information gain ratio）能够对这一问题进行校正。

特征A对训练集D的信息增益率gainRatio(D, A)。定义为其信息增益g(D, A)与训练数据集D的经验熵H(D)之比：

决策树学习之ID3算法

如果一组叶子结点回缩到其父节点之前和之后的损失函数值各自是。且