星期三, 九月 26首页

基于简化信息熵和协调度的改进ID3算法

摘要:决策树算法是数据分类挖掘的核心技术,Quinlan提出的ID3算法是决策树算法中著名的算法,但ID3具有高复杂计算,属性偏好多值,大尺度等缺点, 鉴于上述问题,提出

了将简化信息熵与粗糙集理论中的协调度相结合的改进型ID3算法。 实验结果证明了优化

方案的有效性和可行性。

关键词:决策树;ID3算法;信息熵;协调度

1.简介

包含大量潜在和有价值信息的绝大多数数据都存储在数据库中。 如果我们可以从数据库中提取丰富的隐藏信息,我们将创造更多的潜在价值。 面对上述问题的挑战,数据挖掘技术日趋成熟,表现出强大的生命力,分类挖掘成为基于数据挖掘成功应用的最活跃,最成熟的研究方向领域。

研究人员已经成功应用了各种不同的分类算法,如决策树法,神经网络法,统计方法等,

决策树算法广泛应用于分类数据挖掘领域。 该算法具有快速学习,综合分类规则和高精度

分类等优点,而ID3算法是本文的主要内容,是众多决策树算法的关键。

ID3算法被用作更一般的分类函数,具有可理解的决策规则,计算量少,计算速度更高等优点,但ID3也有一些缺点,例如:(1)使用对数算法计算信息熵不容易,浪费了大量的时间。 (2)在属性选择过程中存在多值BIOS的问题,具有更多值的属性并不总是最优的。 (3)我们无法控制树的大小,这将产生长的分类规则。

为了解决上述问题,基于ID3方法提出了一种优化方案。 首先,通过泰勒公式完成最优属性集的选择,用对数算法代替运行速度。 然后,为每个属性引入不同的权重,使得属性集的选择更加合理。 最后,决策树大小由粗糙集理论中的协调度确定。 实验结果表明,改进算法比ID3具有更好的效果和可行性。

2.ID3算法说明

ID3算法是一种常见的决策树分类算法,由Quinlan在1986年提出,最小熵被选为ID3中的启发式策略。图1为结构决策树的过程概述。

我们来介绍一些符号。 信息熵和信息增益定义如下:

其中,D = {(x1,y1),(x2,y2)··(xm,ym)}代表训练样本集,|D]表示训练样本的数量。A = {a1,a2··ad}表示|D|的属性集,d = {1,2··|κ|}。 pk(k = 1,2,…,|D|)表示每个当前样本集的每个类的比率。 假设在属性ai中存在V个不同的值(V = {a1,a2···aV})。 Di表示每个值的样本子集,|Di|表示当前样本的数量

决策树模型(图2所示的树形图)可以用图1中描述的ID3方法获取,决策树模型通常包括一个根节点,多个内部节点和一些叶节点。

其中,所有决策结果都显示在叶节点中,其他节点对应于不同的测试属性。 基于启发式策略,每个节点中包含的样本集被分类到各个子节点。 整个样本集包含在根节点中。 从根节点到每个叶节点的路径对应于确定的测试序列。

ID3算法分类大量数据有很多优点,如强直观性,易分解性等,但ID3算法也有缺点,例如:用对数算法耗费大量时间来计算信息熵; 当使用信息增益来划分属性时,它倾向于选择具有更多值的属性; 在构建决策树的过程中很难控制树的大小。

本文的目的是解决上述缺点,提出改进的ID3算法,用于改善ID3方法存在的缺点。 希望改进的ID3算法能够在短时间内生成更为简洁的决策树,从而形成更合理的最优属性。

  • 改进的ID3算法

本节提出了相应的改进措施,旨在解决上述ID3算法的缺点。 改进的ID3算法分为三个步骤,下面详细讨论。

  • 信息熵的简化

ID3算法中最优属性的选择基于等式(2),但对数算法增加了计算的复杂度。 如果我们可以找到一个更简单的计算公式,构建决策树的速度将会加快。 本文用泰勒公式简化了等式(2),以降低计算复杂度。 简化过程组织如下:

假设D中有n个反例和p个正例,D的信息熵可以写为:

假设在D的属性ai中包含V个不同的值,并且每个值包含ni个反例和pi个正例。 因此,属性ai的信息增益可以写为:

在非常小的变量x的情况下,公式ln(1 + x)≈x是真的,并且基于泰勒公式可以忽略每个步骤中包含的常数。 在简化过程中,等式(3)可以重写为:

同样,等式(4)中的表达式可以重写为:

因此,等式(4)可以重写为:

 

因此,等式(4)可以用于计算每个属性的信息增益,并且具有最大信息增益的属性将被选择为决策树的节点。在式(4)中只包括加法,减法,乘法和除法的表达式大大降低了计算的难度,并增加了数据处理能力。

B.变种偏差问题及解决方案

许多决策树算法存在品种偏差。 如果可以使用′′′number′ 作为候选属性,则该属性的信息增益将大大高于其他属性,这表明该决策树没有泛化能力和良好的预测能力。 为了避免多值BIOS,引入不同的权重给对应的属性。(′′′number′ 不知道在这里做什么翻译)

假设每个属性的特征值的数量为M,则通过基于大量实验结果的表达式解决品种偏差的问题,因此选择最优属性的标准可以定义为:

如果我们通过上述方法构建决策树,我们将尽快构建一个决策树模型,避免品种偏差的问题,但我们无法控制决策树的大小,因此本文介绍了协调度的理论 改进分割点的特征,以获得更简洁的决策树。

C.不可控的树大小和解决方案

内部节点拆分的程度难以控制,这将带来很大的缺点,如树型大,分类规则长等,因此本文介绍的协调度的概念,在预先确定内部节点的分割属性时起着重要的作用,避免用于处理过拟合问题的后续修剪步骤。 改进算法的基本思想是每个分支的分割属性的标准由协调度的大小和条件确定度决定。

假设A代表训练集,A = {a1,a2··ad}表示条件属性集,它是变量,而adi表示属性ai中的值的子集。 Dl = {y1,y2··yn}标注属性集,这是固定的。 协调程度定义如下:

条件确定度由以下定义:

不同分支的分割属性取决于协调度的大小和子集中的条件确定度。 如果协调度的大小大于或等于协调度的大小,节点将是叶节点,相反,节点将是可以继续分割的非叶节点。

D.改进ID3算法的步骤

改进ID3算法的步骤总结如下:

  • 决策树算法的评估

一般来说,我们应该评估决策树的泛化误差,并通过实验测试方法提出基于算法存在的改进的解决方案。 因此,选择合理的评估算法的步骤是必要的。 评估算法可以通过训练数据集获得,然后预测新数据集,以判断数学模型的准确性。

评估算法有许多种,如保持算法,交叉验证算法,自举算法。最后两种算法在足够数据的情况下更为常见。本文选择第一种算法(保留算法)作为评估算法,以快速,方便的方式判断决策树模型的有效性 详细的过程如图4所示。我们如何从数据集D中进行训练集和测试集? 本文采用第一种方法将D分为两部分:一种用作训练集,另一种用作测试集。

  • 案例

参考表1中描述的与基于天气条件的玩球相关的决策表,其中U = {1,2,…,24}是24个对象的集合。 属性集C = {outlook,Term,Hum,Windy}是条件属性单元,属性集Dl = {d}是一个标签属性集。根据样本有两个数据集随机划分。 训练集共有17个样本,其中包括8 N和9 Y,以及7个样本,包括4 N和3 Y。

 

图5是参考表1的ID3算法构建的决策树模型。同样,图6是由改进的ID3算法构建的决策树模型。

从图5和图6可以看出,改进的ID3算法构建的决策树模型更为简洁。 由ID3算法构建的决策树生成11个节点和7个规则,由改进的ID3算法构建的决策树生成6个节点和4个规则。 相比之下,后者具有较小的规模和较短的规则。 我们可以通过保留算法来预测上述规则的测试集。 改进的ID3算法的准确性等于ID3方法的准确性(即85.71%),改进的ID3的运行时间(即0.072)比ID3算法的运行时间(即0.081)短,运行的差异 两种方法之间的时间趋向于越来越大的样本越来越大,并且由改进的ID3算法构建的树形大小比由ID3方法构建的树形大小更加简洁。

  • 结论

本文基于ID3算法的缺点,提出了一些改进。 通过判断决策树的有效性,可以改进ID3算法。 本研究表明,使用改进算法的决策树基于四个属性的分析具有85.71%的高精度。 决策规则比ID3短。

对于未来的工作,应该研究如何快速,准确地适应在线分类系统中更多的新样本,并选择一种更合理的分配训练集和测试集的评估方法。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注