第10章－基于树的方法(2)-树的剪枝

(1) 使用测试集
如果我们有一个很大的测试集，我们就可以用测试集来计算所有子树的误差，以此找出使得误差率最小的子树。然而，实际中，我们很少能有一个很大的测试集。即使我们有一个很大的测试集，我们宁愿用它来训练一个更好的树，而不是去测试。当样本缺少时，我们更不愿意拿太多的数据去进行测试。

(2) 使用交叉验证
当决策树的生成结果都是不稳定的，又如何进行交叉验证呢？如果训练数据变动一点，则结果可能导致结果变化很大。因此，交叉验证中的树与用全部数据生成的树可能很难相匹配。

然而，尽管我们说树的结果本身可能是不稳定的，但是这不意味着每个树的分类结果是不稳定的。我们可能最后有两棵看似不同的树，但是它们对于分类的结果却是相似的。

决策树的关键策略是选择正确的复杂参数α. 决策树试图找到最优的参数，而并不是评判哪个树最优。

基于交叉验证的剪枝

让我们考虑下 V折交叉验证

我们将原始训练样本L，随机分成V份子样本。 Lv,v=1,...,V . 同时，定义每一折训练样本 L(v)＝L?Lv .

然后，我们定义基于原始数据集生成的树为 Tmax ,那么我们重复每一折交叉验证的步骤，得到基于 L(v) 的 T(v)max .

对于每一个复杂度参数 α ，我们令 T(v) 是 L(v)(α) 下对应的最优代价复杂度子树 .

对于每个最大树，我们得到严格递增的 α 值，α1<α2<α3?<αk<?
然后，基于 α 找到最小代价复杂度。如序列中对于 αk≤αk+1，αk 的最优子树就是 α 的子树。

树T(α) 的交叉验证的错误率通过下式计算：

尽管 α 是连续的，但基于总体样本L，有有限多个最小代价复杂度的树. 考虑每个基于样本L 剪枝后的子树，令 Tk=T(αk) .

为了计算 Tk 的交叉验证错误率，令 α'k=(αk?α'k+1)0.5 .（这个公式没太懂）

得到

RCV(Tk)=RCV(T(α'k))

根据上述公式，得到最小值的 Tk 将被选中。

(10.8.4将与10.11－10.13写到一起)

10.9 R Scripts

1） 获取数据

糖尿病数据，数据集是从 UCI 机器学习 数据库获取的，地址:
http://archive.ics.uci.edu/ml/datasets/Pima+Indians+Diabetes.

• 样本中有768个数据
• 8个数值型变量
• 2种类别：是否有糖尿病标记

把数据加载到R中，如下：
其中，RawData 的最后一列是因变量(响应变量) ，其余列均是自变量。

# set the working directory setwd("C:/STAT 897D data mining") # comma delimited data and no header for each variable RawData <- read.table("diabetes.data",sep = ",",header=FALSE) responseY <- as.matrix(RawData[,dim(RawData)[2]]) predictorX <- as.matrix(RawData[,1:(dim(RawData)[2]-1)]) data.train <- as.data.frame(cbind(responseY,predictorX)) names(data.train) <- c("Y","X1","X2","X3","X4","X5","X6","X7","X8")

2）分类与回归树

构建分类树模型分为两步：生成树以及剪枝。

2.1) 生成树

rpart(formula,method=”class”) 表示响应变量是分类型的；
rpart(formula,method=”anova”) 表示响应变量是连续数值型的；

library(rpart)
set.seed(19)
model.tree <- rpart(Y ~ X1 + X2 + X3 + X4 + X5 + X6 + X7 + X8,data.train,method="class")

下面代码可以画出树，plot(result,uniform=TRUE) 画出树的节点，且是垂直等距的；然后 text(result,use.n=TRUE) 是把决策规则画在节点上。

plot(model.tree,uniform=T)
text(model.tree,use.n=T)

上图中，显示了分类树的每个节点上的预测条件和决策的阈值，并在每个叶节点上显示了样本不同分类的数量。符号’/’ 左侧显示的是 0-类 样本点数量，右侧显示的是1-类 样本点数量。

在每个节点处，如果判断条件是真，则从左侧分支向下延伸，如果为假，则从右侧分支向下延伸。rpart 包的函数画出的树的规则是：让左侧分支属于0-类的响应变量的比例要高于右侧分支。所以，一些决策规则包含“小于”另一些会包含“大于等于”的符号。相比之下，tree 包的函数画出来的树中，所有的决策规则都是“小于”，所以有的分支下对应的0-类响应变量的比例高，有的则小。

2.2) 剪枝

为了避免过拟合进而得到最优规模的决策树，可以使用 rpart 包生成的cptable 中的元素。

model.tree$cptable

（编辑：PHP编程网 - 黄冈站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!