决策树是机器学习中非常经典的一类学习算法，它通过树的结构，利用树的分支来表示对样本特征的判断规则，从树的叶子节点所包含的训练样本中得到预测值。决策树如何生成决定了所能处理的数据类型和预测性能。主要的决策树算法包括ID3，C4.5， CART等。
ID3
ID3是由 Ross Quinlan在1986年提出的一种构造决策树的方法。用于处理标称型数据集。
在节点上选取能对该节点处的训练数据进行最优划分的属性。最后划分的标准是信息增益（Information Gain）。
ID3的特点是：（1）容易造成过度拟合。（2） 使用标称型数据，但是很难处理连续型数据。
C4.5
C4.5是对ID3的改进，其基本过程与ID3类似，改进的地方在于：
（1）既能处理标称型数据，又能连续型数据。为了处理连续型数据，该算法在相应的节点使用一个属性的阈值，利用阈值将样本划分成两部分。
（2）能处理缺失了一些属性的数据。该算法允许属性值缺失时被标记为？，属性值缺失的样本在计算熵增益时被忽略。
（3）构造完成后可以剪枝。合并相邻的无法产生大量信息增益的叶节点，消除过渡匹配问题。
3，CART
CART称为分类决策树（二叉树），既能处理分类问题，又能处理回归问题。与ID3不能直接处理连续型特征不同的是，CART使用二元切分，即使用一个属性阈值对样本数据进行划分。划分的标准除了使用熵增益外，还有基尼纯净度（Gini impurity）和方差缩减（variance reduction)（用于回归）。
ID3算法是决策树的一个经典的构造算法，在一段时期内曾是同类研究工作的比较对象，但通过近些年国内外学者的研究，ID3算法也暴露出一些问题，具体如下： (1)信息增益的计算依赖于特征数目较多的特征，而属性取值最多的属性并不一定最优。
(2)ID3是非递增算法。
(3)ID3是单变量决策树(在分枝节点上只考虑单个属性)，许多复杂概念的表达困难，属性相互关系强调不够，容易导致决策树中子树的重复或有些属性在决策树的某一路径上被检验多次。
(4)抗噪性差，训练例子中正例和反例的比例较难控制。
于是Quilan改进了ID3，提出了C4.5算法。C4.5算法现在已经成为最经典的决策树构造算法，排名数据挖掘十大经典算法之首，下一篇文章将重点讨论。
决策树的经典构造算法——C4.5（WEKA中称J48）
由于ID3算法在实际应用中存在一些问题，于是Quilan提出了C4.5算法，严格上说C4.5只能是ID3的一个改进算法。
C4.5算法继承了ID3算法的优点，并在以下几方面对ID3算法进行了改进：
1) 用信息增益率来选择属性，克服了用信息增益选择属性时偏向选择取值多的属性的不足；
2) 在树构造过程中进行剪枝；
3) 能够完成对连续属性的离散化处理；
4) 能够对不完整数据进行处理。
C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。
另外，无论是ID3还是C4.5最好在小数据集上使用，决策树分类一般只试用于小数据。当属性取值很多时最好选择C4.5算法，ID3得出的效果会非常差。
