《机器学习实战》读书笔记系列（三）：决策树上集

决策树原理

决策树是属于机器学习监督学习分类算法中比较简单的一种，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。

简单来讲如下图：

学习目标 : 如何从一堆原始数据中构造决策树

本节的学习顺序如下：

讨论构造决策树的方法

如何编写构造树的Python代码

提出一些度量算法成功率的方法

使用递归建立分类器，并使用Matplotlib绘制决策树图

实操例子—输入一些隐性眼镜的处方数据，并由决策树分类器预测需要的镜片类型

一．决策树构造

优点–> 计算复杂度不高，输入易于理解，对中间值的缺失不敏感，可以处理不相关特征数据

缺点 -> 可能会产生过度匹配问题（过拟合）

适用数据类型： 数值型和标称型

构造决策树之前，需要解决的第一个问题就是：当前数据集上，哪个特征在划分数据分类时起决定性作用（Kaggle中获胜的大牛往往就是特征工程做得好）

---à为了找到决定性的特征，必须评估每个特征

---à完成测试之后，原始数据集就被划分为几个数据子集

---à这些数据集会分布在第一个决策点的所有分支上

---->如果某个分支下的数据属于同一个类型，比如数据下都表明是无需阅读的垃圾邮件，那就不用再分类。但如果数据子集内的数据不属于同一个类型，就需要重复划分数据子集，如何划分数据子集的算法和划分原始数据集的方法相同，直到所有具有相同类型的数据均在一个数据集内

决策树的一般流程

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

准备数据 ： 树构造算法只适用于标称型数据，因此数值型数据必须离散化

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

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

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

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

一些决策树算法采用二分法划分数据，本书没有采用这种方法。如果依据某个属性划分数据将会产生4个可能的值，我们将把数据划分成4块，并创建四个不同的分支。

本书将使用ID3算法划分数据集，该算法处理如何划分数据集，如何停止划分数据集

（进一步详细信息参见：https://en.wikipedia.org/wiki/ID3_algorithm）

思考 ： 每次划分数据集时我们只选取一个特征属性，如果训练集中存在20个特征，第一次我们选择哪个特征作为划分的参考属性？

知识补充：

说明 ： p(Xi)是选择该分类的概率； n是分类的数目

从公式中可以看出，信息熵就是信息的期望值，信息熵越越小，信息的纯度越高，也就是信息越少，在分类领域来讲就是里面包含的类别越少，所以我们可以得出，与初始信息熵的差越大分类效果越好

为了理解这个东西，在网上找了一位网友提供的例子，如下：

一般买苹果的时候，从外观上评判一个苹果甜不甜有两个依据： 红不红 和 圆不圆

下面是手写的计算

那么稍后我们会编写书本提供的关于熵的代码，再利用苹果的例子测试下，是否代码出来的结果和手酸的结果一致。

书本给了一个鱼分类的例子，如图

我们把熵的代码和鱼的代码都打完了，代码链接如下：

https://github.com/MeggieRong/Machine-Learning-In-Action

下面是测试的结果

小结：学习了如何度量数据集的无序程度，也就是熵，得到熵之后，就可以按照获取最大信息增益的方法划分数据集。

划分数据集

我们会对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式

想象一个分布在二维空间的数据散点图，需要在数据支架划条线，将它们分成两部分，我们应该按照x轴还是y轴划线呢？

我们添加下面代码到trees.py中

打入代码到trees.py之后，我们测试一下

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

我们添加下面的代码

加完之后看一下

结果告诉我，第0个特征是最好用于划分数据集的特征

是真的吗？如果是真的，那么有什么意义吗？

再回来看最初的表

这里 是à1否à

如果按照第一个特征划分数据，也就是第一个特征是1的放一组，第一个特征是0的放一组

那么只有一个是分错了

如果按照第2个特征划分数据，也就是第二个特征是1的放一组，第二个特征是0的放一组

那么分错了两个了

小结： 学习了如何度量数据集的信息熵，如何有效地划分数据集，下一节会学习如何将这些函数功能放在一起，构建决策树

递归构建决策树

上面我们已经学习了从数据集构造决策树算法所需要的子功能模块，其工作原理如下：

得到原始数据集

然后基于最好的属性值划分数据集，由于特征值可能多余两个，因此可能存在大于两个分支的数据集划分

第一次划分之后，数据被向下传递到树分支的下一个节点

在这个节点上，我们可以再次划分数据

因此我们可以采用递归的原则处理数据集

递归结束的条件是 ： 程序遍历完所有划分数据集的属性，或者每个分支下所有实例都具有相同的分类。

如果所有实例具有相同的分类，则得到一个叶子节点或者终止块。任何达到叶子节点的数据必然属于叶子节点的分类。如图

简单来讲就是每个特征分完了，再在这个特征下用下一个特征来分

当所有的特征全部用完时仍属于多类,也就是其中当所有的特征都用完时，采用多数表决的方法来决定该叶子节点的分类，即该叶节点中属于某一类最多的样本数，那么我们就说该叶节点属于那一类

我们添加下面的代码

补充理解：sortedClassCount= sorted(classCount.items(),key = operator.itemgetter(1), reverse=True)

到这里，已经保证说我们的特征等都有所归属，下面再添加一个程序代码

这段代码我还不是特别能理解每一条，后期再结合实际项目做回顾

加完了代码之后，测试一下：

变量myTree包含了很多代表树结构信息的嵌套字典，其实就是构成了整颗树

小结：本节学习了如何正确地构造树，下一节学习如何绘制图形，把结果用图反应出来更容易看

在python中使用Matplotlib注解绘制树形图

首先先学matplotlib注解，非常有用的注解工具就是：annotations

我们创建新的py文件，添加下面的代码

….网上下载的pdf运行不出来和官网代码对不上,周末查一下资料再补充