决策树(decision tree)是一种基本的分类与回归方法。决策树模型呈树形结构，在分类问题中，表示基于特征对实例进行分类的过程。它可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。其主要优点是模型具有可读性，分类速度快。学习时，利用训练数据，根据损失函数最小化的原则建立决策树模型。预测时，对新的数据，利用决策树模型进行分类。决策树学习通常包括3个步骤:特征选择、决策树的生成和决策树的修剪。这些决策树学习的思想主要来源于由Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法，以及由Breiman等人在1984年提出的CART算法。

便于理解，首先介绍熵和条件熵的概念。

熵：在信息论和概率统计中，熵是表示随机变量不确定的度量，通常称为信息熵。设随机变量X服从的概率分布为

P(X=x_i) = p_i, i=1,2,3,\dots,n

则其熵定义为

H(X) = -\sum_{i=0}^{n} p_i log(p_i)

设有随机变量(X,Y)，其联合概率分布为

P(X=x_i,Y=y_j) = p_{ij}, i=1,2,3,\dots,n;j=1,2,3,\dots,m

条件熵：H(Y|X)表示在已知随机变量X的条件下，随机变量Y的不确定性。定义为

H(Y|X) = \sum_{i=0}^{n}p(x_i) H(Y|X=x_i)

当熵和条件熵中的概率有数据估计得到时，所对应的熵和条件熵分别为经验熵和经验条件熵。

ID3

信息增益：特征A对训练集D的信息增益g(D,A)定义为D的经验熵H(D)与特征A给定的条件下D的经验条件熵H(D|A)之差

g(D,A)=H(D)-H(D|A)

ID3算法的特征选择思想是选择信息增益最大特征。缺点：倾向于选择多取值的特征。

C4.5

C4.5针对ID3的缺点进行了改进，采用信息增益比来选择特征，其中信息增益比定义为

g_R(D,A)=g(D,A)/H(A)

CART

分类与回归树(classification and regression tree, CART)模型由Breiman等人在1984年提出，是应用广泛的决策树学习方法。CART同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。以下将用于分类与回归的树统称为决策树。

CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。

CART在生成树时采用不同的准则来选择特征，回归树时采用均方误差最小化准则，生成分类树时采用基尼指数最小化准则。其中基尼指数定义为

\operatorname{Gini}(p)=\sum_{k=1}^{K}p_k(1-p_k)=1-\sum_{k=1}^{K}p_k^2

其中K是类别个数，样本点属于第k类的概率为p_k。如果样本集合D根据特征A是否去某一可能值a被分成D_1和D_2两部分，即

D_1=\{(x, y) \in D \mid A(x)=a\}, \quad D_{2}=D-D_1

在特征A的条件下，D的基尼指数是

\operatorname{Gini}(D, A)=\frac{\left|D_{1}\right|}{|D|} \operatorname{Gini}\left(D_{1}\right)+\frac{\left|D_{2}\right|}{|D|} \operatorname{Gini}\left(D_{2}\right)