决策树（Decision tree）是基于已知各种情况（特征取值）的基础上，通过构建树型决策结构来进行分析的一种方式，是常用的有监督的分类算法。

决策树是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点代表一种分类结果。

其中第8行伪代码，从A中选择最优划分属性，有以下几种算法。

ID3算法

ID3算法通过选择信息增益最大的特征进行节点分裂。

信息熵
信息熵是度量样本纯度的最常用的指标之一。假定当前样本集合$D$中第$k$类样本所占比例为$p_k （k=1,2,…,|y|）$，则$D$的信息熵定义为
$$Ent(D) = - \sum_{k=1}^{|y|}p_k log_2p_k$$

$Ent(D)$的值越小，则$D$的纯度越高

信息增益：

由于不同分支节点所包含的样本数不同，给分支节点赋予一个权重$\frac{|D^v|}{|D|}$，即样本数越多的分支节点影响越大，于是可计算出用属性$a$对样本集$D$进行划分所获得的“信息增益”
$$Gain(D,a) = Ent(D) - \sum_{v=1}^{V} \frac{|D^v|}{|D|} Ent(D^v)$$

一般而言，信息增益越大，则意味着使用属性$a$来进行划分所获得的纯度提升越大。

在ID3算法中，选择属性即为：$a_* = arg\ max\ Gain(D, a)$

C4.5算法

信息增益有一个问题，它偏向取值较多的特征。原因是，当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分之后的熵更低，由于划分前的熵是一定的。因此信息增益更大，因此信息增益比较偏向取值较多的特征。

信息增益率
信息增益率相比信息增益，多了一个衡量本身属性的分散程度的部分作为分母，而著名的决策树算法C4.5就是使用它作为划分属性挑选的原则。

$$Gain_ratio(D,a) = \frac{Gain(D,a)}{IV(a)}$$
其中
$$IV(a) = - \sum_{v=1}^{V}\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}$$

在C4.5算法中，选择属性即为：$a_* = arg\ max\ Gain_ratio(D,a)$

CART算法

CART是分类与回归树（classification and regression tree），其与C4.5算法一样，由ID3算法演化而来。

CART假设决策树是一个二叉树，它通过递归地二分每个特征，将特征空间划分为有限个单元，并在这些单元上确定预测的概率分布。

CART在分类和回归任务中都可用。对于回归树，采用的是平方误差最小化准则；对于分类树，采用基尼指数最小化准则。

基尼指数：在分类问题中，假设有$K$个类别，样本点属于第k类的概率为$p_k$，则概率分布的基尼指数定义为
$$Gini(p) = \sum_{k=1}^{K} p_k(1-p_k) = 1 - \sum_{k=1}^{K} p_k^2$$

直观的来说，$Gini(D)$反映了从数据集$D$中随机抽取两个样本，其类别标记不一致的概率。因此，$Gini(D)$越小，则数据集$D$纯度越高。

属性$a$的基尼指数定义为：
$$Gini_index(D, a) = \sum_{v=1}^{V} \frac{|D^v|}{|D|}Gini(D^v)$$
因此我们在选取属性时，选择使得划分后基尼指数小的属性作为最优划分属性，即
$$a_* = arg\ min \ Gini_index(D,a)$$