如此热的决策树到底是什么鬼

说这个前，需要重申一下，机器学习的主要目的在于预测。对于给定的训练集，总有一个结局变量（outcome，好与坏，高与低，长与短），决策树通常用于结局为二分类变量的案例预测。同时，我们有许多用来预测结局变量的特征变量（比如你想通过外观来预测一个人有没有到了中年，特征变量可能是……胖瘦、皱纹、发量……算了，越写越伤心）。

决策树呢，就是根据某一个特征变量，将结局变量分类。我们需要考虑两个因素，一个是纯度（purity）一个是熵（entropy）。纯度就是在一个特征类别中，一类事物的比例是不是很高，如果胖子里都是中年，那中年在胖子这个特征里的纯度就很高。熵呢，我们在大学化学课学过，它是物质混乱程度的度量，我们这里的熵跟化学课上的熵有一点点不一样，这里是信息熵，表示信息的混乱程度，也用大写的S表示。

决策树大概长这样：

上面这张图片来自百度百科，如果你在犹豫要不要出去打网球，你可能看一下外面，感受一下温度，适度和风的强度，然后做出你的判断，上面的这幅图可能代表了你的决策流程，但是你通常不会画出这种图来，如果你的行为方式被机器掌握，电脑会帮你画出一幅这样的图来，它叫决策树。决策树是如何找出特征变量，帮助决策的呢？下面是一种最常用的算法，叫C5.0，它根据信息的增益率来采纳特征变量：

以下是有点烧脑的部分……

根据熵的定义：

其中c：是类的水平数；Pi：是落入第i类中某案例的比例。

如果只有2各类：那么S∈ [0, 1]；如果有n类：那么S∈ [0, log2n]

这东西咋算？

假设我们有一伙人，青年占40%，中年占60%，则该数据的分割熵计算方法如下：

再回到要不要去打网球的问题：

注：此数据来源于http://m.blog.csdn.net/sinat_26917383/article/details/47617801

这组数据中的outcome中有9个yes和5个no，首先算一下这组数据的总信息熵：

然后，我们要计算根据Outlook这组特征分割案例后得到的熵值：

一个分割得到的总熵是根据案例落入分区中的比例Wi加权的N个分区的熵值总和，表述成公式：

所以，观察上表：Outlook中有三个属性：Sunny、Overcast、Rain。

Sunny有2个Yes，3个No；Overcast里有4个Yes，个No；Rain里有3个Yes，2个No。

所以根据Outlook得到的总熵值：

得结果：

用总信息熵减去分割熵，叫做这个分割属性的信息增益，那么Outlook的信息增益可计算：

用以上同样的方法，可求得：

比较四者，发现Outlook的信息增益是最大的，也就是说，按照Outlook这个属性作为分类，可以尽可能的把去和不去打网球的情况分开，如此Outlook变成了新的节点。

再往下，outlook成为了新的根节点，根据sunny、overcast、rain进行了分割，又有了新一级的信息熵，sunny下方再从Temperature、Hunmidity和Wind中，依据上法寻找新的特征变量进行再次分割，知道分割后的信息增益为，或不再有新的特征变量可供分割。

如此，就是决策树的构建方法了。

文字从来不会治愈谁，它只是一种温柔的陪伴——七七电影解药