决策树扫盲

这是一篇决策树的扫盲篇，没有太多干货。因为我就是一个半盲中。

决策树是机器学习的一种方法，叫决策树的原因是因为这个算法会生成一棵树。包含一个根节点，多个内部节点和叶子节点。每个内部节点代表一种划分属性，也节点代表决策结果。

image.png

这是一张从百度百科上扒下来的图，以Play为正例，训练集中包含9个正例，5个反例。训练集会有多个属性，虽然并没有训练集，但是从图上的可以看出来，至少有天气、湿度、是否有风几个属性。首先根据天气进行分类，其中阴天的分类已经达到只包含一种结果，所以阴天这个节点叶子节点。其他几个没有达到叶子节点标准的会继续进行分类。

这样一棵树是如何从根节点慢慢展开的？选择属性的依据是什么？并不是随意抽取了一个属性就用来进行划分。有多种划分的选择。最基础的便是信息增益。信息增益是由一个叫做“信息熵”的概念计算得出的。

1948年，香农提出了“信息熵”的概念，才解决了对信息的量化度量问题。信息熵这个词是C．E．香农从热力学中借用过来的。热力学中的热熵是表示分子状态混乱程度的物理量。香农用信息熵的概念来描述信源的不确定度。

这一段文字引用于百度百科。简而言之，信息熵可以理解为信息的混乱程度。因此信息熵越小，意味着信息的纯度越高。信息熵的计算公式如下。

image.png

其中D为数据集，k表示数据集中数据的种类，｜Y｜表示数据种类的数量。像之前的例子中，数据只分为Play和Don't Play, 所以｜Y｜就为2，k可以取值1、2，分别代表Play和Don't Play. p表示该种类的概率。
那么在上例中，数据集D的信息熵就如下。

image.png

信息增益可以理解为使用某个属性来进行划分所获得的纯度提升。因此信息增益是针对数据集和属性来共同得出的。信息增益的计算公式如下。

image.png

其中a代表某一属性，v表示属性a中的分类，V属性a中类别的数量。从上边的例子来看，天气这种属性有3种类别，分别是晴天、阴天、雨天。

在划分的时候，每次都选择能够得到最高的信息增益来进行划分。还是以上边的图为例，可以得到以天气为划分属性时的信息增益：

image.png

由于缺少数据集，因此无法计算其他几个属性的信息增益。根据决策树的划分依据，可以推测以天气为划分属性时的信息增益是最大的。以天气划分后，可以看到数据集被分成了三份。由于阴天的数据集全都属于同一个类别，不需要继续划分。对于晴天和雨天，数据集还是会有差距，因此需要对这两个数据集继续进行信息增益的计算。此时对于晴天和雨天，他们的数据集D‘的数量应为5，继续计算信息熵Ent(D')以及信息增益Gain（D’, a）。

对于决策树当然不止信息增益一种划分依据。鉴于篇幅已经很长了，其他以后再说～