决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果[1]
下面先来看一个小例子，看看决策树到底是什么概念：
决策树的训练数据往往就是这样的表格形式，表中的前三列（ID不算）是数据样本的属性，最后一列是决策树需要做的分类结果。通过该数据，构建的决策树如下：
显然，在每一个非叶节点选择哪一个特征作为分支的标准，是构建决策树的核心问题。
信息熵
信息熵就是解决我们上面标准选择问题的一个重要指标。
一方面，熵是一个用来形容系统混乱程度的物理量。假设有135个点分布在二维平面上，并且这些点分别属于两类。分布如下：
假设两种类别的点（Rreen和Ged）分别有70和65个，概率分布如下：
| X | G | R |
|---|---|---|
| P |
从中随机选择一个点，得到两种类别的点的概率很相近，整个系统是一个完全混乱的整体。
假设我们按照图中的方式将所有的点一分为。左侧有65个点，其中60个为Green，5个为Red，则概率分布如下：
| X | G | R |
|---|---|---|
| P |
我们再在左侧的点中随机选择，显然属于Green的概率要大很多，在预测的时候，预测Green的正确率就高很多。
从两种情况的混乱程度来看，第一种情况比第二种情况要混乱很多，这种混乱程度和不同类别的概率有关。
另一方面，一个事件发生所包含的信息量和这个事件发生的概率有关的，即一个事件发生的概率越小，这个事件包含的概率就越大。比如学校每天正常八点响铃，但是如果某一天八点没有响铃，没有响铃这个小概率事件包含的信息，明显比正常响铃这个大概率事件多。
因此，概率分布就把一个事件发生所传递的信息和熵联系起来了，这种熵就称为信息熵。
信息熵的定义
假设变量的取值包含
，概率分布如下：
| X | … | |||
|---|---|---|---|---|
| P | ... |
那么X包含的信息熵定义为：
条件熵
：
发生所包含的熵，减去
发生所包含的熵：即在X发生的前提下，Y的发生所带来的新的熵，就是X发生的条件下，Y发生的条件熵
。
接下来推导的计算公式：
相对熵
相对熵又称为互熵，交叉熵，鉴定信息，Kullback熵等。
设和
是X中取值的两种概率分布，则p对q的相对熵是：
互信息
两个随机变量的互信息，定义为X，Y的联合分布和独立分布乘积的相对熵。
从公式可以看出，互信息其实度量的是和
这两个概率分布的距离。如果X和Y的分布是完全独立的，就会有
。代入公式就可以得到两个变量的互信息为0。
如果我们用减去
：
互信息的物理意义
从上面的推到，我们可以得到等式：
也可以得到不等式：
，
也就是说，只要X和Y不是完全独立，而是存在某些联系，那么只要在给定其中一个做为条件的情况下，另一个事件所包含的信息量都会减少。
这些物理量的关系可以整理成一个Venn图：
决策树的构建
再来看上面的例子：
在根结点中，是否偿还债务的概率分布为：
| 是否偿还债务 | 是 | 否 |
|---|---|---|
| P | 7 | 3 |
信息熵：
在根据是否拥有房产进行划分之后：
拥有房产的部分：
| 是否偿还债务 | 是 | 否 |
|---|---|---|
| P | 3 | 0 |
信息熵：
没有房产的部分：
| 是否偿还债务 | 是 | 否 |
|---|---|---|
| P | 4 | 3 |
信息熵：
我们考虑分支前后的熵的变化，对分支之后的熵求加权平均，计算可得：
显然这应该是一次有效的分支，因为熵变小意味着整体变得更加有序。从分类的直观效果来看，对于有房产的样本，可以直接判断为可以偿还债务。而且很容易理解，熵下降得越快，分支就越有效。
决策树学习
决策树学习采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶节点处的熵值为零，此时每一个叶节点中的实力都属于同一类。
实际过程中我们通常会采用一些剪枝的策略，来避免熵值为零的情况，因为熵值为零通常意味着对训练数据的过拟合。
建立决策树的关键，即为在当前状态下选择哪一个属性作为分类依据。根据不同的目标函数，建立决策树主要有以下三种算法：
- ID3
- Iterative Dichotomiser
- C4.5
- CART
- Classification and Regression Tree
信息增益
当熵和条件中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵和条件熵分别分别称为经验熵和经验条件熵。
信息增益表示得知特征A的信息而使得类X的信息的不确定性减少的程度。
定义：特征A对训练数据集D的信息增益，定义为集合D的经验熵
和特征A给定条件下D的经验条件熵
之差。
其他目标
信息增益率：
-
Gini系数
三种决策树的学习策略
- ID3：使用信息增益、互信息
进行特征选择
- 取之多的属性，更容易使得数据更纯，起信息增益更大
- 训练得到的是一棵庞大且深度浅的树，不合理
- C4.5：信息增益率
- CART：基尼系数
