决策树算法那些事--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

原文发布于微信公众号 - 数据科学与人工智能(DS_AI_shujuren)

原文发表时间:2016-08-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器之心

从香农熵到手推KL散度:一文带你纵览机器学习中的信息论

42510
来自专栏IT派

从香农熵到手推KL散度:一文带你纵览机器学习中的信息论

IT派 - {技术青年圈} 持续关注互联网、大数据、人工智能领域 信息论是应用数学的一个分支,主要研究的是对一个信号包含信息的多少进行量化。它最初被发明是用来...

3678
来自专栏PPV课数据科学社区

干货:基于树的建模-完整教程(R & Python)

来源:“数盟社区” 原文链接:http://dataunion.org/23697.html 简介 基于树的学习算法被认为是最好的方法之一,主要用于监测学习方...

3927
来自专栏机器学习算法与Python学习

一文让你入门CNN,附3份深度学习视频资源

CNN简介 文末附三份深度学习视频资源 后台回复关键词(20180310) 目录: 一些视频资源和文章 CNN简介 图像即四维张量? 卷积的定义 CNN如何工作...

4367
来自专栏机器学习之旅

理论:SVM理论解析及python实现

关于常见的分类算法在不同数据集上的分类效果,在《Do we Need Hundreds of Classifiers to Solve Real World C...

1233
来自专栏人工智能

决策树及ID3算法学习

决策树是一种用树形结构来辅助行为研究、决策分析以及机器学习的方式,是机器学习中的一种基本的分类方法。

1.6K16
来自专栏新智元

【致敬ImageNet】ResNet 6大变体:何恺明,孙剑,颜水成引领计算机视觉这两年

【新智元导读】2015 年,152 层深的 ResNet 横空出世,不仅取得当年ImageNet竞赛冠军,相关论文在CVPR 2016斩获最佳论文奖。ResNe...

5528
来自专栏算法channel

机器学习:提升树(boosting tree)算法的思想

《实例》阐述算法,通俗易懂,助您对算法的理解达到一个新高度。包含但不限于:经典算法,机器学习,深度学习,LeetCode 题解,Kaggle 实战。期待您的到来...

3898
来自专栏AI科技大本营的专栏

干货 | 深度详解ResNet及其六大变体

编译 | 图普科技 本文由图普科技工程师编译自《An Overview of ResNet and its Variants》。 从AlexNet[1]在201...

4966
来自专栏红色石头的机器学习之路

台湾大学林轩田机器学习基石课程学习笔记14 -- Regularization

上节课我们介绍了过拟合发生的原因:excessive power, stochastic/deterministic noise 和limited data。并...

2550

扫码关注云+社区

领取腾讯云代金券