一、什么是ID3

ID3 算法是建立在奥卡姆剃刀（用较少的东西，同样可以做好事情）的基础上：越是小型的决策树越优于大的决策树。

D3算法十分简单，核心是根据“最大信息熵增益”原则选择划分当前数据集的较好特征，信息熵是信息论里面的概念，是信息的度量方式，不确定度越大或者说越混乱，熵就越大。在建立决策树的过程中，根据特征属性划分数据，使得原本“混乱”的数据的熵(混乱度)减少，按照不同特征划分数据熵减少的程度会不一样。在ID3中选择熵减少程度最大的特征来划分数据（贪心），也就是“最大信息熵增益”原则。

ID3缺点：

ID3 没有剪枝策略，容易过拟合；信息增益准则对可取值数目较多的特征有所偏好，类似“编号”的特征其信息增益接近于1；只能用于处理离散分布的特征；没有考虑缺失值。

二、什么是C4.5

C4.5 算法最大的特点是克服了 ID3 对特征数目的偏重这一缺点，引入信息增益率来作为分类标准。

C4.5 相对于 ID3 的缺点对应有以下改进方式：

引入悲观剪枝策略进行后剪枝；引入信息增益率作为划分标准；将连续特征离散化，假设 n 个样本的连续特征 A 有 m 个取值，C4.5 将其排序并取相邻两样本值的平均数共 m-1 个划分点，分别计算以该划分点作为二元分类点时的信息增益，并选择信息增益最大的点作为该连续特征的二元离散分类点；对于缺失值的处理可以分为两个子问题：问题一：在特征值缺失的情况下进行划分特征的选择？（即如何计算特征的信息增益率）问题二：选定该划分特征，对于缺失该特征值的样本如何处理？（即到底把这个样本划分到哪个结点里）针对问题一，C4.5 的做法是：对于具有缺失值特征，用没有缺失的样本子集所占比重来折算；针对问题二，C4.5 的做法是：将样本同时划分到所有子节点，不过要调整样本的权重值，其实也就是以不同概率划分到不同节点中。

缺点：

剪枝策略可以再优化；C4.5 用的是多叉树，用二叉树效率更高；C4.5 只能用于分类；C4.5 使用的熵模型拥有大量耗时的对数运算，连续值还有排序运算；C4.5 在构造树的过程中，对数值属性值需要按照其大小进行排序，从中选择一个分割点，所以只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时，程序无法运行。

三、什么是CART

ID3 和 C4.5 虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但是其生成的决策树分支、规模都比较大，CART 算法的二分法可以简化决策树的规模，提高生成决策树的效率。

CART 在 C4.5 的基础上进行了很多提升。

C4.5 为多叉树，运算速度慢，CART 为二叉树，运算速度快；C4.5 只能分类，CART 既可以分类也可以回归；CART 使用 Gini 系数作为变量的不纯度量，减少了大量的对数运算；CART 采用代理测试来估计缺失值，而 C4.5 以不同概率划分到不同节点中；CART 采用“基于代价复杂度剪枝”方法进行剪枝，而 C4.5 采用悲观剪枝方法。

以上就是关于决策树算法中CART与ID3、C4.5的知识希望对大家有帮助。