ID3算法

2024-07-03

ID3算法（精选7篇）

ID3算法篇1

ID3决策树算法作为一种具有重要理论价值和影响力的数据挖掘算法已经广泛应用于数据分类和模型研究等各个领域。ID3决策树算法引入了信息论中的概念, 将信息增益作为选择非叶节点的标准, 通过对样本数据属性的选择自顶向下的分类并构造决策树, 从而利用决策树完成对整个数据源的检索及统计。由于属于智能决策的一部分, ID3决策树算法同样可以用于数据分类, 如各种专家系统、金融信息服务、气象服务及网络智能搜索等方面。

虽然ID3决策树算法已经得到了广泛应用, 但是该算法还存在一些缺陷和可以改进的方面。通过对ID3决策树算法建立决策树的过程中所存在的多值偏向问题的分析和探索, 提出了一种基于信息增益和样本结构相似度共同作用的属性判断指标, 通过改进指标来修正多值偏向给ID3决策树算法的准确性带来的影响。其实现过程对于在继续改进和丰富ID3决策树算法的判断指标和提高决策的准确性具有一定的现实价值和参考价值。

1 ID3决策树算法的不足

ID3决策树算法选用当前层次信息增益最大的属性来作为节点进行分支判断, 而每次信息增益的计算很大程度上会受到多值偏向性问题的影响, 即取值较多的属性有优先选取的倾向。这就难以判断得到的测试属性究竟是因为本身比较重要还是由于属性取值较多的缘故而被算法作为节点属性而选择的。

如果数据集中的不同属性间关系较为复杂, 属性间联系的强弱关系又没有明确的判断方法时, 信息增益的计算将很大程度上受到样本数据集中取值较多的属性的影响, 从而无法确实的反映客观的分类情况。由此可以得知, 在属性的关系复杂且重要度不确定的情况下构建的ID3决策树存在忽视重要的非多值属性的趋势。为提高分类预测的准确性, 针对ID3 决策树算法引入样本结构相似度模型对原算法的多值偏向性问题进行改进。

2 SS_ID3决策树算法简介

在样本数据集和实际数据集中一般情况下都存在一个共同的分类属性, 该属性具有若干个不同的属性值, 所有的数据元组都将指向这个分类属性中的各个属性值。从样本数据集中列的角度来看, 由于数据元组各个属性中属性值的随机性使得这些数据结构具有很大的不同, 从而使得每个属性列在表面上看起来往往是杂乱无章的。通过经验判断可以看出其中有一部分属性间没有很明确的联系, 但还是有一些属性间确实具有很明显或者很直接的关联关系。因为ID3决策树算法只是通过划分前后信息量之间的差值大小 (即信息增益) 为分类依据, 并没有考虑到描述属性和分类属性间的联系关系, 所以, 提出了一种改进的ID3决策树算法——SS_ID3决策树算法。

SS_ID3算法将描述属性和分类属性间的关联关系引入到了属性选择的步骤中与信息增益联合使用, 这样的处理能够帮助一些与分类属性在结构上相似或联系比较紧密的属性能够在描述属性选择的过程中得到更多的砝码, 从而能够在一定程度上减少或克服一些联系较紧密的描述属性由于属性值偏少而造成信息熵的减少不足导致的在选择中被忽略的问题, 同时还兼顾信息增益较大的属性, 使得这些属性不被样本结构相似度所掩盖。引入的样本结构相似度模型是一个用来度量样本数据集中的描述属性的属性值与分类属性的属性值之间的空间结构重叠性的数值指标, 样本结构相似度越大说明该描述属性的分类样本数在物理上越趋近于分类属性, 反之则越不同。计算主要用到的数值包括: (1) 总的样本数据元组数; (2) 分类属性的属性值; (3) 描述属性的每个属性值; (4) 结构相似矩阵。通过相应的计算得到的数值作为一个加权因子参与到描述属性的选择过程中来完成对ID3决策树算法的改进。

3 属性结构相似矩阵

计算样本结构相似度需要在样本数据集上建立一个数据模型——结构相似矩阵, 用来描述某个描述属性与分类属性间的分布情况, 即每个描述属性的属性值分别在所有分类属性值下出现的次数, 并获取其中重叠次数最多的数值。结构相似矩阵模型将为每个描述属性建立一个矩阵用来提供相应的计算样本结构相似度的参数, 并刻画了属性值在样本数据集中的结构分布情况。

3.1 结构相似矩阵的描述

在分类属性的取值空间R=[r1, r2, …, ry]上不同元组的属性值都有其各自不同的位置和数量, 可以根据属性值的位置得出一个向量V=[v1, v2, v3, …, vn], 其中v1至vn为样本数据集的所有元组所对应的分类属性的所有取值。同样每个描述属性都有一个向量与V对应。将每个描述属性向量分别与分类属性的向量合并成一个二维向量, 通过对这个二维向量进行处理就可以得到每个描述属性相对于分类属性的结构相似矩阵。

3.2 结构相似矩阵的数学定义

设存在一个训练样本数据集S, S中包括s个数据元组;存在数据项B为训练样本集S的一个描述属性, 属性B的取值空间为B={B1, B2, …, Bn}, 属性A在样本数据集中的结构为

undefined

;存在数据项C训练样本集S的分类属性, 具有m个不同值, 用来定义m个不同的类, 属性C的取值空间为C={C1, C2, …, Cm}, 对C按照样本数的多少从大到小进行排序得到整理后新的C′={C′1, C′2, …, C′m}。属性C′在样本数据集中的结构为

undefined

。由该描述属性和分类属性的值所构成的数据结构为:

undefined

。以描述属性B的取值为行, 分类属性C的取值为列, 可以通过UV得到一个n行m列的矩阵A, 按照Bj的顺序定位矩阵A的行顺序, 按照C′i的顺序定位矩阵A的列顺序, 并记矩阵A中的aij为UV中v的取值为C′i时且u的取值为Bj时数据元组的样本数量, 直到将UV中的所有数据自上而下进行遍历, 统计样本数后就得到了描述属性B相对于分类属性C的结构相似矩阵A。

undefined

4 样本结构相似度

通过对该矩阵中的数值进行提取和计算就可以得到该描述属性相对于分类属性的样本结构相似度。简单地来说样本结构相似度是一种通过计算得到的用以判断在样本数据集中指定描述属性的结构相似情况与分类属性的数据分布在不复用数据的情况下相吻合的程度。可见样本结构相似度是一种运用单个描述属性的结构相似矩阵通过计算得到该描述属性与分类属性在结构上的相似度的方法。

4.1 样本结构相似度的计算公式

样本结构相似度的数学定义如下:设存在样本数据集S, S中包含样本数据元组个数为s, 其中包含描述属性B其取值空间为B=[B1, B2 , …, Bn]和分类属性C其取值空间为C=[C1, C2 , …, Cm], B的取值个数为n, C的取值个数为m, 可以得到一个行数为n和列数为m的矩阵DT, 其中的矩阵元素为a[x], [y], 根据如下计算公式可以得到该描述属性相对于分类属性的样本结构相似度Fb (DT) 。

undefined[Max (a[], [j]) ]}, k=[1, 2, …, n]

其中公式Maxk (a[], [j]) 为获得结构相似矩阵DT的第j列的最大值, 而Adrx[Max (a[], [j]) ]是用来得到第j列的最大值所在的行数, k为记录结构相似矩阵DT各个行号得到的数据集, k=k-Adrx[Max (a[], [j]) ]就是将已取得当前列最大值的一行从之后的计算中剔除掉以保证该数据不被复用从而去除二义性和不确定性。

4.2 样本结构相似度的应用

由于样本结构相似度是一种用来修正信息增益在选择属性时产生的多值偏向问题的权值, 所以在ID3决策树算法的运作过程中需要将其加入到节点选择和判断的标准中, 即将样本结构相似度和信息增益相结合以得到进行了结构相似修正后的新的判断数值, 然后再对新数值进行比较来选择用来划分数据集的当前属性。使用相同的样本数据, 见表1, 分别进行ID3决策树和SS_ID3决策树的构建, 通过构建出来的决策属来进行比较。

由于根节点、各内部节点和叶节点的选择参数发生了变化后, SS_ID3算法和ID3算法所构建的决策树存在着明显的不同, 如图1所示。改进后的规则描述由原有的5条增加为8条, 这样就能够对数据的分类更加细致, 有助于提高决策树分类的准确性。

5 结论

通过决策树结构来看, SS_ID3决策树算法对取值数较多的属性并不敏感。SS_ID3算法使得决策树的结构更加平衡, 判断路径更加丰富, 对数据的分类更加细致, 有助于提高决策树分类的准确性。通过比较可以得到一些SS_ID3决策树算法的优点:一是在一定程度上解决了仅使用信息增益作为判断标准而造成的多值偏向问题。二是决策树的结构更加均衡。三是提高了结构相似度较高但取值不多的属性的权重, 使得决策树分类更加科学。四是对数据集的分类会更加细致, 有助于提高分类的准确率。

参考文献

[1]Joong-Hee Lee, Jong-Hyouk Lee, Seon-Gyoung Sohn, et al.Effective Value of Decision Tree with KDD 99 Intru-sion Detection Datasets for Intrusion Detection System[J].2008 (2) :17-20.

[2]Dunham M.Data Mining:Introductory and AdvancedTop ics[M].Upper Saddle River, NJ:Pearson Educa-tion, 2003.

[3]陆秋, 程小辉.基于属性相似度的决策树算法[J].计算机工程, 2009 (3) .

[4]鲁为, 王枞.决策树算法的优化与比较[J].计算机工程, 2007.

[5]房祥飞, 刘希玉.决策树在数据挖掘中的新进展和发展前景[J].信息技术与信息化.

[6]梁循.数据挖掘算法与应用[M].北京:北京大学出版社.

[7]段玉春, 晓艳, 孙玉强.一种改进的ID3决策树算法[J].南阳师范学院学报, 2006 (5) .

[8]唐松华, 姚耀文.数据挖掘中决策树算法的探讨[J].计算机应用研究, 2002 (8)

[9]王静红, 王熙腻.邵艳华, 等.决策树算法的研究及优化[J].微机发展, 2004, 9 (14) .

一类决策树ID3改进算法探究篇2

关键词：决策树,ID3,分类属性,信息熵

0 引言

决策树是一种重要的数据挖掘技术,是从机器学习领域发展而来的一种函数逼近分类方法[1,2,3,4,5,6,7,8,9]。随着人工智能研究的深入,对决策树算法进行改进,尤其是经典决策树算法ID3改进,成为研究热点[10,11,12,13,14]。

1 ID3算法及其基本概念

1.1 ID3算法

ID3具体算法如下[15]。

输入:ID3(Examples,Target_attri,Attri),Examples即训练样例集,Target_attri是决策树要预测的目标属性,Attri是除去目标属性之外供学习的决策树测试的属性列表。

输出:一棵能正确分类给定Examples的决策树Root。

(1)创建树的Root结点

(2)如果Examples都为正例,则返回label= + 的单结点树Root

(3)如果Examples都为反例,返回label= - 的单结点树Root

(4)如果Attri为空,返回单结点树Root,label= Ex-amples中最普遍的Target_attri值。否则,执行(5)。

(5)A ← Attri中分类Examples能力最好的属性;Root的决策属性 ← A;对于A的每个可能值vi:

在Root下加一个新的分支对应测试A = vi;

②令Examplesvi为Examples中满足A属性值为vi的子集;

③如果Examplesvi为空,则在此新分支下加一个叶子结点,结点的label= Examples中最普遍的Target_at-tri值;否则,在此新分支下加一个子树ID3 (Examplesvi,Target_attri,Attri- |A|)。

(6)结束。

(7)返回Root。

在算法(1)处所描述的分类能力最好的属性为具有最高信息增益的属性。

1.2 信息熵与信息增益

确定分类能力最好的属性需要用到ID3算法中规定的信息熵和信息增益。

(1)信息熵。ID3算法认为,对于一个拥有n个反例和p个正例的样例集合S而言,能对其进行正确分类的决策树的信息量为:

若以属性A作为当前样例集S的根,并设A有v个值v1,v2,…,vv,并将S分为对应的v个子集S1,S2,…,Sv,且某子集Si中含有Pi个正例和Ni个反例,规定Si的信息熵为:

规定以属性A为根进行分类的信息熵为:

(2)信息增益。ID3中规定,信息增益最大的属性A可评为分类最好属性,其定义式为:

综合式(1)~式(4),可以推知在当前样例集下,属性A的信息增益最大时,其信息熵E(A)最小。

2 一类ID3改进算法

在众多ID3改进算法中,比较典型的有两种,主要对前述公式中比较复杂的对数函数进行简化。

2.1 用等价无穷小进行代换

文献[16]根据等价无穷小理论,利用当x很小时公式ln(1+x)≈x,作如下化简:

在忽略常数的情况下,有:

文献[16]中,通过使用(省略常系数2)计算每个属性的“平均熵”,并选出其值最小的属性作为决策树的目标属性。

2.2 展开到2阶麦克劳林展开公式

文献[17]利用在x→0时,ln(1+x)在x0=1处的2阶麦克劳林展开公式x-x2/2,并在认定的条件下给出公式:

忽略常系数,给出某个属性的信息增益的简化式。

可知以上两种改进算法给出的信息增益简化式完全一致,皆为。

3 对改进算法的讨论

3.1 利用等价无穷小改进算法讨论

文献[16]通过将对数运算简化为简单的加减乘除运算以提高算法效率,然而其存在如下几个问题:

(1)只有当x足够小时,公式ln(1+x)≈x才合理,但在一个样例集及其子集中,很难保证正例pi或反例ni与正反例之和的比值足够小,因此式(5)与式(6)一般都不成立。从另一个角度看,式(5)与式(6)的简化结果也较粗略。

例如,设一个样例子集中正例pi=70、反例ni=30,则,显然不能断定式(5)与式(6)成立或合理。

(2)式(5)与式(6)不可能同时成立。假设一个样例集或一个样例子集中正例pi与正反例之和pi+ni的比值足够小,趋近于0,则显然有反例ni与正反例之和的比值接近于1;反之亦然。因此,式(5)与式(6)不可能同时成立,或者说结果较粗略,当然在此基础上得出的式(7)则更加粗略。

3.2 2阶麦克劳林展开公式改进算法讨论

从原理来看,展开到2阶麦克劳林展开公式改进算法与利用等价无穷小改进算法完全一致,都希望利用简单的加减乘除运算替代相对比较复杂的对数运算,从而提高算法效率。但展开到2阶麦克劳林展开公式改进算法存在以下问题有待商榷。

(1)此算法中ln(1+x)在x0=1处的2阶麦克劳林展开公式x-x2/2,其假定条件为,难以成立。对于ID3算法而言,一个子集中只有正例和反例,假设正例的比例极低,满足,显然不会有;反之亦然。

(2)进一步,假设能够满足这一前提条件,将在x0=1处展开的2阶麦克劳林公式在很多情况下也非常粗糙,因此无法保证。

例如,设一个样例子集中正例pi=1、反例ni=9999,则,显然这两个式子的结果相差甚远。

4 结语

ID3算法篇3

长期以来, 人们对短期负荷预测作了大量的研究, 传统的预测方法如时间序列法、多元线性回归法等[4,5], 算法比较简单、成熟;但属线性模型。现在正在研究的预测如支持向量机[6]、神经网络法[7—9]、决策树法等, 在实际中取得了较好的效果。文献[10]介绍了决策树在短期负荷预测中的应用;文献[11]结合决策树和专家系统建立了预测模型;文献[12]综合考虑了气温、湿度等气象信息及星期因素对日特征负荷的影响, 建立了决策树模型。

短期负荷预测领域虽然有了丰硕的研究成果, 但由于影响因素众多, 负荷受相关因素影响的规律不断变化, 不同地区变化规律不尽相同, 且随着分布式电源的并网, 机器学习效率急剧降低, 出现过拟合、泛化能力弱、精度低等缺陷。

本文结合决策树ID3算法, 从算法本身偏向多值属性、影响因素越多越容易发生误判两个方面进行分析, 提出改进措施, 对负荷影响规律明确、影响程度大的因素指定其在决策树的位置, 利用信息熵降计算各影响因素的相似度, 对相似历史日进行排序, 识别主导负荷变化的影响因素, 从而有效提高算法的适应性, 提高负荷预测准确率。

1 ID3算法及误判分析

决策树是以实例为基础的归纳学习算法, 从决策树根节点到叶子节点的一条路径形成一条分类规则[13]。在各种决策树学习算法中, Quinlan提出的ID3算法最具影响[14,15], 该算法是以信息论为基础, 以信息熵和信息增益度为衡量标准, 从而实现对数据的归纳分类。基本原理如下:

设S是n个数据样本的集合, 将样本集划分为m个不同的类Ci (i=1, 2, …, m) , 每个类Ci含有ni个样本, 则S划分为m个类的信息熵或期望信息为:

式 (1) 中, pi=ni/n, 为S中的样本属于第i类Ci的概率。

Sv是S中属性A的值为v的样本子集, 即Sv={s∈S|A (s) =v}, 选择A导致的信息熵为

式 (2) 中, E (Sv) 为Sv中的样本划分到各个类的信息熵。

A相对S的信息增益Gain (S, A) 为

由于影响负荷的因素众多, 且ID3算法偏向于多值属性, 决策树节点可能把负荷并不相似的历史日划分到了同一片树叶下, 从而导致误判。

1.1 属性多值引起的误判分析

影响负荷的主要因素有日类型 (如正常日和特殊日) 、气象数据 (如气温、气压、湿度等) 。ID3算法适合处理离散属性值, 在生成负荷预测模型前需要对属性进行离散化处理, 日类型有正常日和特殊日, 无需离散;温度、湿度、气压等气象信息进行离散化处理, 离散后的组数越多, 属性值越多。而ID3算法偏向多值属性, 采用ID3算法自动形成决策树时越容易发生误判。举例说明:

待预测日为5月1日, 在采用ID3算法自动生成决策树, 由于气象因素离散值较多, ID3算法会将气象因素置于决策树顶层, 忽略日类型因素, 将相似日选为4月30日, 实际上, 特殊日与正常日的负荷特征差异很大, 所以应该选择上一年的5月1日为相似日。

1.2 多影响因素引起的误判分析

上层节点对应的属性A已定, 对应的样本数据为S, 则其信息熵E (S) 也应为定值;若属性A有n个值, Si是属性A第i个值的样本子集, 下层节点的信息熵为应:

式中, , Wj为Si中的属于样本S的每一类的样本子集。

将式 (2) 代入式 (1) , 得

当n值越大时, ∣Si∣越小, 分两种情况讨论 (-npj) lg2 (pj) 的值变化趋势:

情况1:pj取值区间为 (0, 2- (1/ln2) ], (-npj) lg2 (pj) 为pj的单增函数, E (S, A) 随pj减小而减小, 则属性A的信息熵增益Gain (S, A) 随之越大;

情况2:pj取值区间为[2- (1/ln2) , 1], (-npj) lg2 (pj) 为pj的单减函数, E (S, A) 随pj减小而增大, 则属性A的信息熵增益Gain (S, A) 随之减小。

以上说明:当影响负荷预测的因素越多, 若样本子集所包含样本各类的数量比减少, 该影响因素的信息增益也就越大, ID3算法将会选择该因素作为决策树上层节点。那么, 若该因素不是影响负荷预测的主要因素, 那么将会发生误判。

同时, 决策树采用自上而下的递归方式, 上层节点决定着下层分支和节点的选择, 所以, 越靠近上层的节点对分类规则的影响越大。在短期负荷预测时, 对负荷预测越重要的影响因素应越靠近决策树的上层。

2 ID3优化算法基本模型

短期负荷预测一般分为三个阶段:一是生成决策树模型;二是利用决策树选取相似日;三是利用相似日数据进行加权、外推待预测日负荷。

2.1 决策树生成模型

由于越重要的影响因素越应靠近决策树的上层, 上层节点的错误会影响预测精度, 为了防止决策树上层节点发生误判, 本文根据实际情况指定对负荷影响规律比较明确、影响程度大的因素, 指定为决策树的前数层。

如图1所示, 基于ID3优化算法的决策树建模思路如下:

第一层节点:因为特殊日负荷变化规律与正常日明显不同, 所以需要特殊考虑, 若采取ID3自动生成, 日类型属性值只有两个, 而ID3偏向于多值属性, 随着节点增多, 误判的可能性越大, 所以该层指定为日类型, 将特殊日和正常日作为决策树的第二层。

第二层节点:该层是正常日和特殊日的下节点, 需分别考虑。预测日为正常日时, 月份不同, 气候状况相差很大, 整个社会的用电特征也有很大不同, 所以该层也进行指定, 比如在中国大部分地区, 一、二月份低温季节, 如湿冷天气, 湿度和温度较低, 会有大量的空调负荷启动。五月份气温逐渐升高, 负荷水平呈现出一个逐步上升的趋势, 九月份气温逐渐降低, 负荷水平呈现出一个逐步下降的趋势。因此, 正常日下层指定为月份。特殊日指国家法定的重大节日或假日, 一般有春节、十一、中秋、元旦等, 每个节日的所在季节不同, 负荷也呈不同特点, 所以分别将每个节日作为特殊日下层节点。

第三层节点:因为双休日负荷要低于工作日, 且负荷曲线形状不同, 所以, 月份下的节点分为日类型;节日下的节点将气象信息进行离散化, 采用ID3算法自动生成。

第四层节点:采用ID3算法自动生成。

2.2 相似日选取模型

决策树学习算法只注意到属性的选取, 而把属性取值置于次要位置。本文将信息熵作为属性的取值, 利用信息熵计算各个影响因素的相似度, 得出综合相似度, 并根据综合相似度大小对相似历史日排序, 利用历史日负荷进行加权、外推来预测待预测日负荷。

2.2.1 主要影响因素的相似度计算

划入决策树同一叶节点的数据为同一类数据, 这类数据可能不止一个。利用已建成的决策树, 选择相似的历史日, 分别计算所选历史日和待预测日每个主要因素的信息熵。将信息熵作为属性的取值, 利用信息熵计算相似度。

设有M个影响因素, N个历史日, 待预测日的第m个影响因素的信息熵为Em.p (S) , 第n个历史日的第m个影响因素的信息熵为Em.n (S) , m=1,

fmn代表第n个历史日的第m个影响因素与待预测日的相似度, 始终不大于1。

针对每种因素, 分别计算各历史日与待预测日的相似度, 获得相似度矩阵:

2.2.2 综合相似度计算

将历史日各因素的相似度相乘, 即:

该式有以下优点:

1) 与影响因素的顺序无关;调整各影响因素的顺序, 不影响综合相似度的值。由于改进决策树算法人为指定了数层, 可以避免自动形成决策树造成误判, 越重要的因素越靠近决策树顶层, 相当于改变了影响因素的排序, 综合相似度采用累乘方式, 能够有效避免因排序所带来的误差。

2) 可解决各因素的权重设定问题。调整各因素的权重值, 不影响历史日排序, 在参数自适应过程中, 能够减少自适应参数的数量, 减少计算量。

3) 可简便识别主导因素。主导因素即影响负荷的主要因素;不同的条件下, 影响负荷变化的主要因素不同, 一般存在1~2个主导因素。成熟的短期负荷预测算法应能识别各种条件下影响负荷变化的主导因素, 确保选取的相似日真正与待预测日相似。利用式 (8) 可简便识别主导因素, 判别方法如下:

当越小, 说明该因素越重要。

2.3 短期负荷预测

在进行短期负荷预测时, 需要考虑权重取值及历史日与待预测日之间的比率关系:

1) 由于各历史日与待预测日的相似程度不同, 根据各历史日的负荷数据寻找规律时, 为了防止历史日与待预测日的相似程度很低, 在各历史日排序后获得权重系数:

式 (12) 中, i表示该历史日在所有历史日与待预测日的排序中排在第i位;α为平滑系数, 是 (0, 1) 区间内的实数。

利用式 (12) , 指定平滑系数, 将历史日的负荷曲线按照一定的权重系数加权平均, 相似度高的历史日负荷曲线权重系数大, 权重系数随相似程度的排序呈指数衰减。当历史日相似程度很低时, 权重也较小, 有效防止在这样的历史日中找出的规律不符合待预测日所体现出来的规律。

2) 计算各个历史日与待预测日之间的比率关系。例如, 待预测日为春节, 根据春节前n天的历史数据, 可得出今年负荷较去年同期的负荷平均增长情况, 利用此平均增长率可得出待预测日比该去年春节的负荷应高出的百分数。

3 工程应用

本算法应用于预测我国北部地区的某城市负荷, 采用96点预测法, 对2006—2012年的负荷进行了预测, 平均准确率都超过了96.5%。其中, 对2008年12月份的负荷进行预测, 每日的准确率如表2所示, 该月份的平均准确率达到97.89%。

以2008年8月7日 (正常日) 为待预测日, 预测精度为98.6%, 负荷预测曲线与实际曲线如图2所示。

以10月1日 (特殊日) 为待预测日, 预测精度为98.6%, 负荷预测曲线与实际曲线如图3所示。

为了体现本算法的优越性, 与自动形成决策树的精度进行比较, 如图4所示, 若采用自动形成决策树预测值, 误差较大;若采用ID3优化算法之后, 预测准确率可达99.8%。

4 结束语

决策树ID3算法的一种改进篇4

ID3算法由Quinlan于1979年提出。其基本思想是:在对训练集进行分类时, 以信息熵为度量, 用于决策树节点的属性选择, 每次优先选取信息量最多的属性对数据进行划分, 以构造一颗熵值下降最快的决策树, 每个叶子节点对应的实例集中的实例属于同一类。

设样本数据集T有s个样本, 每个样本都有u个评估属性kA, m个类别。评估属性划分T成v个子集, 其中jT中包含sj样本, 属于第iC类的样本数为sij (i=1, 2, ...m) 。则有:子集Tj的信息熵:

属性Ak的信息熵为:信息增益为:Gain (Ak) =I (T) -E (Ak)

2 ID3算法的优点和不足

优点:运用信息论知识选择属性, 理论清晰;容易生成IF-THEN语句;对于离散型样本数据处理功能强;ID3自顶向下搜索, 节省系统资源, 计算时间与样本大小。

不足:ID3算法在选择分类属性时往往选择了取值较多的属性;ID3算法只能处理离散型数据, 若分析必须先进行离散化;用ID3算法创建决策树时必须知道所有内部节点。

3 ID3算法的改进

定理1:若函数f (x) 在[a, b]上连续, 在 (a, b) 内有一阶、二阶导数, 并且

在 (a, b) 上, 若f' (x) <0, 则f (x) 在[a, b]上是凸函数;

性质:若f (x) 在区间I上是凸函数,

λ1, λ2, ..., λn>0, 则有:λ1f (x 1) +...+λnf (x n) ≤f (λ1 x1+...+λn xn)

3.1 算法改进的实现

pi表示数据属于类Ci的概率, 在 (0, 1) 上任取p1, p2有p1+p2=1, p1-p2=△p→0, 因为log2 p函数在 (0, 1]上连续, 由定理1可知log2 p函数在其连续区间上是凸函数。

由凸函数性质计算得:

假设样本数据集T有s个样本, u个评估属性m个类别属性。评估属性kA划T成v个子集Tj含sj样本, 第iC类的样本数为sij。所以子集的信息熵为:

属性的信息熵是:信息增益为:Gain (Ak) =I (T) -E (Ak)

3.2 改进算法的应用

表一为某公司调查的顾客数据统计表.通过数据挖掘旨在回答“谁在买电脑”这一问题。

第1步:决策属性的信息熵

第2步:计算条件属性的熵

1) 年龄分三组:老、中、青。青年384人, 正例128人, 反例256人;中年256人, 正例256人, 反例0人;老年252人, 正例125, 反例127人。

老年:I (125, 127) =0.9157所以, E (年龄) =0.6877;G (年龄) =0.9537-0.6877=0.2660;

2) E (收入) =0.9361 G (收入信息增益) =0.9537-0.9361=0.0176;

3) E (学生) =0.7811 G (年龄信息增益) =0.9537-0.7811=0.1726;

4) E (信誉) =0.9048 G (信誉信息增益) =0.9537-0.9048=0.0453。

第3步:计算选择节点。由上可知“年龄”具有最高的信息增益, 选择“年龄”为测试属性。

第4步:递归建树算法, 分别对各个子集分析, 计算选择分支的测试属性。

1) 年龄=“青年”的子集有:选择学生为测试属性对子集进行再划分;

2) 对于年龄=“中年”, 数据都属于同一类, 自然形成树叶;

一种基于ID3决策树的优化算法篇5

关键词：信息增益,分枝合并,属性优先关联度,条件概率,健壮性

1引言

自决策树归纳学习算法产生以来, 经典算法和改进算法不断被研究和应用, 没有一种算法能完全替代其他的算法, 经典的ID3算法[1], 因理论清晰, 描述简单, 分类速度快等优点得到广泛推介和使用。当然, 针对决策树算法的研究和改进仍未终止过, 大多都把注意力集中在属性的选择上, 因为属性选取决定着算法的速度和精度, 这是决策树算法性能评价中四个关键指标的两个。

随着决策树算法的深入研究和应用领域的扩展, 为了改善决策树的容噪和表达能力, 也即决策树的健壮性和简洁性。有人对SLIQ、SPRINT等高层次算法, 通过设定过滤或停止的阀值条件提高决策树的容噪和表达能力。

实际上, 将分枝合并技术和属性按优先度选择的方法结合起来, 对经典算法ID3进行改进, 同样可以实现决策树的健壮性和简洁性, 而计算量并没有明显地增加。

2 ID3算法思想

ID3的算法核心思想是在决策树中各层分枝节点上选择属性, 用信息增益作为属性选择标准, 使得在每一非叶子节点进行测试时, 能获得关于被测试例子最大的类别信息, 使用该属性将样本集划分成子集后, 系统的信息熵值最小。期望该非叶子节点到达各后代叶子节点的平均路径最短, 使生成的决策树平均深度较小[2]。信息增益的计算公式如下:

设训练集S有m个类别, 用Ci表示类别标号, 对应记录数为Si (i=1, 2, …, m) , 则集合S中属性A的信息熵为:

设测试属性A具有a1, a2, …, av等v个不同的属性值, 集合S被分成v个子集Sj (j=1, 2, …, v) , 则Sj包含集合S中值为aj的记录。用Sij表示Sj中包含类别Ci的记录数, 则测试属性A的期望信息熵为:

于是以测试属性A为分割点的信息增益为:

3 ID3算法建树过程及存在不足

按照上述的公式和步骤, 以银行信用卡交易数据为例, 如表1所示, 决策树构建的过程如下:

第一步, 计算各属性的信息增益, 如年龄的信息增益计算过程为:

E (年龄) =5/14*I (2, 3) +4/14*I (4, 0) +5/14*I (3, 2) =0.694;

Gain (年龄) =I (9, 5) -E (年龄) =0.246;

同理, Gain (收入) =0.029, Gain (学生) =0.151, Gain (地域) =0.048。

第二步, 比较和选取具有最大信息增益值的属性作为分割点, 于是用年龄将根节点分割为三个分枝。

第三步, 对各个分枝重复上述步骤, 直到满足停止条件。生成决策树如图1所示。

表1信用卡以往消费数据属性表

从上述过程看, ID3算法具有理论清晰、计算便利等优点, 但也有存在一些不足:

1 它是一种单变量决策树算法, 忽略了属性间的相互联系, 虽然理论清晰, 方法简单, 但表达复杂概念时非常困难。

2 偏向于选择取值较多的属性, 而属性值较多的属性并不总是重要的属性[3]。

3不能处理属性值空缺的样本。

4对噪声较为敏感, 包括训练集中的特征取值错和类别给错。

4基于分枝合并的策略和ID3算法优化

4.1 ID3算法的优化方法

针对ID3算法多值偏向的问题, 可以改进属性选取的标准, 计算各个属性加权后的信息增益, 以平衡属性值较多导致该属性信息增益较大的问题。另外, 减少和合并树的分枝, 提高ID3算法的稳定性。

4.2基于分枝合并的策略[4]

在对属性A进行分割时, 通过计算各属性值在属性类别的条件概率, 决定是否合并相关的分枝, 以此减少无意义和无效的分割。主要思想是:假定属性A作为分裂节点, 属性取值为v1, v2, L, vn, 决策类别属性为P E和NE两类。则可计算出vi在PE和NE上的条件概率为prob (A=vi|PE) 和prob (A=vi|NE) , 选择的类别记为Ci, 并且有如果prob (A=vi|PE) ≥prob (A=vi|NE) , Ci=PE;否则Ci=NE。然后将A的各个取值对应的分枝按照下述规则进行合并:对于A的两个取值vi和vj (i≠j) , 如果Ci=Cj那么vi和vj就可聚为一类, 将对应的分枝进行合并。

4.3基于分枝合并的属性优先关联度ID3算法

针对ID3算法偏向于选择取值较多的属性和对噪声较为敏感的问题, 本文改变属性选取的计算公式, 同时利用属性优先关联度[5]平衡各属性取值的分布, 并在决策树生成过程中按预测概率进行分枝合并, 即基于分枝合并的属性优先关联度ID3算法, 简称P-AID3算法。主要做法是:

1将信息熵、期望信息熵和信息增益的计算公式 (1) 、 (2) 和 (3) 改为:

其中a为属性优先关联度, 需要专家知识或业务经验事先设定, m为属性的权值, 即属性的分枝个数。

2求最小信息增益作为属性分割的标准, 即信息增益的余值, 以减少噪音对决策树的影响。

3 P-AID3算法描述

A.为样本数据选定属性优先值a, 并确定权值m的取值;

B.用 (1-4) 、 (1-5) 、 (1-6) 等改进公式计算所有候选属性的信息增益;

C.用公式 (1-7) 计算各属性信息增益的余值, 选取具有最小信息增益的属性A作为分裂节点;

D.对选定的测试属性A的每个可能值, 创建一个分支, 并据此将样本数据划分到各个分支中;

E.对于A的每个属性值, 计算在各个分枝上类别属性的条件概率, 按照类属概率 (预测概率) 相同的原则对非叶子节点的分枝进行合并;

F.算法递归的使用上述同样的过程, 形成每个划分上的子样本决策树。一旦一个属性被选作为一个节点的测试属性, 就不必再考虑该节点的任何后代, 仅当下列条件之一成立时停止:

a.给定节点上的所有样本数据属于同一类, 即所有记录类标号属性的取值相同;

b.没有剩余候选属性可以用来进一步划分样本;c.分裂后, 某分支没有样本记录。

5 P-AID3算法建树过程和优缺点

5.1 P-AID3算法建树过程

使用表1中的数据表构建P-AID3决策树, 用P代表消费 (是) , N代表不消费 (否) , 具体过程如下:

1设定属性优先关联度的值, 例设属性收入、年龄、常住地、稳定性等属性优先关联度a的值分别为0.1、0.3、0.5、0.7, a的取值越小, 重要性越高, m的权值为3、3、2、2。

2按照上述改进的公式, 计算各个属性信息增益的余值, 有:5 根据预测概率的计算, 合并分枝。由于C高=C中=P, 则将收入为高和中的属性值所在的分枝进行合并, 而属性值为低所在的分枝保持不变。

3选定具有最小信息增益的余值的属性作为分裂节点, 通过比较发现, 可选取收入作为分裂节点。

6重复上述过程, 直到算法终止条件满足为止。构建的决策树如图2所示:

5.2 P-AID3算法的优缺点

通过图1与图2的比较发现, P-AID3算法具有以下优点:

1设置的属性优先值a平衡了属性取值分布, 有效避免了ID3算法的多值偏向问题。同时减少了对数的计算次数, 生成树的复杂度降低了。

2 P-AID3算法能够产生更多的决策规则, 并提高了决策树的分类精度和健壮性。

3由于合并了无意义和无效的分枝, 提高了决策树的逻辑表达能力。

同时, P-AID3算法中属性优先值a依靠专家知识和业务经验来设置, 找到最优的解需要较多的测试和实验, 随着a的变化, 生成的决策树及决策规则有可能完全不同。另外, 由于行业领域和专家知识的限制, P-AID3算法的移植应用较为困难。

6 P-AID3算法实验分析

这里取信用卡消费数据集的26条记录为例验证P-AID3算法的有效性, 把整个数据集随机分为训练集和测试集, 用训练集构造决策树模型, 通过创建的模型在测试集上进行预测, 从而得出分类准确率。实验采用SAS9.12软件实现ID3算法构建决策树, 通过测试集进行验证。P-AID3算法通VC++.net开发工具来实现。实验结果如表2和表3所示。

P-AID3算法的分类准确率并没有降低, 对不同的训练集反而有所提高, 平均准确率要高于ID3算法。与ID3算法构造的决策树模型相比, AID3在“根节点数量”, “叶节点数量”, “树的高度”和“规则数量”等方面与ID3有一定的相似性, 比ID3算法构造的决策树模型要健壮[6]。实验结果充分说明了P-AID3决策树模型不仅克服了多

7结束语

P-AID3算法是一个多技术方法相结合的决策树算法, 利用属性优先度的选择标准和分枝合并的策略, 融合了不同方法的优点, 生成的决策树在分类准确度和健壮性较ID3算法有很大的改善。但是, 由于新算法是不同方法的组合, 若不能确定各个候选属性的优先度, 则分类精度可能达不到业务需求, 同时分枝合并的运算量也会增加。因此, 如何快速有效地确定各个候选属性的优先度将是下一步研究的重点。

参考文献

[1]J.R.QUINLAN.Induction of decision trees[M].Ma-chine Learning 1986, 1.

[2]刘小虎, 李生.决策树的优化算法[J].软件学报.1998, 9 (10) :797-800.

[3]邹永贵, 范程华.基于属性重要度的ID3改进算法[J].计算机应用.2008, B06 (28) :144-145.

[4]洪家荣, 丁明峰.一种新的决策树归纳学习算法[J].计算机学报.1995, 18 (6) :470-474.

[5]韩松来, 张辉, 周华平.关于关联度函数的决策树分类算法[J].计算机应用, 2005, 25 (11) :2655-2657.

ID3算法篇6

数据挖掘主要是从大规模数据库的数据中抽取有效的、隐含的、以前未知的、有潜在实用价值的信息。数据挖掘的关键是在训练数据中发现事实,以测试数据作为检验和修正理论的依据,把知识应用到数据中[1]。其中决策树算法是数据挖掘中的一种重要算法,在分类预测方面得到了广泛的应用[2,3,4],它的目的是根据某个新记录的属性,将其分派到预先定义好的若干类中的一个,并为其添加一个字段以标识该记录的类别。决策树算法沿用的是传统的机器学习算法,处理大数据量数据时,存在三点不足:①基于主存,处理的数据量较小;②算法通常需要将数据以文件形式提供,在进行数据挖掘前需要进行数据转换工作;③面对大量数据,没有充分利用数据库技术所具有的对数据操作的优势,文献[5]对该问题进行了研究。本文在深入研究ID3算法的基础上,结合结构化查询语言SQL具有强大的分组、统计功能,提出一种基于SQL语句的ID3改进算法,通过SQL语句直接对保存在数据库中的数据表进行分组查询,计算测试属性的条件熵,并采用C++面向对象语言实现,充分利用了SQL语句的高效性和C++语言的灵活性,高效地实现了大量数据的分类,工程实践中易于实现。

1 基本概念

决策树学习是以样本为基础的归纳学习方法,表现形式类似树结构,在决策树的内部结点进行属性值测试,并根据属性值判断由该结点引出的分支,在决策树的叶结点得到结论。ID3 是Quinlan于1979年提出的著名的决策树算法。ID3算法的基本策略如下:

(1) 树以代表整个训练样本、全部条件属性作为测试属性集的单个结点开始。

(2) 如果样本都在同一个类,则该结点成为树叶,并用该类标号。

(3)否则,计算每个测试属性的信息增益,选取信息增益最大的属性将样本分类。该属性成为该结点创建分支的判定属性。

(4)对判定属性的每个已知值,创建当前结点的子结点,并根据属性值划分样本,同时将父结点的测试属性集移去判定属性,作为各子结点的测试属性集。

(5)算法使用同样的过程,递归地形成每个结点的子结点。

(6)递归生成子结点仅当下列条件之一成立时停止:①当前结点的所有样本属于同一类;②测试属性集为空,使用多数表决的方法将该结点转换为叶结点;③分支在某一个属性值上没有样本,使用多数表决的方法创建一个叶结点。

2 基于SQL语句的ID3算法的实现方法

2.1 数据结构设计

该算法实现涉及两个问题:①树表示方法,②结点表示方法。树采用孩子兄弟表示法存储,设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟。结点包含测试属性集,样本子集、第一个孩子结点、右兄弟结点,若是叶子,还有类别。其中测试属性集合是在父结点的该属性值基础上与当前判定属性的差集,采用C++ STL中的vector容器存储;样本子集是样本数据表中记录的子集,是将当前结点至根结点所经结点构成的属性名=属性值带入SQL 1 中L参数的查询结果。

2.2 条件熵计算方法

class表示分类属性,计算结点N的测试属性集中某属性c的条件熵tjs:

将数据表中满足N.where 的记录行,按照属性c和分类属性class进行分组统计,即SQL为“select c,class,count(*) from 数据表 where N.where group by c,class order by c,class”,查询结果存入二维数组 r[m][n],m为属性c的取值个数,n为分类属性class取值个数,数组r的每行元素的和存入一维数组s[m]中。计算过程如下:

2.3 递归函数BuildChildNode

基于数据库查询的决策树算法,继承了原ID3算法思路,通过2.2的方法计算测试属性的条件熵。在子树生成过程中,可以采用深度优先和广度优先生成子树的方法实现。递归函数BuildChildNode如下:

输入:存储了测试属性集、记录行筛选条件(无)的根结点pNode。

输出:以pNode为根结点孩子兄弟表示法存储的决策树。

算法描述:

3 算法应用

文献[6]给出了一个可能带有噪音的数据集合。它有四个条件属性:outlook,temperature,humidity,windy。被分成两类,p与n,分别为正例与反例。采用本文提出的算法对该数据集合构造决策树。数据见表1.

决策树构造过程:

①定义决策树的根结点,并初始化。

Node root;

root.attrs={outlook,temperature,humidity,windy}

root.where=NULL;

设参数K表示待测试属性,class表示分类属性,tb_PlayTennis为保存数据集的数据库表名,L为记录筛选条件。三个常用SQL语句如下:

select K,class,count(*) from tb_PlayTennis where L group by K,class order by K,class (SQL 2)

当L为NULL时,SQL 1转变为:

select K,class,count(*) from tb_PlayTennis group by K,class order by K,class (SQL 3)

select * from tb_PlayTennis (SQL 4)

②以root为参数调用递归函数BuildChildNode,即BuildChildNode(& root),

(1) 此时root.where为NULL,将Outlook带入SQL 3中的参数K,将查询结果见表2。

根据2.2的算法,计算得出:H(class,Outlook)=0.552 8

同理,将Temperature、Humidity、Windy分别带入SQL 3中的参数K,依次得出:

H(class,Temperature)=0.917 2,

H(class,Humidity)=0.918 3,

H(class,Windy)=1.00。

②选取Outlook作为分支属性,各个子节点的测试属性集为{temperature,humidity,windy},根据其三个取值sunny、overcast、rain开始生成子节点,按照深度优先的策略构造决策树,

(1)首先生成实例集为将Outlook=' sunny '代入SQL 4中参数L所形成的记录集对应的子结点N2,由于N2的所有记录的class属性值为p,所以标记N2为叶结点,并从递归算法中返回;

(2)同理,当outlook='overcast' 时生成结点N3,各测试属性的条件熵为:

H(class,temperature)=0.444 4,

H(class,humidity)=0.000 0,

H(class,windy)=0.972 8。

选取属性humidity作为分支属性,根据其两个属性值high、normal生成子结点,首先生成实例集为outlook='overcast' and humidity='high'对应的子结点N4,此时class属性值全部为n,从递归函数中返回,然后生成实例集为 outlook='overcast' and humidity='normal' 对应的子结点N5,此时class属性值全部为p,从递归函数中返回;

(3)当outlook='rain' 时,同理生成其子树。这里不再一步一步求解,结果见图1。

4 总结

本文首先介绍了决策树算法的基本概念,针对ID3算法在处理大数据时存在的不足,通过引入数据库查询语句,给出了条件熵计算方法。进而提出ID3算法的一种新的实现方法。并在递归算法中给出了深度优先和广度优先建树方案,解决了ID3算法与数据库继承性差的问题。最后通过实例分析,证明了该算法的正确性。

摘要：ID3算法沿用的是机器学习算法,与数据库集成性差。提出一种基于SQL语句的ID3改进算法。通过SQL语句直接对保存在数据库中的数据表进行分组查询,计算测试属性的条件熵,并给出深度优先和广度优先生成子树的递归算法。实验证明,改进的ID3算法充分利用了SQL的高效性和C++语言的灵活性,降低了算法实现难度,高效实现大量数据的分类。

关键词：ID3,决策树,信息熵,SQL语句

参考文献

[1]李雄飞,李军.数据挖掘与知识发现.北京:高等教育出版社,2003:2—3

[2]王英,刘维亭.决策树算法在电网报警信息处理中的应用.科学技术与工程,2011;11(30):7375—7378

[3]宋晖,张良均.C4.5决策树法在空气质量评价中的应用.科学技术与工程,2011;11(20):4848—4850

[4]丁胜祥,董增川,张莉.基于决策树算法的洪水预报模型.水力发电,2011;37(7):8—12

[5]杨一展,李小平,段霞霞.一种基于数据库查询的改进的决策树算法.计算机工程与应用,2008;44(15):148—150

ID3算法篇7

腐蚀检测系统是利用管道检测技术采集石油管道中的腐蚀数据, 对其进行科学的分析, 找出腐蚀数据内在的联系, 并确定造成管道腐蚀的原因。以往对腐蚀数据的处理方法大多停留在简单的录入、查询、统计等操作阶段, 大量的腐蚀数据没有得到更有效的利用, 造成“丰富的数据, 贫乏的知识”这一尴尬现象。决策树算法中的ID3算法计算速度较快、容易实现, 并且适用于处理规模较大的学习问题。

1 ID3算法原理

ID3算法的核心是在决策树的各级结点上, 使用信息增益方法作为类别选择标准, 来帮助确定生成每个结点时所应采用的合适类别。这样就可以选择具有最高信息增益的类别作为当前结点的测试类别, 以便使用该类别所划分获得的训练样本子集进行分类所需信息达到最小。

1.1 ID3算法

设V为一个包含v个样本的集合, 类别分别可以取n个不同的值, 对应于n个不同的类别ci, i∈{1, 2, ..., n}。设vi为类别ci中的样本数, 则对一个给定数据对象进行分类所需的信息量为:

其中, 为任一个数据对象属于类别ci的概率。

如果选择A为测试类别, A有s个不同的值{a1, a2, ..., as}, A将集合V划分为s个子集{V1, V2, ..., Vs}, 其中Vj包含了V集合中类别A取aj值的数据样本。设vij为子集Vj中属于ci的样本数。则利用A来划分当前样本集合所需要的信息 (熵) 计算如下:

其中, 项被当作第j个子集的权值, 它是由所有子集中类别A取aj值的样本数之和除以V集合中的样本总数。E (A) 计算结果越小, 就表示其子集划分结果越好。而对给定的子集Vj, 其信息为:

其中, 为Vj中任一个数据样本属于类别ci的概率。

这样利用类别A对当前分支结点进行相应样本集合划分所得到的信息增益为:

计算每个类别的信息增益, 然后选择增益最大 (最小熵) 的那个类别作为给定集合的测试类别, 并由此产生相应的分支结点。

通过以上对ID3算法的分析发现, ID3算法计算速度较快、容易实现并且适用于处理规模较大的学习问题, 同时得到的决策树是较为优化的形式。但是, 其仍然存在以下问题:ID3算法较倾向于选择取值较多的类别, 但取值较多的类别不一定总是最优的类别, 即按照使熵值最小的原则被ID3算法列为应该首先判断的类别在现实情况中却并不那么重要;可能会收敛于局部最优解而丢失全局最优解。

1.2 改进ID3算法

针对ID3算法较倾向于选择取值较多的类别, 给出以下改进方案:

当条件熵中第j个子集的权值变小时, 该类别的条件熵也随之变小, 导致该类别的信息增益变大。所以, 本文用作为调节参数, 将其设定为L, 即:

调节该类别的条件熵, 使该类别的条件熵变大, 从而使该属性的信息增益变小, 提升其它类别的信息增益。

则改进后集合V中的第j个子集的权值Vj为:

改进的ID3算法是针对规则生成方法即类别选择标准算法进行改进, 调节信息较大类别的权值, 加强重要类别的信息熵, 降低非重要类别的信息熵, 从而使取值较多类别的信息增益减少, 取值较少类别的信息增益增大, 使生成决策树时数量少的数据元组不会被淹没, 最终使决策树减少对取值较多类别的依赖性, 从而尽可能地减少大数据掩盖小数据的现象发生。对式 (2) 进行改进后为:

因为改进ID3算法引入调节参数是针对规则生成方法 (即类别选择标准) 进行了改进, 在使用调节参数时应注意以下几个方面:

(1) 引入调节参数需要结合领域知识和实际情况。

(2) 在大多数类别的数据量较大, 而个别类别的数据量较小, 并且人们对这部分类别的重要性认识不足时, 对这部分类别加入调节参数, 调节这部分类别的重要性, 使其不会出现大数据掩盖小数据的现象。

(3) 决策中的类别应结合领域知识, 根据实际情况加入调节参数, 不能盲目地改变类别参数, 但可以逐步进行改进, 否则会因人为因素影响决策效果。

与其它ID3算法的改进相类似, 本文对ID3算法的改进只是在传统ID3算法的基础上略加改进, 导致改进ID3算法又回归到传统的ID3算法, 但改进ID3算法在解决某些领域中大量数据掩盖小量数据的重要性问题上具有一定的优势。

2 改进ID3算法在管道腐蚀检测系统中的应用研究

2.1 改进的ID3算法在管道腐蚀检测系统中的研究过程

改进的ID3算法在管道腐蚀检测系统中的研究过程如下:

(1) 确定数据挖掘对象和目标。能够清晰地定义问题, 认清数据挖掘的对象和目的是数据挖掘的第一步, 也是重要的一步, 挖掘的最后结果不可预测, 但要探索的问题是可预见的。

(2) 数据采集。需要获得管道信息、腐蚀信息和石油成分信息。其中腐蚀信息通过电阻探针采集、电化学探针采集得到, 管道信息和石油成分信息由炼油厂石油信息表和管道信息表获得。部分数据可以直接获得, 部分数据需要进行计算获得。

(3) 数据预处理。将采集到的所有腐蚀数据进行数据清理, 去除噪声, 更改不一致的数据, 将所有数据转换成统一数据格式。根据研究目的进行数据变换, 将数据信息集成并转换为一个分析数据模型, 数据模型是针对算法而准备的, 不同的算法可能需要不同的分析数据模型。此步骤工作量较大, 占据时间较多。

(4) 数据分类挖掘。分类挖掘的目的是为了建立一个分类模型。选择一个合适的挖掘算法, 对经过转换的数据进行分类挖掘, 找出分类规则。

(5) 规则提取。结合实际情况, 利用数据分类挖掘得到的分类对管道腐蚀情况进行解释和评估。

2.2 算法应用

本文选取腐蚀检测信息表中2009年1-11月的数据, 共88 703条, 作为训练样本数据集。腐蚀检测信息表中的数据为连续型, 须对其离散化才能应用ID3算法处理腐蚀数据。连续类别值离散化就是在特定连续类别的值域范围内设定若干个离散化划分点, 将类别的值域范围划分为一些离散化区间, 最后用不同的符号或整数值代表落在每个子区间中的类别值。划分后的腐蚀检测信息表如表1。

用改进后的ID3算法构建决策树。生成的决策树结构如图1, 其中正例为腐蚀不严重, 反例为腐蚀严重。

由生成的决策树中可以看出, 从根节点到每个叶子节点的路径形成的部分分类规则如下:

IF年腐蚀率=高THEN腐蚀严重

IF年腐蚀率=中, 盐含量=高THEN腐蚀严重

IF年腐蚀率=中, 盐含量=中, 硫含量=高THEN腐蚀严重

IF年腐蚀率=中, 盐含量=中, 硫含量=中, 酸含量=高THEN腐蚀严重

IF年腐蚀率=中, 盐含量=中, 硫含量=中, 酸含量=中THEN腐蚀严重

IF年腐蚀率=中, 盐含量=中, 硫含量=中, 酸含量=低, 管道材质=优质钢THEN腐蚀不严重

IF年腐蚀率=中, 盐含量=中, 硫含量=中, 酸含量=低, 管道材质=普通钢THEN腐蚀不严重

从上述规则中可以看出, 年腐蚀率的大小与管道腐蚀的严重与否关系极大, 通过年腐蚀率的大小可以间接知道管道腐蚀的严重与否。但在实际操作中, 只知道管道的年腐蚀率与腐蚀深度之间的关系是不够的, 还要知道是什么客观因素 (如硫、酸、盐、温度、材质) 导致管道腐蚀严重 (或不严重) , 从而可以有针对性地对已造成的腐蚀进行防护。所以, 需要调节年腐蚀率的权值, 提升其它类别 (如硫、酸、盐、温度、材质) 的信息熵, 使年腐蚀率的信息增益减少, 使其它类别的信息增益增大, 从而使决策树其它类别的数据元组不会被淹没, 最终使决策树减少对年腐蚀率的依赖。所以, 可以采用改进的ID3算法, 对腐蚀检测信息表中的数据构建决策树。生成的决策树结构如图2, 其中正例为腐蚀不严重, 反例为腐蚀严重。

2.3 分类规则测试

将腐蚀检测信息表中2009年12月的腐蚀数据作为测试数据, 测试数据共6143条, 测试得到分类规则, 按照得到的分类规则进行分类, 将得到的分类结果与测试数据的实际类别进行核对, 最终有5 181条数据分类正确, 准确率达到84%。由此可见, 分类规则具有较高的可信度。

3 结语

ID3算法计算速度较快、容易实现并且适用于处理规模较大的学习问题, 针对其存在倾向于选择取值较多的类别、可能会收敛于局部最优解而丢失全局最优解的情况, 本文提出一种改进的ID3算法, 并将其应用于管道腐蚀检测系统, 以处理采集到的大量数据。经测试, 分类规则具有较高的可信度。

摘要：ID3算法计算速度较快、容易实现并且适用于处理规模较大的学习问题, 但其较倾向于选择取值较多的类别, 从而导致丢失全局最优解。提出一种改进的ID3算法, 并将其应用于管道腐蚀检测系统中, 研究结果表明, 改进后的算法具有较高的可信度。

关键词：决策树,ID3算法,信息增益,管道腐蚀检测系统

参考文献

[1]宋健.基于数据挖掘方法的热轧带钢表面质量缺陷分析[D].上海:上海交通大学, 2008.

[2]李海琼.数据挖掘技术在辽宁大学生就业辅助决策分析系统中的研究与应用[D].沈阳:沈阳工业大学, 2009.

[3]李国安.基于数据挖掘的垃圾邮件过滤技术研究[D].呼和浩特:内蒙古大学, 2008.

【ID3算法】推荐阅读：

扩展算法07-16