决策树算法那些事--CART|机器学习
一、树算法介绍
当前数据挖掘领域中存在10个火热的算法、它们涉及到数据的聚类、分类、关联规则、排序等方面。今天就跟大家说说基于树的分类算法--决策树，决策树有非常良好的优点：
1）决策树的够造不需要任何领域知识，就是简单的IF...THEN...思想 ；
2）决策树能够很好的处理高维数据，并且能够筛选出重要的变量；
3）由决策树产生的结果是易于理解和掌握的；
4）决策树在运算过程中也是非常迅速的；
5）一般而言，决策树还具有比较理想的预测准确率。
CART决策树又称分类回归树，当数据集的因变量为连续性数值时，该树算法就是一个回归树，可以用叶节点观察的均值作为预测值；当数据集的因变量为离散型数值时，该树算法就是一个分类树，可以很好的解决分类问题。但需要注意的是，该算法是一个二叉树，即每一个非叶节点只能引伸出两个分支，所以当某个非叶节点是多水平(2个以上)的离散变量时，该变量就有可能被多次使用。
决策树算法中包含最核心的两个问题，即特征选择和剪枝：
关于特征选择目前比较流行的方法是信息增益、增益率、基尼系数和卡方检验，下文就先介绍基于基尼系数的特征选择，因为本文所描述的CART决策树就是基于基尼系数选择特征的；
关于剪枝问题，主要分预剪枝和后剪枝，预剪枝是在树还没有生长之前就限定了树的层数、叶节点观测数量等，而后剪枝是在树得到充分生长后，基于损失矩阵或复杂度方法实施剪枝，下文将采用后剪枝的方法对树进行修正。
二、特征选择
CART算法的特征选择就是基于基尼系数得以实现的，其选择的标准就是每个子节点达到最高的纯度，即落在子节点中的所有观察都属于同一个分类。下面简单介绍一下有关基尼系数的计算问题：
假设数据集D中的因变量有m个水平，即数据集可以分成m类群体，则数据集D的基尼系数可以表示为：
由于CART算法是二叉树形式，所以一个多水平(m个水平)的离散变量（自变量）可以把数据集D划分为2^m-2种可能。举个例子也许能够明白：如果年龄段可分为{青年，中年，老年}，则其子集可以是{青年，中年，老年}、{青年，中年}、{青年，老年}、{中年，老年}、{青年}、{中年}、{老年}、{}。其中{青年，中年，老年}和空集{}为无意义的Split，所以6=2^3-2。
对于一个离散变量来说，需要计算每个分区不纯度的加权和，即对于变量A来说，D的基尼系数为：
对于一个连续变量来说，需要将排序后的相邻值的中点作为阈值（分裂点），同样使用上面的公式计算每一个分区不纯度的加权和。
根据特征选择的标准，只有使每个变量的每种分区的基尼系数达到最小，就可以确定该变量下的阈值作为分裂变量和分裂点。如果这部分读的不易理解的话，可参考《数据挖掘：概念与技术》一书，书中有关于计算的案例。
三、剪枝
剪枝是为了防止模型过拟合，而更加适合样本外的预测。一般决策树中的剪枝有两种方式，即预剪枝和后剪枝，而后剪枝是运用最为频繁的方法。后剪枝中又分为损失矩阵剪枝法和复杂度剪枝法，对于损失矩阵剪枝法而言，是为了给错误预测一个惩罚系数，使其在一定程度上减少预测错误的情况；对于复杂度剪枝法而言，就是把树的复杂度看作叶节点的个数和树的错误率（错误分类观察数的比例）的函数。这里讲解的有点抽象，下面我们通过一个简单的例子来说明后剪枝的作用。
四、案例分享
以“知识的掌握程度”数据为例，说说决策树是如何实现数据的分类的(数据来源
：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
上面的输出规则看起来有点眼花缭乱，我们尝试用决策树图来描述产生的具体规则。由于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决策树")
上图可一目了然的查看具体的输出规则，如根节点有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
#计算模型的预测准确率
Accuracy <- sum(diag(CM))/sum(CM)
Accuracy
结果显示，模型在测试集中的预测能力超过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
fit2 = rpart(UNS ~ ., data = Train, parms = list(loss = cost))
Pred2 = predict(fit2, Test[,-6], type = 'class')
CM2 <- table(Test[,6], Pred2)
CM2
Accuracy2 <- sum(diag(CM2))/sum(CM2)
Accuracy2
准确率提升了1.4%，且在保证High、Low、Middle准确率不变的情况下，提升了very_low的准确率88.5%，原来为80.8%。
下面再采用复杂度方法进行剪枝，先来看看原模型的CP值:
printcp(fit)
复杂度剪枝法满足的条件是，在预测误差(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
Accuracy3 <- sum(diag(CM3))/sum(CM3)
Accuracy3
很显然，模型的准确率并没有得到提升，因为这里满足条件的cp值为0.01，而函数rpart()默认的cp值就是0.01，故模型fit3的结果与fit一致。
经过上面的学习和实战，大家明白了分类回归树CART的运作思路和方法了吗？动手做一做，对你的理解会更有帮助！
脚本及数据集可至下方链接下载：
http://yunpan.cn/c68YsUUFNS284 访问密码 bde1