CART决策树(分类回归树)分析及应用建模

时间:2022-08-05 04:57:12

一、CART决策树模型概述(Classification And Regression Trees)

    决策树是使用类似于一棵树的结构来表示类的划分,树的构建可以看成是变量(属性)选择的过程,内部节点表示树选择那几个变量(属性)作为划分,每棵树的叶节点表示为一个类的标号,树的最顶层为根节点。

决策树是通过一系列规则对数据进行分类的过程。它提供一种在什么条件下会得到什么值的类似规则的方法。​​决策树算法属于有指导的学习,即原数据必须包含预测变量和目标变量。决策树分为分类决策树(目标变量为分类型数值)和回归决策树(目标变量为连续型变量)。分类决策树叶节点所含样本中,其输出变量的众数就是分类结果;回归树的叶节点所含样本中,其输出变量的平均值就是预测结果。​

决策树是一种倒立的树结构,它由内部节点、叶子节点和边组成。其中最上面的一个节点叫根节点。 构造一棵决策树需要一个训练集,一些例子组成,每个例子用一些属性(或特征)和一个类别标记来描述。构造决策树的目的是找出属性和类别间的关系,一旦这种关系找出,就能用它来预测将来未知类别的记录的类别。这种具有预测功能的系统叫决策树分类器。

决策树有非常良好的优点:

1)决策树的够造不需要任何领域知识,就是简单的IF...THEN...思想 ;

2)决策树能够很好的处理高维数据,并且能够筛选出重要的变量;

3)由决策树产生的结果是易于理解和掌握的;

4)决策树在运算过程中也是非常迅速的;

5)一般而言,决策树还具有比较理想的预测准确率。

CART决策树又称分类回归树,当数据集的因变量为连续性数值时,该树算法就是一个回归树,可以用叶节点观察的均值作为预测值;当数据集的因变量为离散型数值时,该树算法就是一个分类树,可以很好的解决分类问题。但需要注意的是,该算法是一个二叉树,即每一个非叶节点只能引伸出两个分支,所以当某个非叶节点是多水平(2个以上)的离散变量时,该变量就有可能被多次使用。

决策树算法中包含最核心的两个问题,即特征选择和剪枝

关于特征选择目前比较流行的方法是信息增益、增益率、基尼系数和卡方检验,下文就先介绍基于基尼系数的特征选择,因为本文所描述的CART决策树就是基于基尼系数选择特征的;

关于剪枝问题,主要分预剪枝和后剪枝,预剪枝是在树还没有生长之前就限定了树的层数、叶节点观测数量等,而后剪枝是在树得到充分生长后,基于损失矩阵或复杂度方法实施剪枝,下文将采用后剪枝的方法对树进行修正。

二、决策树的核心问题

决策树核心问题有二:一是利用Training Data完成决策树的生成过程;二是利用Testing Data完成对决策树的精简过程。即前面我们提到的,生成的推理规则往往过多,精简是必需的。

1)决策树的生长

决策树生长过程的本质是对Training Data反复分组(分枝)的过程,当数据分组(分枝)不再有意义——注意,什么叫分组不再有意义——时,决策树生成过程停止。因此,决策树生长的核心算法是确定数据分析的标准,即分枝标准。

何为有意义呢?注意,当决策树分枝后结果差异不再显著下降,则继续分组没有意义。也就是说,我们分组的目的,是为了让输出变量在差异上尽量小,到达叶节点时,不同叶节点上的输出变量为相同类别,或达到用户指定的决策树停止生成的标准。

这样,分枝准则涉及到两方面问题:1、如果从众多输入变量中选择最佳分组变量;2、如果从分组变量的众多取值中找到最佳分割点。不同的决策树算法,如C4.5、C5.0、Chaid、Quest、Cart采用了不同策略。

​2)决策树的修剪

完整的决策树并不是一棵分类预测新数据对象的最佳树。其原因是完整的决策树对Training Data描述过于“精确”。我们知道,随着决策树的生长,决策树分枝时所处理的样本数量在不断减少,决策树对数据总体珠代表程度在不断下降。在对根节点进行分枝时,处理的是全部样本,再往下分枝,则是处理的不同分组下的分组下的样本。可见随着决策树的生长和样本数量的不断减少,越深层处的节点所体现的数据特征就越个性化,可能出现如上推理规则:“年收入大于50000元且年龄大于50岁且姓名叫张三的人购买了此产品”。这种过度学习从而精确反映Training Data特征,失去一般代表性而无法应用于新数据分类预测的现象,叫过度拟合(Overfitting)或过度学习。那我们应该怎么办呢?修剪!

常用的修剪技术有预修剪(Pre-Pruning)后修剪(Post-Pruning)。

Pre-Pruning可以事先指定决策树的最大深度,或最小样本量,以防止决策树过度生长。前提是用户对变量聚会有较为清晰的把握,且要反复尝试调整,否则无法给出一个合理值。注意,决策树生长过深无法预测新数据,生长过浅亦无法预测新数据。

Post-pruning是一个边修剪边检验的过程,即在决策树充分生长的基础上,设定一个允许的最大错误率,然后一边修剪子树,一边计算输出结果的精度或误差。当错误率高于最大值后,立即停止剪枝。

基于Training Data(训练集)的Post-Pruning(剪枝)应该使用Testing Data(测试集)。

决策树中的C4.5、C5.0、CHAID、CART和QUEST都使用了不同 剪枝策略。

案例、使用rpart()回归树​分析糖尿病的血液化验指标

install.packages("rpart")​

library("rpart")​​

install.packages("rpart.plot")

library(rpart.plot)​

1、主要应用函数:

1)构建回归树的函数:rpart()

rpart(formula, data, weights, subset,na.action = na.rpart, method,

model = FALSE, x = FALSE, y = TRUE, parms, control, cost, ...)

主要参数说明:

fomula:回归方程形式:例如 y~x1+x2+x3

data:数据:包含前面方程中变量的数据框(dataframe)。

na.action:缺失数据的处理办法:默认办法是删除因变量缺失的观测而保留自变量缺失的观测。

method:根据树末端的数据类型选择相应变量分割方法,本参数有四种取值:连续型“anova”;离散型“class”;计数型(泊松过程)“poisson”;生存分析型“exp”。程序会根据因变量的类型自动选择方法,但一般情况下最好还是指明本参数,以便让程序清楚做哪一种树模型。​

parms:用来设置三个参数:先验概率、损失矩阵、分类纯度的度量方法。​

cost:损失矩阵,在剪枝的时候,叶子节点的加权误差与父节点的误差进行比较,考虑损失矩阵的时候,从将“减少-误差”调整为“减少-损失”

control:控制每个节点上的最小样本量、交叉验证的次数、复杂性参量:即cp:complexitypamemeter,这个参数意味着对每一步拆分,模型的拟合优度必须提高的程度,等等。​​rpart.control对树进行一些设置

xval是10折交叉验证

minsplit是最小分支节点数,这里指大于等于20,那么该节点会继续分划下去,否则停止

minbucket:叶子节点最小样本数;maxdepth:树的深度

cp全称为complexity parameter,指某个点的复杂度,对每一步拆分,模型的拟合优度必须提高的程度,用来节省剪枝浪费的不必要的时间。

2)进行剪枝的函数:prune()

prune(tree, cp, ...)

主要参数说明:

tree:一个回归树对象,常是rpart()的结果对象。

cp:复杂性参量,指定剪枝采用的阈值。cp全称为complexity parameter,指某个点的复杂度,对每一步拆分,模型的拟合优度必须提高的程度,用来节省剪枝浪费的不必要的时间。​

二、特征选择

CART算法的特征选择就是基于基尼系数得以实现的,其选择的标准就是每个子节点达到最高的纯度,即落在子节点中的所有观察都属于同一个分类。下面简单介绍一下有关基尼系数的计算问题:

假设数据集D中的因变量有m个水平,即数据集可以分成m类群体,则数据集D的基尼系数可以表示为:

CART决策树(分类回归树)分析及应用建模
由于CART算法是二叉树形式,所以一个多水平(m个水平)的离散变量(自变量)可以把数据集D划分为2^m-2种可能。举个例子也许能够明白:如果年龄段可分为{青年,中年,老年},则其子集可以是{青年,中年,老年}、{青年,中年}、{青年,老年}、{中年,老年}、{青年}、{中年}、{老年}、{}。其中{青年,中年,老年}和空集{}为无意义的Split,所以6=2^3-2。

对于一个离散变量来说,需要计算每个分区不纯度的加权和,即对于变量A来说,D的基尼系数为:

CART决策树(分类回归树)分析及应用建模

对于一个连续变量来说,需要将排序后的相邻值的中点作为阈值(分裂点),同样使用上面的公式计算每一个分区不纯度的加权和。

根据特征选择的标准,只有使每个变量的每种分区的基尼系数达到最小,就可以确定该变量下的阈值作为分裂变量和分裂点。如果这部分读的不易理解的话,可参考《数据挖掘:概念与技术》一书,书中有关于计算的案例

三、剪枝

剪枝是为了防止模型过拟合,而更加适合样本外的预测。一般决策树中的剪枝有两种方式,即预剪枝和后剪枝,而后剪枝是运用最为频繁的方法。后剪枝中又分为损失矩阵剪枝法和复杂度剪枝法,对于损失矩阵剪枝法而言,是为了给错误预测一个惩罚系数,使其在一定程度上减少预测错误的情况;对于复杂度剪枝法而言,就是把树的复杂度看作叶节点的个数和树的错误率(错误分类观察数的比例)的函数。这里讲解的有点抽象,下面我们通过一个简单的例子来说明后剪枝的作用。

四、案例分享

以“知识的掌握程度”数据为例,说说决策树是如何实现数据的分类的(数据来源

:http://archive.ics.uci.edu/ml/datasets/User+Knowledge+Modeling)。

该数据集通过5个维度来衡量知识的掌握程度,它们分别是:

STG:目标科目的学习时长程度;

SCG:对目标科目的重复学习程度;

STR:其他相关科目的学习时长程度;

LPR:其他相关科目的考试成绩;

PEG:目标科目的考试成绩。

知识的掌握程度用UNS表示,它有4个水平,即Very Low、Low、Middle、High。

#读取外部文件

Train <- read.csv(file = file.choose())

Test <- read.csv(file = file.choose())

#加载CART算法所需的扩展包,并构建模型

library(rpart)

fit <- rpart(UNS ~ ., data = Train)

#查看模型输出的规则

fit

CART决策树(分类回归树)分析及应用建模

上面的输出规则看起来有点眼花缭乱,我们尝试用决策树图来描述产生的具体规则。由于rpart包中有plot函数实现决策树图的绘制,但其显得很难看,我们下面使用rpart.plot包来绘制比较好看的决策树图:

#加载并绘制决策树图

library(rpart.plot)

rpart.plot(fit, branch = 1, branch.type = 1, type = 2, extra = 102,shadow.col='gray', box.col='green',border.col='blue', split.col='red',main="CART决策树")

CART决策树(分类回归树)分析及应用建模
上图可一目了然的查看具体的输出规则,如根节点有258个观测,其中Middle有88个,当PEG>=0.68时,节点内有143个观测,其中Middle有78个,当PEG>=0.12且PEG<0.34时,节点内有115个观察,其中Low有81个,以此类推还可以得出其他规则。

#将模型用于预测

Pred <- predict(object = fit, newdata = Test[,-6], type = 'class')

#构建混淆矩阵

CM <- table(Test[,6], Pred)

CM

CART决策树(分类回归树)分析及应用建模
#计算模型的预测准确率

Accuracy <- sum(diag(CM))/sum(CM)

Accuracy

CART决策树(分类回归树)分析及应用建模
结果显示,模型在测试集中的预测能力超过91%。但模型的预测准确率还有提升的可能吗?下面我们对模型进行剪枝操作,具体分损失矩阵法剪枝和复杂度剪枝:

根据混淆矩阵的显示结果,发现High的预测率达100%(39/39),Low的预测率达91.3%(42/46),Middle的预测率达88.2%(30/34),very_low的预测率达80.8(21/26)。如果希望提升very_low的预测准确率的话就需要将其惩罚值提高,经尝试调整,构建如下损失矩阵

vec = c(0,1,1,1,1,0,1,1,1,2,0,1,1,3.3,1,0)

cost = matrix(vec, nrow = 4, byrow = TRUE)

cost

CART决策树(分类回归树)分析及应用建模
fit2 = rpart(UNS ~ ., data = Train, parms = list(loss = cost))

Pred2 = predict(fit2, Test[,-6], type = 'class')

CM2 <- table(Test[,6], Pred2)

CM2

CART决策树(分类回归树)分析及应用建模
Accuracy2 <- sum(diag(CM2))/sum(CM2)

Accuracy2

CART决策树(分类回归树)分析及应用建模
准确率提升了1.4%,且在保证High、Low、Middle准确率不变的情况下,提升了very_low的准确率88.5%,原来为80.8%。

下面再采用复杂度方法进行剪枝,先来看看原模型的CP值:

printcp(fit)

CART决策树(分类回归树)分析及应用建模

复杂度剪枝法满足的条件是,在预测误差(xerror)尽量小的情况下(不一定是最小值,而是允许最小误差的一个标准差(xstd)之内),选择尽量小的cp值。这里选择cp=0.01。

fit3 = prune(fit, cp = 0.01)

Pred3 = predict(fit3, Test[,-6], type = 'class')

CM3 <- table(Test[,6], Pred3)

CM3

CART决策树(分类回归树)分析及应用建模
Accuracy3 <- sum(diag(CM3))/sum(CM3)

Accuracy3

CART决策树(分类回归树)分析及应用建模
很显然,模型的准确率并没有得到提升,因为这里满足条件的cp值为0.01,而函数rpart()默认的cp值就是0.01,故模型fit3的结果与fit一致。

确定递归建树的停止条件:否则会使节点过多,导致过拟合。

1. 每个子节点只有一种类型的记录时停止,这样会使得节点过多,导致过拟合。

2. 可行方法:当前节点中的记录数低于一个阈值时,那就停止分割。

过拟合原因

(1)噪音数据,某些节点用噪音数据作为了分割标准。

(2)缺少代表性的数据,训练数据没有包含所有具有代表性的数据,导致某类数据无法很好匹配。

(3)还就是上面的停止条件设置不好。

转载于:http://chuansong.me/n/540927751643