数据挖掘之决策树分类-CDA数据分析师官网

数据挖掘之决策树分类

2016-05-19

1. 理论知识

决策树分类算法的一般流程如下：一开始，所有的实例均位于根节点，所有参数的取值均离散化；根据启发规则选择一个参数，根据参数取值的不同对实例集进行分割；对分割后得到的节点进行同样的启发式参数选择分割过程，如此往复，直到(a)分割得到的实例集合属于同一类；(b)参数用完，以子集中绝大多数的实例类别作为该叶节点的类别。

核心问题：参数选择规则

在每一个节点进行参数选择时，由于有众多的选项，需要一个选择规则。基本的原则是使最后构造出的决策树规模最小。基于这个基本原则，我们启发式地定义规则为使分割后得到的子节点纯度最大。于是参数选择规则问题就转化为了纯度定义的问题。

我们利用熵(Entropy)的概念去描述“不纯度”，熵值越大，说明这个节点的纯度越低：当节点的类别均匀分布时，熵值为1；当只包含一类时，熵值为0.熵的计算公式如下图，以2为底的概率对数与概率乘积之和的相反数。

基于熵的概念，我们可以得到参数选择的第一个规则：信息增益(Info Gain).信息增益的定义是分裂前的节点熵减去分裂后子节点熵的加权和，即不纯度的减少量，也就是纯度的增加量。参数选择的规则是：选择使信息增益最大的参数分割该节点。信息增益计算的算例如下图。

信息增益存在的问题时:总是倾向于选择包含多取值的参数，因为参数的取值越多，其分割后的子节点纯度可能越高。为了避免这个问题，我们引入了增益比例(Gain Ratio)的选择指标，其定义如下图所示。

增益比例存在的问题是：倾向于选择分割不均匀的分裂方法，举例而言，即一个拆分若分为两个节点，一个节点特别多的实例，一个节点特别少的实例，那么这种拆分有利于被选择。

为了克服信息增益和增益比例各自的问题，标准的解决方案如下：首先利用信息增益概念，计算每一个参数分割的信息增益，获得平均信息增益；选出信息增益大于平均值的所有参数集合，对该集合计算增益比例，选择其中增益比例最大的参数进行决策树分裂。

上面介绍的是基于熵概念的参数选择规则，另一种流行的规则称为基尼指数（Gini Index），其定义如下图。基尼系数在节点类别分布均匀时取最大值1-1/n，在只包含一个类别时取最小值0. 所以与熵类似，也是一个描述不纯度的指标。

基于基尼系数的规则是：选择不纯度减少量(Reduction in impurity)最大的参数。不纯度减少量是分割前的Gini index减去分割后的Gini index。基尼系数的特点与信息增益的特点类似。

过度拟合问题(Overfitting)

过度拟合问题是对训练数据完全拟合的决策树对新数据的预测能力较低。为了解决这个问题，有两种解决方法。第一种方法是前剪枝(prepruning)，即事先设定一个分裂阈值，若分裂得到的信息增益不大于这个阈值，则停止分裂。第二种方法是后剪枝（postpruning），首先生成与训练集完全拟合的决策树，然后自下而上地逐层剪枝，如果一个节点的子节点被删除后，决策树的准确度没有降低，那么就将该节点设置为叶节点（基于的原则是Occam剪刀：具有相似效果的两个模型选择较简单的那个）。

Scalable决策树分类算法

这里介绍两个算法，一个是RainForest，其主要的贡献是引入了一个称为AVC的数据结构，其示意图如下。主要的作用是加速参数选择过程的计算。

另一个算法称为BOAT，其采用了称为bootstrap的统计技术对数据集进行分割，在分割的子数据集上分别构造决策树，再基于这些决策树构造一个新的决策树，文章证明这棵新树与基于全局数据集构造的决策树非常相近。这种方法的主要优势在于支持增量更新。

2. R语言实现

本文采用rpart和rpart.plot包进行决策树分类的案例讲解。

函数说明

rpart包主要有两个函数组成，分别介绍如下：

rpart(formula, data, weight s, subset, na. action = na. rpart, method, model= FALSE, x= FALSE,y= TRUE, parms, control, cost, . . . )

fomula 回归方程形式: 例如 y~ x 1+ x2+ x3。

data 数据: 包含前面方程中变量的数据框( data frame) 。

na.action 缺失数据的处理办法: 默认办法是删除因变量缺失的观测而保留自变量缺失的观测。

method 根据树末端的数据类型选择相应变量分割方法,本参数有四种取值: 连续型>anova; 离散型>class; 计数型( 泊松过程)>poisson; 生存分析型>exp。程序会根据因变量的类型自动选择方法, 但一般情况下最好还是指明本参数, 以便让程序清楚做哪一种树模型。

parms 用来设置三个参数:先验概率、损失矩阵、分类纯度的度量方法。anova没有参数；poisson分割有一个参数，先验分布变异系数的比率，默认为1；生存分布的参数和poisson一致；对离散型，可以设置先验分布的分布的概率(prior)，损失矩阵(loss)，分类纯度(split）；priors必须为正值且和为1，loss必须对角为0且非对角为正数，split可以是gini（基尼系数）或者information（信息增益）；

control 控制每个节点上的最小样本量、交叉验证的次数、复杂性参量: 即cp: complexity pamemeter, 这个参数意味着对每一步拆分, 模型的拟合优度必须提高的程度, 等等。

PS:交叉验证指，比如xval是10折交叉验证：将数据集分为10组，进行10次拟合，第i次拟合用除了第i组以外的数据训练，用第i组进行预测；目的是减少misclaassification rate。

prune(tree, cp, . . . )

tree 一个回归树对象, 常是rpart()的结果对象。

cp 复杂性参量, 指定剪枝采用的阈值。

建模方法概述

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

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

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

案例

rpart包自带数据集stagec，包含了146位患了stage c前列腺(prostate)癌的病人。变量介绍如下：

pgtime: 出现症状或复发时间，单位年；

pgstat：状态变量，1为复发，0为删减；

age：年龄；

eet：是否内分泌治疗，1为no，2为yes；

g2：g2阶段肿瘤细胞百分比；

grade：肿瘤等级，farrow体系；

gleason：肿瘤等级，gleason体系；

ploidy：肿瘤的倍体状态。

代码：

library(rpart);

## rpart.control对树进行一些设置

## xval是10折交叉验证：将数据集分为10组，进行10次拟合，第i次拟合用除了第i组以外的数据训练，用第i组进行预测；目的是减少misclaassification rate

## minsplit是最小分支节点数，这里指大于等于20，那么该节点会继续分划下去，否则停止

## cp全称为complexity parameter，指某个点的复杂度，对每一步拆分,模型的拟合优度必须提高的程度

ct <- rpart.control(xval=10, minsplit=20, cp=0.01)

## method：树的末端数据类型选择相应的变量分割方法:

## 连续性method=“anova”,离散型method=“class”,计数型method=“poisson”,生存分析型method=“exp”

## parms用来设置三个参数:先验概率、损失矩阵、分类纯度的度量方法（gini和information）

## parms的解释：For classification splitting, the list can contain any of: the vector of prior probabilities (component prior), the loss matrix (component loss) or the splitting index (component split). The priors must be positive and sum to 1. The loss matrix must have zeros on the diagonal and positive off-diagonal elements. The splitting index can be gini or information. The default priors are proportional to the data counts, the losses default to 1, and the split defaults to gini.

## cost：给每个变量一个成本，选择某个变量进行split时，split改进量/成本作为评价标准，默认都为1

str(stagec)

progstat <- factor(stagec$pgstat, levels=0:1, labels=c("No", "Prog"))

cfit <- rpart(progstat~age + eet + g2 + grade + gleason + ploidy,

data=stagec, method="class", control=ct,

parms=list(split="gini")

);

print(cfit)

# 绘制决策树

library(rpart.plot);

rpart.plot(cfit, branch=1, branch.type=2, type=1, extra=102,

shadow.col="gray", box.col="green",

border.col="blue", split.col="red",

split.cex=1.2, main="Stage C决策树");

## rpart包提供了复杂度损失修剪的修剪方法，printcp会告诉分裂到每一层，cp是多少，平均相对误差是多少

## 交叉验证的估计误差（“xerror”列），以及标准误差(“xstd”列)，平均相对误差=xerror±xstd

printcp(cfit);

## 使用1-SE法则选出最优cp值:找到xerror最小的行，得到误差阈值为该行的xerror+xstd

## 找到所有xerror小于这个阈值的行，取其中最大值的上限为prune的阈值

cfit2 <- prune(cfit, cp=0.03);

rpart.plot(cfit2, branch=1, branch.type=2, type=1, extra=102,

shadow.col="gray", box.col="green",

border.col="blue", split.col="red",

split.cex=1.2, main="Kyphosis决策树");

附：cp表

CP nsplit rel error xerror xstd

1 0.104938 0 1.00000 1.00000 0.10802

2 0.055556 3 0.68519 1.00000 0.10802

3 0.027778 4 0.62963 0.88889 0.10511

4 0.018519 6 0.57407 0.92593 0.10618

5 0.010000 7 0.55556 0.92593 0.10618

决策树先验概率 R语言偏差数据挖掘

数据分析咨询请扫描二维码

上一篇图论在大数据分析中的作用！

下一篇CDA认证再升一档！与国家共同推进大数据人才培养标准教育事业！

数据挖掘之决策树分类

考试指南

报考指南

热门栏目