决策树是机器学习中非常经典的一类学习算法，它通过树的结构，利用树的分支来表示对样本特征的判断规则，从树的叶子节点所包含的训练样本中得到预测值。决策树如何生成决定了所能处理的数据类型和预测性能。主要的决策树算法包括ID3，C4.5， CART等。
1，ID3
ID3是由 Ross Quinlan在1986年提出的一种构造决策树的方法。用于处理标称型数据集，其构造过程如下：
输入训练数据是一组带有类别标记的样本，构造的结果是一棵多叉树。树的分支节点一般表示为一个逻辑判断，如形式为a=aj的逻辑判断，其中a是属性，aj是该属性的所有取值。
在该节点上选取能对该节点处的训练数据进行最优划分的属性。最后划分的标准是信息增益（Information Gain），即划分前后数据集的熵的差异。
如果在该节点的父节点或者祖先中用了某个属性，则这个用过的属性就不再使用。选择好最优属性后，假设该属性有N个取值，则为该节点建立N个分支，将相应的训练数据传递到这N个分支中，递归进行，停止条件为：
（1）该节点的所有样本属于同一类，该节点成为叶节点，存放相应的类别。
（2）所有的属性都已被父节点或祖先使用。这种情况下，该节点成为叶节点，并以样本中元组个数最多的类别作为类别标记，同时也可以存放该结点样本的类别分布。
ID3的特点是：（1），容易造成过度拟合。（2）， 使用标称型数据，但是很难处理连续型数据。
2， C4.5
C4.5是对ID3的改进，其基本过程与ID3类似，改进的地方在于：
（1）既能处理标称型数据，又能连续型数据。为了处理连续型数据，该算法在相应的节点使用一个属性的阈值，利用阈值将样本划分成两部分。
（2）能处理缺失了一些属性的数据。该算法允许属性值缺失时被标记为？，属性值缺失的样本在计算熵增益时被忽略。
（3）构造完成后可以剪枝。合并相邻的无法产生大量信息增益的叶节点，消除过渡匹配问题。
3，CART
CART称为分类决策树，classification and regression tree，既能处理分类问题，又能处理回归问题。最初由Breiman提出。与ID3不能直接处理连续型特征不同的是，CART使用二元切分，即使用一个属性阈值对样本数据进行划分。划分的标准除了使用熵增益外，还有基尼纯净度（Gini impurity）和方差缩减（variance reduction)（用于回归）。