Python数据分析之决策树

已介绍了两种分类算法，可点击题目回顾：

本文参考于《机器学习实战》

决策树(decision tree)是一种基本的分类与回归方法。以下图为例，它就是一颗决策树。长方形代表判断模块(decision block)，椭圆形代表终止模块(terminating block)，表示已经得出结论，可以终止运行。从判断模块引出的左右箭头称作为分支(branch)，它可以达到另一个判断模块或者终止模块。

我们可以把决策树看成一个if-then规则的集合。创建分支的伪代码函数createBranch()如下所示：

检测数据集中的每个子项是否属于同一分类：

If so return 类标签；

Else

寻找划分数据集的最好特征

划分数据集

创建分支节点

for 每个划分的子集

调用函数createBranch并增加返回结果到分支节点中

return 分支节点

决策树的一般流程

收集数据：可以使用任何方法。

准备数据：收集完的数据需要进行整理，树构造算法只适用于标称型数据，因此数值型数据必须离散化。

分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。

训练算法：构造树的数据结构。

测试算法：使用经验树计算错误率。

使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。

信息增益

划分数据集的大原则是：将无序的数据变得更加有序。在划分数据集之前之后信息发生的变化称为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。集合信息的度量方式称为香农熵或者简称为熵。熵定义为信息的期望值。如果待分类的事务可能划分在多个分类之中，则符号xi的信息定义为：

其中p(xi)是选择该分类的概率。

为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值(数学期望)，通过下面的公式得到：

其中n是分类的数目。下面给出计算给定数据集的熵的代码：

得到熵之后，我们就可以按照获取最大信息增益的方法划分数据集。下面给出划分数据集的代码：

接下来我们将遍历整个数据集，循环计算香农熵和splitDataSet()函数，找到最好的特征划分方式。熵计算将会告诉我们如何划分数据集是最好的数据组织方式。下面是选择最好数据划分方式的代码：

我们可以通过简单的数据集进行测试：

结果：

结语

本文介绍了如何计算数据集的熵和如何选择最优特征作为分类特征。下一节我们将介绍如何将这些函数功能放在一起，构建决策树，以及如何修建和可视化。