ID3与C4.5的区别

决策树是机器学习中非常经典的一类学习算法，它通过树的结构，利用树的分支来表示对样本特征的判断规则，从树的叶子节点所包含的训练样本中得到预测值。决策树如何生成决定了所能处理的数据类型和预测性能。主要的决策树算法包括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)（用于回归）。