女娲造人番外篇-决策树

什么是决策树？

百度上的解释是这样的。决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。说的什么意思？反正看一遍是看不懂。下面让我们来听一个故事。

故事发生在不知道什么时期，女娲造了十个人，有一帮非常无聊的神仙，他们就开始讨论这十个人的颜值问题了，最后他们就投票选出了四个好看的人。女娲就特别好奇这些神仙选好看的人的标准是什么，于是，她利用了决策树的思想，造出了一棵判断一个人是否好看的决策树。她发现，神仙们选好看的人的标准为：柳叶眉，大眼睛，高鼻梁，性感唇，瓜子脸。

许多年后，人们就拿着这样的标准去判断一个人是否好看了。让我们来看看这棵树是怎么构建出来的。

用机器学习的语言来解释，就是有10个样本，每个样本有眉毛，眼睛，鼻子，嘴巴，脸型这5个特征。4个是好看的人，6个不好看的人。分别根据这5个特征维度对样本进行分类，10个人中有9个人是柳叶眉，1个不是。然后剩下9个人中，8个人是大眼睛，1个不是。然后剩下8个人中，7个是高鼻梁，1个不是，依次类推，最后我们发现好看的4个人都顺着这颗树走到了一起。其实，也就是好看的人都有共同的特征-柳叶眉，大眼睛，高鼻梁，性感唇，瓜子脸。

当然了，以上只是为了举例子方便，请大家不要对号入座啊，哈哈哈。。。

下面我们来看下Scikit-learn中的代码实现：

这个代码中，我们对鸢尾花数据用决策树算法进行了分类，为了方便绘制图像，我们只取了鸢尾花的前2个特征。Scikit-learn中决策树分类算法用的是DecisionTreeClassifier. 可以看到这里我们传了2个参数，第一个是max_depth, 就是说让构造出的决策树最大深度是2. 第二个参数是criterion,构造决策树时选择属性的准则，entropy指信息熵，gini指基尼系数。这里我们选择了信息熵，最后绘制出了决策边界，可以看出决策边界将我们的样本分成了3类。

信息熵

熵在信息论中代表 随机变量不确定度的度量。信息熵的计算方式如下：

如果一个系统系统中，有K类样本，且它们所占的比例为Pi，那么这个系统的信息熵为每类的概率和概率倒数取对数的总和，我们把对数中的1/Pi提出去就是前面加负号了，所以信息熵是永远都是一个大于等于0的值。怎么理解这么个抽象的概念呢？ -logPi 可以理解为i类别所承载的信息量，-Pi*logPi 即为i类别发生的可能性（概率）和 它的信息量的乘积，每个类别发生的概率和它们信息量的乘积总和即为总信息量。信息熵即为信息量的期望。

对于一个完全确定的系统，它的信息熵就是0. 而在机器学习中，我们处理的都是不确定的系统，确定的就没必要用机器学习，如果你都知道明天一定会下雨了，也就没有必要用机器学习模型去预测明天是否会下雨了。而决策树是在干什么？本质上，就是减少系统的信息熵，即减少系统的不确定性，直到信息熵不能再小了，变为一个几乎确定的系统。让我们来看下这个信息熵函数：

对于一个二分类问题，两类数据在样本中的概率分别是p和1-p，由此我们可以绘制不用p值对应系统的信息熵图像。由上图可以看出，它是个类似于抛物线的图像，当p取到0.5时，信息熵达到最大，为log2，这里因为机器学习中对数一般取的是自然数e为底的，所以差不多是0.7.

再拿回我们最初举女娲造人的例子来说，好看的人和不好看的人分别占总样本的比例为4/10和6/10，则针对这个样本系统，它的信息熵为

-4/10 *log(4/10) - 6/10 * log(6/10) = 0.67. 而当我们只把样本分为柳叶眉和非柳叶眉的人的时候，是柳叶眉的分支上还有9人，其中4人是好看的，没有柳叶眉的人是1人，且这1个人是不好看的。则对于没有柳叶眉的这个分支，它的信息熵为 -1 * log1 = 0, 说明这个分支不用再走下去了，已经确定。而对于有柳叶眉的分支，它的信息熵为 -4/9 * log(4/9) - 5/9 * log(5/9) = 0.69. 就这样直到到了最后一个 是瓜子脸的分支，它的信息熵为 -1 * log1 = 0. 整个系统就确定下来了。决策树就构造完成了，没有一个分支还可以继续减少信息熵了。模型训练好了，如果我们要预测女娲捏出的新人是不是好看的人，只要放进这棵树的根节点开始判断，最后走到的好看的叶子结点，则为好看的人，否则为不好看的人。

用决策树寻找最优划分

可以看到第一次划分，是以x轴进行划分，最优划分值是2.45，划分结果红色的部分的信息熵已经为0，蓝色和黄色的部分还可以进行第二次划分，第二次划分是以y轴进行划分，最优划分值为1.75,最后将蓝色和黄色两类样本分开来了。两次划分中，我们可以看到哥分支的信息熵越来越小了。信息熵减小，不确定性就减少了，确定性就增加了，系统就越发趋近于稳定。本例子还可以进行划分，这里就不继续划分了。

基尼系数

基尼系数和信息熵一样都可以用来表示系统的不确定性

基尼系数寻找最佳划分

跟使用信息熵时的结果一样，这里不再佳赘述了。

信息熵 VS 基尼系数

大多数时候二者没有特别的效果优劣。信息熵的计算比基尼系数稍慢，所以Scikit-learn中默认使用的是基尼系数。