第10章－基于树的方法(1)-生成树

原文参考：https://onlinecourses.science.psu.edu/stat857/node/22

一，本章简介

1，本章主要学习目标

• 理解决策树的基本概念
• 理解构成决策树的三个基本元素
• 理解’不纯度’及其他度量公式的定义
• 知道如何估计每个树节点的各个所属分类的后验概率
• 理解基于树的分类方法的优点
• 理解训练误差(或称再代入误差) 和 代价复杂度测量方法，知道它们的区别，以及为什么要介绍这种方法
• 理解 weakest-link pruning (等价代价复杂度剪枝)
• 理解剪枝后的最优子树都是互相嵌入的，可以被递归地获取
• 理解基于交叉验证来选择复杂性的参数和最终子树的方法
• 理解的model averaging目的
• 理解装袋法(bagging)的步骤
• 理解随机森林(random forest)的步骤
• 理解提升法(boosting)的步骤

决策树既可以解决回归问题也可以解决分类问题。下面我们主要关注分类问题。

分类树是与如k近邻等原型法不同的一种方法。原型法的基本思想是对空间进行划分，并找出一些具有代表性的中心。决策树也不同于线性方法，如线性的判别分析、二次判别分析和logistic回归。这些方法是用超平面作为分类边界。

分类树是对空间进行层级的划分。从整个空间开始递归地划分成小区域。最后，被划分出来的每个小区域都被赋予了一个类标签。

2，介绍(CART)算法

一个医疗案例：

决策树的一个巨大的优点就是构造的分类器具有高度的可解释性。这对于医生来说是一个非常吸引人的特点。

在这个例子中，病人被分为两类：高风险vs低风险。基于最初的24小时的数据，预测为高风险的病人可能无法存活超过30天。每个病人第一个24小时内都有19个测量指标，如血压、年龄等。

下图是一个树形分类器，规则及解释如图所示：

这个分类器只关注了三个测量指标。对于一些病人，用一个指标就可以确定最终结果。所以，分类树对医生来说检验过程很简单。

10.1 构建树

我们要牢记：树代表了对空间的递归地划分。因此每一个感兴趣的节点都对应原空间的一个子区域中的节点。两个子节点占据了不同的区域，如果合并两个子节点，则合并后的区域也与父节点对应的区域相同。最后，每个叶节点都会被赋予一个分类。

树形分类器的构造就是从X空间自身开始，不断的划分出越来越小的子空间。

定义：

我们用X定义特征空间。X是多维欧式空间。然而有些时候，一些变量可能是分类变量，如性别。CART算法的优点，就是可以用统一的方法处理数值型变量和分类型变量。而对于大多数其他分类方法来说并不具备这种优势，如LDA。

• 假设输入变量表示为：X∈X，包含p个特征， X1,X2,...,Xp
• 用 t 表示节点， tL 代表左子节点， tR 代表右子节点。
• 树种所有节点的集合用 T 表示，所有叶节点的结合用 T?
• 一次划分用s表示，划分的集合用S表示

根据下图看一下，空间树如何被划分出来的：

三个基本要素

• 空间划分的选择，如在哪个节点上进行划分，以及如何划分？
• 当我们知道如何划分生成树的时候，又在何时可以确定一个终结点并停止进行划分呢？
• 我们必须对每一个终结点赋予一个类标签。那么我们又何如赋予这些标签呢？

1) 标准问题集－ 划分空间节点的准备

如之前所述，假定输入向量 X=(X1,X2,?,Xp)，既包含了分类变量也包含了定序变量特征。CART算法使事情变得简单，因为每次划分仅从一个变量入手。

如果我们有定序变量，如Xj — 那么此处拆分问题可以转化为比较Xj是否小于或等于一个阈值。因此，对于任意定序变量Xj，问题集Q的统一形式如下：

{Is Xj ≤ c ?}，对于任何实数 c.

当然也有其他形式的划分方法，比如，你可能想问，是否可以形如 X1+X2≤ c ? 这种情况下，划分线不是平行于坐标轴的(划分线是斜率为－1，截距为c的线)。因此，这里我们可以限制问题格式。每个问题均是取一个特征 Xj 与阈值进行比较。

因为训练集是有限的，因此只有有限多个阈值 c 对数据点进行划分。

如果 Xj 是分类变量,取值于{1,2,…,M},那么问题集Q 形如:

{Is Xj ∈ A ?}，其中，A 是 {1,M} 的子集.

所有p个特征向量的划分或问题构成了划分的候选集合。

综上，第一步就是先确定所有的候选问题。以便在下一步构建树的时候，可以挑选在哪个节点上用哪个问题来进行划分。

2) 确定划分优度－’goodness of split’

当我们选择问题进行划分的时候，我们需要测量该问题下每一个划分的’goodness of split’。这既取决于问题的选择也取决于被划分的节点。这个’goodness of split’ 是用“不纯度”公式来测量的。

直觉地,当我们划分节点时候，我们想要使得每个叶节点的区域都更“纯”。换句话说，就是使这个划分区域中的点都尽可能多的属于同一个分类，即，该类占有绝对主导地位。

来看下面的例子。图中有两个分类，x 和 o 。划分的时候我们先检查水平变量是否高于或低于一个阈值，如下图

（编辑：衡阳站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!