第10章-基于树的方法(1)-生成树
原文参考:https://onlinecourses.science.psu.edu/stat857/node/22一,本章简介1,本章主要学习目标
决策树既可以解决回归问题也可以解决分类问题。下面我们主要关注分类问题。 分类树是与如k近邻等原型法不同的一种方法。原型法的基本思想是对空间进行划分,并找出一些具有代表性的中心。决策树也不同于线性方法,如线性的判别分析、二次判别分析和logistic回归。这些方法是用超平面作为分类边界。 分类树是对空间进行层级的划分。从整个空间开始递归地划分成小区域。最后,被划分出来的每个小区域都被赋予了一个类标签。 2,介绍(CART)算法 一个医疗案例: 决策树的一个巨大的优点就是构造的分类器具有高度的可解释性。这对于医生来说是一个非常吸引人的特点。 在这个例子中,病人被分为两类:高风险vs低风险。基于最初的24小时的数据,预测为高风险的病人可能无法存活超过30天。每个病人第一个24小时内都有19个测量指标,如血压、年龄等。 下图是一个树形分类器,规则及解释如图所示: 这个分类器只关注了三个测量指标。对于一些病人,用一个指标就可以确定最终结果。所以,分类树对医生来说检验过程很简单。 10.1 构建树我们要牢记:树代表了对空间的递归地划分。因此每一个感兴趣的节点都对应原空间的一个子区域中的节点。两个子节点占据了不同的区域,如果合并两个子节点,则合并后的区域也与父节点对应的区域相同。最后,每个叶节点都会被赋予一个分类。 树形分类器的构造就是从X空间自身开始,不断的划分出越来越小的子空间。 定义: 我们用X定义特征空间。X是多维欧式空间。然而有些时候,一些变量可能是分类变量,如性别。CART算法的优点,就是可以用统一的方法处理数值型变量和分类型变量。而对于大多数其他分类方法来说并不具备这种优势,如LDA。
根据下图看一下,空间树如何被划分出来的: 三个基本要素
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 。划分的时候我们先检查水平变量是否高于或低于一个阈值,如下图 划分被蓝线标注。切记我们候选划分的特性,划分区总是被平行于坐标轴的线所分割的。就上面的例子说,我们会觉得是个好的划分,因为左手边比较“纯”了,基本都是 x 类,只有2列属于 o 。右手边同样比“较纯”。 直觉上选择每个划分节点的时候我们都想生成“纯”的节点。如果我们再往更深一层次探索,我们会再多两个划分,如下图 现在,如您所见,坐上区域叶节点仅包含 x 类。因此纯度是100%的,没有其他的分类出现。一旦我们达到这个水平,我们就不必再进行更近一步的划分了。因为所有的划分都是100%的纯度。在此训练集上,更多的划分不再有更好的结果,尽管可能在测试集上会有所不同。 10.2 不纯度的测量公式不纯度公式是用来测量包含不同分类点划分区域的“纯的程度”的。假设有K个不同的类别,那么就会有
不纯度的测量公式可以被定义成不同的形式,但是最基本的要要素是要满足下面的三个要素。 定义:一个不纯度的测量公式 Φ ,对于所有K 元组(
定义:给定一个不纯度的测量公式 Φ ,对于 t 节点不纯度为 i(t) : i(t)=Φ( p(1|t),p(2|t),p(k|t) ) 式中,p(j|t) 是给定节点t中的一个点为 j 类的后验概率估计。一旦我们知道了i(t),我们就可以定义对于节点 t,划分优度,定义为 Φ(s,t):
式中,可以看出 Δi(s,t) 是节点 t 的不纯度,与左右子节点不纯度加权求和之间的差值。权值
再来看一下下图例子: 假设紫色阴影的左侧区域要被继续划分,上半部分(x)是左侧子节点,下半部分(o)是右侧子节点。那么此时左侧子节点的比例为8/10,右侧为2/10. 分类树算法会遍历所有候选划分集,找到最大△i(s,t)对应的最优划分。 接下来我们定义 I(t) = i(t) p(t),即,节点t 的加权不纯度值。 p(t)与上述中左右子节点的权值定义一致。当然如果节点t 是总体的第一个划分得到的子节点,那么权值是总体的样本中被被划分到节点t 的样本的占比。 那么对于一个树T,不纯度的总测量定义为 , I(T): 这是所有叶节点的加权求和,注意不是所有节点,是叶节点集合T’。 且对于任何节点有: 进而,我们定义一个父节点与两个子节点之间的不纯度之差:(我们得到了一个递归公式) 最后,我们揭开了不纯度度量的神秘面纱… 下面介绍可能会经常使用的不纯度度量公式:
另一种方法:The Twoing Rule另一种分类树的分裂方法是“the Twoing Rule”. 与上述的不纯度度量公式不同。 直觉上看,在两个子节点的类别的分布应该尽可能的不同,并且落到子节点中的数据占比应该比较均衡。 The twoing rule: 对于节点 t,选择一个分裂是使下面值最大的情况: 当我们把一个节点分裂成两个子节点时,我们希望每个分类的后验概率尽可能的不同。如果差异达到最大,则每个分类都是趋于更纯的。 总的来说,我们既可以用划分优度也可以用twoing rule方法,在一个节点处,我们可以使用所有的方法,然后选择最好的。 10.3 每个节点下分类的后验概率估计不纯度的测度是关于k个分类先验概率的函数,这一节,我们要回答如何估计先验概率。 我们先来定义:
于是,对于节点t,如果把所有的分类加起来,我们得到: 并且,对于分类j,如果我们把左右子节点的样本数加起来,应该等于父节点的样本数: 接下来我们定义类的先验概率为
上述数计算先验概率的一种方式,有时也可能是预先给定的。比如说,在医疗的例子中,研究者收集患有某一疾病的病人了大量的数据。在收集数据中,患有某一疾病的样本比例可能远高于总体的实际比例。这种情况下,就不太适合使用实际数据计算得到的经验频率。但如果数据是总体中的随机样本,则是可行的。 j 类样本属于节点 t 的条件概率估计为,
假设我们知道如何得到
那么在节点t下的样本的概率为: 现在我们就需要知道如何计算 p(j|t) 了,即节点t下的一个样本属于 j类的条件概率:(注意,此处的条件概率是翻转的,不是p(t|j) )
. 决定节点所属分类的规则假设我们已经构建了一个树,那么这个决策树是如何对新的样本点进行分类点呢,步骤如下: 那么,构建决策树的时候是如何确定一个叶节点(终节点)的类别的呢,步骤如下: 如果我们用0-1损失,那么类的确定规则会很像k均值-我们选择叶节点样本中,出现频次最多的类或者具有最大后验概率的类作为该节点的类:
假设我们已经有了一个树,而且没个叶节点上也都赋予了分类。现在我们就需要估计这个树的分类错误率了。 在这个例子中,我们需要介绍错分概率的再代入估计 r(t),给定一个落到节点t 的样本,则: 定义
接下来,我们要花点时间证明如果我们把节点拆分成子节点,那么错分率一定是又提升的。换句话说,如果用再代入估计计算错误率,那么节点的拆分越多,错误率越小。这就导致了再代入误差的一个问题:偏向更大的树。 证明,对于任何节点t,拆分成子节点
定义 j*=k(t). 10.4 例子(略)10.5 树结构方法的优点
10.6 变量合并目前为止,我们假设分类树只是平行坐标轴地对空间进行划分。对于这样严格地划分,会带来什么结果呢? 让我们来看一下下面这个例子: 而且对于分类树的延伸方法也是有许多的,比如并不是按照每个独立变量阈值逐一去划分的线性判别分类(划分一次就使用了样本点的所有信息)。 再或者说,我们用更复杂的问题,如,线性变量的线性组合 (显然增加了计算量): 研究似乎表明,使用更灵活(复杂)的问题即使没有使结果变坏,也往往不会导致明显更好的分类结果。而且,更灵活的问题更容易导致过拟合问题。 10.7 缺失变量在一些训练样本中,有些变量可能会有缺失值。测试样本中可能也会有。决策树有个很好的办法处理缺失值——替代分裂(surrogate splits)。 假设对于节点t ,最优的划分是t,该划分用到了
分类树将会通过找到一个替代分裂点处理这个问题。通过另一个变量找到另一个划分。遍历所有变量,找到最接近最优划分的替代。如果替代划分同样存在缺失值,那么继续找次优的代替分裂,以此类推。 当搜寻代替分裂时,需要注意一个事项。分类树并不是根据分类优度的测量而找到第二个最好的划分,而是找到尽量接近最优划分结果的代替。“此处接近,个人理解为是结构上的接近”。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |