1.简介
决策树（Decision Tree）是一种非参数的有监督学习方法，它能够从一系列有特征和标签的数据中总结出决策规则，并用树状图的结构来呈现这些规则，以解决分类和回归问题。决策树算法容易理解，适用各种数据，在解决各种问题时都有良好表现，尤其是以树模型为核心的各种集成算法，在各个行业和领域都有广泛的应用。
决策树常用的算法：ID3、C4.5与CART算法。
2.数学基础部分
2.1、熵（Entropy）
熵表示随机变量不确定性的度量，随机变量X的熵定义如下：
熵越大代表随机变量的不确定性就越大。
2.2、条件熵（Conditional Entropy）
设有随机变量(X,Y)，其联合概率分布为：
条件熵H(Y|X)表示在已知随机变量X 的条件下，随机变量Y的不确定度。随机变量X给定的情况下随机变量Y的条件熵H(Y|X)定义为X给定条件下Y的条件概率分布的熵对X 的数学期望：
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）。
2.3、信息增益（Information Gain）
信息增益表示得知特征A的信息而使得类D的信息的不确定性减少的程度。
特征A对训练数据集D的信息增益g(D,A)，定义为集合D 的经验熵H(D)与特征A 给定条件下D的经验条件熵H(D|A)之差，即：
一般地，熵H(D)与条件熵H(D|A)之差称为互信息（Mutual Information）。决策树学习中的信息增益等价于训练数据集中类与特征的互信息。
决策树学习应用信息增益准则选择特征。给定训练数据集D和特征A，经验熵H(D)表示对数据集D进行分类的不确定性。而经验条件熵H(D|A)表示在特征A 给定的条件下对数据集D进行分类的不确定性，那么它们的差，即信息增益，就表示由于特征A而使得对数据集D的分类的不确定性减少的程度。不同的特征往往具有不同的信息增益，信息增益大的特征具有更强的分类能力。
缺点：信息增益偏向取值较多的特征
原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较 偏向取值较多的特征。
2.4、信息增益比（Information Gain Ratio）
信息增益比本质：是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。
信息增益比 = 惩罚参数 * 信息增益
特征A对训练数据集D 的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集D 关于特征A的值的熵HA(D)之比，即：
其中的HA(D)，对于样本集合D，将当前特征A作为随机变量（取值是特征A的各个特征值），求得的经验熵。
惩罚参数：数据集D以特征A作为随机变量的熵的倒数，即：将特征A取值相同的样本划分到同一个子集中（之前所说数据集的熵是依据类别进行划分的）
缺点：信息增益比偏向取值较少的特征；
原因：当特征取值较少时HA(D)的值较小，因此其倒数较大，因而信息增益比较大。因而偏向取值较少的特征。
使用信息增益比：基于以上缺点，并不是直接选择信息增益率最大的特征，而是现在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。
2.5、Gini指数（Gini Index）
定义：基尼指数（基尼不纯度）：表示在样本集合中一个随机选中的样本被分错的概率。Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。
基尼指数= 样本被选中的概率 * 样本被分错的概率
分类问题中，假设有K个类，样本点属于第k类的概率为pk，则概率分布的基尼指数定义为：
说明:
1. pk表示选中的样本属于k类别的概率，则这个样本被分错的概率是(1-pk)；
2. 样本集合中有K个类别，一个随机选中的样本可以属于这k个类别中的任意一个，因而对类别就加和；
3. 当为二分类是，Gini(P) = 2p(1-p)；
对于给定的样本集合D，其基尼指数为（假设集合中有K个类别）：
如果样本集合D 可以根据特征A是否取某一可能值a被分割成D1、D2两部分，即：
则在特征A的条件下，集合D的基尼指数定义为：
基尼指数Gini(D)表示集合D的不确定度，基尼指数Gini(D,A)表示经A=a分割后集合D的不确定度。基尼指数越大，样本集合的不确定度也就越大，这一点与熵很相似。
