决策树是机器学习中一种应用比较广泛的一种模型，比较常用的集成模型GBDT以及XGBOOST都是基于决策树。而且决策树在生活中也所处可见，下面用一个图例表示某一天的活动。

上面的图例就是一个比较简单的决策树模型。决策树模型是基于一系列的问题来进行决策的，在处理实际问题的时候会比上面树要大的多。一颗决策树通常都会包括一个根结点（明天做什么？）、若干个内部结点（能够继续分）、若干个叶结点（不能继续分）。叶结点对应的是决策的结果，其他的结点对应的是一个属性的测试。每个结点包含的样本集合根据属性测试的结果被划分到子结点中，根结点包含了所有的样本。从根结点到子结点的路径就是一个判定测试序列。决策树的泛化能力比较强，而且还遵循分而治之的策略。决策树又根据不同的划分方式可以分为ID3决策树、C4.5决策树、CART决策树。下面就介绍一下这些决策树之间的区别。

一、ID3决策树

信息熵(information entropy)是度量样本集合纯度的一种最常用的指标。一个样本集合为D，D由n类样本所组成，第k类样本的概率为p(k)(k为1到n的任意值)，则样本集合D的信息熵为

当p(k)=0时，p(k)*log2(p(k))=0，Ent(D)的最小值为0，Ent(D)的值越小纯度越高，因为到Ent(D)=0时,p(k)=1。

集合D根据不同属性a可以被分为{D1,D2,D3....}，利用属性a对于集合D进行划分的所获得的信息增益为

信息增益越大，表示使用属性a进行划分的所获得的纯度提升越大。ID3决策树进行属性划分的时候每次都是根据最大信息增益的属性进行划分的。为了便于大家理解下面通过一个西瓜分类的例子来说明一下

上面的17条西瓜数据定为集合D，可以根据属性色泽、根蒂、敲声、纹理、脐部、触感五个属性来划分整个集合。首先，我们来计算每个属性的信息增益。先计算色泽的信息增益，西瓜的色泽取值有青绿、乌黑、浅白。根据西瓜的色泽将集合D可以分为D(1)色泽为青绿、D(2)色泽为乌黑、D(3)色泽为浅白。通过观察上面的表格可以发现，属于D(1)的西瓜编号有{1,4,6,10,13,17},其中{1,4,6}为好瓜，{10,13,17}为坏瓜。属于D(2)的西瓜编号有{2,3,7,8,9,15}，其中{2,3,7,8}为好瓜，{9,15}为坏瓜。属于D(3)的西瓜编号有{5,11,12,14,16}，其中{5}为好瓜，{11,12,14,16}为坏瓜。所以，不同颜色的信息熵为

根结点的信息熵为

所以，西瓜色泽属性对于集合D的信息增益为

通过上面的方法，我们可以获得其他属性的信息增益

然后，选择信息增益最大的属性进行划分，划分之后需要重新计算属性的信息增益。

二、C4.5决策树

ID3决策树是使用信息增益来进行划分的，而信息增益准则对于可取值数目较多的属性有所偏好，为了减少这种偏好可能带来的不利影响，C4.5决策树不直接使用信息增益准则，而是使用增益率来进行属性的划分选择的，增益率定义为

其中，a为集合D的某一属性,n表示属性a的取值数目。n越大，IV(a)越大。所以，增益率准则对于属性取值数目较少的属性有所偏好。因此，C4.5算法并不是直接使用增益率最大的候选划分属性，而是使用了一种启发式的方式，先从候选属性中选择属性的信息增益高于平均信息增益的属性，然后再从这些属性中选择增益率最高的属性。

三、CART决策树

CART决策树是使用基尼系数来选择划分属性的。数据集D的纯度用基尼值来定义为

从基尼值定义的公式来看，从集合D中随机抽了两个样本i和j，两个样本类别不一致的概率。Gini(D)越小，则表示集合D中的纯度越高。属性a的基尼指数定义为

在使用基尼指数在候选属性集合中，进行划分的时候选择使得划分之后基尼指数最小的属性作为最优划分属性。

参考：《机器学习》周志华