Tree 分类方法
06 Dec 2012
一、关于
tree方法是一种机器学习(数据挖掘）方法。核心是自动寻找不同变量之间的关系，将目标变量以其他变量为基准划分为若干个类别。目标变量可以是离散的，比如两元的（0或1、True or Not），还可以是多元的（若干个类别），另外,目标变量也可以是连续的。针对于不同的变量类型，Tree方法分为两类：对于离散变量，用的是分类树；对于连续变量，用的是回归树。
两种类型的树思想一致。对于分类树，其基本思想，我的理解是，按照一种标准去选择分叉。具体来说是，当从一个节点向下分割时，有多种分割方案，选择的标准是使树的偏倚（deviance for the tree)下降最大。当节点的大小（size)比较小，或到达同质性（homogeneous,即一个节点内的观测属于同一类）时，就不再从该节点往下分割。
我主要参考了MASS上第九章Tree-Based Methods来学习这个方法。
应用Tree方法时，有两个步骤
- 种植一棵大树
- 修剪你种植的大树
二、举例1
使用到的数据集是MASS包自带的cpus(计算机性能，具体可见”？cpus”)
library(MASS）
data(cpus)
数据集有许多变量，分析的目标是寻找哪些变量（cpus[,2:8])影响到了计算机性能(perf).
R中实现分类树函数的包是rpart，函数名称与包名称一样。加载rpart包，并使用rpart()构建一棵大树:
library(rpart)
set.seed(123)
cpus.rp <- rpart(log10(perf) ~ ., cpus[, 2:8], cp = 1e-3)
一个关键的参数是cp, cp越小，这棵树就越大，分类越细。以上程序中cp=0.001，由此得到的树比较大，如下图：
plot（cpus.rp, uniform = T);text(cpus.rp, digits = 3)
接下来，修剪这棵树。剪刀是”cp”,在修建之前，首先来介绍cp。通过printcp()可以获得cp的信息。cp变化：
printcp(cpus.rp)
Regression tree:
rpart(formula = log10(perf) ~ ., data = cpus[, 2:8], cp = 0.001)
Variables actually used in tree construction:
[1] cach chmax chmin mmax syct
Root node error: 43.116/209 = 0.20629
n= 209
CP nsplit rel error xerror xstd
1 0.5492697 0 1.00000 1.01104 0.097303
2 0.0893390 1 0.45073 0.47958 0.048631
3 0.0876332 2 0.36139 0.44147 0.042823
4 0.0328159 3 0.27376 0.33667 0.033338
5 0.0269220 4 0.24094 0.31215 0.031402
6 0.0185561 5 0.21402 0.28840 0.030518
7 0.0167992 6 0.19546 0.30547 0.031813
8 0.0157908 7 0.17866 0.29447 0.029633
9 0.0094604 9 0.14708 0.27439 0.028943
10 0.0054766 10 0.13762 0.25274 0.029346
11 0.0052307 11 0.13215 0.24151 0.028239
12 0.0043985 12 0.12692 0.23945 0.028320
13 0.0022883 13 0.12252 0.23481 0.028117
14 0.0022704 14 0.12023 0.23617 0.028255
15 0.0014131 15 0.11796 0.23177 0.028221
16 0.0010000 16 0.11655 0.23293 0.028252
试猜想，如果我们不做任何分割（或者说树只有一个节点），也就是采用随机猜或扔硬币的方式对目标变量进行判断，此时的判断效果应该是比较差的，估计误差比较大。当我们开始对节点做分割，这意味着我们不是乱猜了，而是有根据地进行判断，这是整体的判断效果就比较好，估计误差就会减小。我们把rel error度量该误差，而cp是每次分割rel error的下降幅度。每一次节点的分割都会相应地计算cp值，cp意味着每次分割后树复杂度下降的幅度。cp下降的越快，说明分割越成功。如果cp下降越缓慢，说明分割效果不是很好，继续分割失去意义。
由以上处理可见，第一次分割cp值为0.549，这说明通过这次分割，判断误差下降了了54.9%，分割效果比较好。并不是每次分割效果都这么好，随着分割的进行，树渐渐增大，而cp值变得越来越小，也就是说，分割效果不是很明显。如果你设定cp=0.001，这就意味着，如果分割可以将误差减少0.1%就继续分割，一旦cp<0.001,就停止分割。
例如，如果我们选择cp=0.0094604.就意味着我们的树是这样的:
CP nsplit rel error xerror xstd
1 0.5492697 0 1.00000 1.01104 0.097303
2 0.0893390 1 0.45073 0.47958 0.048631
3 0.0876332 2 0.36139 0.44147 0.042823
4 0.0328159 3 0.27376 0.33667 0.033338
5 0.0269220 4 0.24094 0.31215 0.031402
6 0.0185561 5 0.21402 0.28840 0.030518
7 0.0167992 6 0.19546 0.30547 0.031813
8 0.0157908 7 0.17866 0.29447 0.029633
9 0.0094604 9 0.14708 0.27439 0.028943
这棵树从根节点开始进行了9次分割,这棵树目前就会有10片叶子，而不是最初种植的17片叶子的大树。cp越小，树就越大。开始我们种植了一棵硕大的树，为的是方便我们选择修剪。
如何来选择合适的cp呢？采用的标准是xerror相对于cp的变化。
plotcp(cpus.rp)
随着cp的继续减小，xerror下降已不明显。我们采用1-SE准则。以xerror的最小值加其一个标准差画一条水平线，该水平线下方最左边的cp值即为剪刀cp.
利用prune()进行修剪：
cpus.rp1 <- prune(cpus.rp, cp = 0.006)
plot(cpus.rp1, branch = 0.4, uniform = T)
text(cpus.rp1, digits = 3)
修剪后的树与开始种植的大树相比，更漂亮一些。
###举例2
下面的例子也是来源于别人的成果，我稍微整理一下。每个人都有自己的邮箱，你会发现每个邮箱里都有一个“垃圾邮件”的文件夹。当某某商城给你发了一个促销邮件，你会发现这个邮件会自动进入“垃圾邮件”文件夹。这是怎么回事呢？这就是垃圾邮件的识别问题。关于垃圾邮件垃圾邮件的识别主要运用的就是统计方法（可以看看这儿).好,下边咱用tree方法也来识别一下垃圾邮件，详细代码移步这里.
首先，先来说一下数据集里的内容。数据集是从一些垃圾邮件和非垃圾邮件提取的信息。数据集中共有4601封邮件信息，每封邮件提取的信息如下
names(spam)
[1] "wf.make" "wf.address" "wf.all" "wf.3d"
[5] "wf.our" "wf.over" "wf.remove" "wf.internet"
[9] "wf.order" "wf.mail" "wf.receive" "wf.will"
[13] "wf.people" "wf.report" "wf.addresses" "wf.free"
[17] "wf.business" "wf.email" "wf.you" "wf.credit"
[21] "wf.your" "wf.font" "wf.000" "wf.money"
[25] "wf.hp" "wf.hpl" "wf.george" "wf.650"
[29] "wf.lab" "wf.labs" "wf.telnet" "wf.857"
[33] "wf.data" "wf.415" "wf.85" "wf.technology"
[37] "wf.1999" "wf.parts" "wf.pm" "wf.direct"
[41] "wf.cs" "wf.meeting" "wf.original" "wf.project"
[45] "wf.re" "wf.edu" "wf.table" "wf.conference"
[49]"cf.semicolon" "cf.roundbkt" "cf.sqbkt" "cf.exclaim"
[53] "cf.dollar" "cf.pound" "capavg" "caplong"
[57] "captot" "spam"
以wf开头，表示该单词的频率；以cf开头，表示该字符的频率。capavg表示连续大写字符的平均长度。capmax表示连续大写字符的最大长度。captot表示连续大写字符的总长度。spam表示是否为垃圾邮件，1表示为垃圾邮件，0表示非垃圾邮件。
我们的目标是通过前57个变量信息来判断一封邮件是否为垃圾邮件。我们的任务是首先通过样本来寻找spam这个变量与前57个变量之间的关系。我们构建的统计模型是tree方法。为了验证方法的准确性，我们把样本分为两个部分，一部分为训练集，一部分为测试集；训练集来寻求关系，测试集来验证关系的准确性。
set.seed(102)
train <- sort(sample(nrow(spam), 3065))
spam.train <- spam[train, ]
spam.test <- spam[-train, ]
现在用训练集来构建一棵大树，取cp尽量小，这里取为0.001.
set.seed(200)
rp <- rpart(spam ~ . , spam.train,parms = list(split = "information"), method = "class",
cp = 0.001)
树有些大，现在我们要把它修剪，其实就是在合适的cp与xerror之间寻求一种平衡。
按照前面介绍的方法，我们取cp=0.0033.修剪ing.
rp1 <- prune(rp, cp = 0.0033)
plot(rp1, uniform = T, compress = T, margin = 0.05)
text(rp1, use.n = T)
Anyway,似乎有些好。下面我们验证一下这种分类的效果，也就是错误率。首先试验训练集。
> r2.train.class <- predict(rp1, type = "class")
> table(predicted = r2.train.class, actual = spam.train$spam)
actual
predicted 0 1
0 1747 96
1 105 1117
> (105+96)/(1747+1117)
[1] 0.07018156
实验结果是，错误率为7%，正确率超过90%，比较理想。关键的是对于测试集的分析结果：
> r2.test.class <- predict(rp1, type = "class", newdata = spam.test)
> table(predicted= r2.test.class, actual = spam.test$spam)
actual
predicted 0 1
0 863 56
1 73 544
> (73+56)/(863+544)
[1] 0.09168443
对于测试集来说，错误率高于训练集，这很正常，毕竟模型是用训练集的数据建立的。不过现在正确识别邮件的概率仍然超过90%，还算比较理想吧。辅以其他统计方法，共同决策，准确性会更高。就是这样。