决策树，它是一种树形结构，树的每个非叶子节点表示对样本在一个特征上的判断，节点下方的分支代表对样本的划分。决策树的建立过程是一个对数据不断划分的过程，每次划分中，首先要选择用于划分的特征，之后要确定划分的方案（类别/阈值）。我们希望通过划分，决策树的分支节点所包含的样本“纯度”尽可能地高。节点划分过程中所用的指标主要是信息增益和GINI系数。
-
信息增益
- 信息增益衡量的是划分前后信息不确定性程度的减小。信息不确定程度一般使用信息熵来度量，
表示样本的标签，p表示该类样本出现的概率。其计算方式是：
- 当我们对样本做出划分之后，计算样本的条件熵,其中
表示用于划分的特征的取值。：
- 信息增益定义为信息熵与条件熵的差值,信息增益IG越大，说明使用该特征划分数据所获得的信息量变化越大，子节点的样本“纯度”越高。：
- 信息增益衡量的是划分前后信息不确定性程度的减小。信息不确定程度一般使用信息熵来度量，
-
基尼系数
- 我们也可以利用Gini指数来衡量数据的不纯度，计算方法如下：
- 当我们对样本做出划分后，计算划分后的Gini指数：
- 一般来说，我们选择使得划分后Gini指数最小的特征（注意这里是直接根据Gini指数进行判断，而并非其变化量）。
- 我们也可以利用Gini指数来衡量数据的不纯度，计算方法如下：
-
下方给出了决策树的一个例子，我们要训练一个模型，根据天气、温度和风力等级来判断是否打网球。
DecisionTree.png
首先我们通过计算信息增益或Gini指数确定了首先根据天气情况对样本进行划分，之后对于每个分支，继续考虑除天气之外的其他特征，直到样本的类别被完全分开，所有特征都已使用，或达到树的最大深度为止。
