R 中的数据挖掘算法/分类/决策树

介绍

任何基于决策树的算法的操作哲学都非常简单。事实上，尽管在执行某些步骤的方式上存在着重要的差异，但这类算法的任何一种都基于分治的策略。总的来说，这种哲学是基于将问题逐次划分为多个维度较少的子问题，直到可以找到每个简单问题的解决方案。基于这一原理，基于决策树的分类器试图找到将宇宙逐次细分为更多子群的方法（创建包含相应测试的节点），直到每个子群只包含一个类别，或者直到某一类别显示出明显的优势，从而不再需要进一步细分，在这种情况下，将生成一个包含多数类别的叶子。显然，分类只是按照沿着树排列的连续测试所指示的路径进行，直到找到一个包含要分配给新示例的类别的叶子。

尽管所有基于决策树的分类器都具有相同的基本哲学，但它们在构建方式上有很多种可能性。在选择用于构建决策树的算法的所有关键点中，一些关键点应该因其重要性而突出显示

用于选择每个节点中使用的特征的标准
如何计算示例集的划分
何时决定某个节点是叶子
分配给每个叶子的类别的选择标准是什么

决策树的一些重要优势可以被指出，包括

可以应用于任何类型的数据
分类器的最终结构非常简单，可以以一种优雅的方式存储和处理
非常有效地处理条件信息，将空间细分为独立处理的子空间
通常显示出健壮性，对训练集中的错误分类不敏感
生成的树通常易于理解，可以很容易地用于更好地理解所讨论的现象。这可能是所有列出的优点中最重要的一点

算法

决策树的基本算法是一种贪婪算法，它以自上而下的递归分治方式构建决策树。我们通常采用贪婪策略，因为它们效率高且易于实现，但它们通常会导致次优模型。也可以使用自下而上的方法。自上而下的决策树算法在算法 1 中给出。它是一种递归分治算法。它以数据集的子集 D 作为输入，并评估所有可能的分割（第 4 到第 11 行）。选择最佳分割决策（第 12 行），即信息增益最高的分割，将数据划分为两个子集（分治），并递归调用该方法（第 14 和第 15 行）。当满足停止条件时（第 1 到第 3 行），算法停止。

停止条件

可以使用多种停止条件来停止递归过程。当任何一个条件为真时，算法停止

所有样本都属于同一个类别，即具有相同的标签，因为样本已经是“纯净”的
如果大部分点已经属于同一个类别，则停止。这是第一种方法的泛化，具有某些误差阈值
没有剩余的属性可以进一步分割样本
分支测试属性没有样本

属性选择

现在我们需要一个客观的标准来判断分割的质量。信息增益度量用于在树中的每个节点选择测试属性。具有最高信息增益（或最大熵减少）的属性被选为当前节点的测试属性。该属性将对结果分区中样本进行分类所需的信息降至最低。

总的来说，熵衡量系统中的无序程度或不确定性。在分类设置中，较高的熵（即更多的无序）对应于样本具有混合标签集合的情况。较低的熵对应于我们主要具有纯分区的情况。在信息论中，样本 D 的熵定义如下

H(D)=-\sum _{i=1}^{k}P(c_{i}|D)\log _{2}{P(c_{i}|D)}

其中 $P(ci|D)$ 是 D 中数据点被标记为类别 $c_{i}$ 的概率，k 是类别的数量。 $P(ci|D)$ 可以直接从数据中估计如下

P(c_{i}|D)={\tfrac {|\{x_{j}\in D|x_{j}{\text{ has label }}y_{j}=c_{i}\}|}{|D|}}

我们也可以将决策/分割的加权熵定义如下

H(D_{L},D_{R})={\tfrac {|D_{L}|}{|D|}}H(D_{L})+{\tfrac {|D_{R}|}{|D|}}H(D_{R})

其中D由于某种分割决策，被划分为 $D_{L}$ 和 $D_{R}$ 。最后，我们可以将给定分割的信息增益定义为

Gain(D,D_{L},D_{R})=H(D)-H(D_{L},D_{R})

换句话说，Gain是知道一个属性的值后，熵的预期减少量。

Rpart

R 工具中找到的 rpart 包可用于决策树分类，也可用于生成回归树。递归划分是数据挖掘中的一项基本工具。它帮助我们探索数据集的结构，同时开发易于可视化的决策规则，以预测分类（分类树）或连续（回归树）结果。rpart 程序使用两阶段程序构建具有非常通用结构的分类或回归模型；生成的模型可以表示为二叉树。树构建过程如下：首先找到最能将数据分成两组的单个变量（“最佳”将在后面定义）。分离数据，然后将此过程分别应用于每个子组，递归地进行下去，直到子组达到最小尺寸（此数据为 5）或无法再进行改进为止。所得模型无疑过于复杂，因此像所有逐步程序一样，问题就变成了何时停止。该过程的第二阶段包括使用交叉验证来修剪完整的树。

生长树

要生长一棵树，请使用

    rpart (formula, data=, method=, control=)

其中

公式	格式为：outcome ~ predictor1+predictor2+predictor3+ect。
数据=	指定数据框
方法=	“class” 表示分类树 “anova” 表示回归树
控制=	用于控制树生长的可选参数。例如，control=rpart.control(minsplit=30, cp=0.001) 要求节点中的最小观测数为 30 才能尝试分割，并且分割必须将总体拟合不足减少 0.001 倍（成本复杂度因子）才能尝试。

可视化和示例

printcp

printcp 命令显示拟合 rpart 对象的 cp 表。根据复杂度参数打印最佳修剪的表。

用法

    printcp(object, digits=getOption("digits") - 2)

其中 object 是一个 rpart 对象，digits 是要打印的数字的位数。

示例

    fit <- rpart(Price ~ HP, car.test.frame)
    printcp(fit)

输出

    Regression tree:
    rpart(formula = Price ~ HP, data = car.test.frame)
    Variables actually used in tree construction:
    [1] HP
    Root node error: 983551497/60 = 16392525
    n= 60
    CP nsplit rel error xerror xstd
    1 0.41417 0 1.00000 1.03808 0.21528
    2 0.12304 1 0.58583 0.71817 0.15575
    3 0.01000 2 0.46279 0.62650 0.11675

plotcp

plotcp 命令对 rpart 对象中的交叉验证结果进行可视化表示。一组来自嵌套集的树的可能的成本复杂度修剪。对于 cp 值的间隔的几何平均值（其中修剪是最佳的），通常在初始构建中已由 rpart 进行交叉验证。拟合中的 cptable 包含交叉验证预测相对于每个几何平均值的误差的均值和标准差，并且这些误差由该函数绘制。修剪的良好 cp 选择通常是均值位于水平线以下的最左侧值。

用法

    plotcp(object, minline = TRUE, lty = 3, col = 1, upper = c("size", "splits", "none"), args)

其中 object 是一个 rpart 对象，minline 指示是否在曲线的最小值之上绘制一条水平线，lty 是这条线的线型，col 是这条线的颜色，upper 指示在上轴上绘制的内容：树的大小（叶子数）、分割数还是什么都没有，args 是要传递到或从其他方法传递的参数。

示例

    fit <- rpart(Kyphosis ~ Age + Number + Start, method="class", data=kyphosis)
    plotcp(fit)

文件：First plot.png

rsq.rpart

将近似 r 平方与分割数以及不同分割的相对误差与分割数绘制在一起（两个图）。

用法

    rsq.rpart(object)

其中 object 是一个 rpart 对象。

示例

    fit <- rpart(Mileage ~ Weight, car.test.frame)
    rsq.rpart(fit)

文件：Second plot.png

打印

打印一个 rpart 对象。

用法

    print(object, minlength=0, spaces=2, cp, digits= getOption("digits"), args)

其中 object 是一个 rpart 对象，minlength 控制标签的缩写，spaces 是缩进增加深度的节点的空格数，digits 是要打印的数字的位数，cp 从打印输出中修剪所有复杂度小于 cp 的节点，args 是要传递到或从其他方法传递的参数。

示例

    fit <- rpart(Kyphosis ~ Age + Number + Start, method="class", data=kyphosis)
    print(fit)

    n= 81
    node), split, n, loss, yval, (yprob)
    * denotes terminal node
    1) root 81 17 absent (0.7901235 0.2098765)
    2) Start>=8.5 62 6 absent (0.9032258 0.0967742)
    4) Start>=14.5 29 0 absent (1.0000000 0.0000000) *
    5) Start< 14.5 33 6 absent (0.8181818 0.1818182)
    10) Age< 55 12 0 absent (1.0000000 0.0000000) *
    11) Age>=55 21 6 absent (0.7142857 0.2857143)
    22) Age>=111 14 2 absent (0.8571429 0.1428571) *
    23) Age< 111 7 3 present (0.4285714 0.5714286) *
    3) Start< 8.5 19 8 present (0.4210526 0.5789474) *

总结

返回拟合的 rpart 对象的详细列表。

用法

    summary(object, cp=0, digits=getOption("digits"), file, args)

其中 object 是一个 rpart 对象，digits 是结果中使用的有效数字位数，cp 修剪复杂度小于 cp 的节点，file 将输出写入给定文件名，args 是要传递给或从其他方法传递的参数。

示例

    fit <- rpart(Mileage ~ Weight, car.test.frame)
    summary(fit)

    Call:
    rpart(formula = Mileage ~ Weight, data = car.test.frame)
    n= 60
    CP nsplit rel error xerror xstd
    1 0.59534912 0 1.0000000 1.0294527 0.17907324
    2 0.13452819 1 0.4046509 0.6261647 0.10545991
    3 0.01282843 2 0.2701227 0.4746041 0.08567822
    4 0.01000000 3 0.2572943 0.4884699 0.08551818
    Node number 1: 60 observations, complexity param=0.5953491
    mean=24.58333, MSE=22.57639
    left son=2 (45 obs) right son=3 (15 obs)
    Primary splits:
    Weight < 2567.5 to the right, improve=0.5953491, (0 missing)
    Node number 2: 45 observations, complexity param=0.1345282
    mean=22.46667, MSE=8.026667
    left son=4 (22 obs) right son=5 (23 obs)
    Primary splits:
    Weight < 3087.5 to the right, improve=0.5045118, (0 missing)
    Node number 3: 15 observations
    mean=30.93333, MSE=12.46222
    Node number 4: 22 observations
    mean=20.40909, MSE=2.78719
    Node number 5: 23 observations, complexity param=0.01282843
    mean=24.43478, MSE=5.115312
    left son=10 (15 obs) right son=11 (8 obs)
    Primary splits:
    Weight < 2747.5 to the right, improve=0.1476996, (0 missing)
    Node number 10: 15 observations
    mean=23.8, MSE=4.026667
    Node number 11: 8 observations
    mean=25.625, MSE=4.984375

plot（和 text）

在当前图形设备上将 rpart 对象绘制为决策树。函数 text 对决策树图进行标注。

用法

    plot(object, uniform=FALSE, branch=1, compress=FALSE, nspace, margin=0, minbranch=.3, args)

其中 object 是一个 rpart 对象，uniform 如果为 TRUE，则使用节点的均匀垂直间距，branch 控制从父节点到子节点的支线的形状，compress 如果为 FALSE，则叶节点将位于 1:nleaves 的水平绘图坐标处，如果为 TRUE，则例程将尝试更紧凑地排列树，nspace 是具有子节点的节点和叶节点之间的额外空间量，margin 是围绕树边界留出的额外百分比的空白空间，minbranch 将分支的最小长度设置为 minbranch 乘以平均分支长度，args 是要传递给或从其他方法传递的参数。

示例

    fit <- rpart(Price ~ Mileage + Type + Country, cu.summary)
    plot(fit, compress=TRUE)
    text(fit, use.n=TRUE)

文件：Third plot.png

post

创建 rpart 对象的 PostScript 演示图。

用法

    plot(object, uniform=FALSE, branch=1, compress=FALSE, nspace, margin=0, minbranch=.3, args)

Object 是一个 rpart 对象，uniform 如果为 TRUE，则使用节点的均匀垂直间距，branch 控制从父节点到子节点的支线的形状，compress 如果为 FALSE，则叶节点将位于 1:nleaves 的水平绘图坐标处，如果为 TRUE，则例程将尝试更紧凑地排列树，nspace 是具有子节点的节点和叶节点之间的额外空间量，margin 是围绕树边界留出的额外百分比的空白空间，minbranch 将分支的最小长度设置为 minbranch 乘以平均分支长度，args 是要传递给或从其他方法传递的参数。

示例

    fit <- rpart(Mileage ~ Weight, car.test.frame)
    post(fit, file = "", title="Classification Tree for Wikibook")
    post(fit, file = "c:/output.ps", title = " Classification Tree for Wikibook")

文件：Fourth plot.png

案例研究

场景和输入数据

考虑下表中的关系数据库，其模式由属性 Play、Outlook、Temperature、Humidity 和 Windy 组成。决策树允许预测属性 Play 的值，前提是我们知道 Outlook、Humidity 和 Windy 等属性的值。

天气	温度	湿度	风力	高尔夫球运动
晴朗	炎热	高	无风	否
晴朗	炎热	高	少量	否
多云	炎热	高	无风	是
雨	温暖	高	无风	是
雨	寒冷	中等	无风	是
雨	寒冷	中等	少量	否
多云	寒冷	中等	少量	是
晴朗	温暖	高	无风	否
晴朗	寒冷	中等	无风	是
雨	温暖	中等	无风	是
晴朗	温暖	中等	少量	是
多云	温暖	高	少量	是
多云	炎热	中等	无风	是
雨	温暖	高	少量	否

将数据导入 R 很简单。从第一行包含变量名称的逗号分隔文本 (CSV) 文件中，我们可以使用以下命令

    play_base <- read.table("path_to_the_file/play.csv", header=TRUE, sep=",")

我们可以使用命令 print(play_base) 或仅 play_base 查看加载的表格，使用命令 "summary(play_base)" 查看 rpart 对象的详细列表

    Play    Outlook      Temperature   Humidity   Windy
    no :3   overcast:2   cool:5        high :4    false:7
    yes:7   rainy :4     hot :2        normal:6   true :3
            sunny :4     mild:3

执行和输出

加载数据后，我们需要构建决策树。属性“Play”是要预测的结果。我们可以使用以下命令

    fit <- rpart(Play ~ Outlook + Temperature + Humidity + Wind, method="class", data=play_base,
    control=rpart.control(minsplit=1))

我们可以使用命令 summary(fit) 查看加载的决策树的详细列表，使用命令 print(fit) 查看决策树

    1) root 10 3 yes (0.3000000 0.7000000)
      2) Temperature= mild 3 1 no (0.6666667 0.3333333)
        4) Outlook= sunny 2 0 no (1.0000000 0.0000000) *
        5) Outlook= overcast 1 0 yes (0.0000000 1.0000000) *
      3) Temperature= cool, hot 7 1 yes (0.1428571 0.8571429)
        6) Windy= true 1 0 no (1.0000000 0.0000000) *
        7) Windy= false 6 0 yes (0.0000000 1.0000000) *

以下命令将 rpart 对象绘制在当前图形设备上，作为决策树

    plot(fit, uniform=TRUE, main="Decision Tree - Play?")
    text(fit, use.n=TRUE, all=TRUE, cex=.8)

文件：Play or not play.png

玩还是不玩

分析

决策树的构建始于对问题的描述，该描述应指定变量、操作以及决策过程的逻辑顺序。在决策树中，一个过程会导致一个或多个条件，这些条件可以导致操作或其他条件，直到所有条件确定一个特定操作，一旦构建，您就可以看到决策过程的图形视图。

为解决问题而生成的决策树，描述的步骤顺序确定以及天气条件，验证玩还是不玩是否是一个好的选择。例如，在条件序列 (temperature = mild) -> (Outlook = overcast) -> play = yes 中，而在序列 (temperature = cold) -> (Windy = true) -> play = no 中。这表明决策树是做出决定的绝佳工具。因此，这种分类方法可以成为获取信息的绝佳工具，这些信息通常是组织不知道的，但对战术和管理层极其重要。

参考文献

Jiawei Han。数据挖掘：概念与技术。Morgan Kaufmann 出版社，2001 年。

Mohammed J. Zaki 和 Wagner Meira Jr.. 数据挖掘算法基础。剑桥大学出版社，2010 年。

Terry M. Therneau、Elizabeth J. Atkinson 和 Mayo 基金会。使用 RPART 例程的递归划分简介，1997 年。

R 语言定义 - [1]

R 简介 - [2]

Quick-R - [3]

Terry M Therneau 和 Beth Atkinson。包“rpart”，2009 年。