决策树的基本概念
决策树算法是一类常用的机器学习算法，在分类问题中，决策树算法通过样本中某一维属性的值，将样本划分到不同的类别中去。
选择最佳划分的标准
选择划分数据集的特征的时候存在一定的顺序，选择的依据是这一维特征对数据的划分更具区分性，在决策树算法中，通常有这些标准：信息增益、增益率和基尼系数。
熵是度量样本集合纯度最常用的一种指标，
信息增益
信息熵表示的是不确定度。均匀分布时，不确定度最大，此时熵就最大。当选择某个特征对数据集进行分类时，分类后的数据集信息熵会比分类前的小，其差值表示为信息增益。信息增益可以衡量某个特征对分类结果的影响大小。
假设在样本数据集 D 中，混有 c 种类别的数据。构建决策树时，根据给定的样本数据集选择某个特征值作为树的节点。在数据集中，可以计算出该数据中的信息熵：
其中 D 表示训练数据集，c 表示数据类别数，Pi 表示类别 i 样本数量占所有样本的比例。
对应数据集 D，选择特征 A 作为决策树判断节点时，在特征 A 作用后的信息熵的为 Info(D)，计算如下：
其中 k 表示样本 D 被分为 k 个部分。
信息增益表示数据集 D 在特征 A 的作用后，其信息熵减少的值。公式如下：
对于决策树节点最合适的特征选择，就是 Gain(A) 值最大的特征。
ID3决策树算法就是利用信息增益作为划分数据集的一种方法。
在每次分裂的时候贪心选择信息增益最大的属性，作为本次分裂属性。每次分裂就会使得树长高一层。这样逐步生产下去，就一定可以构建一颗决策树。（基本原理就是这样，但是实际中，为了防止过拟合，以及可能遇到叶子节点类别不纯的情况，需要有一些特殊的trick）
OK，借鉴一下一个小例子，来看一下信息增益的计算过程。
这个例子是这样的：输入样本的属性有三个——日志密度（L），好友密度（F），以及是否使用真实头像（H）；样本的标记是账号是否真实yes or no。
然后可以一次计算每一个属性的信息增益，比如日致密度的信息增益是0.276。
同理可得H和F的信息增益为0.033和0.553。因为F具有最大的信息增益，所以第一次分裂选择F为分裂属性，分裂后的结果如下图表示：
上面为了简便，将特征属性离散化了，其实日志密度和好友密度都是连续的属性。对于特征属性为连续值，可以如此使用ID3算法：先将D中元素按照特征属性排序，则每两个相邻元素的中间点可以看做潜在分裂点，从第一个潜在分裂点开始，分裂D并计算两个集合的期望信息，具有最小期望信息的点称为这个属性的最佳分裂点，其信息期望作为此属性的信息期望。
再借鉴一个例子：
这里我们举一个信息增益计算的具体的例子。比如我们有15个样本D，输出为0或者1。其中有9个输出为1， 6个输出为0。 样本中有个特征A，取值为A1，A2和A3。在取值为A1的样本的输出中，有3个输出为1， 2个输出为0，取值为A2的样本输出中,2个输出为1,3个输出为0， 在取值为A3的样本中，4个输出为1，1个输出为0.
样本D的熵为：
样本D在特征下的条件熵为：
对应的信息增益为
下面我们看看具体算法过程大概是怎么样的。
输入的是m个样本，样本输出集合为D，每个样本有n个离散特征，特征集合即为A，输出为决策树T。
算法的过程为：
1)初始化信息增益的阈值ϵϵ
2）判断样本是否为同一类输出DiDi，如果是则返回单节点树T。标记类别为DiDi
3) 判断特征是否为空，如果是则返回单节点树T，标记类别为样本中输出类别D实例数最多的类别。
4）计算A中的各个特征（一共n个）对输出D的信息增益，选择信息增益最大的特征AgAg
5) 如果AgAg的信息增益小于阈值ϵϵ，则返回单节点树T，标记类别为样本中输出类别D实例数最多的类别。
6）否则，按特征AgAg的不同取值AgiAgi将对应的样本输出D分成不同的类别DiDi。每个类别产生一个子节点。对应特征值为AgiAgi。返回增加了节点的数T。
7）对于所有的子节点，令D=Di,A=A−{Ag}D=Di,A=A−{Ag}递归调用2-6步，得到子树TiTi并返回。
增益率
ID3算法虽然提出了新思路，但是还是有很多值得改进的地方。
a)ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
b)ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。如果校正这个问题呢？
c) ID3算法对于缺失值的情况没有做考虑
d) 没有考虑过拟合的问题
ID3 算法的作者昆兰基于上述不足，对ID3算法做了改进，这就是C4.5算法，也许你会问，为什么不叫ID4，ID5之类的名字呢?那是因为决策树太火爆，他的ID3一出来，别人二次创新，很快 就占了ID4， ID5，所以他另辟蹊径，取名C4.0算法，后来的进化版为C4.5算法。下面我们就来聊下C4.5算法。
C4.5决策树算法就是利用增益率作为划分数据集的方法。
C4.5算法定义了分裂信息，表示为：
很容易理解，这个也是一个熵的定义，pi=|Dj||D|pi=|Dj||D|，可以看做是属性分裂的熵，分的越多就越混乱，熵越大。定义信息增益率：
基尼系数
基尼指数是另一种数据的不纯度的度量方法，其公式为：
其中 c 表示数据集中类别的数量，Pi 表示类别 i 样本数量占所有样本的比例。
从该公式可以看出，当数据集中数据混合的程度越高，基尼指数也就越高。当数据集 D 只有一种数据类型，那么基尼指数的值为最低 0。
如果选取的属性为 A，那么分裂后的数据集 D 的基尼指数的计算公式为：
其中 k 表示样本 D 被分为 k 个部分，数据集 D 分裂成为 k 个 Dj 数据集。
对于特征选取，需要选择最小的分裂后的基尼指数。也可以用基尼指数增益值作为决策树选择特征的依据。公式如下：
在决策树选择特征时，应选择基尼指数增益值最大的特征，作为该节点分裂条件。
CART决策树算法中利用Gini指数来作为划分数据集的方法。
