决策树算法理解

为了更好的理解决策树算法，我们先来看个小例子：

假设我们知道一个人特征「黑色皮肤，头发鬈曲，身高175cm」，现在需要去判断这个人是来自非洲还是亚洲。 根据我们经验来说，这个人大概率是来自于非洲，为什么呢，因为首先他是黑色皮肤，这个基本就能确定是来自非洲了，而且他还是卷发，我们知道头发鬈曲也是黑色人种的一大特征，所以我们判断这个人是来自于非洲。

• 为什么先看肤色再看头发呢？ 因为根据我们的经验，肤色是更能区分亚洲人与非洲人的特征，虽然头发鬈曲也是非洲人的一大特征，但我们也知道在亚洲人中也会存在一些卷发的情况，所以我们先看肤色再看头发。
• 为什么不看身高这个特征？ 因为根据我们的经验，不管是亚洲人还是非洲人，高的矮的都存在，我们没法通过身高去进行判断。

这其实也就是决策树算法在训练过程中需要完成的，在多个特征中，我们需要找出最能区分结果的特征，区分结果差的直接丢掉。

决策树（ID3算法为例）

目前决策树算法中分为ID3，C4.5和CART三种，区别在于ID3在使用信息增益来选则分类属性，C4.5使用信息增益比，CART使用基尼系数，整体逻辑都一样，公式如下：

• 熵：

entropy(D) = -\sum_{i=1}^n P_ilog_2 P_i

其中D为数据集，i为数据集D的可能分类标签,

P_i

为该标签的概率

• 条件熵：

entropy(D,A) = \sum_{i=1}^k \frac {D_{A_i}}{D} log_2D_{A_i}

其中A表示约束特征，k表示A特征的种类

• 信息增益:

gain(D,A) = entropy(D) - entropy(D,A)

• 信息增益率：

gain_{rate}(D,A) = gain(D,A)/entropy(D,A)

• 基尼指数:

gini(D) = \sum_{i=1}^n p_k (1-p_k)

• 条件基尼指数：

gini(D,A) = \sum_{i=1}^k \frac {D_{A_i}}{D} gini(D_{A_i})

我们本篇将以ID3为例，我们需要理解三个概念：

• 熵(entropy):别看这个字比较生僻，其实很好理解，熵表示整个数据集的复杂度，数据集越复杂，熵值越大。当然何为复杂，以二分类为例，当正负样本比为1:1的时候最复杂，这时候熵等于1；
• 条件熵：理解了熵之后条件熵就很好理解了，即在给定某个条件的情况下熵为多少；
• 信息增益：信息增益其实就是熵减去条件熵，整个决策树算法的目标就是找出信息增益最大的条件（特征），也就是找出能让复杂度降低最多的那个条件。

通俗理解：首先我们整个数据集的复杂度可能是0.9，然后我们在知道特征A之后复杂度变为了0.2，在知道特征B的时候复杂度性变成了0.5，特征A和特征B的信息增益分别是0.7和0.4，那这样我们就能判断特征A是比特征B更能区分结果的特征，所以我在判断的时候会优先看特征A。

Example

我们现在有如下数据，需要通过声音，头发和体重三个特征去判断性别。

获取决策树步骤如下：

1. 计算熵：

entropy = -（\frac {6}{11}*log_2 \frac {6}{11} +\frac {5}{11}*log_2 \frac {5}{11}）\approx 0.994

1. 分别计算「声音，头发，体重」的条件熵： a. 声音粗：

entropy_{声音粗} = -（\frac {1}{7}*log_2 \frac {1}{7} +\frac {6}{7}*log_2 \frac {6}{7}）\approx 0.592

b.声音细：

entropy_{声音细} = -（\frac {1}{4}*log_2 \frac {1}{4} +\frac {3}{4}*log_2 \frac {3}{4}）\approx 0.811

c. 条件熵：

entropy_{声音} = \frac {4}{11}*entropy_{声音细} +\frac {7}{11}*entropy_{声音粗} \approx 0.672

1. 计算信息增益：

gain_{声音} =0.994-0.672\approx 0.323

计算头发和体重的也一样，就不重复了，直接放结果

gain_{头发} =0.994-0.796\approx 0.198

gain_{体重} =0.994-0.730\approx 0.264

1. 声音的信息增益最大，所以我们选择声音作为根结点；
2. 这时候我们会生成两个节点，声音粗和声音细。我们接下来要做的是分别判断是否满足停止条件，若满足， 则将其设为子节点停止分裂，输出结果即占比最大的类别，若不满足，则重复1-4步。

停止条件：关于停止条件我们可以简单分为被动停止和主动停止。

• 被动：所有特征已经使用完毕，不能再继续分裂
• 主动：达到设置的最大深度或者熵的值低于我们设定的阈值等

最后我们会得到一个如下的树：

最后

整个决策树的生成逻辑也就是这样，还是挺简单的，相对于其他算法，决策树计算简单，而且输出结果解释性很强，你可以很直观的看到这么一棵「树?」，但缺点也很明显，就是当特征或者特征值过多的时候很容易出现过拟合现象。