第26卷第2期 水电能源科学 Vol26No.2 2008年4月 Water Resources and Pow er Apr.2008 文章编号：10007709(200802-012905 决策树中ID3算法与C4.5算法分析与比较 李会胡笑梅 (安徽财经大学信息工程学院.安徽蚌埠233041 摘要：论述了决策树表示方法及D3、C4.5决策树学习算法，特别对决策属性的选取法则进行了说明。通过 实例解析D3、C4.5算法实现，结果表明C4.5算法在决策树分类效率和直观性都得到了提高。 关键词：数据挖掘：决策树：D3算法：C4.5算法 中图分类号：TP301.6 文献标志码：A 1 概述 2ID3与C4.5算法简介 决策树方法是挖掘分类规则的有效方法，通 2.1ID3算法 常包括两个部分：①树的生成，开始时所有的数据 D3算法通过对一个训练例集进行学习生成 都在根节点，然后根据设定的标准选择测试属性 一棵决策树，训练例集中的每一个例子都组织成 用不同的测试属性递归进行数据分割。②树的修 属性一属性值对的形式。假设一个例子仅属于正 剪，就是除去一些可能是噪音或异常的数据。基 例（符合被学习目标概念的例子）或反例（不符合 于信息熵的D3算法、C4.5算法都能有效地生成 目标概念的例子两种分类之一，例子的所有属性 决策树，建决策树的关键在于建立分支时对记录 都为离散属性。对于每个训练例集E,如果正例 字段不同取值的选择。选择不同的字段值使划分 的比例为P+,则反例比例就为P-=1-P,嫡 出来的记录子集不同，影响决策树生长的快慢及 的公式为： 决策树的结构，从而可寻找到规则信息的优劣。 Entropy(E.)=-P.log2P.-P-log2P 可见，决策树算法的技术难点就是选择一个好的 (这里约定log20=0) (1 分支取值。利用好的取值产生分支可加快决策树 若用属性A将训练例集E,分组，Entropy(E,) 的生长，更重要是产生好结构的决策树，并可得到 将会降低，新的期望信息量设为： 较好的规则信息。相反，若根据一个差的取值产 New_Entropy(E,A)= 生分支，不但减慢决策树的生长速度，而且使产生 的决策树分支过细、结构差，从而难以发现有用的 e,A1611B.1)Entropy(E.)(② 规则信息。 A相对于E.的信息赢取Gain(E,A),即 随省训练样本集中样本个数的不断增多（即 Entropy(E)降低的数量，信息赢取越大的属性对 样本集规模不断扩大)，训练样本集在主存中换进 训练例集越有利： 换出就耗费了大量的时间，严重影响了算法效率。 Gain(E,A)=Entropy(E.)-New_Entropy(E,A) 因此使算法能有效处理大规模的训练样本集已成 (3) 为决策树算法研究的一个重要问题，也是目前国 2.2C4.5算法 内对决策树算法研究的热点。本文结合实例数 在C4.5的决策树中，每个节点都保存了可 据.介绍了ID3算法与C4.5算法的实现过程，并 用于计算E值属性的信息，这些信息由属性的每 进行了比较分析。 个取值所对应的正例与反例计数组成。根据放在 收稿日期：200？0910，修回日期：20071225 基金项目：安徽财经大学教学研究基金资助项目(ACJY YB2200816) 作者简介：李会(1983)，女，讲师，研究方向为数据挖掘及数据仓库，Emai止ihuianny@126.om 通讯作者；1胡笑梅(966女副教授，研究克向为信息管理及信息支持F用ik hymein吧ei@yahoo.mm:vww.cmki.net
第26卷第2期 2 0 0 8 年 4 月 水 电 能 源 科 学 Water Resour ces and Pow er Vo l. 26 No . 2 Apr. 2 0 0 8 文章编号: 1000- 7709( 2008) 02-0129- 05 决策树中 ID3 算法与 C4. 5 算法分析与比较 李 会 胡笑梅 ( 安徽财经大学 信息工程学院, 安徽 蚌埠 233041) 摘要: 论述了决策树表示方法及 ID3、C4. 5 决策树学习算法, 特别对决策属性的选取法则进行了说明。通过 实例解析 ID3、C4. 5 算法实现, 结果表明 C4. 5 算法在决策树分类效率和直观性都得到了提高。 关键词: 数据挖掘; 决策树 ; ID3 算法; C4. 5 算法 中图分类号: T P301. 6 文献标志码: A 收稿日期: 2007- 09- 10, 修回日期: 2007- 12- 25 基金项目: 安徽财经大学教学研究基金资助项目 ( ACJYYB200816) 作者简介: 李会( 1983-) , 女, 讲师, 研究方向为数据挖掘及数据仓库, E-mail: lihuianny@ 126. com 通讯作者: 胡笑梅( 1966- ) , 女, 副教授, 研究方向为信息管理及信息支持, E-mail: hxmeimei@ y ahoo. com. cn 1 概述 决策树方法是挖掘分类规则的有效方法, 通 常包括两个部分: ¹ 树的生成, 开始时所有的数据 都在根节点, 然后根据设定的标准选择测试属性, 用不同的测试属性递归进行数据分割。 º 树的修 剪, 就是除去一些可能是噪音或异常的数据。基 于信息熵的 ID3 算法、C4. 5 算法都能有效地生成 决策树, 建决策树的关键在于建立分支时对记录 字段不同取值的选择。选择不同的字段值使划分 出来的记录子集不同, 影响决策树生长的快慢及 决策树的结构, 从而可寻找到规则信息的优劣。 可见, 决策树算法的技术难点就是选择一个好的 分支取值。利用好的取值产生分支可加快决策树 的生长, 更重要是产生好结构的决策树, 并可得到 较好的规则信息。相反, 若根据一个差的取值产 生分支, 不但减慢决策树的生长速度, 而且使产生 的决策树分支过细、结构差, 从而难以发现有用的 规则信息。 随着训练样本集中样本个数的不断增多( 即 样本集规模不断扩大) , 训练样本集在主存中换进 换出就耗费了大量的时间, 严重影响了算法效率。 因此使算法能有效处理大规模的训练样本集已成 为决策树算法研究的一个重要问题, 也是目前国 内对决策树算法研究的热点。本文结合实例数 据, 介绍了 ID3 算法与 C4. 5 算法的实现过程, 并 进行了比较分析。 2 ID3 与 C4. 5 算法简介 2. 1 ID3 算法 ID3 算法通过对一个训练例集进行学习生成 一棵决策树, 训练例集中的每一个例子都组织成 属性 ) 属性值对的形式。假设一个例子仅属于正 例( 符合被学习目标概念的例子) 或反例( 不符合 目标概念的例子) 两种分类之一, 例子的所有属性 都为离散属性。对于每个训练例集 Es, 如果正例 的比例为 P + , 则反例比例就为 P- = 1- P+ , 熵 的公式为: Entropy(E s) = - P + lo g2P + - P - log 2P- (这里约定 log2 0= 0) ( 1) 若用属性 A 将训练例集Es 分组, Entropy(Es ) 将会降低, 新的期望信息量设为: New _Entropy(E s i , A ) = i I VEalue( A ) (| Es i | / | E s | )Entropy(Es i ) ( 2) A 相对于 E s 的信息赢取 Gain (E s, A ) , 即 Entropy(E s) 降低的数量, 信息赢取越大的属性对 训练例集越有利: Gain(Es, A)= Entropy(Es) - New_Entropy(Es i , A) ( 3) 2. 2 C4. 5 算法 在 C4. 5 的决策树中, 每个节点都保存了可 用于计算 E 值属性的信息, 这些信息由属性的每 个取值所对应的正例与反例计数组成。根据放在
·130 水电能源科学 208年 节点的信息就可判断哪个属性的训练例集E.值 正例，不舒适时为反例。 一开始全部包含在根节点 最小.从而确定当前用某个屈性讲行划分。C45 中，为找当前的最住划分属性先必须根据式1)计 算法属性洗择基出品基干伸生成的决簧树中节点 算训练例集E,的熵值。节点的熵值为： 所含的信息熵最小。嫡越小则记录集合的无序性 EntropyEs)=-9log2(9/20)/20 越小，即记录集合内的属性越有顺序越有规律。 1110g2/11/20)/20=0.g93 集合S的熵计算公式为： 再计算例子集中各个属性信息赢取值。对属 2网C,s/1s1)· 性穿衣指数”分为三个分支“很多”、“正常”、“较 Info(S)=- 绍。①当i=“很多”时.6项对应天气不舒适”，1 logz (freg(C:.S)/I SI)) 4 项对应天气舒适”。因此Entropy(E.穿衣指数 式中，freq( ,S)为集合S中属于类C:(k个可能 很多)=-1log(/7)17-6l0g2(6/7)/7 类中的一个)的样本数量：1S1为集合S中的样本 0.592:②当i仁“较多”时.Entrop5(E.穿衣指数 数量。子集进行熵的加权和的计算公式为： 较多)=-210g:(2y7)/7-5log(5/7)/7=0.863 Info (T)=-(/ITI)Info(T))(5) ③当i=“正常”时，Entropy(E,穿衣指数正 式中，T为按照属性x进行分区的集合。计算分 常)=-6log2(66)/6-0l0g2(0/6)/6=0: 区前的集合的熵和分区后的熵的差（增益），增益 Nw_Entropy(E,穿衣指数)=7/20x0.592 大的就是要选取的节点。 7/20x0.863+6/20x0=0.509,Gaim(E,穿衣 C4.5算法将分类范围从分类的属性扩展到 指数)=0.9928-(7/20X0.592+7/20X0.863+ 数字属性。如果数据集中存在连续型的描述性属 620x0=0.484:同理，Gaim(E温度)=002 性（数字属性），C4.5算法首先将这些连续型属性 Gain(E.混度)=0.083，Gain(E.风力)=0. 的值分成不同的区间，即离散化”。通常将连续 从Gain(E.穿衣指数)>Gain(E.湿度) 型属性值“离散化”的方法为：①寻找该连续型属 Gain(E,温度)>Gaim(E,风力)可看出，以“穿 性的最小值并将它赋值给mm,寻找该连续型属 衣指数这个属性进行例子集分类的信息赢取值 性的最大值，并将它赋值给max:②设置区间 最大。因此选取“穿衣指数”用于划分属性可得 [min,mx/中的N个等分断点A,其中，i=L, 到如图1所示的决策树。 2N;③分别计算把minA:/和(A,mx 学穿衣指数”为较多、“很多”时，天气有好 (i=l,2,N)作为区间值时的Gain值并进行 有差因此必须计“较多”、“很多"两个分支的实例 比较：④选取Gain值最大的A:作为该连续型属 组成的例子集重复上述计算过程共有14个实例， 性的断点。将属性值设置为[minA]和(A, Entropy(E.)=0.7500 max)两个区间值。 Gain(E,湿度)=Q.3210 Gain(E.,温度)=0.0005 3 实例解析 Gain(E.,风力)=0.0200 由于Gam(E,湿度)>Gain(E,温度) 3.1ID3算法实现 Gaim(E,风力)，可看出以“湿度”这个属性进行例 通过某地天气变化实例说明D3算法的实现 子集分类的信息赢取值最大，因此选取“湿度”用 过程其样本数据见表1。天气的舒适度舒适时为 于划分属性得到如图2所示的决策树。 表1某地天气样本数据集 Tab.I Dat a set of weather sample 属性穿衣指数 温度 湿度 风力 天气舒适度属性 穿衣指数 温度 湿皮 风力 天气舒适度 多 适中 很高 有 很大 中等 15 较 67 正常 10 舒 mie ishing httn cnki ne
节点的信息就可判断哪个属性的训练例集 E s 值 最小, 从而确定当前用某个属性进行划分。C4. 5 算法属性选择基础是基于使生成的决策树中节点 所含的信息熵最小。熵越小则记录集合的无序性 越小, 即记录集合内的属性越有顺序越有规律。 集合 S 的熵计算公式为: Info( S ) = - E k i = 1 ( (fr eq( Ci , S)/ | S | ) # log2 ( freq(Ci , S)/ | S | ) ) ( 4) 式中, fr eq( Ci , S)为集合 S 中属于类C i( k 个可能 类中的一个)的样本数量; | S | 为集合 S 中的样本 数量。子集进行熵的加权和的计算公式为: Infox ( T) = - E ((| Ti | / | T | ) Info( Ti)) ( 5) 式中, T 为按照属性 x 进行分区的集合。计算分 区前的集合的熵和分区后的熵的差( 增益) , 增益 大的就是要选取的节点。 C4. 5 算法将分类范围从分类的属性扩展到 数字属性。如果数据集中存在连续型的描述性属 性(数字属性), C4. 5 算法首先将这些连续型属性 的值分成不同的区间, 即/ 离散化0。通常将连续 型属性值/ 离散化0的方法为: ¹ 寻找该连续型属 性的最小值, 并将它赋值给 min, 寻找该连续型属 性的最大值, 并将它赋值给 max ; º 设置区间 [ min, max ] 中的 N 个等分断点 A i , 其中, i= 1, 2, , N ; » 分别计算把[ min, Ai ] 和( A i , max ) (i= 1, 2 , , N )作为区间值时的 Gain 值, 并进行 比较; ¼选取 Gain 值最大的 A k 作为该连续型属 性的断点, 将属性值设置为[ min, A k ] 和( Ak , max) 两个区间值。 3 实例解析 3. 1 ID3 算法实现 通过某地天气变化实例说明 ID3 算法的实现 过程, 其样本数据见表 1。天气的舒适度舒适时为 正例, 不舒适时为反例。一开始全部包含在根节点 中, 为找当前的最佳划分属性, 先必须根据式( 1) 计 算训练例集 Es 的熵值。节点的熵值为: Entro py( Es) = - 9log 2 ( 9/ 20)/ 20- 11log2 ( 11/ 20)/ 20= 0. 993 再计算例子集中各个属性信息赢取值。对属 性/ 穿衣指数0分为三个分支/ 很多0、/ 正常0、/ 较 多0。¹ 当 i= / 很多0时, 6 项对应/ 天气不舒适0, 1 项对应/ 天气舒适0。因此 Entropy(E s 穿衣指数, 很多) = - 1 log2 ( 1/ 7 ) / 7 - 6log 2 ( 6/ 7 )/ 7 = 0. 592; º 当 i= / 较多0时, Entro py (E s 穿衣指数, 较多) = - 2log 2 ( 2/ 7) / 7- 5log2 ( 5/ 7)/ 7= 0. 863; » 当 i = / 正常0 时, Entr opy ( Es 穿衣指数, 正 常) = - 6log2 ( 6/ 6) / 6 - 0lo g2 ( 0/ 6 )/ 6 = 0; New _Entropy( Es i , 穿衣指数) = 7/ 20 0. 592+ 7/ 20 0. 863+ 6/ 20 0= 0. 509; Gain (E s, 穿衣 指数) = 0. 992 8- ( 7/ 20 0. 592+ 7/ 20 0. 863+ 6/ 200) = 0. 484; 同理, Gain (E s, 温度) = 0. 027 Gain( Es , 湿度) = 0. 083 , Gain( Es, 风力) = 0。 从 Gain(Es , 穿衣指数) > Gain(E s, 湿度) > Gain( Es , 温度) > Gain( Es , 风力) 可看出, 以/ 穿 衣指数0这个属性进行例子集分类的信息赢取值 最大。因此, 选取/ 穿衣指数0用于划分属性可得 到如图 1 所示的决策树。 当/ 穿衣指数0为/ 较多0、/ 很多0时, 天气有好 有差, 因此必须对/ 较多0、/ 很多0两个分支的实例 组成的例子集重复上述计算过程, 共有 14 个实例: Entropy(Es ) = 0. 750 0 Gain(Es , 湿度) = 0. 321 0 Gain(Es , 温度) = 0. 000 5 Gain(Es , 风力) = 0. 020 0 由于 Gain ( E s, 湿度) > Gain (E s, 温度) > Gain( Es , 风力), 可看出以/ 湿度0这个属性进行例 子集分类的信息赢取值最大, 因此选取/ 湿度0 用 于划分属性得到如图 2 所示的决策树。 表 1 某地天气样本数据集 Tab. 1 Dat a se t o f w e a t her sample s 属性 穿衣指数 温度 湿度 风力 天气舒适度 属性 穿衣指数 温度 湿度 风力 天气舒适度 1 较多 很高 很大 没有 不舒适 11 较多 适中 很大 中等 不舒适 2 较多 很高 很大 很大 不舒适 12 很多 适中 正常 没有 不舒适 3 较多 很高 很大 中等 不舒适 13 很多 适中 正常 中等 不舒适 4 正常 很高 很大 没有 舒适 14 较多 适中 正常 中等 舒适 5 正常 很高 很大 中等 舒适 15 较多 适中 正常 很大 舒适 6 很多 适中 很大 没有 不舒适 16 正常 适中 很大 很大 舒适 7 很多 适中 很大 中等 不舒适 17 正常 适中 很大 中等 舒适 8 很多 很高 正常 没有 舒适 18 正常 很高 正常 没有 舒适 9 很多 很高 正常 很大 不舒适 19 很多 适中 很大 很大 不舒适 10 较多 适中 很大 没有 不舒适 20 正常 很高 正常 中等 舒适 # 130 # 水 电 能 源 科 学 2008 年
第26卷第2期 会等：决策树中D3算法与C4,5算法分析与比较 ·131 段多 正微 围1按“穿衣指数”划分生成的决策树 Fig.1 Decision tree according to"index of clothing" 厚农指散 多 正 正 墅股铁鞋腰销路确 [紧影揭叠揭交祸矣不聚影德串聚周受 围2按“湿度”第二次划分生成的决策树 Fig.2 Decision tree according to"humidity" 当温度为很高”、“适中”及风力为“没有”、 由于样本数据中存在数字属性，因此需将数 “很大”、“中等”时还未明确分类。通过上述计算 字属性分成不同的区间。图4中子集T3中有7 可得Gain(E ,温度)=Gain(E,风)=0.31l 个样本。通过分析，按照湿度>70%进行检验，即 因此任选其中一·个都可得如图3所示的决策树。 将数字属性分为58%，70%]、[70%，92%1两个 3.2C4.5算法实现 区间，假设此时检验为X1,则lnfo(T)= 从上述计算可知：Gaim(穿衣指数 ,Gain( log:(57j/7 20g(2/7)/7=0.863。用湿度 度)>Gaim(温度)>Gain(风力)，可看出以“穿衣指 将T3分区两个子集.结果信息为：1foT3)=0 数这个属性进行例子集分类的信息赢取值最大 该信息增量为最大Gai山(X,)=0.863-0= 因此选取“穿衣指数”用于划分属性。将表2中的 0.863.对于子集T1采用同样的计算方法。最后 样本数据集进行划分，得到如图4所示的决策树。 得到的最终决策树如图5所示。 根多 校多 正 正 得爱德出羯大器鼻彩 度 段量毫瑞大品县留贤多德串袋哭密 段多出天本雾图 风力] 得影德串蓝餐器餐 多，限席正然没有，都 图3按温度“风力第三次划分生成的决策树 C1004-2012Ch ved.http://www.cnki.ne
图 3 按/ 温度0 、/ 风力0 第三次划分生成的决策树 Fig . 3 De cisio n t re e ac c or ding t o / t emper at ure0 and / w ind pow e r0 当温度为/ 很高0、/ 适中0 及风力为/ 没有0、 / 很大0、/ 中等0时, 还未明确分类。通过上述计算 可得 Gain(E s, 温度) = Gain( Es , 风力) = 0. 311, 因此任选其中一个都可得如图 3 所示的决策树。 3. 2 C4. 5 算法实现 从上述计算可知: Gain(穿衣指数) > Gain(湿 度) > Gain(温度) > Gain(风力), 可看出以/ 穿衣指 数0这个属性进行例子集分类的信息赢取值最大, 因此选取/ 穿衣指数0用于划分属性。将表 2 中的 样本数据集进行划分, 得到如图 4 所示的决策树。 由于样本数据中存在数字属性, 因此需将数 字属性分成不同的区间。图 4 中子集 T3 中有 7 个样本。通过分析, 按照湿度> 70%进行检验, 即 将数字属性分为[ 58%, 70% ] 、[ 70% , 92%] 两个 区间, 假设此时检验为 X 1 , 则 Info ( T3 ) = - 5log 2 ( 5/ 7)/ 7- 2lo g2 ( 2/ 7)/ 7= 0. 863。用/ 湿度0 将 T3 分区两个子集, 结果信息为: Info( T3 ) = 0, 该信息增量为最大: Gain ( X 1 ) = 0. 863 - 0 = 0. 863。对于子集 T1 采用同样的计算方法。最后 得到的最终决策树如图 5 所示。 第 26 卷第 2 期 李 会等: 决策树中 ID3 算法与 C4. 5 算法分析与比较 # 131 #
·132· 水电能源科学 2008年 表2某地天气样本数据集 Tab.2 Dat a set of weather samples 属性穿衣指数温度/℃湿度/%风力 天气舒适度 属性 穿衣指数温度℃湿度/%风力天气舒适度 较多 35 70 1 不舒适 11 较多 22 92 不舒适 较多 33 78 7 不舒适 12 很多 28 55 不舒适 较多 34 80 4 不舒适 13 很多 27 6 不舒适 正常 32 5 0 舒适 14 较多 25 65 舒适 正常 33 5 舒适 15 较多 26 好 > 舒适 6 很多 90 2 不舒适 16 正常 27 舒适 > 很多 4 8 3 不舒适 17 正常 2 9 舒适 8 很多 3 1 舒适 18 正常 35 65 1 舒适 9 很 60 6 不舒适 19 很多 20 95 不舒适 10 多 26 86 0 不舒适 20 正常 30 g 舒适 导衣指数 很多 正常 较多 .25,90.2.不1话 32.85%,0,舒适 24 88 51 30 50%. 60 30, 56,3,第遇 小 不不不 55 ! 第.20.953 图4 按“穿衣指数”划分生成的决策树 Fig.4 Decision tree according to"index of clothing" 穿衣指敬 很多 正常 较多 湿度X: 85N 湿度X 501 ≥70 {很多.30,50%，1.都适 根多，25.90%，2，不舒适 辍多纸：影落 段多3570 蒸，31.60%，6.不3 28.55%,1.不 多，27.68，5.不因 较较较 22.92 图5按“穿衣指数”划分生成的决策树 Fig.5 Decision tree according to "index of clothing" C4.5算法解决了ID3算法无法描述属性连 b.C4.5算法为D3算法的扩展有如下改 续型的情况.在实现过程中利用C4.5算法建立 进：①用信息增益率选择属性，克服了用信息增 决策树的速度较ID3算法迅速，而且决策树结构 益选择属性时偏向选择值多的属性的不足。② 也较D3算法合理，同时也找到较好的规则信息。 可处理连续数值型属性。③为避免树的高度无 节制的增长和过度拟合数据，采用了从“规则后修 4结语 剪”方法演变而来的后剪枝方法。该法使用训练 样本集本身估计剪枝前后的误差，从而决定是否 aID3通过循环处理，逐步求精，直至找到 真正剪枝。④对于缺失值的处理。利用C4.5算 完全正确的决策树。ID3算法不存在无解的危 法可提高决策树生长速度，优化决策树结构，挖掘 险：全盘使用训练数据，而不是象侯选剪除算法逐 较好的规则信息。挖掘的数据越多，算法的效率 个地考虑训练例，从而抵抗噪音。ID3倾向于选 和性能越好，算法的优越性越明显。 择取值较多的属性.却不是最优的属性，这样就有 cC4.5算法被应用于较多工程中，如在水 可能得到局部最优解而失去全局最优解：在搜索 库工程环境评价中就可根据提供的样本数据，采 过程中无回溯：D3不能增量的接受训练集，每增 用C4.5算法构建决策树获得较优的规则信息 加一次实例就抛弃原有的决策树，重新构造新的 并能为今后水库环境质量治理提出参考性意见。 决策树，开销很大na Academic Joural Electronic Publishing House,.All rights reserved(.下转第I63页i.net
表 2 某地天气样本数据集 Tab. 2 Dat a se t o f w e a t her sample s 属性 穿衣指数 温度/ e 湿度/ % 风力 天气舒适度 属性 穿衣指数 温度/ e 湿度/ % 风力 天气舒适度 1 较多 35 70 1 不舒适 11 较多 22 92 5 不舒适 2 较多 33 78 7 不舒适 12 很多 28 55 1 不舒适 3 较多 34 80 4 不舒适 13 很多 27 68 5 不舒适 4 正常 32 85 0 舒适 14 较多 25 65 4 舒适 5 正常 33 85 5 舒适 15 较多 26 58 7 舒适 6 很多 25 90 2 不舒适 16 正常 27 84 8 舒适 7 很多 24 88 3 不舒适 17 正常 23 79 4 舒适 8 很多 30 50 1 舒适 18 正常 35 65 1 舒适 9 很多 31 60 6 不舒适 19 很多 20 95 8 不舒适 10 较多 26 86 0 不舒适 20 正常 30 56 3 舒适 C4. 5 算法解决了 ID3 算法无法描述属性连 续型的情况, 在实现过程中利用 C4. 5 算法建立 决策树的速度较 ID3 算法迅速, 而且决策树结构 也较 ID3 算法合理, 同时也找到较好的规则信息。 4 结语 a. ID3 通过循环处理, 逐步求精, 直至找到 完全正确的决策树。ID3 算法不存在无解的危 险; 全盘使用训练数据, 而不是象侯选剪除算法逐 个地考虑训练例, 从而抵抗噪音。ID3 倾向于选 择取值较多的属性, 却不是最优的属性, 这样就有 可能得到局部最优解而失去全局最优解; 在搜索 过程中无回溯; ID3 不能增量的接受训练集, 每增 加一次实例就抛弃原有的决策树, 重新构造新的 决策树, 开销很大。 b. C4. 5 算法为 ID3 算法的扩展, 有如下改 进: ¹ 用信息增益率选择属性, 克服了用信息增 益选择属性时偏向选择值多的属性的不足。 º 可处理连续数值型属性。 » 为避免树的高度无 节制的增长和过度拟合数据, 采用了从/ 规则后修 剪0方法演变而来的后剪枝方法。该法使用训练 样本集本身估计剪枝前后的误差, 从而决定是否 真正剪枝。¼对于缺失值的处理。利用 C4. 5 算 法可提高决策树生长速度, 优化决策树结构, 挖掘 较好的规则信息。挖掘的数据越多, 算法的效率 和性能越好, 算法的优越性越明显。 c. C4. 5 算法被应用于较多工程中, 如在水 库工程环境评价中就可根据提供的样本数据, 采 用 C4. 5 算法构建决策树获得较优的规则信息, 并能为今后水库环境质量治理提出参考性意见。 ( 下转第 163 页) # 132 # 水 电 能 源 科 学 2008 年
第26卷第2期 徐伟等：加强线路绝缘对220kV变电站绝缘配合的影响 ·163· b.从仿真计算的结果看出，加强线路绝缘后 社，2001. 绝缘子片数增加到15片，变压器、断路器上的过 [2】周卫华，蒋毅.加强线路绝缘对变电站绝缘配合的 电压均未超出其耐受水平，其他设备的绝缘配合 影响[J.湖南电力，2005,25(5)：子11 也不会受到威胁。但是.当雷击点较近时，流过避 [3)(加)Dommel H W.电力系统电磁暂态计算理论 雷器的过电流较大，可能会对避雷器造成破坏。 [M].李永庄，林集明，曾昭华译.北京：水利水电出 因此，建议”1和2杆塔仍保持原有绝缘水平（即 版社.1991. 13片绝缘子)。 「4DL/T620.交流电气装置的过电压保护和绝缘配合 c在加强输电线路绝缘的同时，应进一步加 [.北京：中国电力工出版社，1997. 强220kV变电站进线段线路的防雷保护。 [5)李汉明，陈维江，张翠霞，等.多雷地区110kV和 参考文献： 220kV散开式变电所的雷电侵入波保护[J].电网 [刂文远芳.高电压技术[M].武汉：华中科技大学出版 技术.2002.26(8)：3943 Influence of Strengthening Line Insulation on Insulation Coordination in 220 kV Substation XU Wei'ZHANG Dapeng'LIU Xun'TANG Cheng?LIU Xi WU Guohua' (1.Collage of Elect ric and Elect ronic Eng.,HUST,Wuhan 430074,China; 2.Wuhan High Voltage Research Institute,Wuhan 430074,China) Abstract:Strengthening line insulation is effect ive in reducing pollution flashover accident and lowering converselyat- tack rat es of the lines.But it may cause a threat to current insulation coordinat ion.The numerical simulat ion calculation models of certain 220 kV substat ion and transmission lines were established for its two different operating modes by elee- tromagnet ic transient calculation program ATPEMT P.The over-voltage and lightning current generat ed in the elect rical equipments of the substation were calculated and effects of lightning intruding surge on insulation coordination in substa tion after strengthening line insulation were studied in this paper.The research shows that there is no threat to current in- sulation coordination if line insulat ion is strengt hened. Key words:lightning intruding surge;insulation of transmission lines;insulation coordination:ATPEMT P (上接第132页) 术[M].范明，孟小峰译.北京：机械工业出版社 参考文献： 2005. [刂陈文伟，黄金才，赵新显.数据挖掘技术[M]北京： [可史忠植.知识发现[M.北京：清华大学出版社 北京工业大学出版社.2004 2002. [2】Kantardzic Mehmed.数据挖掘一概念，模型，方法和 [刀王晓国，黄韶坤，朱炜，等.应用C4.5算法构造客户 算法M].闪四清，陈茵，程雁译.北京：清华大学出 分类决策树的方法[J.计算机工程，2003.29(14)： 版社，2004. 8991 3]Quinlan J R.Induction of decision treef J].Machine [8刘小虎.李生.决策树的优化算法[刀.软件学报. Learning.1986(1):8k86 1998,910):797800 [4 Agosta Lou.数据仓库技术指南[M.潇湘工作室 [9)丁华，张少中，王秀坤.基于改进D3算法的轨迹化 译.北京：人民邮电出版社.2001. 决策研究[J].计算机工程与设计，2004,25(10)：1 [)Jiaw ei Han,,M icheline Kamber.数据挖据概念与技 7211723 Analysis and Comparison between ID3 Algorithm and C4.5 Algorithm in Decision Tree LI Hui HU Xiaomei School of Infor mat ion Eng..An'hui Univ.of Finance and Economics,Bengbu 233041,China) Abstract:This paper presented the expressing method of decision tree and an optimized decision tree learning alge rithm of ID3 and C4.5,especially explained how to select the regulation of decision attribut ion.Compared w ith C4.5. there are many short oomings in ID3.C4.5 improves decision tree classification efficiency and presentation distinctness. Key words:data mining:decision tree;ID3 algorithm:C4.5 algorithm C 1994-2012 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
b. 从仿真计算的结果看出, 加强线路绝缘后 绝缘子片数增加到 15 片, 变压器、断路器上的过 电压均未超出其耐受水平, 其他设备的绝缘配合 也不会受到威胁。但是, 当雷击点较近时, 流过避 雷器的过电流较大, 可能会对避雷器造成破坏。 因此, 建议 # 1 和 # 2 杆塔仍保持原有绝缘水平( 即 13 片绝缘子) 。 c. 在加强输电线路绝缘的同时, 应进一步加 强 220 kV 变电站进线段线路的防雷保护。 参考文献: [ 1] 文远芳. 高电压技术[ M] . 武汉: 华中科技大学出版 社, 2001. [ 2] 周卫华, 蒋毅. 加强线路绝缘对变电站绝缘配合的 影响[ J] . 湖南电力, 2005, 25( 5) : 7- 11 [ 3] ( 加) Dommel H W. 电力系统电磁暂态计算理论 [ M] . 李永庄, 林集明, 曾昭华译. 北京: 水利水电出 版社, 1991. [ 4] DL/ T 620. 交流电气装置的过电压保护和绝缘配合 [ S] . 北京: 中国电力工出版社, 1997. [ 5] 李汉明, 陈维江, 张翠霞, 等. 多雷地区 110 kV 和 220 kV 敞开式变电所的雷电侵入波保护[ J] . 电网 技术, 2002, 26( 8) : 39-43 Influence of Strengthening Line Insulation on Insulation Coordination in 220 kV Substation XU Wei 1 ZHANG Dapeng 1 LIU Xun 1 T ANG Cheng 2 LIU Xi 2 WU Guo hua 1 ( 1. Co llage of Elect ric and Elect ronic Eng. , H UST, Wuhan 430074, China; 2. Wuhan H ig h Vo ltag e Research Institute, Wuhan 430074, China) Abstract: Str eng thening line insulatio n is effect ive in reducing pollutio n flasho ver accident and lowering conversely- attack rat es o f the lines. But it may cause a threat t o current insulation coor dinat ion. T he numerical simulat ion calculation models of certain 220 kV substat ion and transmission lines wer e established for its tw o different operating modes by elect romag net ic transient calculatio n pro gr am ATP-EMT P. The o ver- voltage and lig htning current g enerat ed in the elect rical equipments of the substatio n w ere calculated and effects of lig htning intruding sur ge on insulatio n coo rdinatio n in substat ion after str eng thening line insulation w ere studied in t his paper. The r esear ch shows t hat there is no threat to current insulation co or dination if line insulat ion is strengt hened. Key words: lig htning intr uding surg e; insulation of tr ansmissio n lines; insulatio n coo rdinatio n; ATP-EMT P ( 上接第 132 页) 参考文献: [ 1] 陈文伟, 黄金才, 赵新显. 数据挖掘技术[ M ] . 北京: 北京工业大学出版社, 2004. [ 2] Kanta rdzic Mehmed. 数据挖掘) 概念, 模型, 方法和 算法[ M] . 闪四清, 陈茵, 程雁译. 北京: 清华大学出 版社, 2004. [ 3] Quinlan J R. Induction o f decision t ree[ J] . Machine Learning, 1986( 1) : 81- 86 [ 4] Ago sta Lo u. 数据仓库技术指南[ M] . 潇湘工作室 译. 北京: 人民邮电出版社, 2001. [ 5] Jiaw ei H an, M icheline Kamber. 数据挖掘概念与技 术[ M] . 范明, 孟小峰译. 北京: 机械工业出版社, 2005. [ 6] 史忠植. 知识发现[ M] . 北京: 清华大学出版社, 2002. [ 7] 王晓国, 黄韶坤, 朱炜, 等. 应用 C4. 5 算法构造客户 分类决策树的方法[ J] . 计算机工程, 2003, 29( 14) : 89- 91 [ 8] 刘小虎, 李生. 决策树的优化算法[ J] . 软件学报, 1998, 9( 10) : 797- 800 [ 9] 丁华, 张少中, 王秀坤. 基于改进 ID3 算法的轨迹化 决策研究[ J] . 计算机工程与设计, 2004, 25( 10) : 1 721- 1 723 Analysis and Comparison between ID3 Algorithm and C4. 5 Algorithm in Decision Tree LI Hui HU Xiaomei ( Scho ol o f Informat ion Eng ., An. hui Univ . o f Finance and Eco nomics, Bengbu 233041, China) Abstract: This paper pr esented the expressing method of decisio n tree and an o ptimized decision t ree learning alg orithm of ID3 and C4. 5, especially expla ined how to select the reg ulatio n of decisio n attribut ion. Compared w ith C4. 5, ther e are many short comings in ID3. C4. 5 impr ov es decision tr ee classification efficiency and pr esentatio n distinctness. Key words: data mining ; decision tree; ID3 algo rithm; C4. 5 algo rithm 第 26 卷第 2 期 徐 伟等: 加强线路绝缘对 220 kV 变电站绝缘配合的影响 # 163 #