数据分析教程决策树原理

决策树原理

决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。决策树分为分类树和回归树两种，分类树对离散变量做决策树，回归树对连续变量做决策树。也就是说，决策树既可以用来解决分类问题，也可以解决回归问题。

 

 

决策树其实是一棵倒树，它的根在最上面，叶子在下面。

决策树由节点(node)和有向边(directed edge)组成。节点有两种类型：内部节点(internal node)和叶节点(leaf node)。内部节点表示一个特征或属性，叶节点表示一个类。

下面我们通过一个小例子来看下，这棵树到底怎么用

 

 

决定我们是否打篮球的因素有三个，是否下雨，温度是否适合，是否是室内。我们一步一步，通过判断不同的条件，最后得出不同的结论。

我们首先选取了决定是否打篮球的条件，并且以是否下雨为根节点开始分裂，然后根据不同情况构造了一棵树，最后根据该树的分枝，来决定是否打篮球。

概括来说，就是根据特征的值做判断，最后得出不同的分类。

决策树学习过程

那么决策树要如何构建呢？通常，这一过程可以概括为3个步骤：特征选择、决策树生成和修剪。

特征选择：特征选择是指从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准标准，从而衍生出不同的决策树算法。

决策树生成：根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树生长。

剪枝：决策树容易过拟合，一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。

特征选择

特征选择是为了选择出对于训练数据具有分类能力的特征。比如说，使用某一个特征进行决策树分类的结果与随机分类的结果没有任何区别，那么该特征就不具备分类能力，可以直接丢弃掉该特征。当然我们要选择能够分类出更好的类别的特征，作为根节点。

那么一般情况下该如何选择特征呢，业界通常会使用信息增益的方式来选择。

先来看几个概念：

信息熵

条件熵

信息增益

信息熵

信息熵是信息的期望值，是用来衡量信息不确定性的指标。信息的不确定性越大，熵越大。

比如说对于抛硬币事件，每次抛硬币的结果就是一个不确定的信息。

如果根据我们的经验，一个均匀的硬币正面和反面出现的概率是相等的，都是50%。所以我们很难判断下一次是出现正面还是反面，所以这个事件的信息熵值很高。

但是如果该硬币不是均匀的，并且根据历史数据显示，100次试验中，出现正面的次数有98次，那么下一次抛硬币，我们就很容易判断结果了，故而该事件的信息熵很低。

其计算公式为：

 

 

其中：

P(X=i)为随机变量 X 取值为 i 的概率

n 代表事件的 n 种情况

我们还是以上面抛硬币的例子来求解下两种情况下的信息熵各为多少

注意，由于编辑器的原因，以下所有 log(2) 均表示以2为底的对数

均匀硬币

硬币	P
正面	0.5
反面	0.5

信息熵 = -0.5 * log(2)0.5 - 0.5 * log(2)0.5 = 1

非均匀硬币

硬币	P
正面	0.98
反面	0.02

信息熵 = -0.98 * log(2)0.98 - 0.02 * log(2)0.02 = 0.14

思考：如果正面的概率是100%，那么此时的信息熵是多少呢

答：此时信息熵是0，也可以说明，信息熵是0到1之间的数值。

条件熵

条件熵是通过获得更多的信息来减小不确定性。当我们知道的信息越多时，信息的不确定性越小。

比如说某个用户曾经购买了一种商品，但是我们没有办法仅仅根据这个信息来判断，该用户是否会再次购买该商品。但是如果我们增加一些条件，比如双十一促销活动信息之后，我们就能够更加容易的发现用户购买商品与促销活动之间的联系，并通过不同促销力度时用户购买的概率来降低不确定性。

其计算公式为：

 

 

其中：

Y 为条件

P(Y = v)表示 Y 有多种情况，当 Y 处于 v 的概率

H(X|Y = v)表示 Y 处于 v 条件时的信息熵

信息增仪

信息增益的定义就是信息熵减去条件熵

 

 

这里只是数学上的定义，那么该如何使用信息增益来创建决策树呢，还是举例来看。

 

 

在上图中，我先按照某种条件，把红点和黄框分成了如图所示的两类，接下来我们计算下熵值

父节点信息熵 = -(6/10log(2)6/10)-(4/10log(2)4/10) = 0.97

上面子节点信息熵 = -(2/6log(2)2/6)-(4/6log(2)4/6) = 0.91

下面子节点信息熵 = -(2/4log(2)2/4)-(2/4log(2)2/4) = 1

此处两个子节点其实就是某种条件下的信息熵，因为在分类的时候，是隐含了某种分类条件的。

下面根据条件熵的定义，可以得到条件熵

条件熵 = 上面子节点出现的概率 * 该条件下的信息熵 + 下面子节点出现的概率 * 该条件下的信息熵

= 6/10 * 0.91 + 4/10 * 1

= 0.946

再根据信息增益的定义，可以得到信息增益

信息增益 = 父节点信息熵 - 条件熵

= 0.97 - 0.946

= 0.024

再来看另一种分类方式

 

 

父节点信息熵 = -(6/10log(2)6/10)-(4/10log(2)4/10) = 0.442

上面子节点信息熵 = -(6/6log(2)6/6)-(0/6log(2)0/6) = 0

下面子节点信息熵 = -(4/4log(2)4/4)-(0/4log(2)0/4) = 0

条件熵 = 0

信息增益 = 0.442

从图中明显可以看出，第二种分类是好于第一种的，而此时第二种的信息增益是较大的，由此可以得到，在通过信息增益来确定节点时，需要使用信息增益最大的那个特征。   也就是说，信息增益是相对于特征而言的，信息增益越大，特征对最终的分类结果影响也就越大，我们就应该选择对最终分类结果影响最大的那个特征作为我们的分类特征。

决策树生成

构建决策树的工作原理：

拿到原始数据集，然后基于最好的属性值划分数据集，由于特征值可能多于两个，因此此时可能存在大于两个分支的数据集划分。第一次划分之后，数据集被向下传递到树的分支的下一个结点。在这个结点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。

构建决策树的算法有很多，比如 C4.5、ID3 和 CART，这些算法在运行时并不总是在每次划分数据分组时都会消耗特征。ID3 和 C4.5 算法可以生成二叉树或多叉树，而 CART 只支持二叉树。

基于 ID3 算法

ID3 算法其实就是计算信息增益，在决策树各个结点上对应信息增益准则（选取信息增益最大的）选择特征，递归地构建决策树。

具体方法是：从根结点(root node)开始，对结点计算所有可能的特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同取值建立子节点；再对子结点递归地调用以上方法，构建决策树；直到所有特征的信息增益均很小或没有特征可以选择为止，最后得到一个决策树。

我们使用如下的数据集来演示下该如何通过 ID3 算法构建决策树，该数据集记录的是某位客户，在不同天气下打高尔夫的情况。

weather	temp	wind	play golf
rainy	hot	false	no
rainy	hot	ture	no
overcast	hot	false	yes
sunny	mild	false	yes
sunny	cool	false	yes
sunny	cool	ture	no
overcast	cool	ture	yes
rainy	mild	false	no
rainy	cool	false	yes
sunny	mild	false	yes
rainy	mild	ture	yes
overcast	mild	ture	yes
overcast	hot	false	yes
sunny	mild	ture	no

计算根节点

我们首先来计算是否打高尔夫球的信息熵

是否打高尔夫	频度	概率	信息熵
No	5	5/14 = 0.36	-0.531
Yes	9	9/14 = 0.64	-0.410

根据信息熵的计算公式可以得出，Play Golf 的信息熵为

H(play golf) = -[-0.531 + (-0.410) ] = 0.940

下面计算3种天气状况下的条件熵

以天气状况为节点

各种天气状况出现的概率

weather	Yes	No	天气状况各情况出现频度	概率
rainy	2	3	5	5/14 = 0.36
overcast	4	0	4	4/14 = 0.29
sunny	3	2	5	5/14 = 0.36

各种天气状况下的条件熵

weather	Yes（打高尔夫的概率）	No（不打高尔夫的概率）	信息熵
rainy	2/5 = 0.4	3/5 = 0.6	0.971
overcast	4/4 = 1	0/4 = 0	0
sunny	3/5 = 0.6	2/5 = 0.4	0.971

以 weather 为节点的条件熵 0.36 * 0.971 + 0.29 * 0 + 0.36 * 0.971 = 0.69

此时的信息增益为 0.94 - 0.69 = 0.25

以温度为节点

各种温度出现的概率

temp	Yes	No	温度个情况出现频度	概率
hot	2	2	4	4/14 = 0.29
mild	4	2	6	6/14 = 0.43
cool	3	1	4