文章

机器学习（6）——决策树

前言：

前言：

通过第前面的学习介绍了机器学习回归模型创建的流程，并且知道了机器学习要做的事情是找到目标函数，优化它，通过每次迭代都使目标函数值最小，最优解就是目标函数最小化时侯对应的模型参数。而这一章会介绍一种和回归模型流程相反的模型—决策树，它是通过建立树模型之后，才得到的损失函数，并且成为衡量决策树模型的指标。有时候数据特征众多且巨大，可以利用这种直观的树结构对数据特征进行切分，然后再构建模型。

本章主要涉及到的知识点有：

  • 信息熵

  • 决策树

  • 决策树优化

  • 树剪枝算法

  • 决策树可视化

算法思想：从决策到决策树

本节首先通过我们做决策时候的经历引出决策树算法的基本思想，然后介绍决策树的基本概念。

决策

首先来看什么是决策。我们在生活中经常会依靠各种信息做出各种决策，比如说选择大学，选择专业，找工作，找对象……。又或者你过年回家经常就会碰到这样的问题：

母亲：给你介绍个对象。

你：年纪多大了？

母亲：26。

你：长的帅不帅？

母亲：挺帅的。

你：在哪工作？

母亲：和你在一个城市

你：干什么呢？

母亲：听说是程序员。

你：那好，我去见见。

这个时候你在做决策的时候就运用了决策树的核心思想。通过“对象”的许多特征，你可以决定见或者不见。

决策的过程为我们理解决策树的建立提供了很大的帮助。计算机是通过数据来对事情做出预测，下面给一个更加直观的例子如图：

image

能否偿还债务表

通过给出10组数据来构建决策树判断是否能偿还贷款债务。

依据决策画出决策树如下：

image

能否偿还债务决策树

中红色结点（根结点）表示判断条件，橙色结点（叶子结点）表示决策结果。通过数据得到决策树的过程叫决策树的构建。 注意：寻找最优根节点和使得叶子节点最优化是决策树算法的最主要的任务。这种注意技巧两页必须有一个。

决策树

  • 定义

基于上面的理解我们可以给出决策树的定义：

决策树( Decision tree)是在已知各种情况发生概率的基础上,通过构建决策树来进行分析的一种方式,是一种直观应用概率分析的一种图解法;决策树是一种预测模型,代表的是对象属性与对象值之间的映射关系;决策树是-种树形结构,其中每个内部节点表示—个属性的测试,每个分支表示一个测试输出,每个叶节点代表一种类别;决策树是一种非常常用的有监督的分类算法。

注意：“内部节点”和“叶子节点” 决策树的决策过程就是从根节点开始,测试待分类项中对应的特征属性,并按照其值选择输出分支,直到叶子节点,将叶子节点的存放的类别作为决策结果。 决策树分为两大类:分类树和回归树,前者用于分类标签值,后者用于预测连续值,常用算法有lD3、C45、CART等

2．决策树构建

决策树算法的重点就是决策树的构造;决策树的构造就是进行属性选择度量,确定各个特征属性之间的拓扑结构(树结构);构建决策树的关键步骤就是分裂属性,分裂属性是指在某个卡点按照某一类特征属性的不同划分构建不同的分支,其目标就是让各个分裂子集尽可能的纯(让一个分裂子类中待分类的项尽可能的属于同一个类别)： 注意：寻找“分裂属性”以及使得“叶子节点”更“纯” 构建步骤如下:

q 1.将所有的特征看成一个一个的节点;

q 2.遍历每个特征的每一种分割方式,找到最好的分割点;将数据划分为不同的子节点,eg:N1、N2、…、Nm计算划分之后所有子节点的纯度信息;

q 3.对第二步产生的分割,选择出最优的特征以及最优的划分方式;得出最终的子节点:N1、N2.、……、Nm

q 4对子节点N1、N22Nm分别继续执行2-3步,直到每个最终的子节点都足够纯

3．决策树属性类型

根据特征属性的类型不同,在构建决策树的时候,采用不同的方式,具体如下：

q 属性是离散值,而且不要求生成的是二叉决策树,此时一个属性就是一个分支

q 属性是离散值,而且要求生成的是二叉决策树,此时使用属性划分的子集进行测试,按照“属于此子集”和“不属于此子集”分成两个分支

q 属性是连续值,可以确定一个值作为分裂点 split point,按照> split point和

![image](/writing/ml/ml-6-decision-tree/img-03.png)

编码图

每个字母平均用两个用2个bit位。

然而用如图8.2.2.2编码进行传递，传递的序列为：010001100111000

![image](/writing/ml/ml-6-decision-tree/img-04.png)

编码图2

每个变量平均用的bit位数量计算如图8.2.3所示：

![image](/writing/ml/ml-6-decision-tree/img-05.png)

编码公式

这正好香农提出的香农熵的概念很相似。

### 信息熵

又叫香农熵，是香农在1948年引入的一个概念，他指出，一个系统越是有序，信息熵就越低，一个系统越混乱信息熵就越高，信息熵被认为是一个系统有序程度的度量。

1．**信息量**

指一个样本所蕴含的信息，如果一个事件发生的概率越大，那么就认为该事件所蕴含的信息量越少。例如：

极端情况下，“太阳从东边升起”，因为是确定事件，所以不携带任何信息。

“昨儿逛街碰上了周杰伦”，这句话就包含很多信息

2．**信息熵**

信息熵公式如图所示：

![image](/writing/ml/ml-6-decision-tree/img-06.png)

信息熵公式

随机变量X中的有m个事件，每个事件平均需要bit位的个数就是信息熵得概念。如果某一个事件的概率特别大，那么该变量蕴含的信息量就会变少，从而信息熵就会变小。例子如下：

赛马比赛中，有两组赛马共八匹，获胜的概率如图：

![image](/writing/ml/ml-6-decision-tree/img-07.png)

赛马信息

对于第一组而言概率一样，很难猜测哪匹马会赢，对于第二组来说，很明显可以得出结论A马更容易获胜。算出信息熵第一组H(X)=2;第二组H(X)=1.336

### 条件熵（H(Y|X)）

总体来说就是熵的期望。

1．**定义**

给定条件X的情况下，随机变量Y的熵就叫条件熵：

例如图所示：

![image](/writing/ml/ml-6-decision-tree/img-08.png)

专业信息

专业（X为数学时）Y的信息熵H(Y|X=数学)=1在给定条件X的情况下，所有不同x值的情况下Y的信息上的平均值叫做条件熵。上述例子中求得的条件熵的结果如图所示：

![image](/writing/ml/ml-6-decision-tree/img-09.png)



## 决策树模型构建

### 决策树量化纯度

问题一：前面算法思想里面提到了，决策树模型的关键是分割属性使得最终的叶子节点的纯度越“纯”，可是如何衡量叶子节点的纯度呢？ 问题二：另外属性的分割是决策树算法的另一个要面对的重要问题，那么如何进行属性分割呢？ 通过上面的问题我们给出信息增益度的概念

1．**信息增益度**

结合信息熵的概念可以得知，信息熵越小，叶子节点中某一事件的概率越大，我们可以认为此叶子节点就越纯，所以信息熵可以是衡量叶子节点纯度的一个指标。信息熵公式如上图所示。 当计算出各个特征属性的量化纯度值后使用信息增益度来选择岀当前数据集的分割特征属性;如果信息增益度的值越大,表示在该特征属性上会损失的纯度越大那么该属性就越应该在决策树的上层,计算公式为: Gain=△=H(D)-H(D|A) Gan为A为特征对训练数据集D的信息增益,它为集合D的经验熵HD)与特征A给定条件下D的经验条件熵HDA)之差。此外我们评估叶子纯度指标还有两个，分别是gini系数和错误率

2．**决策树算法的停止**

决策树构建的过程是一个递归的过程,所以必须给定停止条件,否则过程将不会迸行停止,一般情况有两种停止条件：

q 当每个子节点只有一种类型的时候停止构建

q 当前节点中记录数小于某个阈值,同时迭代次数达到给定值时,停止构建过程,此时使用max(P(i)作为节点的对应类型


方式一可能会使树的节点过多,导致过拟合 Overfiting)等问题;比较常用的方式是使用方式二作为停止条件

3．**决策树算法评估**

和分类算法一样，可以采用通用的，准确率，召回率，F1等指标进行评估。

可是和别的分类算法不同的是可以采用叶子节点的纯度来评估算法效果，叶子纯度值和越小，则分类的越清楚，算法越好，公式如图：

![image](/writing/ml/ml-6-decision-tree/img-10.png)



当然了，根据之前学的损失函数的定义，该公式可以被叫着损失函数或者目标函数，我们的目的就是找到这样一颗决策树，使得loss最小。

4．**三种决策树算法**

决策树一般有下列三种算法,其基本都是运用上面原理构建决策树的：

q ID3

q C4.5

q CART


ID3算法是决策树的一个经典的构造算法,内部使用信息熵以及信息增益来进行构建;每次迭代选择信息增益最大的特征属性作为分割属性。 优点是构建速度快，实现简单。缺点是对于特征数目较多的数据，效果很差，它不考虑属性之间的关系，抗噪性差，只能是适应于小规模数据集。

C4.5算法是在D3算法的基础上,进行算法优化提出的-种算法(C4.5); 现在C4.5已经是特别经典的一种决策树构造算法;使用信息增益率来取代|D3算法中的信息增益,在树的构造过程中会进行剪枝操作进行优化;能够自动完成对连续属性的离散化处理;C4.5算法在选中分割属性的时候选择信息增益率最大的属性,涉及到的公式为: P(i)=-∑P(i)log2(P(i))

信息增益率：

![image](/writing/ml/ml-6-decision-tree/img-11.png)



优点是准确率高，实现简单，对特征数目没有限制，缺点是效率不如ID3

CART算法最大的区别是使用二叉树，它的特点是属性特征可以重复性使用，是最常用的一种算法，后面的例题中就会使用CART算法。

5．**分类树和回归树的区别**

分类树采用信息增益、信息增益率、基尼系数来评价树的效果,都是基于概率值迸行判断的;而分类树的叶子节点的预测值一般为叶子节点中概率最大的类别作为当前叶子的预测值

在回归树种,叶子节点的预测值一般为叶子节点中所有值的均值来作为当前叶子节点的预测值。所以在回归树中一般采用MSE作为树的评价指标,即均方差。

![image](/writing/ml/ml-6-decision-tree/img-12.png)



一般情况下,只会使用CART算法构建回归树。

## 决策树优化

一般情况下决策树优化有两种方法分别是剪枝优化和随机森林，这里主要介绍剪枝优化，在后面的集成学习中会介绍随机森林。

### 剪枝优化

决策树的剪枝是决策树算法中最基本、最有用的一种优化方案,主要分为两大类。

**1**．**前置剪枝**

在构建决策树的过程中,提前停止。

一般有两种停止条件：

1） 控制数的深度

2） 控制叶子节点中样本的数目


**2**．**后置剪枝**

在决策树构建好后,然后再开始裁剪,一般使用两种方式:

  1. 用单一叶子节点代替整个子树,叶节点的分类采用子树中最主要的分类;

  2. 将一个子树完全替代另外一棵子树;后置剪枝的主要问题是计算效率问题。


后剪枝总体思路(有点类似交叉验证)完全树T开始,剪枝部分节点得到T1,在此剪枝得到T2….直到仅剩树根的树T在验证数据集上对这k+1个树进行评价,选择最优树Ta(损失函数最小的树)

剪枝过程：

对于给定的决策树T0，步骤如下：

1 计算所有内部非叶子节点的剪枝系数

2 查找最小剪枝系数的节点,将其子节点进行删除操作,进行剪枝得到决策树Tk;如果存在

3 多个最小剪枝系数节点,选择包含数据项最多的节点进行剪枝操作

4 重复上述操作,直到产生的剪枝决策树T只有1个节点

5 得到决策树T0T1T2…Tk

6 使用验证样本集选择最优子树Ta


问题来了，如何计算非叶子节点的剪枝系数呢？通过验证集选择最优子树的标准,可以使用原始损失函数来考虑。原始的损失函数：

![image](/writing/ml/ml-6-decision-tree/img-13.png)



叶子节点越多，决策树越复杂，则损失越大，我们添加一个关于叶子节点数目的系数α，上式可以写作： loss= loss +α* leaf 剪枝前后的损失函数分别为loss（r）和loss（R），为了保证减掉的多余的枝子，可以认为： loss(r)-loss(R)=0 带入上述公式求得系数为： α = loss(r)-loss(R)/leaf-1 命名α为剪枝系数，则可以通过求到的α进行决策树优化了。

## 决策树可视化

决策树可视化可以方便我们直观地观察所构建的模型，它依赖于graphviz服务，可视化之前执行如下操作。

### 软件安装以及环境配置

1.graphviz服务安装

q 下载安装包，官方网站：http:www.graphviz.org/

q 执行下载好的安装包（双击msi安装包）

q 将bin文件夹添加到PATH环境变量中

2.安装python插件

01 pip install graphviz

02 pip install pydotplus


### 可视化实例

有二种方法可以实现可视化，我们假设已经建好了模型，把模型进行可视化输出代码如下：

**1**．**将模型转化为dot文件，通过命令行执行dot命令： dot -Tpdf iris.dot -o iris.pdf，将dot文件转化为pdf文件**

01 /// 引入可视化包

02 from sklearn import tree

03 with open(‘model.dot’, ‘w’) as f:

04 da = tree.export_graphviz(tre, out_file=None）

05 f.write(da)


**然后通过指令转化为pdf格式，如图所示：**

![image](/writing/ml/ml-6-decision-tree/img-14.png)



2．**使用image对象直接显示图片**

01 /// 引入可视化包

02 import pydotplus

03 from sklearn import tree

04 dot_data= tree.export_graphviz(model, out_file=None）

05 graph = pydotplus.graph_from_dot_data(dot_data)

06 Image(graph.create_png())

注意：“model”是我们已经创建好的决策树模型


在 tree.export_graphviz方法里面可以给定可视化的颜色使得决策树更加的好看。下面是例子中通过上面程序画出来的决策树，如图所示：

![image](/writing/ml/ml-6-decision-tree/img-15.png)

决策树的可视化

每个节点都有着详细的信息，包括，样本的数目，特征的数量，所属的特征属性等。

## 综合示例

本节将利用回归部分模型建立的基本步骤和本章决策树的原理，实现一个完整的示例： 通过鸢尾花数据集，构建出决策树模型，并且对新的数据进行预测，并且进行可视化展示。

注意：问什么选鸢尾花数据集？第一，该数据是机器学习的经典数据集，是sklearn学习文档的指定数据集，第二，该数据集能够体现决策树深度对决策树过拟合的影响。


### 决策树模型构建流程

**1. 收集并准备数据**

收集数据可以用任务方法，这里用到的数据是从国外经典数据网站下载的，网址：http://archive.ics.uci.edu/ml/datasets/Iris

数据集包含150个数据集，分为3类，每类50个数据，每个数据包含4个属性。可通过花萼长度，花萼宽度，花瓣长度，花瓣宽度4个属性预测鸢尾花卉属于（Setosa，Versicolour，Virginica）三个种类中的哪一类。

- **导入数据**

  1. import pandas as pd

  2. path = “datas/iris.data”

3. df = pd.read_csv(path,sep=”,“,header=None)


查看前五行数据如8.6.1所示：

![image](/writing/ml/ml-6-decision-tree/img-16.png)

鸢尾花数据

- **划分特征属性和目标属性**

从图可以看出，前三列为特征属性，第四列为目标属性
  1. x = df.iloc[:,0:4]

2. y = df.iloc[:,4]

  1. ** 把数据集分为训练集和测试集**

直接引入sklearn中的划分数据集的包

  1. from sklearn.model_selection import train_test_split

2. x_train,x_test,y_train,y_test=train_test_split(x,y,test_size=0.2,random_state=0)

为什么要引入包？用别人做好的包，代码很简洁，写起来很轻松，自己也能实现数据集划分的源码，可非常繁琐，例如，手写数据集划分的源码如下：

def loadDataset(fileName,split,trainingSet=[],textSet=[]):

with open(fileName, "r") as f:

    reader = csv.reader(f)

    data = list(reader)

    for x in range(len(data) - 1):

        for y in range(4):

            data[x][y] = float(data[x][y])

        if random.random()

image

决策树深度对模型的影响

分析：从图中可以看书，随着树的深度的加深，正确率会提高，达到临界值之后（树的深度为6），训练集正确率达到最高，而测试集正确率开始下降，多以决策树的深度越深就会出现过拟合。从而引出过拟合问题的解决办法，只保留深度为2的决策树的情况下，通过建立很多树的模型——随机森林。

本章小结

本章先介绍了决策树是通过原始数据做出决策的一种算法，它清晰直观，直接就按照特征属性来划分数据集。而划分数据集的关键是寻找使得叶子节点信息熵最小，这是决策树的基本原理；而后介绍了，决策树的优化方法，决策树的树的深度对过拟合的影响等，通过决策树的特征属性的划分方法，我们得知通过构建决策树，可以得到特征属性对目标属性影响的权重。最后给一个经典的例子，来更好理解决策树的原理。接下来我们我会解决本章最后提高的问题。