决策树利用损失函数最小的原则建立模型，然后利用该模型进行预测。
决策树学习通常包含三个阶段：特征选择、树的生成、树的修建。

特征选择

通常我们选择特征时，会考虑到两种不同的指标，分别为信息增益和信息增益比。要弄清楚这两个概念，首先要知道什么是：熵。
熵Entropy是表示随机变量不确定性的度量。简单来讲，熵越大，随机变量的不确定性就越大。而特征 A 对于某一训练集 D 的信息增益 定义为集合 D 的熵 与特征 A 在给定条件下 D 的熵之差。

简单来讲，每一个特征针对训练数据集的前后信息变化的影响是不一样的，信息增益越大，即代表这种影响越大。而影响越大，就表明该特征更加重要。

生成算法

ID3

ID3通过递归的方式建决策树，从根节点开始，对节点计算每个独立特征的信息增益，选择信息增益最大的特征作为节点特征。

C4.5

使用信息增益比来选择特征，是ID3算法的一种改进。

这两个算法从信息增益和信息增益比开始，对整个训练集进行分类，拟合出的模型针对训练集非常完美，但是使模型整体复杂度较高，对其他数据集的预测能力降低了，也就是常说的过拟合使模型的泛化能力变弱。
过拟合问题也是可以解决的，就是对决策树进行修剪。

决策树修剪

通过优化损失函数来去掉一些不必要的分类特征。
修建的方式，是从叶节点出发，向上回溯，逐步判断。如果去掉某一特征后，整颗决策树对应的损失函数更小，那就该将该特征及其分支剪掉。

由于 ID3 和 C4.5 只能生成决策树，而修剪需要单独进行，这也就使得过程更加复杂了。

CART

CART 算法本身就包含了决策树的生成和修剪，并且可以同时被运用到分类树和回归树。这就是和 ID3 及 C4.5 之间的最大区别。
CART 算法在生成树的过程中，分类树采用了基尼指数（Gini Index）最小化原则，而回归树选择了平方损失函数最小化原则。基尼指数其实和前面提到的熵的概念是很相似的。简单概述区别的话，就是数值相近但不同，而基尼指数在运算过程中的速度会更快一些。
CART 算法也包含了树的修剪。CART 算法从完全生长的决策树底端剪去一些子树，使得模型更加简单。而修剪这些子树时，是每次去除一颗，逐步修剪直到根节点，从而形成一个子树序列。最后，对该子树序列进行交叉验证，再选出最优的子树作为最终决策树。