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