转载：基于神经网络的分类决策树构造.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：0.39M 资料格式：pdf 举报版权申诉

lijin_1234-3981152-4744300845170511299.pdf-第1页.png

第1页 / 共4页

lijin_1234-3981152-4744300845170511299.pdf-第2页.png

第2页 / 共4页

lijin_1234-3981152-4744300845170511299.pdf-第3页.png

第3页 / 共4页

lijin_1234-3981152-4744300845170511299.pdf-第4页.png

第4页 / 共4页

文本预览

基于神经网络的分类决策树构造 , 徐爱琴张德贤中国科技大学研究生院（北京 $"""(-）河南大学软件工程重点实验室（开封 ).+""$） /01234：56789:;43<##=>9??#@2# L<3HA Q@3A2，RH3S3AP $"""(-） >*(26 1#?0(2 TUHO B2;FJ2?FJO F> LF>?V2JH /AP3AHHJ3AP F> WHA2A MA3NHJE3?O，U23>HAP ).+""$X !.-+&()+： G@H EO1;F43< 299JF2<@HE <:JJHA?4O 2JH ?@H 123A 1H?@FKE >FJ <42EE3>3<2?3FA J:4HE 13A3AP#R:? JHY:HA?4O#G@H 12SFJ JH2EFA 3E ?@2? 24?@F:P@ AH:J24 AH?VFJ=E <2A P3NH 2 @3P@ 9JH<3EH 3A <42EE3>3<2?3FA，3? 3E K3>>3<:4? ?F 2 ?@H 299JF2<@ 9JHEHA?HK 3E 2E >F44FVE：>3JE?4O ?@JF:P@ AH:J24 AH?VFJ= 4H2JA3AP， ?@H JH42?3FA 1FKH4 F> 2??J3;:?HE 2AK <42EZ E3>3<2?3FA F> ?@H K2?2 13A3AP 9JF;4H1 3E HE?2;43E@HK，?@HA ?@H KH<3E3FA ?JHH 3E <42EE3>3<2?3FA 2AK ?@FEH 2??J3;:?HE#G@H KH?234HK 24PFJ3?@1E >FJ HE?2;43E@1HA? F> KH<3E3FA ?JHH 2JH 9JHZ 31943<3? JH42?3FAE PHAHJ2?HK ;O AH:J24 AH?VFJ=E，?@H JH42?3FA0HA@2A<3AP 9J2>H>H 2A24OE3E F> AHEE F> ?@3E 299JF2<@# @#A$’&8-：K2?2 13A3AP，KH<3E3FA ?JHH，AH:J24 AH?VFJ= $ 引言分类问题是数据挖掘中的一个重要问题，其旨在找出将给层各神经元的输出值关系分析而实现分类规则的提取。这种方法算法较为复杂，实现难度较大。定数据集分成若干类的具体分类规则。目前主要有两种基本方该文提出了一种基于神经网络输入输出关系分析来解决法来解决分类规则提取问题：其一是基于符号处理的方法 %$&’%(&；神经网络所隐含规则与知识提取问题的新方法。该方法通过神其二是基于神经网络的连接主义方法。尽管神经网络具有较高经网络训练建立各属性与分类结果之间的关系，并通过提取各的分类精度，但由于难于提取其所隐含的分类规则等问题，从属性与分类结果之间的导数关系来建立分类决策树，从而实现而限制了这种方法的应用。同时神经网络所隐含规则与知识的神经网络所隐含规则与知识的提取。从本质上讲，这种方法属提取问题也是目前神经网络研究中的一个亟待解决的关键问于基于神经网络的输入输出关系分析方法。与基于神经网络的题。结构分析方法相比，该方法具有算法简单、易实现等特点。该文目前，在解决神经网络所隐含规则与知识提取问题的研究给出决策树构造具体算法以及神经网络训练算法。同时为了提中 %)&’%*&，具有代表性的解决方法是基于神经网络的结构分析方高神经网络所隐含关系的提取效果，提出了关系强化约束的概法%)&%+&。该方法的基本算法思想如下：通过修剪已训练的神经网念并建立了具体的模型，最后给出了典型分析实例。络来减少隐含层神经元的个数以及不必要的连接，并对隐含层神经元输出进行离散化处理，进而通过输入层、隐含层和输入 ! 分类决策树的构造算法 , 该文研究工作得到河南省自然科学基金资助。作者简介：徐爱琴，讲师，硕士研究生，主要研究方向为神经网络、算法设计与分析等。张德贤，副教授，博士，主要研究方向为神经网络、软件工程等。计算机工程与应用 !"""#$" )(

!#$ 决定强度的定义设给定训练数据集为 %，% 中的样本由特征向量及其分类结果表示，分类对象的属性表为&’$，’!， ###，’()，全部分类结果构成的集合为*+$，+!，###，+,-，一般的有 (!$ 和 ,!!。对于每一属性 ’.，其值域为 /（’.）。值域可以是离散的，也可以是连续的。这样训练数据集的一个样本就可以表示成012+3456的形式。其中 1 为样本中各属性具体取值2+（1）"*+$2+!，…2+,- 为实例 1 的分类结果。对于给定训练数据集 %，对各属性取值与分类结果取值在（"，$）的范围内进行量化，并通过神经网络训练2则可获得各属性 ’. 与分类结果的具体数学关系模型，即 +（1）78（’$2’!2…2’( 对于给定结构的神经网络来讲，上述关系是以网络的具体）权值与阈值来体现。因此就可以通过网络的具体权值与阈值来分析各特征 ’. 与分类结果的具体作用关系。为了便于分析各属性 ’. 与分类结果的具体作用关系，在此引入各属性 ’. 的决定强度 /9（’.）的概念。所谓的决定强度 /9（’.）就是属性 ’. 对分类结果的决定程度。决定强度 /9（’.）的具体定义如下： /9（’. ）7 #+（1） #’. 即为分类结果 +345对属性 ’. 偏导数的绝对值。因此，决定强度 /9（’.）反映了属性 ’. 对分类结果的影响程度。基于决定强度 /9 （’.）在各种条件下的具体取值就逐步构造分类决策树，以获取具体的分类规则。 !#! 决定强度的计算决定强度 /9（’.）的计算主要涉及分类结果 +345对属性 ’. 偏导数的计算。在该文的研究中，选择多输入单输出的前馈网络，即多个输入层节点分别对应于数据集 % 的各属性 ’.，单输出层节点对应于分类结果 +（1）。取网络的激发函数为 :3457 $ ! &$;<=34 > !"5)，其中，!" 为一常数，在该文的研究中取为 "#?。对于单隐含层前馈神经网络，可以推出网络输出对网络输入的偏导数的通用计算公式如下 EF$ #@A #B. :3!@ A5&$D:3!@ 7 C !! " 为输出层各神经元的网络输出；B. !*:3! A5) F$ F$ G 5&$D:3! G 5)HAGHG.- G 7 $ 其中，@A 为输入层各神 A 经元的网络输入；!@ 层各神经元的总输入；HAG 个神经元的连接权重；HG. 个神经元的连接权重；EF$ EB 数。为输出层各神经元的总输入；! 为隐含 F$ G 为输出层第 A 个神经元与隐含层第 G 为隐含层第 G 个神经元与输入层第 . 为隐含层神经元个数，.7$2!2I2 …2EB2 为输出层神经元个为输入层神经元个数；A77$2!2I2…2E@ ，E@ 个神经元的连接权重；EF$ 经元个数。与 EF! 分别为第 $ 与第 ! 隐含层的神分析以上两式可以看出：（$）前馈网络的导数计算公式明显具有递推性，因此容易递推出多隐含层网络的输出对输入的导数计算公式。（!）在神经网络的导数计算公式中包含有权值的乘积项，并且隐含层数越多，权值乘积的阶数就越高。因此，权值的变化对导数的影响将比对输出值的影响大。在面向关系辨识的网络训练中应限制网络权值的不必要变化。 !#I 决策树的构造算法基于神经网络的决策树构造过程与算法如下： $#数据预处理。数据预处理主要涉及内容包括数据筛选、属性取值的离散化处理与编码、以及属性值与分类结果的量化处理。在量化处理时，按某种顺序使属性与分类结果均在（"，$）范围内取值。从而形成神经网络训练的具体样本。从本质上讲，在面向决策树构造的神经网络训练中，其训练的主要目的旨在辨识各属性对分类结果的决定强度的顺序，而不强调输出数据的准确性。各属性对分类结果的决定强度的顺序就体现了网络的输出与输入之间的关系。从大量的网络训练实例中可以看出：当样本数据愈多时，输出与输入之间的关系愈易辨识。因此在学习速度允许的情况下，应适当取较多的训练样本。 !#神经网络训练。利用给定的样本对网络进行训练。在网络的训练中，只要各属性对分类结果的决定强度的顺序稳定，就可以认为网络训练已完成。 I#建树算法。算法的核心是选取决定强度最大的属性作为扩展属性。具体算法如下：（$）对当前例子集合，选择决定强度最大的属性 ’. 作为扩展属性。（!）把在 ’. 处取值相同的例子归于同一子集，’. 取几个值就得几个子集。（I）对包含不同类的子集，若分类精度低于预定精度，递归调用建树算法；（C）若子集为同一种类，对应分枝标上具体种类，返回调用处。 I 关系强化约束定义与建模对于用于决策树构造的网络训练，网络训练的目的旨在根据具体训练数据集，建立一种能准确体现各属性与分类结果之间关系的具体网络模型。目前的神经网络训练方法主要是通过使网络的输出误差逐步减少而实现网络的训练。因此在这些训练方法中，建立输入与输出数值上的正确对应是直接性的，而建立输入与输出正确的关系是间接性的。结果会造成输出的误同样，对于两隐含层前馈网络，可以推出网络输出对网络差很小，但是输入与输出关系（例如导数关系）的误差却很大。输入的偏导数的通用计算公式如下基于这些情况，为了提高网络辨识输入与输出关系的效率，并 EF$ 便于这些关系的分析与利用，就应在网络训练的误差计算中引 #@A #B. 7 ? !I " :3!@ A5&$D:3!@ !*:3! A5) F! F! J 5&$D:3! J 5)HAJ EF! J 7 $ !:3! F$ G 5 G 7 $ &$D:3! F$ G 5)HJGHG.- F! 与 ! F$ G J 其中，! 分别为第 $ 与第 ! 隐含层各神经元的总输为输出层第 A 个神经元与第 ! 隐含层第 J 个神经元的连为第 ! 隐含层第 J 个神经元与第 $ 隐含层第 G 个神为第 $ 隐含层第 G 个神经元与输入层第 . 入；HAJ 接权重；HJG 经元的连接权重；HG. CC !"""#$" 计算机工程与应用入相应的约束。这些约束就是网络训练的关系强化约束。这些关系约束的主要作用是提高网络训练的关系学习能力。根据关系强化约束的性质，这些约束基本上属于诱导型约束。因此约束的引入可采用如下的引入方式，即 K（1）7L315; !H.M. （1） . 其中，1 为基于具体网络结构的训练解；L（1）为网络的输

出误差；%&（’）为第 & 个关系强化约束的约束误差；(& 为第 & 个关系强化约束的诱导权重，其值取决于该关系强化约束的重要程度以及 )（’）与 %&（’）的数量差别；*（’）为网络训练的总误差。根据决策树构造过程的具体需要，一般需要引入以下两种关系强化约束：（$）权值限制约束。从神经网络的偏导数计算公式中可以看出，在这些计算公式中包含有权值的乘积项。为了限制权值的不必要变化，提高网络所建立关系的准确性，应引入对权值变化的限制约束。具体约束模型如下导数关系如图 $ 所示。在这种情况下，无用属性 ?)2A)BC?>B) 的导数波动仍较大，各有用属性的导数变化不均匀。因此所表现的关系不够清晰。图 !RS 为利用关系强化约束对网络进行训练时所获得的结果。其中权值限制约束的加权系数为 "#""M，导数关系限制约束的加权系数为 "#"M。在这种情况下，减少了无用属性 ?)2A)BC?>B) 的导数波动量，并使各有用属性的导数变化均匀。因而使建立决策树所需的各种关系变得更加清晰。 %(+’,- !.(&+’,. & 其中，%(+’,为权值约束误差；(&+’,为网络的所有连接权重。（!）导数关系限制约束。该约束的主要作用为尽可能减小各属性导数值的不必要变化。即尽可能减小对分类结果影响小属性的导数值变化。同时也尽可能使各有用属性导数值均匀单调变化，以便进行各属性对分类结果作用强度的综合比较。该约束实现的一种简单方法是要求输出层第 / 个神经元对输入层第 & 个神经元的偏导数为线性关系，这是一种对导数关系的较弱限制。该约束模型可通过如下方式建立：先求出偏导数与输入层相应神经输入的线性回归曲线，约束误差可利用在各样本点处的回归曲线的计算值与相应的偏导数值之差来表示，即图 $ 各属性与分类结果的导数关系（无关系强化约束）（’）- %0 !3456+%&,27+ !8/ !%& 2 - $ 1 （’）（’）,29! 其中，+ !8/ !%& （’）（’）,2 为第 2 个样本点处输出层第 / 个神经元对输入层第 & 个神经元的偏导数值；4 与 6 为偏导数与输入层第 & 个神经元输入的线性回归常数；+%&,2 为输入层第 & 个神经元第 2 个样本点处的输入值。 : 算法试验与分析为了便于说明，下面采用一个关于气候的典型实例 3;9来进行试验与分析。其分类对象的属性表为<=>?/==@，?)2A)BC?>B)， D>2&E&?F，G&HEFI。各属性的值域为：0（=>?/==@）-HHF，=K)BLCJ?， BC&HI，量化为 <"#!，"#M，"#NI；0 （?)2A)BC?>B)）-2&E&?F）-)，PC/J)I，量化为<"#!，"#NI。分类结果集合为?/==@ 的决定强度最大，因此决策树的根节点为属性 =>?/==@。同时当属性 =>?/==@ 取值为 J>HHF（样本 $、!、N、T、$$）时，属性 D>2&E&?F 的决定强度最大，因此属性 D>2&E&?F 为属性 =>?/==@ 取值为 J>HHF 的扩充属性。同样属性 G&HEF 为属性 =>?/==@ 取值为 BC&H（样本 :、M、U、$"、$:）的扩充属性。因此就构成足以将样（下转 MM 页）计算机工程与应用 !"""#$" :M

%#! 影响域与 5.I8 的联系 BRS] M*+7/62I18 ^ E8, 一个影响域相当于一个映射函数，将（5.I8，测度）映射为可信度的线形测度。如图 ( 所示，在一个循环图中的表有 & 个主要部分：中心维度（如顾客），用来计算中心的测度（如利润），内部属性（如顾客年龄），外部属性（如某个顾客最喜欢的产品颜色）以及非中心测度（如某个顾客每次购买的货物的平均数量‘。在 b;VM 发现的过程中，当通过遍历混合空间来实现影响分析时，中心会沿着不同的尺度表不断地移动。这一点在图 ! 中也反映出来了，在图 ! 中，当中心环绕星形从一个尺度到另一个尺度不断移动时，b;VM 发现引擎能够通过影响计算来实现对 b;VM 引擎和 G-; 引擎的交替调用。 _2‘ 影响域将维度和测度映射为可信度（I） 5.I8 将维度映射为测度图 & 如上图 &2，&I 所示，已知 _坐标，测度 ‘，坐标为坐标轴 _城市，月份，颜色‘上的三元组_北京，十月，兰‘，测度为利润，影响域告诉人们关于在北京兰颜色的商品对测度为销售量或利润的影响的可信度为 X&a。 %#’ 影响域与 5.I8 的差别已知星形图可用于处理聚簇。但它不能用于影响分析。可以发现影响域的尺度要远远大于 5.I8 空间的尺度。而 5.I8 空间本来就已经很大了。所以，为了遍历影响域，必须进行 b;VM 交叉运算。这些影响运算需要一个能存储更多聚簇的图。在图 ’ 中，可以看到分析的中心沿顺时针方向从顾客转移到商店，再到商品等。对于在这一顺时针移动中的每一点，都需要附加聚簇的或挑选的数据项来丰富中心维度表。既然分析的中心看来是环绕星形旋转，这里将提出一个术语“循环图”来说图 ( & 结束语文章介绍了 b;VM 数据采掘的体系结构及基于影响空间的多维代数结构，指出 b;VM 模型与决策支持系统之间的关系。描述了多维代数结构的基本概念和相应的计算。讨论了 5.I8 与影响域之间的联系与区别。（收稿日期：$>>> 年 > 月）参考文献 $#M2*,2J8，c#]8U T821F, +7 V021J,/,#O262I2, M*+<*2FF/0< d O8,/<0， $>>(#% !#M2*,2J8，c#O262 9/08, 7+* O262 e2*8:+.,8,#O262I2,8 M*+<*2FF/0< d O8,/<0，$>>(#> ’#9/0>?#X %#G.*2Z/6 H:2.4:.*/#V0 b[8*[/8U +7 O262 e2*8:+.,/0< 204 b;VMB8A 5:0+1+>X &#G2F886 V<2*U21#b0 6:8 H+FK.626/+0 +7 9.16/4/F80,/+021 V<<*8<268,# 明这些结构。 $>>( （上接 %& 页）本分类的决策树，如图 ’ 所示。进一步可以建立具体的规则性知识，从而实现神经网络的知识抽取。从上例的决策树构造结果可以看出，基于文中所提出的基于神经网络的决策树构造方法可以构造出节点最少的决策树。从而也证明了该文提出的方法是可行且有效的。（收稿日期：!""" 年 ( 月）参考文献 $#)#*+,, -./0120#304.56/+0 +7 485/,/+0 6*88,#925:/08 ;82*0/0<=$>?(@$ （$）：?$A$"( !#B2C8,:/ D.C.42，E2,.:/C+ 9+*/F+6+，G:/0/5:/ 9+*/,:/62#H+0,6*.56/0< 877/5/806 485/,/+0 6*88 IJ .,/0< +K6/F/L84 0.F8*/5 2,,+5/26/+0 *.18,# M*+5884/0< +7 6:8 !!04 N;OP H+078*8058 9.FI2/（P+FI2J），304/2： $>>(：$%(Q$&& ’#E2,.:/C+ 9+*/F+6+，R/*+F. 3,://，B2C8,:/ D.C.42#S77/5/806 5+0,6*.5A 6/+0 +7 T8<*8,,/+0 6*88, U/6: *20<8 204 *8>X：$((Q$X& %#R+0>&：$(>Q$?" &#袁曾任，卢振中#由神经网络提取规则的一种方法及其应用#信息与控制，$>>X；!(（$）：($A(( (#9 B2Z/08，O S1/L+04+#W*+U/0< F86:+4, 7+* H+0,6*.56/0< T85.*,/[8 4868*F/0/,6/5 K8*58K6*+0 08.*21 086U+*C, 204 C0+U184<8 8\6*256/+0# V*6/7/5/21 306811/<8058#$>>?；$"!（!）：!>&A’!! X#陈文伟#智能决策技术#北京：电子工业出版社，$>>? 计算机工程与应用 !"""#$" &&

分享到：

赞收藏

资料库

转载：基于神经网络的分类决策树构造.pdf

相关推荐

课程资源

热门标签

最新资料