prerequiste:决策树基本思想
决策树构建一个重要的步骤是选择最优划分属性，基于不同的判断标准可以衍生出不一样的方法。这篇博文介绍常用的三种决策树算法：ID3、C4.5、Cart，这三种算法的区别在于选择特征作为判断结点时的标准（数据纯度函数）不同。本文仅介绍理论，为节省篇幅没有举例，你可以在文末的参考文献中找到具体的例子。
ID3算法
ID3算法使用最大信息增益作为特征选择标准。
信息熵表示信息的不确定度，假设数据
可以被分为
个类别，其中第
个类被的数据在总数据的比率为
，则数据D的信息熵计算公式为：
该信息熵在文献中也被称为经验熵。
再使用某一特征A对数据及逆行分类后，其不确定度会减少（已经进行过一定程度的分类），此时的信息熵也会减小。假设特征A
将数据分为
个类别，则
(也称为经验条件熵)的计算公式为：
其中
表示
中分类为
的个数。
那么使用特征
进行分类的信息增益定义为分类前后的差值：
即经验熵和经验条件熵的差值。
在构造决策树的过程中，计算所有属性的信息增益，并使用能产生最大信息增益的属性作为最优属性构造决策树的分类结点。
ID3算法的缺点
ID3算法倾向于选择取值多的属性，因为它信息增益最大，这会造成构造结点时偏向分支较多的结点。为了削弱这种缺点，可以使用信息增益比来替代信息增益，由此产生了C4.5算法。
C4.5算法
特征
对数据
的信息增益比定义为:
其中，
通常情况下，我们选择一个信息增益比最大的属性来构造分类结点。
C4.5算法的缺点
采用最大信息增益比依然有缺点，它倾向于选择分类较少的属性。
实践中，我们可以结合两种方法来使用：首先计算信息增益和信息增益比，然后选取信息增益在平均值以上的那些变量，最后在这些变量中选择信息增益比最大的变量。
Cart算法 - 最大基尼指数
Cart算法使用基尼系数作为判断标准。
Cart算法基本思想
Cart算法是一种二分的递归分割方法，它将当前样本划分为两个子样本集，再不断地递归分割使得每个非叶结点都有两个分支。因此，Cart算法生成的是一颗二叉树，二叉树的每个结点产生的选择只有是或者否两种，即每个结点只分两类。
假设数据有
共n个自变量（或者称为维度），
是其标签。算法的核心步骤为：
GINI系数
Gini系数也是用来衡量信息的纯度的，同熵类似，样本总体包含的类别越杂乱，对应的Gini系数越大。
假设
为某一类比所占总体的概率，类别共有
类，则Gini系数定义为：
当我们按照特征
对数据
进行分类时，假设特征
将数据分为
类，则划分后的Gini系数为：
补充，此时Gini系数的增加值为：
依次计算每一个变量的Gini系数增加值，选取最大的那个变量划分数据集。
不同算法之间的对比
三种算法本质上都是贪心算法。
信息增益反映的是给定条件之后不确定性减少的程度，特征取值越高意味着确定性越高，也就是条件熵越小，信息增益越大。ID3很容易在训练集上取得良好效果， 但也很容易过拟合。通过引入信息增益比，来对取值较多的特征进行一定程度的惩罚，提高决策树的泛化能力。
从样本类型的角度来看，ID3只能处理离散型变量，而C4.5和Cart都可以处理连续性变量。C4.5可以通过排序找切分点将连续属性转换为布尔型；Cart由于二值划分的特征天然适应连续性变量。
从应用角度，ID3和C4.5只能用于分类任务，而Cart(Classification and Regression Tree)也可以用于回归任务。
ID3对样本缺失值比较敏感，而C4.5和Cart可以对缺失值进行不同程度的处理。
ID3和C4.5可以在每个结点上产生多叉分支，且每个特征在层级之间不会复用，而Cart则每个结点只产生两个分支，因此最终生成一颗二叉树，而且每个特征被重复利用。
ID3和C4.5通过减枝来权衡准确性和泛化能力，而Cart直接利用全部数据发现所有可能的树结构进行对比。
参考文献
百面机器学习 - Hulu
分类算法 – 决策树ID3算法
分类算法 – 决策树C4.5算法
分类算法 – 决策数CART算法
