英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
共进化决策树分类方法
M.J. Aitkenhead
摘要：决策树分类提供了一种快速有效的数据集分类方法。尽管目前存在许多用于优化决策树结构的算法方法，但是这些方法易受训练数据集变化的影响。因此提出了一种进化方法，通过使用决策树和训练数据集之间共同发展的竞争来实现决策树的灵活性。这个方法使用两个不同的数据集进行了测试，其结果可与其他分类方法相比或优于其他分类方法。最终讨论认为决策树在考虑大量变量的情况下比算法或其他替代方法（例如神经网络）更实用。
关键词：决策树；演化计算；模拟退火；数据挖掘；分类
1 引言
在许多分类问题中，所研究系统的区别特征或性质因实例而异。此外，噪声数据集和定性和定量数据的结合可以使统计比较变得不同或不可能。现代分类系统示例或识别类型依赖的陈规定型示例的方法必须能够处理大型、往往是主观和嘈杂的数据集，并且在处理不同类型的问题时必须高度灵活。在此提出了一种将决策树范式与不同的进化概念相结合的方法，以产生具有这种灵活性的分类方法。
1.1 决策树
决策树为许多使用大型数据集和包含的信息复杂并可能包含错误的分类问题提供了一个有用的解决方案。在Russell和Norvig（2002）中给出了决策树的定义，作为一个构造，它“将一组属性描述的对象或情况作为输入，并输出一个是/否的决策。因此，决策树表示布尔函数。这些布尔“是”/“否”响应组合成一个分层的“树状”结构，形成了决策树的形状，它是众所周知的。
在能力方面，决策树是一种快速有效的分类数据集条目的方法，可以提供良好的决策支持能力。Mehta、Agrawal和Rissanen（1996年）强调了分类在大型数据集挖掘中的重要性，以及在经济、医疗和科学领域中的广泛用途。 基于分类的决策树方法在科学和医学中的应用占主导地位，例如Markey、Tourassi和Floyd（2003年），他们将一个简单的决策树应用于肺癌患者的临床标本分类，或Salzberg（1995年）和Salzberg等人（1998）使用决策树方法识别编码外显子的DNA切片（基因中含有产生蛋白质的功能部分的区域）。
决策树所采取的形式通常可以使用以下语句来描述：
bull; 分类是通过重复使用布尔yes/no问题来进行的，涉及问题的特定属性。
bull; 属性可以是值（整数、浮点数等） 或特性(开/关、特征类型等)。
bull; 每个问题或父节点都有两个子节点，它们可以是父节点本身，也可以是输出节点来进行预测。
bull; 输出预测用离散分类说明正在讨论的主题被定义为一件事或另一件事。
图 1 决策树的表示
图 1提供了决策树设计的示例。决策树也在通常为其他人工智能应用程序保留的领域取得进展。 例如，Levow（1998）使用决策树允许自然语言识别系统识别人类用户何时进行口语校正，从而允许它学习和识别问题话语，而Greenspan（1998）使用决策树分类器在杂乱和嘈杂的图像中进行对象识别。然而，无论其应用范围有多广，决策树仍然是最常用的分类用途，尽管这里可以使用这个词来涵盖极其广泛的主题，并且可以在广泛的人类努力范围内应用。例如，Jensen和Arnspang（1999）使用决策树分类系统从音色数据中识别乐器，而Zmazek、Todorovski、Dzˇeroski、Vaupoticˇ和Kobal（2003）使用该范式预测来自其他环境因素的氡气浓度，从而导致未来可能的地震预测系统。Bernstein和Provost（2001）在开发中使用了决策树在开发知识发现助手时使用决策树，以便对用于解决特定问题的不同方法进行分类。这些例子只是许多需要分类或分类的案例中的一些，在这些案例中，决策树的使用非常成功。正如在许多不同情况下应用的概念所预期的那样，存在一系列用于开发和优化决策树的方法。
1.2 优化方法
Dietterich（1990）讨论了20世纪80年代末决策树设计方法的改进，并为这些和更经典的决策树开发方法提供了良好的背景。最近，Lim、Loh和Shih（1998）在各种数据集上比较了几种决策树、统计和神经网络方法。这两项工作都表明，从常用的不同决策树算法可以获得广泛的速度和精度，并且不同算法的有效性随数据集的变化而变化很大。目前，最常见的诱导决策树结构的“基准”方法之一是C4.5，由Quinlan（1993）设计，它还能够处理变量是连续的或整数的数据集，或者缺少数据的数据集。这套算法提供了大量关于已被操纵的数据的信息，以及为处理这些数据而开发的决策树，其中大多数不会在这里进行检查。然而，Llora`和Garrell（2001）提供的将C4.5用于培训互联网上可用的数据集，允许将新方法与此基准系统进行比较。
所有决策树开发方法都有两个主要过程。第一个是树的生长，使它能够准确地分类正在使用的数据集，第二个是剪枝阶段，在这个阶段，多余的节点和分支被移除。Bradford、Kunz、Kohavi、Brunk和Brodley（1998）使用了一种将错误分类误差最小化的剪枝分类器树的方法，而Ferri、Flach和Hernandez-Orallo（2003）分析了几种估计树的剪枝算法，从而确定了在特定情况下应用的最佳算法。这是另一个例子，说明在决策树方面存在大量的方法，以及难以决定哪一种方法适用于给定的问题。
Friedman, Kohavi,和Yun（1996）讨论了构造决策树的问题，其中主要的问题是在每个节点上问什么问题，以便对数据集进行最优的划分。他们表明，随着处理越来越大的数据集和越来越多的变量，这个问题变得更加困难。 Fulton、Kasif、Salzberg和Waltz（1996）在对能够处理大型复杂数据集的决策树生成问题的相关分析中表明，构建能够处理原始数据集的一小部分的决策树更简单。 正如导言后面所讨论的，这一概念对目前的工作很重要。Alsabti、Ranka和Singh（1998年）讨论了另一个相关的主题，他们讨论了将决策树扩展到大型数据集的问题，结果往往会失去准确性。
在许多情况下，在开发决策树时，准确性不是唯一的考虑因素。用户必须能够实现并至少在一定程度上理解和遵循所涉及的问答过程。Garofalakis、Hyun、Rastogi和Shim（2000）讨论了用户定义的约束（如大小限制或精度）构造决策树的方法。这些限制对于用户能够充分理解或使用数据集，或避免决策树与可用数据过度拟合往往很重要。Ankerst、Elsen、Ester和Kriegel（1999）使用了一种交互式方法，用户通过使用培训数据的可视化来更新决策树。这种方法产生了一个更直观的决策树，用户能够根据他们现有的有关该系统的知识来实现该决策树。
近年来，人工智能研究的不同分支之间发生了一个融合过程。其中两个领域显示出巨大的前景，当相互配合使用时，是决策树和进化计算。Li和Belford（2002）讨论了决策树分类固有的不稳定性，表明训练集的轻微变化可能需要树拓扑的剧烈变化。进化方法似乎提供了一种自适应方法，允许自动对树进行更改，以处理不能以任何精度纳入当前系统的新数据集值。
Llora`和Garrell（2001），以及Papagelis和Kalles（2001）表明，当用于开发分类决策树时，进化方法允许开发重要和不重要的属性和关系，并允许识别不重要的因素。Cantuacute;-Paz和Kamath（2000）同时讨论了一种专门用于开发分类树的进化方法，而Turney（1995）使用了决策树进化适应度的定义，该定义不仅包括错误率，而且还包括其他成本，如大小。Endou和Zhao（2002）研究了一种基于所使用的训练数据集演化的决策树实现方法。训练数据集的发展是为了提供对领域知识的最佳覆盖。此外，Siegel（1994）还讨论了竞争进化决策树作为增强进化方法的一种方法的实施。
1.3 目标
本节目的是表明一种新的决策树和进化方法的组合可以提供一种有用和准确的分类方法。在选择机制过程中利用决策树的大小和分类精度，以及决策树和训练数据集的竞争协同进化的应用。使用这一特定进化范式的目的是双重的，因为(a)通过从一个小数据集开始，决策树将能够避免在一开始就花费很长时间寻找一个大型复杂问题的解决方案，(b)希望共同进化过程比正常的独立进化方法更快、更有效地找到解决方案。
2 方法
2.1 决策树设计
决策树的基本结构对应于图 1中所示的结构。有一系列的布尔语句，这些布尔语句依次导致一组正在考虑的变量的预测。在开发决策树之前，用户将任意变量设置为要实现的适应度的目标（第2.3节给出了适应度的定义）。决策树设计以最大深度常数的形式对其进行了进一步的限制。这个常量防止决策树变得如此之大，以至于它要么过于适合数据，要么在计算上变得难以处理。
决策树的每个节点（无论是问题还是预测）都使用四个值进行编码。第一个值标识正在被查询（在问题节点的情况下）或预测(在预测节点的情况下）的变量，并且是可以设置为任何变量标识符的整数。每个节点的第二个值决定了节点是预测（1）还是问题（2），并且可以在这两个值之间交替。这里有一个冗余的因素，因为该系统本来可以以一种明显的方式实施，即是否有人提出问题(例如正在考虑的变量不是正在预测的变量)或正在进行预测（正在考虑的变量是正在预测的变量）。然而，对于进化过程来说，有一个专门确定节点性质（问题或预测）的值比引入一些额外的算法复杂性更容易。
每个节点中的第三个值是一个整数，描述变量是否大于（1），等于（2）或小于（3）第四个变量中给出的值。对于预测，假设第三个变量的值总是2，表示相等，而对于问题，这个值可以是1、2或3。在数据集中使用的变量是浮点的情况下，询问特定变量是否等于某些值的能力不太可能被使用，但在这些值可以是整数或代表某些定性描述的情况下，它将是有用的。这里提出的另一个考虑是，对于数据集中的变量，其值仅由整数组成，则是描述该变量的每个节点中的第四个值（即正在比较或预测的）总是整数。对于用浮点值表示的变量，第四个值是浮点。
2.2 训练数据集
这两个数据集来测试比较的方法都是从Merz和Murphy（1998）获得的。 其中一个数据库提供了V.Speihler提供的关于玻璃化学性质的信息，其中有10个变量(其中一个为类型分类）和214个数据条目。变量信息如下，取自Speihler的数据库：
1. RI：折射率
2. Na：钠（单位测量：相应氧化物中的重量百分比，如属性3-9）
3. Mg：镁
4. Al：铝
5. Si：硅
6. K：钾
7. Ca：钙
8. Ba：钡
9. Fe：熨斗
10. 玻璃类型：（类属性）
(a) 楼窗户，浮子处理
(b) 建筑窗户，非浮层处理
(c) 车辆车窗，浮子处理
(d) 车辆窗口，非浮动处理（此数据库中无）
(e) 集装箱
(f) 餐具
(g) 头灯
表 1提供了从Spiehler文件复制的数据库中使用的变量的摘要
第二个数据库提供了汽车成本评估的数据（Bohanecamp;Rajkovic，1988年），有7个变量（其中一个为类型分类）和1728个数据条目。类型有（1）不可接受，（2）可接受，（3）良好和（4）非常好。用于描述CAR数据集成分的变量包括以下内容，变量和类型分类类别之间给出了相关值：
1. 成本：（1）很高，（2）高，（3）中等，（4）低。类相关 =0.283。
2. 保养：（1）很高，（2）高，（3）中等，（4）低。类相关性=0.232。
3. 门：（1）2，（2）3，（3）4，（4）5以上。类相关性=0.066。
4. 人员：（1）2人，（2）4人，（3）以上。类相关=0.342。
5. 行李容量：（1）大，（2）中，（3）小。类相关=-0.158。
6. 安全性：（1）低，（2）中，（3）高。类相关=0.439。
与大多数现实生活中的数据集一样，在这里使用的两种情况下，要预测的变量的值的频率分布不是平坦的，相反，一些值发生的频率比其他值更多。为了防止对某一分类产生偏见，通过对包含这些值的数据条目进行随机重采样，增加了较少频率值的计数。在程序上，这种方法与方法后面讨论的“套
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[259418]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
