决策树

概述
常用算法
程序包加载
rpart函数用法:
rpart.control函数用法:
剪枝: rpart.prune( ) 函数
J48 函数
C5.0 和 C5.0Control 函数

概述

简单来说，建立决策树的目的即是根据若干输入变量的值构造出一个相适应的模型，来预测出目标/输出变量的值，并以树形结构呈现。

数据挖掘中的决策树可以分为两个主要类型：分类树和回归树。

分类树：分类树是针对于目标变量为离散型的情况，即最终目标是预测各样本的所属类别，如根据天气预报来预测人们是否会打高尔夫。
回归数：回归数则适用于目标变量为连续型的情况，如预测出某人的月收入，可以建立回归树，但当预测其月收入所属区间时（如：[1000，2000] 或 [2000，3000]），则属于分类树范畴。

常用算法

决策树两种使用最为普遍的算法：CART（Classification and Regression Trees）和 C4.5（successor of ID3）。

在决策树算法的实现过程中，我们将主要用到4个软件包，分别为 rpart、rpart.plot、maptree及RWeka 。其中，rpart主要用于建立分类树及相关递归划分算法的实现；rpart.plot顾名思义，即是专用来对rpart模型绘制决策树；maptree则用来修剪、绘制不仅仅局限于rpart模型的树形结构图；RWeka包提供了R与Weka的连接，Weka中集合了用Java编写的一系列机器学习算法，从数据预处理，到分类、回归，再到聚类、关联分析，以及各种可视化技术。

表1：决策树软件包和相关函数

名称	类别	作用
draw.tree()	函数	绘制树状图
J48()	函数	实现C4.5算法的核心函数
post()	函数	对rpart()结果绘制演示图
prune.rpart()	函数	对rpart()的结果进行剪枝
rpart()	函数	建立CART决策树的核心函数
rpart.plot()	函数	对rpart()的结果绘制决策树
maptree	软件包	提供函数draw.tree()
mvpart()	软件包	提供数据集car.test.frame
rpart	软件包	提供函数rpart()、prune.rpart()、post()
rpart.plot	软件包	提供函数rpart.plot()
Rweka	软件包	提供函数J48()
sampling	软件包	提供函数strata()

表2：软件包及算法函数

算法名称	软件包	核心函数
CART	rpart	rpart()、prune.rpart()、post()
CART	rpart.plot	rpart.plot()
CART	maptree	draw.tree()
C4.5	RWeka	J48()
C5.0	C50	C5.0、C5.0Control

程序包加载

https://cran.r-project.org/web/packages/rpart/
https://cran.r-project.org/web/packages/C50/
https://cran.r-project.org/web/packages/RWeka/

install.packages('rpart')
install.packages('rpart.plot')
install.packages('maptree')
install.packages('RWeka')
install.packages('C50')

library(rpart)
library(rpart.plot)
library(maptree)
library(RWeka)
library(C50)

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，当输出变量为除了y的所有变量时，也可用y~. 来表示。
data 为待训练数据集，包含前面方程中变量的数据框( data frame ) 。
subset 可以选择出data中的若干行样本来建立模型。
na.action 缺失数据的处理办法: 默认办法是删除因变量缺失的观测而保留自变量缺失的观测。（用来处理缺失值，其默认选择为na.rpart，即仅剔除缺失y值，或缺失所有输入变量值的样本数据，这是rpart模型很有用的一项功能。）（有待进一步测试了解其用法）
method 用于选择决策树的类型，根据树末端的数据类型选择相应变量分割方法，本参数有四种取值: 连续性method=“anova”,离散型method=“class”,计数型method=“poisson”,生存分析型method=“exp”。程序会根据因变量的类型自动选择方法，但一般情况下最好还是指明本参数，以便让程序清楚做哪一种树模型。其中，anova型对应于我们所说的回归树，而class型则为分类树。
parms 用来设置三个参数:先验概率、损失矩阵、分类纯度的度量方法（gini和information）。
cost 我觉得是损失矩阵，在剪枝的时候，叶子节点的加权误差与父节点的误差进行比较，考虑损失矩阵的时候，从将“减少-误差”调整为“减少-损失” 。
poisson分割有一个参数，先验分布变异系数的比率，默认为1；生存分布的参数和poisson一致；
对离散型，可以设置先验分布的分布的概率(prior)，损失矩阵(loss)，分类纯度(split）；
priors必须为正值且和为1，loss必须对角为0且非对角为正数，split可以是gini（基尼系数）或者information（信息增益）；）

rpart.control函数用法:

rpart.control ( minsplit=20, minbucket = round(minsplit/3), cp = 0.01,  maxcompete = 4, maxsurrogate = 5, usesurrogate = 2, xval = 10,  surrogatestyle = 0, maxdepth = 30, ... )

rpart.control 对树进行一些设置
xval 是10折交叉验证，交叉验证的次数
minsplit 是最小分支节点数，这里指大于等于20，那么该节点会继续分划下去，否则停止
minbucket 叶子节点最小样本数
maxdepth 可控制数的高度，即设置节点层次的最大值，为任何最终的树节点的最大深度，根节点深度为0计算。
cp 即指复杂度参数complexity
pamemeter 这个参数意味着对每一步拆分，模型的拟合优度必须提高的程度。假设我们设置了cp=0.03，则表明在建模过程中仅保留可以使得模型拟合程度提升0.03及以上的节点，该参数的作用在于可以通过剪去对模型贡献不大的分支，来提高算法效率。

剪枝: rpart.prune( ) 函数

prune (  tree,  cp, . . . )

tree 一个回归树对象，常是rpart( ) 的结果对象。
cp 复杂性参量, 指定剪枝采用的阈值。

通常分为两步建立回归树，最初生成一颗较大的树，然后通过统计估量删除底部的一些节点来对树进行修剪。这个过程的目的是防止过度拟合。

使用rpart函数构建树的过程中，当给定条件满足时构建过程就停止。偏差的减少小于某一个给定界限值、节点中的样本数量小于某个给定界限、树的深度大于一个给定的界限，上面三个界限分别由rpart()函数的三个参数(cp、minsplit、maxdepth)确定，默认值是0.01、20和30。如果要避免树的过度拟合问题，就要经常检查这些默认值的有效性，这可以通过对得到的树采取事后修剪的过程来实现。

选择树的方法一般有两种，第一种是最小化交叉验证的相对方差（xerror）。第二种是在剪枝理论中，比较著名的规则就是1 - SE( 1标准差) 规则，其意思是: 首先要保证预测误差( 通过交叉验证获得，在程序中表示为xerror) 尽量小，但不一定要取最小值，而是允许它在“最小的误差”的一个相应标准差的范围内（xerror ± xstd），然后在此范围内选取尽量小的复杂性参量，进而以它为依据进行剪枝。这个规则体现了兼顾树的规模( 复杂性) 和误差大小的思想，因为一般说来，随着拆分的增多，复杂性参量会单调下降( 纯度越来越高 )，但是预测误差则会先降后升，这样，就无法使复杂性和误差同时降到最低，因此，允许误差可以在一个标准差内波动。

library(rpart)
library(rpart.plot)
library(survival)
fit<- rpart( Surv( pgtime, pgstat) ~ age+eet+ g2 +   grade+ gleason+ ploidy , data=stagec,method="exp")
plot(fit,uniform=T, branch=1, margin=0.1, main="Classification Tree")
text(fit,use.n=T, col="blue")

plotcp(fit)
printcp(fit)

## 
## Survival regression tree:
## rpart(formula = Surv(pgtime, pgstat) ~ age + eet + g2 + grade + 
##     gleason + ploidy, data = stagec, method = "exp")
## 
## Variables actually used in tree construction:
## [1] age     g2      gleason grade  
## 
## Root node error: 192.11/146 = 1.3158
## 
## n= 146 
## 
##         CP nsplit rel error  xerror     xstd
## 1 0.129460      0   1.00000 1.01215 0.071343
## 2 0.042056      1   0.87054 0.90852 0.075573
## 3 0.029200      2   0.82848 0.95397 0.085121
## 4 0.017989      3   0.79928 0.93144 0.085137
## 5 0.015406      4   0.78130 0.97566 0.090276
## 6 0.013354      5   0.76589 0.96533 0.089467
## 7 0.011506      7   0.73918 0.97326 0.089267
## 8 0.010000      8   0.72768 0.98009 0.090366

#选择树的方法有两种，一种是最小化交叉验证的相对方差（xerror）
#可以看到最小的误差是第2行xerror=0.88732,相应的标准差xstd=0.074117，相加得到0.961437，由于是交叉验证，每次运行的数值可能不相同。
#0.96介于第6行和第7行的xerror，可以看到树的最大节点数为5，cp必须大于第7行的cp值
#本例可以选择0.012
# fit2<- prune(fit,cp=0.012)
# plot(fit,uniform=T, branch=1, margin=0.1, main="Classification Tree")
# text(fit,use.n=T, col="blue")
#可以动态的对树进行剪枝
snip.rpart(fit)

## n= 146 
## 
## node), split, n, deviance, yval
##       * denotes terminal node
## 
##  1) root 146 192.111100 1.0000000  
##    2) grade< 2.5 61  44.799010 0.3634439  
##      4) g2< 11.36 33   9.117405 0.1229835 *
##      5) g2>=11.36 28  27.602190 0.7345610  
##       10) gleason< 5.5 20  14.297110 0.5304115 *
##       11) gleason>=5.5 8  11.094650 1.3069940 *
##    3) grade>=2.5 85 122.441500 1.6148600  
##      6) age>=56.5 75 103.062900 1.4255040  
##       12) gleason< 7.5 50  66.119800 1.1407320  
##         24) g2< 13.475 24  27.197170 0.8007306 *
##         25) g2>=13.475 26  36.790960 1.4570210  
##           50) g2>=17.915 15  20.332740 0.9789825 *
##           51) g2< 17.915 11  13.459010 2.1714480 *
##       13) gleason>=7.5 25  33.487250 2.0307290  
##         26) g2>=15.29 10  11.588480 1.2156230 *
##         27) g2< 15.29 15  18.939150 2.7053610 *
##      7) age< 56.5 10  13.769010 3.1822320 *

J48 函数

函数 J48()是实现C4.5算法的核心函数，基本格式为：

J48 (formula, data, subset, na.action,control = Weka_control(), options = NULL)

其中formula 放置用于构建模型的公式，data为建模数据集，na.action用于处理缺失数据，而control则是对树的复杂度进行控制的参数，其设置形式为control= Weka_control()，具体取值情况见下表。

表3：J48()函数中control参数的部分取值及其含义

参数名	获取全部取值.WOW.J48.
U	不对树进行剪枝，默认为TRUE
C	对剪枝过程设置置信阈值，默认值为0.25
M	对每个枝节点设置最小观测样本量，默认值为2
R	按照错误率递减方式进行剪枝，默认为TRUE
N	设置按照错误率递减方式进行剪枝时，交互验证的折叠次数，默认值为3
B	每个节点仅分为两个分支，即构建二叉树，默认为TRUE

决策树

baorui