ID3 提出了初步的决策树算法；
C4.5 提出了完整的决策树算法；
CART (Classification And Regression Tree) 目前使用最多的决策树算法；
一、ID3 算法
ID3 算法是决策树的经典构造算法，内部使用信息熵和信息增益来进行构建，每次迭代算则信息增益最大的特征属性作为分割属性。
优点：
决策树构建速度快，实现简单。
缺点：
计算依赖于特征数目较多的特征，而属性值最多的属性并不一定最优。
ID3算法不是递增算法。
ID3算法是单变量决策树，对于特征属性之间的关系不会考虑。
抗噪性差。数据集中噪音点多可能会出现过拟合。
只适合小规模的数据集，需要将数据放到内存中。
思考： 树形结构能否并行计算？
二、C4.5 算法
C4.5 算法是在ID3算法上的优化。使用信息增益率来取代ID3中的信息增益，在树的构造过程中会进行剪枝操作进行优化，能够自动完成对连续属性的离散化处理。
ID3当时构建的时候就没有去考虑连续值这个问题。
C4.5 算法在选中分割属性的时候选择信息增益率大的属性，公式如下：
优点：
产生规则易于理解。
准确率较高。(因为考虑了连续值，数据越多拟合程度就越好。)
实现简单。
缺点：
对数据集需要进行多次扫描和排序，所以效率较低。(比如之前例子中收入的连续值，分割次数越多，需要扫描的次数也就越多，排序次数也越多。)
只适合小规模数据集，需要将数据放到内存中。
三、CART算法
使用基尼系数 Gain作为数据纯度的量化指标来构建决策树算法，叫做CART算法。
GINI增益 作为分割属性选择的标准，选择GINI增益最大的作为当前数据集分割属性。可以用于分类和回归两类问题。
注意： CART构建的是二叉树。
四、总结
1、ID3和C4.5算法只适合小规模数据集上使用。
2、ID3和C4.5算法都是单变量决策树。
3、当属性值比较多的时候请使用C4.5。
4、决策树分类一般情况只适合小数据量的情况(数据可以放内存)
5、CART算法是最常用的一种决策树构建算法。
6、三种算法的区别只是对于当前树的评价标准不同而已，ID3使用信息增益，C4.5使用信息增益率，CART使用基尼系数。
7、CART算法构建的一定是二叉树。
网友评论