12.4 决策树（I）在线视频

大家好

欢迎来到《R语言数据分析》课程

今天和大家交流

决策树相关的内容

在前面课程里面我们讲到

机器学习有两个非常重要的视角

一个是概率 另外一个就是几何的视角

机器所能学到的都是变量之间的关系

和数据空间的结构

在我们前面讲近邻法的时候

假如从数据空间的结构的角度讲的话

它是一种什么样的结构

或者通过哪种结构的划分实现分类

我们看一下

比如说我们的K近邻

假如这个K=1的话

也就说所谓的最近邻

它其实是把原有的训练集的数据点

它都划成了一个一个的

有一个的自己的势力范围

比如说这两个点

用中垂线一连

这两点中垂线一点

这样的话相互之间

就形成了一个一个像蜂巢一样的

这种自己的势力范围

一旦有一个测试点过来之后

怎么样落入哪个势力范围

那它相应的就归为哪一类了

比如说一旦落入这个这片区域

它后面的标签怎么样

就和这个点◯打的一样

假如这个黑色的区域

它就和这个差×

它的那个标签是一样

这其实就是从我们空间划分的角度讲

近邻法它的一种数据空间划分的过程

说到数据空间划分

其实还有另外一种方法

它也可以用来做分类

比如说这是一个

(由特征属性X和Y构成的)二维的数据空间

显然在这个二维数据空间里面

假如我们不利用这个特征本身的信息的话

这里面其实既有正例也有负例

或者说针对我们这个问题来讲

既有文科也有理科

假如我们一旦开始利用这个(特征)信息的时候

我们可以怎么样进行这个空间的细分

比如说我先细分一下

当X大于0.5的时候

这个时候其实已经将什么

将我们这个二维数据空间分成了两个部分

在右边这一部分 x>0.5 的时候

毫无疑问怎么样

这里面每一个数据点

它的类别都是一样的

比如说我们这是文科的

那当 x<0.5 的时候

这个时候还不够纯

这里面还有不同的类别

那怎么样

继续细分

比如说 x<0.5

并且 y>0.5

这个时候多少

这个时候我们一看

其实就是

它的类别又只有一个了

假如我们说这是文科的话

这边就是理科

当X小于0.5并且Y小于0.5

这个小区域里面它还不够纯

还是有不同的类别

不能用来做分类

还不能把它归某一类

那怎么办

我继续来细分这个数据空间

当我这个 x<0.5

并且 x>0.25的时候

(并且)y < 0.5

这个时候怎么办

它又是属于

又属于理科

否则的话怎么样

属于文科

这其实又是我们今天要引的

另外一种数据空间划分的办法

就是一层一层

细分我这个数据空间

在细分之后

我这里面

每个数据空间里面点

它的标签都是相对比较纯的

然后从而实现了我的分类

将数据空间不断细分

从而实现分类的这么一种办法

其实就是我们今天要讲的

类似于左边这样的决策树

当然决策树有很多具体的那个算法模型

我们今天要讲的是比较经典一种

叫CART分类回归树

咱们接下来看一看

我们具体这棵树长什么样子

我们前面讲了

数据框是我们最美好的结构

几乎可以这样这么说

发现数据背后的规律

在很大程度上都是发现数据框背后的规律

这个数据框同时也是一个数据空间

我们要对这个数据空间进行划分的时候

就可以形成一棵树

也就是说我们可以基于这个数据框

来生成一棵决策树

这棵树什么样

这棵树是一个倒着长的树

根节点在上面

根节点在上面

叶子节点在哪在最下面

中间还有很多内部节点

还有很多内部节点

在这个根节点和这个内部节点上面

都要进行都要进行属性

就是我的特征属性的不同的取值

根据这个取值不同

我进行不同的分枝

在这个分枝的过程

在这个分裂的过程中

其实也是

也就是对我这个空间在进行不断的细分了

直到细分到时候

我这空间已经相对比较纯了

这个时候我就形成一个叶子节点

我们来看一下

一个实际的例子看看究竟是怎么

进行细分的

这个决策树的工作原理是什么样的

比如说我们现在已经有这么一棵决策树了

现在我们有了一条数据记录

或者说我们一个测试集

我根据这个决策树

我怎么来判断我是否是文理分科

就是如何层层细分我这个数据空间

最后做这个判断

首先我们这是根节点

这是原始的起点

起点之后我先看

物理是否大于等于86

我们先判断一下物理是81

毫无疑问它不满足这个条件怎么办

它应该往右走

满足条件往左走 不满足条件往右走

接下来怎么样

我看这个性别

性别等于男

我们看一下性别等于男

那这步怎么样

我应该就往左走了

往左走

接下来我再来进行细分

语文yw

看看我们的语文成绩是不是小于等于这个88

我们看语文

语文成绩的话81

也是满足条件的

接着往左走

接下来再看

化学是否大于等于93

看看化学成绩

化学成绩在这88分

那这个时候毫无疑问得向右走

因为它不满足这个条件

再往下走 我们看看

看历史的情况

是小于86还是大于等于86

小于的话向左走大于等于的话向右走

我们看一下

这个历史的话94

毫无疑问这个时候怎么办

它应该就是到叶子节点了

这个空间已经细分的足够小了

怎么办

我可以做这个判断

这个时候应该是

一看这叶子节点

它的类标签是文科

那这个时候我们触底了

就已经到文理分科就变成

就变成应该就视之为文科

恰好

和我们原始记录它的文理分科的类别是一致的

也就是说通过这么一个决策树我可以

我可以做空间的细分

然后做出一个类别的判断

我们来看看这是模型

我们最后建的模型就这么一棵树模型

这么一个树的模型

那我们怎么来学到这么一棵树

或者说我们怎么从这个数据框里面

挖出这么一棵树出来

我们先看看

现在我们有了数据框之后

其实我们刚才通过这个决策树的工作过程

可以看得出来

它其实就是

其实就是各种各样条件属性的组合

如果物理小于86

并且性别等于男

并且语文小于88

并且化学小于93

并且历史大于等于86

等等这些条件满足之后怎么办

我可以作这个判断

文理分科就是文科

那这个时候我们就可以想

假如我现在想通过这么一个数据框

来挖出这些规则的话

它其实有形成那么一棵树

但是我们要考虑

比如说我们现在总多少属性

总共有性别

再加上后面这个九科成绩

总共有十个属性十个特征

然后每个特征上面有不同的取值

性别有男女

然后语文数学外语等等等等这个科目

它又有不同的那个取值的范围

取值的区间

我们可以很容易想象

这么一个组合的话

假如我是通过蛮力搜索

这个时候应该是组合爆炸

没有可操作性

或者说我们这个想找到一个全局最优的

就把所有的规则[条件]都组合起来之后

我判断情况之下我的规则最好的

生成一个最好的决策树

这是一个NP问题

这是一个NP问题

所以我们得想 有办法来生成

我们这棵决策树对空间进行逐步细分

进行判断

但同时又(具)有可操作性

我们再看一下我们的决策树

决策树怎么做的

我们再看一眼

生成的这棵决策树

我们从上往下看的时候就会发现一个特点

其实我们这棵树是一层一层往下走的

逐层深入 逐层细化

它并不是说我们刚才那条规则

一次性把这个规则所有的条件

都判断都都考虑了

比如我同时考虑性别

同时考虑语文 数学 地理 化学等等

这些不同科目的取值情况

我都一次性考虑

不是这样的

因为这样一次性考虑所有的条件的时候

我们没有办法进行一个有效的搜索

而且我们一下考虑不过来怎么办

我采用一种

局部最优的方法 步步为赢

什么意思

我们看比如说我第一次我只考虑物理

在针对这个目前这个数据集的时候

我只选择一个属性(的分裂点)来进行分裂

做一个条件判断

比如说我先选好一个物理这个条件

这个属性(划分)是最好的

然后再找到一个一个分裂的条件

怎么办

就看物理是否大于等于86

大于等于86的是一种情况

小于等于86另外一种情况

在大于等于86的情况之下

这个时候我已经将这个数据集

将这个数据空间进行了细分

在这个细分的基础之上

我再怎么样再考虑下一个

在这十个特征(的诸多分裂点)里面再选一个最好的

再进行第二次细分

再进行第三次细分

所以可以看得出来

它并不是一次性把所有的特征(分裂点)一次性

完整考虑

我再说我一次性把所有的条件组合

都遍历一下

不是这么一种蛮力搜索的方法

而是什么

我在当前这个情况之下我选一个最优的

只选择一个属性

(同时)找它相应的最优的分裂点

然后在这个情况之下

我在第二步的时候第二层的时候再往下走

我们可以这样想这样

这样来形容这个问题

它是一个局部最优的过程

是一个步步为赢的过程

步步为赢的过程

或者说它是一个摸着石头过河的过程

因为这个全局的过程我没有办法看到

那我就先把当前这一步先走好

在目前这个情况之下

哪一个属性(分裂点)是最好的

哪个属性(分裂点)可以进行分裂

然后我进行一个空间的细分

然后再下一次

接着对这个子空间再进行细分

直到将我的数据空间分的足够小的时候

这里面相应的类标签是比较纯的

就可以做分类和判断

所以 这是我们决策树的一个非常核心的思想

它是一个局部最优的过程

就是我先盯着当前的利益

先往前迈好当前这一步

我们刚才讲了

这里面其实一个选择的过程

就是它其实我们总共可以有十个特征

进行选择进行分裂

但是不同的特征(分裂点) 它的分辨能力是不一样的

为了说明这个问题

我们对前面这个数据进行一个简化

比如说我们现在只考虑性别和语文

这两个属性

两个特征

我既可以根据性别进行

进行后面文理分科的判断

也可以根据语文进行文理分科的判断

性别和语文它虽然都是候选

但它的分辨能力是不一样的

什么意思

它最后比如说我性别为男的时候为理科

性别为女的时候为文科

或者说成绩为好的时候

为文课成绩不好的时候为理科

类似这个意思

那其实它的分辨能力是不一样的

我们看一下

假如我是根据这个性别来进行划分的话

我们一看

当我性别为男取理科

这时候只有一个错误的

其它的全是理科

当我性别为女的时候基本上全都是文科

也只有一个是错误的

但是假如我现在根据语文成绩的好坏

来做文理分科的判断的话

那就不一样了

当然前面成绩不好的时候

有一个是文科一个错误

然后成绩好的时候

大家看看理科文科理科理科文科文科

几乎就没有分辨能力

所以这个时候我们涉及到一个问题

虽然我们是局部最优步步为营

但要走好当前这一步的话怎么样

我必须找到一个比较好的特征(分裂点)

我后面才能

将这个数据空间划分得比较纯

就是子空间相对比较纯

才有利于我们后面做类别的判断

决策树的算法它属于一个递归的过程

递归划分的过程

我们说递归的话毫无疑问

它就是一个层层递进

逐层回归的过程

那必须有一个触底

我先定义这个触底的过程

触底的过程的话

我们这边是满足我这个停止条件的话

我相当于触底了

这个停止条件是

比如说

切分的子空间已经足够纯了

这个类标签是完全一样的

毫无疑问我就不需要再进行进一步的细分

当然也有另外一种情况

不是说不需要有是没有办法再继续细分

比如说我现在总共有十条记录

也就有十个特征向量

那这十个特征向量怎么样

它取值都是一样的

那我也没有办法再继续进行细分

这个时候都满足所谓的停止条件

这个停止条件一旦满足的话

那我就相当于这个递归的时候已经触底了

层层递进时候已经触底

触底的话时候怎么办

就创建一个节点作为叶子结点

并且对这个叶子节点进行类别的划分

也就说给这个叶子节点贴上相应的标签

那这个贴这个标签怎么贴

这个Classify怎么来贴

这个标签怎么做分类

其实又回到我们最初讲的

叫“有生于无”

也就是说当我们没有任何模型的时候

这时候怎么办

那就是通过平均值众数这个最基本的方法

我们这个叶子标签对这个分类问题来讲怎么办

我就是取它的众数就是少数服从多数

这个子空间里面

类别标签最多的那一个把这个标签拿过来

作为我当前这个叶子节点的标签

同时返回这个叶子节点

这个时候就做了

就实现了这个触底的过程

咱们更需要关注一下这个递归的过程

递归怎么做的

我先创建一个节点作为根节点一个root

当前这个根节点上面这份数据这个D

这个D这个数据

我怎么样我找到一个最好的分裂的属性

根据这个属性取值的不同

进行一个分枝

对我们这个问题来讲

比如说以这个决策树为例

它选择是物理

然后具体的分裂的条件是

就是物理是否大于等于86

大于等于86是一个条件

小于86是另外一个条件

我们将这两个条件放在一个集合里面来

放这个V里面来

接下来我们再看接下来步骤

我们看一下这个时候对于每一个v∈V

就是我们这个大于等于86和小于86

每一个v∈V都做一个操作是

我先看看

我有哪些数据是满足这一个条件

其实就在做数据空间的切分

切分完之后比如说

我刚开始有700多条数据

根据我这个物理成绩的大小

然后我就把它分成两部分了

对于这个数据的子集我又怎么样

我进一步又

调用我这个生长这个算法

生长这个函数

树生长这个函数进行

递归调用

也就是说我先将这个百分之百的数据

创建了一个节点

然后把它分成两部分

第一部分包含43%的数据

另外一部分包含57%的数据

对于我这43%的数据怎么样

同样还要做一个

继续往下进行分裂

分裂完之后

我再看它子集是不是还要再进行分裂

也说一直往下层层递进

不断做分裂

这个时候我怎么样

因为你在做分裂的过程中也要创建个节点吧

对于这个新的这个Dv这个数据集来讲

我还要创一个节点

再进行逐层的递归的划分

这个时候我将

最后将这两个节点连在一起

作为一条边

同样对于这个数据集来讲

我还是要做

还是要进行划分进行划分

划分完之后怎么样这里面有不同的节点

将这个节点和这个

root连接起来

作为一条边

以此类推 逐层递进

生长这棵树

当然我们在讲这个过程的时候

也发现里面一个非常关键的点是

就是选择最优的属性(分裂点)进行分裂

进行空间的划分

那样的属性(分裂点)才是最好的

其实我们刚才通过前面例子可以看得出来

就是经过这个分裂之后

我这个子空间要足够纯

因为我最终是要对这个子空间贴上标签

那子空间越纯的话我怎么样

我的这个当前这个属性分裂是最优的

其实几乎所有的决策树算法

它都是这么一个层层递进

逐层分区的过程逐层划分

对我这个数据空间进行分区的过程

不同的是不同的决策算法

它有不同的不纯度的划分的判断的标准

就是如何选择这个最优的分裂

这里面有所有所区别而已

比如说我们有

我们有这个ID3算法有了改进的叫C4.5

再比如说我们有这个CART算法

它其实是基于不同的不纯度的划分

也就是说你这个叶子节点

你这个就是你这个相应的属性判断完之后

相应的属性进行不同取值之后

我进行我进行子空间划分的时候

子空间不纯度如何降低

这个不纯度降低的越快的话我就来怎么样

我就把当前这个属性(分裂点)

当前这个属性取值不同

我来进行一个相应的分裂

ID3算法是根据这个

信息增益来做这个不纯度的衡量的

然后这个C4.5是根据这个增益率

而我们这边今天要讲的这个CART

是根据什么

基尼指数(系数)

这里面是相应的一些不纯度的一个评价的方法

比如说这里面有那个信息熵的方法

有基尼指数的方法

当然也可以这种

就是直接这个分类错误率也可以

就是我最多的那一类它所占的比例是多少

然后一减掉它就是我们分类的错误率了

因为我们刚才讲到了这个所谓的每个节点上面

它其实贴上标签的时候都是少数服从多数

就是最多的那一类作为我的标签

那其它的都作为分类错误率

这是我们决策树的一个算法的最基本的原理

我们举个实际的例子看一看

这个不纯度怎么计算

比如说我们以这个分类错误率为例

我们当前拿到这个数据

它文理分科其实相对是不纯的

我们始终盯着这一列

始终盯着这一列

文理分科这里面有多少个

1-2-3-4-5

有5个理科有4个文科

那这个时候不纯度

假如按照这个分类错误率来看的话

不程度多少 4/9

4/9也就是0.44左右

现在假如我是根据这个性别进行分裂的话

我们看一下这个性别分完之后

你看这里面错的

第一组里面为男的话错了几个

应该是5个里面错了1个

然后为女生的话我们再看这个分裂

应该是4个里面错了1个

所以它分别的每一个子集的

这个不纯度分别是1/5和1/4

当然因为它是进行了一个分裂

所以我们要乘一个

做一个加权平均分别是5/9和4/9相乘

然后最后它的不纯度多少0.22

0.22毫无疑问这个不纯度下降就比较快了

就是由0.44下降成0.22

所以这个通过性别来进行分裂

进行一个空间的划分是可行的

那相反我们看看这个语文它的表现怎么样

比如语文这一块的话我也是分成的

我们为了这个演示我们只将它分成两组

一个是不好一个是好

不好的话这里面有分类错误率多少

1/3也是不纯度是1/3

我们再看那个(语文成绩)好的这一部分

它总共有6个错了3个是3/6

同样我们也做一个加权平均的话

它结果多少

0.44

也就是说

假如我经过这个语文来进行分裂的话

其实它不纯度基本上没有降低的

也就是说什么意思

当我在这个

性别和语文两个特征(分裂点)里面选择的时候

毫无疑问应该选择

我应该选择性别这一个

选择性别这个属性(分裂点)进行一个空间的拆分

这个时候才有利于我们

将这个空间的不纯度进行降低

这其实也就是我们这个所谓的

决策树一个最基本的原理

根据相应的属性不同的取值

进行拆分拆分拆分

拆分的选择的标准是就看它不纯度

哪一个属性上面取值进行分裂的话

它的不纯度降低是最快的

就变得越来越纯

这个时候我就把它作为

当前的一个拆分的条件

层层递进直到我们达到这个终止条件

我们用一句话来形容

简单总结一下

我们所谓决策树的生长

它就是递归划分不断生长的过程

在这个过程中

我们始终要强调

局部最优 步步为赢

如果这个数据无需再分

就比如说当前所有的这个子空间里面

这个类标签都为一类了

或者说是无法再分

比如说所有的特征向量取值都相同

或者说这个数据记录数太少了

那这个时候怎么样我建立叶子节点

并且按照这个

少数服从多数的原则进行

分类 进行打标签

否则的话我就找一个属性

根据该属性对

不同的取值情况把数据分成

纯度较大的

两个或多个子集

进行空间的切分

对这些子集怎么办

这个子空间我继续递归执行以上操作

进行开枝散叶

不断生成这个

让这个决策树不断往下生长

这就是我们决策树归纳法的一个最基本的原理

咱们看一下在R里面是如何实现的

我们刚才讲它是一个递归划分的过程

所以我们有一个相应的包叫rpart

我们通过这个TaskViews可以看得出来

就是rpart实现我们这里面所谓的

这个分类回归树

我们看一下具体是如何实现的

我们可以加载这个包

就是通过这个library()这个函数

加载rpart.plot

我们一看是对rpart进行绘图

当然这个包它其实会自动关联地加载

rpart这个包

加完之后

我们调用这个rpart里面的相应的这个函数

这个函数名字还叫rpart

它接受至少两个参数

首先我的公式

波浪号前面是因变量

波浪号后面是自变量

这个点号表示点号表示

除了这个因变量之外的这个数据集里面

所有的其它变量都作为都作为自变量

当然你要基于哪个数据建模

也得告诉这个rpart这个函数

建完模型之后我们看看

看看这个imodel它究竟是

我们所建的模型在控制台里面显示这样的

这么一些具体的一些结果信息

首先这个n=542表示什么

我们把数据分成两部分

一个是训练集一个测试集

训练集里面用来训练这棵树的

总共有多少542条记录

接下来这一行是这一行是指示性的

用来说明以下的所有的每一行

它究竟代表意思

以下每行里面首先有个节点的编号

有这个node的编号有如何做分裂的split

记录数

错误的数量

相应的取值以及

它相应的不同的概率

所占的不同的比例

我们看一下具体的

比如说首先一个根节点

这个时候也是542条记录

我要判断它是我要判断它是是文科

因为少数服从多数了

文科相对是多一点

文科在这542条记录里面占多少

占到50.9%理科占到49%

这个时候错误的有多少

错的有266

然后接下来往往下走

就是第二个第三个第四个节点

咱们结合这棵树来看一下

比如这棵树的话

这边是第一个节点

这个第二个

第三个

4-5-6-7-8-9

10-11-12-13-14-15

16-17-18-19

注意了

8-9-10-11-12-13-14-15

这下边一个是多少

16-17-18-19

毫无疑问

这个时候因为它第8个节点已经触底了

这个时候第8个节点下面是没有

第16 第17的

但是在后面的结果里面

它编号的时候还要当做它有

所以我们看到的是

18 19这么相应的一些节点

就第9个节点下面是18 19

对于每一个节点我们看一下

比如说第二个节点的话是我作一个判断

是数学是否是大于等于86

下面是85.5做了一个round四舍五入

这个时候总共的记录是多少 322条

有多少错误 115条是错误的

我们这个判断它判断是理科

理科占了64%

假如在当前这个节点上就停止分裂的话

因为我是理科占多数 占64%

文科占35%那毫无疑问

当前这个叶子节点应该是一个理科

但是当前这个节点还不能作为叶子节点

就当前这个节点不能作为叶子节点

因为为还没有达到我们这个停止的条件

要继续分裂

什么时候是叶子节点

当我这个是星号的时候是叶子结点

我们看了一下

这边有一个说明

星号代表它是叶子节点

就是逐层分裂组成分裂一直分裂到

满足了相应的停止条件之后

我就视为叶子节点了

这就是一棵树的一个输出的结果

它其实和我们看到的可视化的方式

它其实是完全一致的

咱们看看这个数它的性能表现如何

我们先看看在训练集上的拟合的效果

这个时候还是一个训练的误差

怎么样呢

要用这个模型来做预测的话

看这个训练集的表现的话

我还是用predict()

用这个函数

这里面这个newdata和我们刚才训练集合的

那个data应该是设得一致的

我先看看训练集的拟合效果怎么样

然后我预测结果是

预测结果是type="class"

就表示我返回的结果不是这个比例不是概率

而是而是我具体的这个类标签了

我们再调用这个Metrics

这个包里面的ce表示

分类错误率

我将这个实际的值和这个预测值进行一个比较

就发现它的错误率是多少19%

就是100个同学里面

有19个可能预测错了

也是十之七八 十之八九

这里边能预测对

有80%左右预测对

当然这只是一个训练集的效果

我们更应该看

应该看测试集

因为测试集的效果

在某种程度上和我们泛化的误差是近似的

我们看一下在测试集上性能表现怎么样

测试集同样我还是用这个predict()这个函数

来进行预测这个newdata这个时候设成注意了

这个时候就是我的相应的测试集了

同样我预测结果还是

还是我一个具体的类标签

我们看一下这个ce的表现多少

这个时候达到25%

就有75%是对的 有25%是错的

这是我们一个模型的一个泛化的性能

测试的误差

这里面到此为止

我们基本上就将这个决策树的算法

这个生长的过程我们讲了一下

并且在R里面如何实现的

通过这个rpart这个包来实现它

那是不是我们这个事情就完事了吗

或者说我们这个决策树这个建模工作

包括我这个预测这个具体的在数据集

进行训练进行训练进行测试

是不是整个流程走完了吗

还没有

我们对决策树来讲

生长它只是第一个环节

还有后面一个必不可少的步骤是剪枝

为什么呢

我们先看看 看这么一个例子

假如我通过决策树也好通过哪个分类算法也好

我来对这个瓶子进行二值分类

就判断我们目前这个图像里面哪些是瓶子

哪些不是瓶子

当然我们可以找到一些具体属性一些特征

比如说这个瓶子的肚子的大小 脖子的长度

或者还有它的颜色都可以

假如我们来做拟合的话

通过这个决策树来拟合

其实我可以相对一棵比较简单的树

我直接判断

当我这个容器它肚子比较大

脖子比较细比较修长的时候

它就是一个瓶子

根据这么几个简单的属性就已经可以做判断了

假如我这个训练的这个树生长的太茂密的话

太茂密的话

就先考虑的因素太多了

这个时候可能出现一个情况

比如说我连这个颜色我都考虑进来了

当我这里面是蓝色的时候

我就将它视为瓶子

这个时候就出现一个问题

就这个树生长太茂密之后

就出现一个过拟合的问题

实际上并不是说所有的瓶子都必须是

必须是蓝色的

但因为受我当前这个训练集的影响

受我当前这个训练集的局限

我们要是考虑太多的那个属性的话

就会发现

它在我们当前这个训练集上面

毫无疑问它是比较准确的

但是它泛化能力就比较差了

所以我们希望我们这棵树不要太复杂

这就是后面我们要讲的第二个步骤

就是在生长完之后我还对树进行剪枝

具体剪枝过程我们下节课再讲

本次课到此结束

谢谢大家