机器学习之决策树模型

在实现决策树模型之前，先需要了解信息的熵，熵被定义为信息的期望值，下面说明信息熵的计算方法：

         假如事件发生的可能性包括A，B，C三类；那么计算分类A的熵按照以下方式

         L(A) = -log2P(A)

         其中L(A)为分类A的熵。P(A)为事件发生后是A类的概率（可能性）。那么所有类别的熵计算方式如下：

         H = -∑P(xi)log2P(xi)  其中P(xi)为i类别的概率。

如果给出一份待训练的数据集合，则可以根据以上公式计算出该数据集的信息熵，计算规则如下：

         1：根据分类标签，计算不同分类下的概率P

         2：利用最大熵计算原则计算该数据集的熵。

         以上是信息熵的基本概念。

下面说明信息增益的概念：

         信息增益是对信息前后变化量的描述，其计算方式为

         数据变化前的信息熵与数据变化后的信息熵之差，如果信息增益越大，说明变化后的数据信息熵减少，其数据更加有序，价值更高。

什么是决策树。

决策树是一个树形结构，该树的每个分支对应一个判断条件，从树的根节点出发，通过一层又一层的分支进行判断，最终行进到叶子节点，该叶子节点对应哪个决策结果。这样的一个过程被称为决策树（非常类似于程序设计中的流程图）

如下图：

如何构造决策树

         构造决策树的过程如下

         1：选取数据集中的某个特征，根据该特征将数据集划分为两部分（例如：我们的数据集中有特征A，A的取值位a1和a2，那么我们可以根据特征A将数据集合划分为A取值为a1的子集1和A取值为a2的子集2），然后我们计算划分为子集后数据的信息增益是多少。

         2：对每个特征都做步骤1的这种处理。最后检查看根据那个特征划分子集后，数据集的信息增益最大。

         3：根据信息增益最大的特征构造决策树的第一层节点。

         4：然后在子集上继续利用该原则，根据数据特征进行决策树第二层的构造。

         5：如此递归，直到待判断的数据集属于同一个类别为止，这样一颗完整的决策树结构就构造成功。

         这个决策树后续就可以用在对新数据类别的预测上。

决策树python例子：

使用下面的海洋生物数据说明决策树的生成

以上数据，在代码中我们用1表示是，用0表示否。用一个多维列表进行存储，代码描述该数据结构如下：

数据集的熵计算代码如下：

 

在构造决策树的过程中，需要根据数据的特征将数据集划分为多个子集

 

在构造决策树的过程中，选择一个特征时，需要确保信息丢失最小，如下函数实现数据集合上特征的选择：

最后我们完成决策数据的创建

我们定义一个数据结构保存决策树的节点。在python中我们用字典作为决策树结点。

其中字典的key为决策判断所得到的特征，value是一个列表，为该特征不同取值下指向下一个节点。

类似于如下结构：

{bestfeature:[{1:{bestfeature:[]}}, {2:{bestfeature[]}}, {3:{bestfeature:[]}}]

构造决策树代码如下（通过递归方式实现）

 

完成决策树以后，对于新的数据，则可以通过遍历决策数据，对新数据进行预测，预测代码流程如下：

 

整体代码的使用可以按照以下方式进行使用：