决策树是一种简单、常用的基础模型。之所以说它简单，不仅因为它的思想原理简单具体、贴近实际，它并不需要像线性回归模型一样用一个数学公式来表征，而是由规则来抽象。说它基础，是因为它是一系列复杂强大的模型的基础。

决策树的基本思想是通过将数据不断划分，使原来混乱的数据信息逐渐清晰。举一个简单的例子：如果你去相亲，你可能以外貌为第一特征来决定是否继续往下考虑；如果外貌过关了，你可能还会考虑职位和收入水平；如果收入水平也过关了，再去考虑品质……这种层层筛选的过程就蕴含着决策树的朴素思想。

决策树不局限于数学模型的具体形式，它既可以用来作分类，也可以用来作回归，二者的基本思想类似，处理方法上有差别。

分类树

根据前文的描述，应该有两个问题：1、如何表征数据的混乱或清晰的程度？2、如何将数据划分？

一个分类变量，设想一下极端情况，如果都是True或False，那它取True或False的概率就是0或1，这些都是100%确定的，你无需做任何猜测，这种情况下数据就是最清晰的；反之，如果一个变量各有50%的True或False，你甚至没办法预测一个样本更有可能是True还是False，这种情况下数据就是最混乱的。

有两个指标可以用来衡量数据的不确定程度：熵和基尼系数（并非经济学上的概念），定义如下：

熵：

熵的定义

基尼系数：

基尼系数的定义

具体就不推导了，可见当p接近0或1时，这两个指标都接近于0，表示不确定度最低，信息最为清晰；当p接近0.5时，不确定度最高，信息最为混乱。

第一个问题解答了，第二个问题如何来进行数据划分？分类树的主要过程如下：

• 首先计算分类变量在不做任何划分下的熵或基尼系数
• 计算每一个特征在各个水平下的划分的加权熵或基尼系数
• 选择令分类变量熵或基尼系数减少得最多的特征作为节点往下划分
• 重复以上过程，直至数据被清晰划分

以Carseats的座椅销量水平高低为二分类变量，演示构建分类树的过程。

> library(tree)
> library(ISLR)
> attach(Carseats)
> 
> # 建立二分类变量
> High = ifelse(Sales <= 8 ,"No","Yes")
> Carseats = data.frame(Carseats,High)
> 
> # 划分训练集和测试集
> set.seed(1)
> train = sample(1:nrow(Carseats),200)
> Carseats.test = Carseats[-train,]
> High.test = High[-train]
> 
> tree.carseats = tree(High~.-Sales,Carseats,subset=train) # 建立决策树模型
> dim(Carseats) # 10个特征
[1] 400  13
> summary(tree.carseats) # 只用了6个特征，产生了16个节点的决策树，训练错误率为6.5%
Classification tree:
tree(formula = High ~ . - Sales, data = Carseats, subset = train)
Variables actually used in tree construction:
[1] "ShelveLoc"   "Price"       "Income"      "CompPrice"   "Advertising" "Population" 
Number of terminal nodes:  16 
Residual mean deviance:  0.3088 = 56.82 / 184 
Misclassification error rate: 0.065 = 13 / 200 
> # 可视化决策树模型
> plot(tree.carseats)
> text(tree.carseats,pretty = 0)
> 
> 
> tree.pred = predict(tree.carseats,Carseats.test,type="class")
> table(tree.pred,High.test)
         High.test
tree.pred No Yes
      No  93  38
      Yes 21  48
> (93+48)/200 # 测试正确率仅为70.5%
[1] 0.705

剪枝前的决策树

这个模型的训练误差为93.5%，测试误差却仅为70.5%，看到这棵树分支很多，说明什么？说明模型太复杂，过拟合了。决策树的过程就是不断将数据集细分的过程，可是如果细分过头了，模型的泛化能力就差，在新的测试数据中预测准确率就低。

那么如何解决决策树过拟合的问题？剪枝。迭代过程无需细分那么多步，决策树无需有那么多层。

剪枝有2种思路：一种是预剪枝，决策树每次分裂时，只有分裂后的RSS减小超过某一阈值才分裂，但这种方法只看眼前一步，看不到后面的几步，因此不免过于短视，容易错过最优的模型。另一种后剪枝，就是先就生成一棵大树，然后再剪去那些细枝末节。

> set.seed(2)
> cv.carseats = cv.tree(tree.carseats,FUN = prune.misclass) # 以分类错误率为指标来剪枝
> cv.carseats$size
[1] 16 14 12 10  7  6  2  1
> cv.carseats$dev
[1] 47 46 45 43 46 46 49 78
> plot(cv.carseats$size,cv.carseats$dev,type = "b") # 10个结点的决策树交叉验证误差最低
> prune.carseats = prune.misclass(tree.carseats,best=10)
> plot(prune.carseats)
> text(prune.carseats,pretty = 0)
> tree.pred = predict(prune.carseats,Carseats.test,type = "class")
> table(tree.pred,High.test)
         High.test
tree.pred No Yes
      No  93  37
      Yes 21  49
> (93+49)/200
[1] 0.71

剪枝后的决策树

可见，剪枝之后的决策树不仅模型变得更简单，更易于解释，测试准确率也提升了（虽然提升得不多）。

回归树

决策树不仅可以用来分类，也可以用来回归。回归树与分类树的差别主要在于两点：

• 回归树并不采用熵或基尼系数，而是将连续的特征采用分割点分割成离散的区间，以左右两侧的RSS最小为优化目标；
• 分类树最后以划分空间内点的投票作为分类结果，而分归树最后以划分空间内的平均值作为回归值。

以Boston数据集的房价中位数预测为例，演示构建回归树的过程。

> # 回归树
> 
> library(MASS)
> set.seed(1)
> train = sample(1:nrow(Boston),nrow(Boston)/2)
> tree.boston = tree(medv~.,Boston,subset = train)
> boston.test = Boston[-train,]
> summary(tree.boston)

Regression tree:
tree(formula = medv ~ ., data = Boston, subset = train)
Variables actually used in tree construction:
[1] "lstat" "rm"    "dis"  
Number of terminal nodes:  8 
Residual mean deviance:  12.65 = 3099 / 245 
Distribution of residuals:
     Min.   1st Qu.    Median      Mean   3rd Qu.      Max. 
-14.10000  -2.04200  -0.05357   0.00000   1.96000  12.60000 
> 
> ## 可视化
> plot(tree.boston)
> text(tree.boston,pretty = 0)
> 
> ## 交叉验证
> tree.pred = predict(tree.boston,boston.test)
> mean((tree.pred-Boston$medv[-train])^2) # MSE
[1] 25.04559
> 
> # 剪枝
> cv.boston = cv.tree(tree.boston)
> plot(cv.boston$size,cv.boston$dev,type = "b")
> cv.boston$size[which.min(cv.boston$dev)] # 最优节点数就是不剪枝时的节点数，因此不必剪枝
[1] 8

回归决策树

节点数的交叉验证

本例中通过交叉验证证明不用剪枝，构建出的回归值是离散的，通过把新的数据沿着决策树分枝归类，然后赋予其一个回归值。

决策树的优缺点

• 解释性强，比线性回归更强
• 更贴近人的决策模式，易于理解
• 易于可视化（高维线性回归模型则不能）
• 可以直接处理分类型变量而不需要创建哑变量
• 决策树的准确性不是很高

前文提到决策树具有容易过拟合、准确性不太高的缺点，可以用装袋、随机森林和提升方法来对组合大量的决策树，从而提高预测效果。

装袋

装袋法(Bagging)又称自助法聚集（bootstrap aggregation），联想到之前提到的自助法的思想方法，对于n个同方差σ^{2的观测，其平均值的方差为σ}2/n，这说明求平均可以降低方差。那么自然地可以进一步联想，通过自助法抽取n个样本，建立n个决策树模型，然后对n个预测结果求平均，也可以降低方差，提高准确性。那么装袋法就可以定义如下：

Bagging

装袋法通过自助法抽样B个样本，建立B棵高方差的决策树，不必剪枝。对于分类问题，B个分类结果投票选最多的就好；对于回归问题，B个回归值求平均。B取大一点也不会造成过拟合。装袋法并不仅适用于决策树，但对决策树尤其有用。

随机森林

随机森林是装袋的延伸，不同之处在于：每一次用自助法建立的样本之后并不用全部特征去建立决策树，而是同样对特征也进行抽样，每次抽m个特征（m一般为√p，当m=p时，随机森林就变成装袋法了）。为什么每次不用全部而只有部分特征？在之前进行多元线性回归模型拟合时有一个问题必须注意：特征之间的相关性。对于装袋法来说，每次都用所有特征，如果有一些强特征，导致每棵树的分裂方式都类似，这样不同树之间的预测变量就高度相关，这样即使求平均，能减小方差也有限。

随机森林的思想就是每次只抽一部分特征来建模，在大量的树下确保所有的特征都会被使用，这样平均之下就会减弱不同树之间特征的高度相关性，以减小总体的方差，达到总体的最优。

下面演示装袋和随机森林的代码。

> # 装袋法做回归
> library(randomForest)
> set.seed(1)
> train = sample(1:nrow(Boston),nrow(Boston)/2)
> boston.test = Boston[-train,]
> bag.boston = randomForest(medv~.,data = Boston,subset = train,mtry=13,ntree=500,importance=T) # 每次分裂都考虑全部13个特征，此时随机森林变成了装袋
> bag.boston # 500棵树解释了86.57%的方差

Call:
 randomForest(formula = medv ~ ., data = Boston, mtry = 13, ntree = 500,      importance = T, subset = train) 
               Type of random forest: regression
                     Number of trees: 500
No. of variables tried at each split: 13

          Mean of squared residuals: 11.08966
                    % Var explained: 86.57
> 
> ## 测试结果
> yhat.bag = predict(bag.boston,newdata = Boston[-train,])
> plot(yhat.bag,boston.test$medv)
> abline(0,1)
> mean((yhat.bag-boston.test$medv)^2)
[1] 13.33831

与上面最优减枝的单个决策树相比，装袋法的测试MSE差不多缩小了一半。

> set.seed(1)
> rf.boston = randomForest(medv~.,data = Boston,subset = train,mtry=6,importance=T)
> yhat.rf = predict(rf.boston,newdata = Boston[-train,])
> mean((yhat.rf-boston.test$medv)^2) 
[1] 11.48022
> importance(rf.boston)
          %IncMSE IncNodePurity
crim    12.547772    1094.65382
zn       1.375489      64.40060
indus    9.304258    1086.09103
chas     2.518766      76.36804
nox     12.835614    1008.73703
rm      31.646147    6705.02638
age      9.970243     575.13702
dis     12.774430    1351.01978
rad      3.911852      93.78200
tax      7.624043     453.19472
ptratio 12.008194     919.06760
black    7.376024     358.96935
lstat   27.666896    6927.98475
> varImpPlot(rf.boston)

可见与装袋法相比，随机森林进一步减小了测试MSE。

随机森林给出的变量重要性

important()函数可以给出随机森林模型筛选的变量重要性，2列2张图表示2个测度指标。%IncMSE表示排除此变量时，袋外误差（自助法并不能抽到全部样本，每次约能抽到2/3的样本，剩下的1/3就作为袋外观测可用来测试模型）准确性的平均减小值，IncNodePurity表示此变量导致的结点不纯度减小的总量。从上图可看出，最重要的两个变量是rm和lstat。

提升

提升(boosting)与装袋类似，都是集成学习算法，基本思想方法都是把多个弱分类器（但正确率要大于50%否则没有集成的意义）集成成强分类器。不过与装袋不同，装袋的每一步都是独立抽样的，提升每一次迭代则是基于前一次的数据进行修正，提高前一次模型中分错样本在下次抽中的概率，打个比方就是给一个学生做一张卷子，每做完一次就把他做错的题抽出来让他继续做，直到他所有的题都能做对为止。

以下是经典的Adaboost算法流程：

为每个样本初始化权值w=1/n；开始迭代，在第t轮迭代中：

1. 使用训练集训练分类器Ct，训练误差e=所有被分类错误样本的权值之和
2. 计算分类器的权值为α=1/2ln((1−e)/e)
3. 更新样本当前的权值wt：
   若分类正确，则减少权值，wt+1=wt∗e^−α；
   若分类错误，则加大权值，wt+1=wt∗e^α
4. 将所有样本的权值归一化，使其相加为1。
   用生成的所有分类器预测未知样本X，最终结果为所有分类器输出的加权平均。

以下演示boosting模型的构建过程：

> library(gbm)
> set.seed(1)
> boost.boston = gbm(medv~.,data = Boston[train,],distribution = "gaussian",n.trees=5000,interaction.depth=4)
> summary(boost.boston)
            var    rel.inf
lstat     lstat 45.9627334
rm           rm 31.2238187
dis         dis  6.8087398
crim       crim  4.0743784
nox         nox  2.5605001
ptratio ptratio  2.2748652
black     black  1.7971159
age         age  1.6488532
tax         tax  1.3595005
indus     indus  1.2705924
chas       chas  0.8014323
rad         rad  0.2026619
zn           zn  0.0148083

特征相对影响图

> par(mfrow=c(1,2))
> plot(boost.boston,i="rm")
> plot(boost.boston,i="lstat")

两个变量的偏相关图

> yhat.boost = predict(boost.boston,newdata = Boston[-train,],n.trees = 5000)
> mean((yhat.boost-boston.test$medv)^2)
[1] 11.84434

可见boosting的效果跟随机森林差不多。

还可以给提升法加上正则项压缩参数λ，默认是0.001，这里增大成0.2。

> boost.boston = gbm(medv~.,data = Boston[train,],distribution = "gaussian",n.trees=5000,interaction.depth=4,shrinkage=0.2,verbose=F)
> yhat.boost = predict(boost.boston,newdata = Boston[-train,],n.trees = 5000)
> mean((yhat.boost-boston.test$medv)^2)
[1] 11.51109

可见效果好一点。