非洲水牛优化决策树：ABO算法在大数据挖掘中的有效性

沙特国王大学学报基于改进非洲水牛算法阿查纳河作者：JiangJiang，Dharmpal D.多耶湾aShri Guru Gobind Singhji工程技术学院，印度Nandedb电子和电信工程，Shri Guru Gobind Singhji工程和技术学院，印度Nanded阿提奇莱因福奥文章历史记录：收到2020年2021年1月18日修订2021年1月18日接受在线预订2021年保留字：决策树群体智能自然启发式数据挖掘非洲水牛优化C4.5A B S T R A C T决策树归纳是一种简单但功能强大的学习和分类工具，用于从数据库中发现知识数据库中的数据量正在增长到相当大的大小，无论是在属性和实例的数量。决策树的一些重要局限性是不稳定性，局部决策和过度拟合这些广泛的数据。非洲水牛优化算法（African Buffalo Optimization，ABO）具有简单、有效和不收敛的特点，适合于求解复杂的优化问题。在本文中，我们提出了非洲水牛优化决策树（ABODT）算法创建全球优化决策树使用非洲水牛的智能和集体行为使用改进的非洲水牛优化算法来创建高效和最优的决策树。为了评估所提出的非洲水牛优化决策树算法的效率，在15个不同大小和领域的标准UCI学习库数据集上进行了实验。结果表明，非洲水牛优化决策树算法全局优化决策树，提高了准确性，减少了决策树的大小这些优化的决策树比传统的决策树更版权所有©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个开放的访问CC BY-NC-ND许可证下的文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍大型数据库是当今大数据数字世界的重要规范。数据挖掘是从各种来源收集的大型数据库中调查有用样本的实践。数据挖掘被认为是通信、广告、教育、社交媒体、保险和零售等不同行业和学科分析工作的核心。 根据用户的需求，使用各种数据挖掘技术，如分类，聚类，回归，汇总，关联和异常检测。分类是数据分析的重要任务之一，用于有效地对数据进行分类。在各种分类技术中，决策树被认为是一种简单，表达，鲁棒和有效的分类器（Han和Kamber，2006）。决策树是一种有监督的表达式分类器，它由节点集合和叶子节点组成，节点集合中的内部节点是测试节点*通讯作者。电子邮件地址：archana10bhosale@rediffmail.com（A.R. Panhalkar）。沙特国王大学负责同行审查节点是决策节点。决策树实现中的关键挑战是发现在每个级别需要选择哪些属性。处理这种选择被称为属性选择。有不同的属性选择措施，以选择属性，可以在每个级别上最好的表现 一些流行的翻译算法，如CART（Brieman等人，1984）、ID3（Quinlan，1986）和C4.5（Quinlan，1993）被用于创建准确和鲁棒的决策树。这些方法易于理解和解释.所有这些算法都遵循自顶向下的贪婪方法来构建决策树。这些方法做出了一个“贪婪”的选择，以确定应该在决策树中测试哪个属性以及如何确定分裂。除了最好的表达能力，易于理解，理解的品质外，决策树还具有以下主要限制（Bertsimas和Dunn，2017; Bennett和Blue，1996）：由于决策树是不稳定的，训练数据中的微小变化可能会大大改变决策树的组织。由于在每个决策中选择最佳属性的局部决策，会产生不准确和次优的树。每个决策都是根据每个节点上的可用数据完成的，因此无法利用所有数据点的特征，这导致分类能力较弱。由于局部搜索，有影响力的分裂被隐藏在较弱的分裂后面。https://doi.org/10.1016/j.jksuci.2021.01.0111319-1578/©2021作者。由爱思唯尔公司出版代表沙特国王大学这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.com●●●●A.R. Panhalkar和D. D. 多耶沙特国王大学学报4764决策树是一步最优的，因此每次拆分都是在不考虑未来拆分和对决策树的不利影响的情况下确定的自上而下的决策树方法无法处理惩罚，而使树变得更复杂。这会导致决策树的过度拟合。自上而下的归纳方法通常在挑选分割时优化不确定性度量，而不是使用训练数据点的错误分类率。诱导树的计算变得非常复杂和冗长，主要是如果许多值是不确定的，或者如果几个结果是相关联的。决策树组合倾向于抽样，因为这些对离群值是鲁棒的，并且具有过拟合的趋势。如果采样的训练数据与测试有点不同，那么决策树可能会产生不正确的分类。本研究的主要目的是克服决策树的这些局限性，并创建优化的和全局的决策树。自然启发的算法，如群体智能算法，由于其两个重要的特性，即适应性和可扩展性，被发现在优化问题中是有前途的（Brezocnik等人，2018; Abualigah，2019）。因此，为了创建一个全局优化的决策 树 ， 一 个 新 的 自 然 启 发 式 算 法 称 为 非 洲 水 牛 优 化 决 策 树（ABODT）。这种新颖的方法使用了一种称为非洲水牛优化的群智能算法的修改版本（Odili等人，2015）来构建高效且优化的决策树。本文的其余部分有以下几个部分：在第2节中，简要讨论了优化决策树的各种方法以及一些元启发式方法。在第3节中，解释了基本的非洲水牛优化。第4节详细介绍了构造决策树的基本自顶向下方法。第5节详细讨论了一种使用改进的ABO优化决策树的新方法。第6节对实验和结果进行了讨论。最后，在第7中给出了本文的结论。2. 文献综述为了避免过度拟合和大型生长树，修剪是在构建决策树时或在构建树之后应用的最佳机制之一（Windeatt和Ardeshir，2001;Esposito等人，1997年）。决策树修剪从决策树中删除一个或多个子树。该方法避免了树的过拟合，使修剪后的树对测试数据的分类更加准确。已经提出了 不 同 的 决 策 树 修 剪 方 法 （ Han 和 Kamber ， 2006; Bertsimas 和Dunn，2017; Bennett和Blue，1996）。这些方法选择性地用叶子替换子树，如果它不降低修剪数据集上的分类准确性。剪枝的主要缺点是它可能会增加训练数据集上的分类错误，但它提高了对未知数据点的分类精度。在选择分裂属性的同时，可以通过在每个节点处使用全局决策来解决过度生长的树的问题。全局选择方法提高了决策树的质量。这导致在一个步骤中构造整个决策树，允许在所有其他决策分裂的完整知识的情况下找到每个分裂。这将导致给定训练数据集的最佳树。寻找最优决策树是一个NP完全问题（Laurent and Rivest，1976）。由于属性的数量、树的深度过大以及分裂点众多，不是全球性的。因此，全局最优树实际上也是不可能的。为了避免分类错误，决策树不应该过拟合，并且是全局最优的。研究人员进行了许多努力来开发有效的方法来构建最优树。线性（Bennett和Evans，1992）和连续优化（Bennett和Blue，1996）方法用于构建最优决策树。线性优化也被发现有希望优化各种分类器（Bhosale和Chaudhari，2019）。连续优化使用基于Frank Wolfe和扩展点禁忌搜索算法的非参数目标误差函数（Bennett和Blue ，1996）。一种基于多线性规划的非贪婪全局树优化方法比标准贪婪树产生更高精度的树（Bennett，1994）。该方法首先创建一个通用的决策树，然后固定树的结构。它最小化分类错误，以固定树的结构。迭代线性规划用于创建优化的决策树。为了创建最优的二叉决策树，使用动态规划来完成向量空间划分（Payne和Meisel，1977）。在最优决策树的创建中，演化方法被用作半最优超平面来构造决策树的深度（Son，1998）。所有这些方法的主要局限性是它们只适用于创建二叉决策树。实际上，这些方法无法在有限的时间内创建最佳的最优树。最近，混合最优化被用来创建最优决策树（Bertsimas和Dunn，2017）。最小深度和最优非二进制决策树使用分类方法创建（Tzirakis和Tjortjis，2016）。从文献中可以看出，决策树的优化除了剪枝方法。 很少有方法是基于进化的方法（儿子，1998年）和元启发式方法在文献中使用，以创建优化的决策树。一些基于群体智能的决策树构建算法使用蚁群优化来构建树（Occupy等人，2012年; Boryczka和Kozak，2015年）。Obery和Freitas（Obery等人，2012）提出了一种新的方法来建立利用信息素和启发式信息量选择决策节点，生成一棵决策树，称为Ant-Tree-Miner。该方法使用构造图表示，其中决策树的节点是顶点，边缘表示决策节点的分支。每个顶点都由一个三元组[level，condi- tion，edge]表示。通过将三元组映射到信息素值，建 立信息素矩阵。Boryczka和Kozak （Boryczka和Kozak，2015）使用相同的方法诱导决策树，然后是Ant-Tree-Miner（Occupy等人， 2012年，进行了一些修改。 在这种改进的方法中，修改的决策标准被用来选择决策节点，每个蚂蚁创建一个决策树。它选择蚂蚁创建的最佳决策树。所有这些元启发式方法都只关注决策树的准确 性 ， 而 未 能 优 化 决 策 树 。 基 于 蚁 群 的 矿 工 （ Ant-Miner ）（Parpinelli等人，2002）使用蚁群优化提取准确的分类规则。它使用顺序覆盖方法来找到完全覆盖所有训练实例的规则。在发现规则后，Ant-Miner执行规则的修剪，由于这种有效的分类规则得到生产。蚁群决策树（ACDT）是一种基于蚁群优化的决策树构建算法（Boryczka和Kozak，2010）。在ACDT中，蚂蚁被用来选择最好的属性在每个节点上进行分割。该算法利用基于启发式函数和信息素值的属性拖引准则来寻找最优属性。自然启发算法是有前途的问题解决引起研究人员注意的途径和方法由于其优异的性能（Jr等人， 1307;Yang ， 2014; Odili 等 人 ， 2017; Abualigah 和 Diabat ， 2020;Abualigah等人，2020年）。各种自然启发的算法（Jr等人，1307）是人工神经网络，进化计算，模糊系统和群体智能。这些算法能够解决几个现实世界的问题。在所有这些有前途的方法中，群体智能已被标记为多学科方法之一。●●●●●A.R. Panhalkar和D. D. 多耶沙特国王大学学报4765fxx¼x1n;x2;··· xn这些方法侧重于蚂蚁、鸟群、鱼群和陆地动物群的集体行为启发式方法（Yang，2014）使用试错法在时间内为复杂的实际问题找到满意的结果。不可能为复杂的问题找到所有可能的解决方案这些算法必须在更短的时间内找到可行的更好的解决方案启发式算法不能保证找到最优解。自然启发的算法将在迭代中工作，并产生有效的解决方案。元启发式算法有两个主要组成部分探索和开发。产生多样化和全球性的解决方案被称为探索。利用是指在一个局部区域内进行搜索，通过分析该局部区域内的信息，找到当前较优的解最流行的组合优化问题是旅行商在TSP上分析了11种自然启发算法的性能（Odili等人，2017年）。非洲水牛优化和蚁群优化被认为是优越的寻找最佳或接近最佳的解决方案。算法在解决问题中的优势是惊人的，因为它们具有 影 响 力 和 鲁 棒 性 的 可 搜 索 性 及 其 在 处 理 高 维问 题 中 的 措 施（Abualigah等人， 2020年）。群体智能包括一群具有分散控制的智能体（Li和Zhang，2008年8月）。这些代理人在本地相互作用，并与他们的环境。其动机来自自然界，尤其是生物系统。这些代理遵循直接的规则，规定个体代理应该如何行为（本地决策），并且彼此之间的某种随机交互构建了“智能”全局行为，对个体代理来说是奇怪的。在群体智能中，智能体选择他们的行动，然后执行它们。它们灵活、健壮、可扩展、分散和自组织的行为在优化任务中提供了最佳性能。群智能算法（如多变量优化算法）可以与其他优化算法混合，以改善复杂问题的优化（Abualigah，2020）。非洲水牛优化（African Buffalo Optimization，ABO）是一种简单的非参数化和有效的算法（Odili等人，2015年）。在文献中比较和验证了ABO用于不同应用的性能（Alweshah等人，2020; Bera等人，2020; El-Ashmawi ， 2018; Odili 和 Kahar ， 2015; Padmapriya 和Maheswari，2017; Singh等人，2020年）。提出了基于ABO的双层优化方法，以同时确定电池储能系统和风力涡轮机的尺寸和最佳可能位置（Singh等人，2020年）。本文提出了一种改进的ABO算法，并将其用于分布式能源的集成，取得了良好的效果.结果表明，ABO血型鉴定的速度优于随机配血法。M. Alweshah等人（Alweshah等人，2020）提出了一种基于ABO的神经网络的有效方法。采用ABO算法对概率神经网络进行训练和权值调整。基于ABO的PNN通过提高分类精度，为各种数据集提供了有效的性能。为了在具有多个中间节点的大型异构网络中工作，ABO实现了控制无线传感器节点的有效性能（Bera例如，2020年）。这是管理源节点到目的节点之间网络中所有传感器节点的有效方法之一。ABO被有效地应用于全局减少网络中的流量和中间传感器节点的能量消耗。为了解决各种现实问题，协作团队在社交网络中发挥着重要作用。W. Ashmawi（El-Ashmawi，2018）应用ABO算法来降低这些社交网络协作团队的通信成本。ABO通过将离散交叉算子与交换序列算子相结合来优化通信成本。该算法首先求出最优解，然后在最佳群体适应度和水牛探索参数之间引入离散算子。Odili等人（Odili和Kahar，2015）应用ABO算法优化各种数值函数。这20个基准函数被约束为无约束的，从不同的域的单峰到多峰，这证明了ABO是执行全局优化的最佳元启发式算法。R. Padmapriya和D.Maheshwari（Padmapriya和Maheswari，2017）应用ABO优化来最大限度地减少移动蜂窝通信中的干扰。这种方法涉及到一个组合的支持向量机与ABO增加无线信道的吞吐量和容量实时分类器需要更少的响应时间，并且可以在优化方法的帮助下实现（Anwar和Azrag ， 2015;Bhosale 和 Chaudhari ， 2019;Bhosale 和Chaudhari，2017）。为了解决第1节中描述的决策树的所有限制，基于修改的非洲水牛优化算法，采用新颖的自然启发决策树优化技术来优化决策树。它创建了高效、准确、小型的决策树。在各种UCI机器学习存储库数据集（Lichman，2013）上获得的结果表明，与现有的决策树构建方法相比，它表现出色。3. 非洲水牛优化算法Odili，Kahar和Anwar（Odili等人， 2015）提出了一种新颖、快速、简单的非洲水牛优化算法来优化旅行商问题。ABO的灵感来自于非洲水牛的迁徙，它们是食草动物，为了寻找郁郁葱葱的绿色牧场而迁徙。这群水牛正在南非寻找安全和绿色的地区。非洲水牛有三个非凡的特性帮助它们生存。第一个重要的属性是，他们正在使用他们的“maaa” 和“waaa”的声音相互交流‘‘waaa” vocalization is anindication to other buffalos in the herd that keep movingbecause the place is not suitable or it is 第二个特点是他们的记忆能力很强，可以记住数千公里的路线.最后一个也是非常重要的属性是水牛的民主本质。如果牛群中有一些水牛反对，那么水牛的所有这些聪明的行为产生了更大的生产结果。所有这些水牛优化决策树的智能行为都被应用到ABODT中。在这项工作中，修改后的版本的ABO被用来创建优化的决策树，这是高效和优化。这些优化的决策树提供了更好的性能比其他优化技术和决策树的修剪。ABO算法（Odili等人， 2016年，开始将每个Buffalo随机地在n维解空间中。在这种算法中，在随机放置水牛后，每个水牛在bgrmax（牛群最佳适应性）和bprmax（个体最佳适应性）的帮助下，vidual buffalo）使用Eq.（一）.算法1.非洲水牛优化（ABO）1. 考虑具有目标优化函数的n头不2. buffalo的位置：将每个buffalo随机放置在解决方案空间的节点上。3. 对于每个k1/4到n（接下页）A.R. Panhalkar和D. D. 多耶沙特国王大学学报4766ðÞ（续）算法1. 非洲水牛优化（ABO）使用Eq. （一）.最大值为1磅/升，最大值为1磅/升，最大值为2磅/升，最大值为：k-Wak=1磅/升4. 更新水牛相对于bgrmax的位置，bprmax：k使用等式（二）、Wak1WakMak=0： 52算法2.决策树构造构建树T型列车1. 创建一个决策节点nd。2. 如果来自T序列的所有数据样本都是同质类，Ci然后使nd作为具有标签Ci的叶节点。3. 如果属性集A为空，则将nd作为具有最常见的类Ci标签的叶节点（使用多数表决）。4. 从属性集合A中选择具有最高信息增益的属性Aj，然后用属性Aj标记nd。5. 对于属性Aj的每个值v：5. 如果bgrMax 已更新，然后转到步骤6，否则转到步骤2。a. 从nd分支，条件为A j¼ v。b. 令Strain是Ttrain中的样本子集，其中Aj^v。6. 检查停止标准，如果不符合，则转到步骤3。端7. 输出最佳优化解决方案。如果水牛的当前适应度优于个体如果当前的适应度优于牛群的整体最佳适应度，则保存牛群的最大适应度（bgr max）并在下一次通过使用等式（2）更新所有水牛的位置，并查看种群中的下一个水牛。在对全局最佳适应度的检查满足退出标准之后，它结束算法并给出保存的当前位置向量作为给定问题的解。如果最佳水牛位置在迭代次数内没有改善，则重新初始化整个牛群并转到步骤2。由方程式其中，lfrand1和lfrand2是取范围[0由于这种受自然启发的算法的灵活行为，修改后的ABO用于优化决策树。得到的优化树能够执行全局优化。这种高效、非参数化且简单的算法以前从未在决策树中使用过。该方法的优点是不依赖于参数，设计简单，易于实现。ABODT算法在第5节中详细阐述。4. 决策树学习器决策树学习器是有影响力的分析模型，易于理解，可视化，应用和评估（Quinlan，1986）。决策树是一种监督分类器。它训练一个决策树分类器，并使用它来测试看不见的实例。一决策树的一个主要优点是它需要更少的数据来训练，并给出最佳的评估性能。决策树构造算法（Quinlan，1986，1993）使用分而治之的方法来构造树。它使用给定的T训练集构造决策树。 此训练集包含一组实例，具体取决于用于训练的数据集的大小。每个实例都由属性值和类组成。它计算训练集Ttrain中实例的类的频率。如果所有实例都属于同一个类，则node将与该类一起创建。但是，如果集合Ttrain包含多个类的实例，则选择使用分裂准则的最佳属性进行分裂。训练集Ttrain被划分为k个不同的子训练集T train。使用选定属性的测试设置fT1;T2;·· ·····TkgC.如果S train为NIL，则将A j标签附加到T train中具有最常见类的叶节点，否则将Build_Tree创建的节点附加到T train; Aj。该决策树算法使用递归方法构建树模型。一旦模型被训练，看不见的样本 将 被 应 用 于 检 查 模 型 的 准 确 性 。 CART （ Brieman 等 人 ， ID3（Quinlan，1986）和C4.5（Quinlan，1993）是一些流行和广泛使用的创建决策树的方法。由于它们的性能，它们被用于决策树的构造和混合分类器。ABODT的主要目的是克服第1节中所述的决策树的缺点。这些树基于可用数据进行局部决策，因此无法进行全局决策。所提出的方法是优化这些树，以采取全球决策的帮助下，ABO算法。这些决策树的非洲水牛的特点进行优化。结果表明，采用非洲水牛优化决策树（ABODT）方法优化的决策树具有全局决策能力，与文献中的方法相比，具有最佳的性能。我们使用J48算法的Weka实现来应用我们的ABODT算法（Hall等人， 2009年）。5. 拟议的系统方法决策树是一种很有前途的分类器，可以准确地对数据进行分类。 决策树倾向于过度拟合、欠拟合和局部决策（Occupy等人，2012年;Boryczka和Kozak，2015年）。为了改进和全局优化决策树，在文献中使用了各种Meta启发式算法，包括遗传算法和蚁群优化（Occupy等人，2012; Boryczka和Kozak，2015，2010; Parpinelli等人，2002; Jr等人，1307; Yang，2014; Odili等人，2017年）。所有这些算法都是参数化的，需要加强以获得更好的结果并使其更快。ABO被认为是有前途的信息传播，因为整个牛群作为一个单位。本文采用改进的非洲水牛优化算法来构造一个全局最优的精确决策树。提出了非洲水牛优化决策树（ABODT），以建立一种高效、准确、优化的决策树. ABODT算法参数较少。非洲水牛的行为和该算法充分利用了非洲水牛的所有属性，提高了决策树的分类性能。非洲水牛的以下特征被用于修改ABO以创建全局优化的决策树，这在Odili等人创建的标准ABO算法中没有被灌输。（2015年）。● 当非洲水牛从一个位置移动到另一个位置时，递 归 地 ， 该 算 法 被 应 用 于 每 个 非 空 分 区 。 构 建 决 策 树 的 算 法（Quinlan，1986，1993）如下：寻找绿色牧场，最好的水牛向绿色牧场移动，如果目标区域的绿色牧场是安全的，那么只有它呼吁其他水牛。A.R. Panhalkar和D. D. 多耶沙特国王大学学报4767XS联系我们jTtrain jinfo Ttrain j在第一头水牛迁移到目的地后，其他水牛也陆续迁移到目的地。迁移后，如果任何水牛发现或认识到目标地区是不安全的，那么水牛返回。如果不安全的水牛向后移动，那么剩下的水牛会根据多数水牛的决定做出决定。如果大多数水牛向目标地区迁移，而水牛又回来，那么这些水牛就向目标地区迁移。水牛的这一特性被称为选举，根据多数，水牛做出决定。如果与几头水牛搬回来相比，最大的水牛被迁移到目标地区，那么目标地区对水牛来说是安全的。所有这些特性都被应用到改进的Buffalo优化算法中。具有上述特征的改进ABO可产生优化的ABO血型树。所提出的ABODT算法创建一个优化的决策树，其大小小于原始大小的决策树。所提出的ABODT的一般程序如图1的方框图所示。该框图示出了所提出的ABODT算法中的主要步骤，该算法从获取输入数据并使用ABODT算法执行决策树的优化开始。以下是修改的ABO算法的步骤，创建全局最优决策树，并在此基础上，ABODT算法的实现和评估。改良ABO算法如算法3所示：算法对决策树进行优化。ABODT算法通过创建全局优化的决策树来提高决策树的精度和大小等各种参数，并避免过拟合。计算决策树的准确性通过在提供用于测试的实例的总数中由决策树正确分类的不可见实例的数量。决策树中的节点总数表示为大小一棵决策树。在ABODT算法中，首先用算法1构造C4.5决策树（Quinlan，1986），然后用改进的ABO算法对C4.5决策树进行优化C4.5决策树（Quinlan，1986）被认为是一种很有前途的分类器，它对所有类型的数据都有出色的性能。在ABODT算法中使用了一些基本术语。决策树的节点被描绘为水牛。每个非叶节点表示在创建决策树时选择用于比较的最佳特征每个非叶节点对应于ABODT中的一个水牛假设在决策树中创建了n个节点具有拟合度的这组节点（属性或特征）被输入到修改的ABO算法。每次迭代中每个节点的适应度计算评估与其他节点的竞争力。计算适应度的主要目标是选择树的上层上的最佳节点。在应用优化标准之后，这些节点也被认为是单个树中的最佳特征。在ABODT中，任何节点的适应度都是使用称为信息增益比的随机函数来计算的启发式搜索是一个用于知识搜索的函数，它会找到最佳路径。它输入代理的当前状态并查找估计值。智能体距离目标有多近启发式算法3.改进ABO算法1. n：在n维搜索空间中随机放置水牛。2. 移动最好的水牛到目标绿色牧场：具有最高健身的水牛被移动到目标安全和欲望绿色区域。3. 最好的水牛给4. 计算目标区域中水牛的适应度：在将每个水牛移动到目标区域后，使用“maaa”调用计算每个水牛的新适应度。如果兽群方法给出了最佳解决方案的最大时间，但它肯定会找到一个更好的解决方案，在最短的时间。增益比（Quinlan，1993）用于从一组属性中找到一个好的属性，这些属性将数据分割，以便每个后继节点尽可能纯。它选择最好的属性与高的程度秩序，分布的实例从其他类的一个单 一的类。 信息增益偏 向于多值 属性（ Han 和 Kamber ，2006）。增益比消除了这个缺点，因此为了选择具有最佳适应度的节 点 ， ABODT 使 用 C4.5 中 使 用 的 增 益 比 训 练 集 T train 由 C1; C2;C3;···组成：C ng n不同班一个实例属于类Ci的概率pi为使用Eq. （三）（bgrmax）在添加此新适应性后增加，p/vfreqCi;Ttrainð3Þ布法罗将继续留在目标地区。5. 如果迁移的水牛发现目标地区不安全，那么它就会返回：在目标地区，如果任何迁移的水牛发现不安全，那么水牛就会向旧地区移动。6. 检查目标区域的适合性：如果大多数水牛迁移到目标区，则意味着目标区是安全的，这表明目标区的适应性较好。给出了ABODT算法生成全局最优决策的步骤算法中显示了使用修改的ABO算法的子树4. ABODT从以下步骤开始构建决策树：ijT列车j其中，jTtrainj是Ttrain中的实例总数。属于类C i的实例数由freqC i;T train给出。T列的信息增益使用方程计算。（四）n信息-pi×log2pi41/1基于非类属性Ai的域值将数据集T训练划分为s个分区。通过该分份过程获得的信息（五）X. Ttrainj..Σ第1页训练数据，然后修改非洲水牛优化属性Ai的信息增益使用等式（1）计算（六）gain__信息增益的问题在于它偏向于具有多个值的属性。因此，在ABODT中用作适应度的增益比使用等式计算。（七）、图1.一、提出的ABODT算法的一般框图gainratio AgainAisplitinfo中文（简体）ð7Þ●●●●信息库Ai;T列车信息库-ð5ÞA.R. Panhalkar和D. D. 多耶沙特国王大学学报4768S..×log. ..Σ←克雷奇←-f gsplitinfo_train_Ai计算通过将训练集T_train划分为测试属性Ai上的s个子集而获得的信息。 splitinfoΔiΔi由等式（1）计算。（八）、如算法4的步骤1所示，在搜索空间中随机地在第k节点处搜索buffalo。每个非叶节点代表一只水牛。每个节点的适应度是该节点的增益比（bprmax）。如步骤2所示，splitinfo中文（简体）Xj1/4T列车jjT列车j2T列车jjT列车jð8Þ初始化优化的树为空和剥削和explo-每头水牛的口粮为0.将具有最高适应度的节点移动到优化节点的增益比是在该节点处测试的属性的增益比为了选择最佳的水牛，ABODT使用节点的适应度，该适应度是使用增益比计算的，这在决策树的优化中给出了有效的性能这些buf- falos使最好的水牛健身整个ABODT算法在算法4中给出如下：列出并更新单个节点的位置：从决策树Tr中选择具有最高适应度的节点，并移动到目标优化决策树列表。使用等式更新节点的开发。9，如步骤5和步骤6所示。bgrmax是herd的适应度，其是优化的决策树的适应度。每个元启发式算法都使用适应度作为优化的基本因素，因此它是使用等式针对树Tr中的每个节点计算的。9.每头水牛开采量平均值1是使用以前的开采量计算的算法4.非洲水牛优化决策树（African Buffalo OptimizedDecision Tree，ABODT）输入：决策树训练nd1;nd2;nd3;···：：;ndn使用训练集T训练输出：优化的选项树开始1. 在树的每个节点上随机放置水牛2. 初始化选择Tr←f£g对于Tr中的每个节点nd，doWannd←0马nd0端3. 对于Tr中的每个节点nd，do4. 移动最好的水牛（节点）到目标区域（选择树）。选项Tr←选项tr[fndg5. lf rand1= Math.Random（）lf rand2= Math.Random（）bgrmax=平均Pm0fitness位置Mand.以信息为基础的参数lfrand1和lfrand2帮助水牛决定迁移的必要性。这通过从它们的一般最佳bgr max和个人最佳bpr max中减去当前勘探位置Wa nd来实现。最后，迁移水牛更新它（10）最适合目标区域。确定适应度并鼓励其他节点探索：在此阶段，每个节点根据其之前的最大位置bpr max确定其位置 以及一些证据从最近的邻居的剥削中获得这是...使用Eq. （九）、这增强了算法，以便于参考优化过程中的节点的方向。在这一步中，一个重要的决定是决定探索是否会导致实现更好的适应性，如图所示在步骤7中。如果它未能实现，则当前探索不更新。遵循牛群（10）其中用于更新牛群的最佳适应度bgr max值由方程式（10）、开发驱动器选择为0.5为最佳性能BPRMax =f itnessk¼检查适应性并根据更新的适应性做出决定其中m是迁移到目标面积（Opt Tr）。6. 更新每头水牛最大值为1磅/小时，最大值为 1磅/小时，最大值为1磅/小时最大值：nd-Wand2007. 更新每个水牛Wand1WandMand=0： 5 108. bgrmax更新了吗？如果是，则转到步骤4，否则转到步骤79. 从OptTr中删除节点（由于目标区域不安全，Buffalo返回）选项转换选项转换并转到步骤410. 端11. 使用训练集T检验评估优化的树OptTr整个ABODT算法4通过以下阶段详细说明：这是用于初始化种群的每个元启发式算法的基本步骤。在ABODT算法中，水牛的种群是决策树Tr中的非叶节点的数量。配置过程通过将如果牛群如果bgrmax没有增加，则检查停止ping标准，否则返回buffalos并对剩余buffalos重复该过程，如步骤8和步骤9所示。评估优化的节点列表：一旦满足标准，算法就会终止执行，如旅行推销员问题，GA，PSO等。根据优化策略，我们需要在测试数据集上评估优化的树。停止后，ABODT使用字符串特征选择和优化算法产生最佳优化树。ABODT算法的整个流程如图2所示。整个流程表明，在建立决策树后，应用改进的ABO算法。应用ABO算法的主要目的是获得决策树分类器的全局优化，并且得到的树应该是准确和高效的。任何算法的效率都是通过算法找到结果所需的时间和空间来衡量的ABODT算法能够准确地对实例进行分类，同时对未发现的实例进行分类所需的时间和空间也较少。6. 实验结果6.1. 数据集描述ABODT算法在来自UCI机器学习库的15个不同标准数据集上进行评估（Lichman，2013）。这些数据集来自不同的领域，具有数值和猫-A.R. Panhalkar和D. D. 多耶沙特国王大学学报4769图二、整个ABODT算法的详细流程结果表明，改进的ABO算法的ABODT比其他元启发式算法具有更好的性能。 为了评估所提出的方法的结果，使用10倍交叉验证方法。每个数据集分为十个部分。表1数据集摘要数据集实例属性类汽车测评172864虹膜15043肺癌32564苗圃12,96085蘑菇8124222淋巴造影148184酒178133声纳208602玻璃21496肝脏疾病34562动物园101177kr-vs-kp3196362Tic-Tac-Toe95892皮马印第安人糖尿病76882Statlog车辆846184在每个折叠中，对数据集的九个部分进行训练，一个部分用于评估ABODT算法的性能。这些UCI数据集的详细描述见表1。6.2. ABODT与基本决策树算法的比较为了证明ABODT算法的效率，第一个结果进行了比较，C4.5基本决策树，这是有前途的基本分类。计算所有褶皱的预测精度结果，然后计算平均结果。在应用算法之前，从数据集中移除具有缺失值的记录。预测准确度是通过正确分类的实例数与测试实例总数之比来计算的。C4.5决策树算法被认为是一个有效和准确的分类器，并解决优化的树特性，ABODT与C4.5的各种参数，如未见过的实例，分类器的大小和叶数的准确性进行了比较。优化后的决策树与原决策树相比具有精度高、叶子最少、规模小等优点。表2显示了ABODT与C4.5的准确度（%）、树的大小和叶数对不同规模数据集的测试结果表明，ABODT的分类精度优于C4.5决策树分类器。精度A.R. Panhalkar和D. D. 多耶沙特国王大学学报4770F表2C4.5与所提出的ABODT方法的精度、尺寸和叶片比较数据集方法精度叶片数树的大小汽车测评C4.592.47131182ABODT94.10116159肺癌C4.540.65611ABODT47.3369车辆C4.573.8098195ABODT75.7475159声纳C4.572.571835ABODT73.101429虹膜C4.59659ABODT97.1248肝C4.563.672651ABODT71.882243糖尿病C4.573.832039ABODT76.191730酒C4.593.2859ABODT95.3259玻璃C4.566.823059ABODT73.242047蘑菇C4.51002429ABODT96.21925表3Ant Miner和ACDT与拟定ABODT方法的准确度（%）比较数据集蚂蚁矿工ACDT提出动物园85.4196.898.01淋巴造影75.5380.2386.10乳腺癌92.4492.5896.25Tic-Tac-Toe73.2493.1687.70kr-vs-kp92.9799.3999.60苗圃86.2399.4198.30图三. C4.5与拟定ABODT方法的准确度（%）比较。与C4.5决策树相比，Mushroom数据集的大小和叶子数量减少了如图 3、由于将水牛从一个位置移动到另一个位置进行全局优化，ABODT创建的决策的准确性从1%提高到8%。改进的ABO算法避免了决策树因数据过多而产生的过拟合问题。使用ABODT创建的决策树比原始的C4.5决策树小对于Liver数据集和Glass数据集，ABODT不仅提高了准确性，还优化了树。通过使用树的大小和决策树中的叶子数量来测量优化的树由于叶子的数量越多意味着比较越多，这导致测试时间增加。与C4.5决策树相比，ABODT使树全局最优且准确。6.3. ABODT与其他元启发式算法的比较为了验证ABODT算法的性能，将其与基于元启发式算法的高效决策树方法进行了实验比较ABODT算法是唯一的，也是第一个使用ABO算法优化决策树的方法ABO算法的主要特点是水牛从一个位置移动到另一个位置，以增加群体的适应度增加的适应度导致决策树的准确性的提高 Ant Miner（Parpinelli等人，八月 2002）和ACDT（Boryczka和Kozak，2010）是用于使用任何群体优化算法来优化决策树的元启发式算法。ABODT与这些元启发式算法进行了比较。Ant之间比较的准确度结果（%）miner和ACDT的数据如表3所示。实验结果表明，ABODT在最大数据