第4 O卷第 l l A期 2 0 1 3年 1 1月
计
算
机
科
学
Co mp u t e r S c i e n c e
Vo 1 . 4 0 No . 1 1 A NO V 2 0 1 3
用遗传算法改进的 B P神经网络剪枝算法来优化决策树模型 武彤程辉
(贵州大学计算机科学与信息学院贵阳 5 5 0 0 2 5 ) 摘要决策树是一种有效的分类方法,但在构建决策树模型的过程中,常常会出现模型过度拟合的现象。利用基于
B P神经网络的决策树剪枝算法( B P - P r u n i n g )进行软剪枝处理,然后根据 B P - P r u n i n g的一些不足,提出一种改进算法,简称 GB P - P r u n i n g算法。该算法通过引入遗传算法来训练 B P - P r u n i n g算法模型中的权值和阈值,从而克服了B P - P r u n i n g算法上的不足,最后验证了 GB P - P r u n i n g算法的可行性。
关键词
数据挖掘,决策树, B P神经网络,遗传算法,剪枝算法 T P 3 9 文献标识码 A
中图法分类号
BP Ne ur a l Ne t wo r k Pr u ni n g Al g o r i t h m I mpr o v e d o n Ba s e o f Ge n e t i c Al g o r i t h m t o Opt i mi z e De c i s i o n Tr e e Mo de l WU To n g CH E NG Hu i ( Sc h o o l o f Co mp u t e r Sc i e n c e a n d I n f o r ma t i o n, Gu i z h o u Uni v e r s i t y, Gu i y a n g 5 5 0 0 2 5, Ch i n a )
A ̄ t mc t De c i s i o n i S a n e fe c t i v e c l a s s i f i c a t i o n me t h o Bu t d u r i n g t h e b u i l d i n g p r o c e s s o f d e c i s i o n t r e e . t h e r e u s u a l l y a p p e a r o v e r - f i t t i n g p h e n o me n a o f mo d e l s . Th i s p a p e r d i s c u s s e d s o f t p r u n i n g p r o c e s s i n g b y u s
i n g B P p r u n i n g wh i c h i s b a s e d o n BP n e u r a l n e t wo r k . Th e n, a c c o r d i n g t o t h e s h o r t a g e s o f BP p r u n i n g, t h i s p a p e r p r o p o s e d a r e v i s e d a l g o r i t h m, n a me d GB P - P r u n i n g . Th i s a l g o r i t h m i s a b l e t o t r a i n we i g h t a n d t h r e s h o l d v a l u e o f BP - P r u n i n g mo d e l b y b r i g i n n g i n g e— n e t i c a l g o r i t h m, S O t h a t i t c a n o v e r c o me t h e s h o r t a g e s o f B P - Pr u n i n g . I t a l s o p r o v e d t h e f e a s i b i l i t y o f GB P- P r u n i n g . Ke y wo r d s Da t a mi n i n g, De c i s i o n - t r e e, BP n e u r a l n e t wo r k, Ge n e t i c a l g o r i t h m, Pr u n i n g a l g o r i t h m
决策树是一种有效的分类方法,对于多峰分布之类的问
被分割为单一实例的叶节点。这种划分虽然分类比较完全, 但会产生过多的冗余无用的规则,不利于预测。再加上训练集数据中存在噪音或者训练数据样例太少,以致于不能产生目标函数具有代表性的采用。
题尤为方便。利用决策树采用分级的形式,可以把一个复杂 的多类别分类问题转化为若干个简单的分类问题来解决 1]。
但是在建立决策树模型时会出现如下问题。 给定一个空间 H,一个假设 h∈H,如果存在其他的假设 h ∈H,使得在训练样例上 h的错误率比矗 小,但在整个实例 分布上 h 的错误率比 h小,那么就称假设 h为过度拟合训练数据 l 2]。其现象表现为一个假设在训练数据上能够获得比其他假设更好的拟合,但是在训练数据外的数据集上却不能很好地拟合数据。如图 1所示,在决策树创建过程中,横
轴表示结点总数,纵轴表示决策树做出的预测的精度。实线表示决策树算法在训练集上的精度,虚线表示决策树算法在测试集上的精度。从图中可以看出,随结点总数的增加,在训练样例
图 1决策树过度拟合现象不意图
为了防止决策树模型过度拟合现象的出现,本文研究采
用基于遗传算法改进的 B P神经网络剪枝算法对决策树模型 进行优化处理。
上的精度上升,但是在测试集上的精度下降。当结点总是小于1 6时,决策树在训练集与测试集的精度都上升。当树的结点总数大于 1 6时,其在训练集上的精度上升而测试集上的精度会下降,从而产生预测不准确的情况。 在决策树构建过程中出现上述现象的主要原因是决策树生成算法中,结点的分割标准是一直到该结点中所包含的全部实例属于同一类别时才停止划分。从而使得有些结点可能
1 基于 B P神经网络的决策树剪枝算法 决策树剪枝操作是优化决策树模型的有效手段。它可以防止决策树模型出现过度拟合现象。传统的决策树剪枝算法 是在其树结构的基础上根据某些标准裁剪一些节点,从而减小模型规模,防止过度拟合现象,最终生成剪枝后的决策树规
本文受贵州省 2 0 1 0年工业攻关项目:生产线质量控制决策支持系统的开发研究(黔科合 G Y字[ 2 0 1 0 1 3 0 6 1 )资助。 武
彤( 1 9 6 4一),女,硕士,教授, C C F会员,主要研究方向为数据仓库技术、 Ol A P、数据挖掘。 2 7 8

针对这些不足引入遗传算法 来优化 BP 神经网络的初始权值,从而解决网络初始权值... 遗传算法具有优化训练 BP 网络的能力,将遗传算法优化的 BP 网络模型应用于股票...
本文对相关性剪枝算法进行了改进,采用减法聚类方法确定初始的网络结构,然后再用传统相关性剪枝算法重复优化网络。通过实验结果的分析,验证了改进的神经网络相关性剪枝...
方法首先利用Workbench对零件进行分析得到 实验数据,然后用改进型BP神经网络对实验数据进行训练并建立起多目标优化的模型,采用NSGA- Ⅱ遗传算法对模型进行多目标优化。...
基本思想是先用 GA 粗选神经网络权值,再用 BP 算法精细与优化。 1.2 算法步骤遗传 BP 神经网络的算法步骤: (1) 随机产生一组分布,然后采用实数编码方案对该 ...
基于多策略的决策树剪枝算法及其应用_经济学_高等... 遗传算法、 粗糙集理 论、 人工神经网络、 贝叶斯... 最 后还要对生成树进行剪枝和优化〔1 〕 由 ...
该方法极大的缩小了神经网络初始权值的随机性,使其更 有利于最优神经网络模型的...优化算法 32-39 4.1.1 神经网络的 BP 算法 32-35 4.1.2 结合遗传算法...
决策树优化算法研究_计算机软件及应用_IT/计算机_...遗传 算法和神经网络等.其中决策树方法是一种较为...判断各种决策树的生成算法和 剪枝算法的优劣,精度是...
一种用于预测的 BP 算法的改进旷昀神经网络中的 ... 所 [4] 以人们将这种方法叫做模拟退火组合优化法...(0<A<l)的概率下使用BP算法来计算联接权的调整量...
桨优化设计曾志波,丁恩宝,唐登海(中国船舶科学研究中心,江苏无锡214082) 摘要:在原有图谱设计方法的基础上,采用BP(Back—Pmpagation)人工神经网络模型和遗传算法GA(...
基于遗传算法的改进BP神经... 5页 2财富值 基于改进BP算法神经网络的... ...2006 基于 BP 神经网络的供应商 评价决策优化模型杨月锋1 2 黄河 邓旭东3 (...
热门文档