图片

365体育官网_365体育投注-中国直播

当前位置:主页 > 毕业论文 > 计算机 > 计算机理论 > >

基于构造超平面的两阶段决策树算法的研究

来源::未知 | 作者:365体育官网_365体育投注-中国直播 | 本文已影响
   摘要:如何在测试节点里构造一个恰当的分割超平面是构造决策树的关键,与单变量决策树不同,多变量(倾斜)决策树可以找到与特征轴不垂直的超平面。本文将从几何学角度说明构造测试节点的过程,提出了一种两阶段决策树的算法。
  Abstract: How to construct an appropriate partitioning hyperplane in test node is the key to construct a decision tree. Different from decision tree with a single variable, the multi-variable (tilted) decision tree can find a hyperplane which is not perpendicular to the characteristic shaft. This paper will explain the process of constructing the test node and propose a two-stage decision tree algorithm.
  关键词:超平面;两阶段;决策树

  0引言
  决策树有着许多不同的应用,其中包括诊断学里面的长度衰退[1]、分等级的多级标签的分类[2]等。在机器学习和数据采集方面,决策树已经成为一种最广泛的模型。一些决策树分类器的算法,比如ID3[3],C4.5[4],CART等,经常被作为评价其他分类器性能的基准。它之所以流行,是因为其形式简单、判断迅速、解释容易和精确度高。
  1两阶段决策树算法
  1.1 两阶段构造超平面构造多变量决策树的中心问题是,在每个测试节点内对于连续的属性如何研究分割超平面函数如式(1):w1x1+w2x2+…+wnxn+threshold(阈值)=0,这里的X=(x1,x2…xn,1)是一个图形向量,它是由一个常数和n个描叙实例的特征组成的。WT=(w1,w2,…,wn,wn+1)是一个X的参数向量,也可以称为权向量(本文中假设WT是一个单位向量)。为了研究在每个测试决策树节点内构造超平面的过程,首先调整方程式(2):1w1x1+w2x2+…+wnxn=threshold,权向量WT=(w1,w2…wn)可以看作是用函数2构造的超平面的法线方向,然后我们可以将寻找超平面函数2的过程分为两个步骤:首先找出标准向量WT,然后再找出参数阈值。使WT中至少有一个参数不等于0,得到的超平面就会向特征轴倾斜;使WT中只有一个参数不为0,例如WT=(0,0,…,wi,…,0),得到的超平面就会与特征轴垂直。显然,如果在每个超平面的WT中只有一个参数不为0,构造的决策树将会退化为单变量树。为了深入研究这个问题,首先我们作了一个定义1。
  定义1设V=(v1,v2…vn)(单位向量)是实例空间P内的一个方向向量,a=(a1,a2…an)是实例空间P内的一点。?坌a,如果a′=∑1?燮i?燮naivi,我们就说a′是a的V成分。
  根据定义1可知,如把V当作标准轴,那么a′就是V轴上的值。
  命题1设H是用函数(2)构造的分割超平面,假设A和H的交点的标准成分是v,那么v=threshold(阈值)。
  证明设a=(a1,a2,…,an)是实例空间内的一点,?坌a∈P,a的标准成分b=∑1?燮i?燮nwiai。设a′=(a,a,…,a)是从a到标准轴的映射点,得到式(3):b=∑1?燮i?燮nwiai=∑1?燮i?燮nwia。
  设t=(t1,t2,…,tn)是A和实例空间P的交点,因为WT是实例空间p内的标准向量,所以t=a′。联合(3)式,可以得到:b=∑1?燮i?燮nwia=∑1?燮i?燮nwiti=v。根据方程式(2),得到v=threshold(阈值)。
  在权重向量WT内,如果只有一个参数不是0,例如WT=(0,0,…,wi,…,0),那么命题1中法线方向是准确的一个实例空间特征。因此,单变量决策树满足命题1。从这个角度来看,我们的框架是单变量决策树的延伸。此外,一旦发现有法线方向,就可以简单地解决超平面阈值:计算每个实例的标准成分作为一维空间值,然后根据一些标准(如基尼),寻找作为函数(2)阈值的最佳分割阈值。
  1.2 两阶段决策树算法通过在1.1内的分析,寻找超平面函数的过程可以划分为两个阶段。基于这个,介绍两阶段决策树算法,这种算法通过两个阶段为每个测试节点构造超平面,如图1。除了步骤2和3,此算法和其他决策树算法没有什么区别。步骤2(第一阶段),候选超平面的标准列表是用某种研究函数构造的。许多著名的方法可直接用在这里寻找法线方向,如主成分分析,合作联盟等。步骤3(第二阶段)分为两个阶段:在第一阶段中,每个候选超平面阈值是基于一些纯判断标准(如信息增益率和基尼)。在寻找连续属性分割点方面,这个阶段类似于单变量决策树算法。在第二阶段,此模型根据判断标准从候选列表中选出最佳分割超平面。 
  在图2中给出了构造两阶段决策树的控制算法。许多算法只能处理一组特定的数据。为了简化问题分析的复杂性,步骤1对输入数据集进行预处理。预处理数据集之后,步骤2构造一个使用算法1的构造决策树树(参见图1)。一旦决策树被构造,它就会被修剪回来。在修剪阶段有两项措施用以评估每个测试节点:如果它是叶指数,则在测试节点下对一些子树指标(如错误率)和测试节点进行评估。如果是前者且后者满足一些条件(如后者的错误率小于前者),则其根是节点的整个树,由叶取代。不同的算法,采用不同的修剪指标。Quinlan使用错误率评估基于统计界的评估[4],BrEiman等人使用成本复杂性评估基于错误率和树的规模(由叶节点数量来衡量)。但是我们采用EBP C4.5[4]和CCP CART来测试已修剪的构造决策树的性能和修剪算法的影响。
  2结论
  在本文中,首先从几何学角度重新解释了构造测试节点的过程,并在此基础上,提出了两阶段方法来为决策树的每个测试节点构造超平面。第一阶段寻找基于无监督或监督方法的合适的法线方向。基于一些如基尼和增长比的标准,第二阶段找出在法线方向上的超平面的截距。最后提出了两阶段的构造决策树算法。
  参考文献:
  [1]Su,X.G.,Tsai,C.-L.,& Wang,C.(2009).Tree-structured model diagnostics for linear regression.Mach Learn 74:111-131.
  [2]Vens, C. Struyf, J., Schietgat, L., Dzeroski, S., & Blockeel,H.(2008). Decision trees for hierarchical multi-label classification.Mach Learn,73:185-214.
  [3]Quinlan,J.R(1979).Discovering rules by induction from large collection of examples.In D.Michie,editor.
  [4]Quinlan J R.(1993).C4.5:Programs for Machine Learning[M].San Mateo,CA:Morgan Kaufman

365体育官网_365体育投注-中国直播

热榜阅读TOP

本周TOP10

基于全景图的虚拟现实系统研究

基于全景图的虚拟现实系统研究

摘要 全景图(Panoramic Image)是近来出现在Internet上的另一种新的交互式的虚拟场景表示方式,它基于图像...