一种改进的GMDH算法

张秋菊, 朱帮助

(五邑大学 系统科学与技术研究所 广东江门529020)

一种改进的GMDH算法

张秋菊, 朱帮助

(五邑大学 系统科学与技术研究所 广东江门529020)

传统GMDH算法在进行多变量非线性建模时耗时较长,一定程度上限制了它的应用范围.针对这个问题,提出了一种改进的GMDH算法,扩大了每一个初始输入元素的信息含量,采用随机分组建立中间模型的方式代替原算法枚举出所有两两组合中间模型的方式,减少了中间模型的数量,提高了建模效率.将改进算法应用于中国GDP的趋势预测,结果表明与传统GMDH算法相比,在不牺牲预测精度的情况下,改进算法效率更高.

GMDH;传递函数;复杂系统;预测建模

0 引言

1967年,乌克兰科学家Ivakhnenko首次提出数据分组处理方法(GMDH)[1].由于自组织数据挖掘在复杂系统预测建模方面表现出色,受到了各国学者关注,并开展了一些改进和应用研究[2-8].这些研究大多针对GMDH算法的传递函数、外准则、中间模型自由度、样本数据集划分等问题.而传递函数的形式及其引起的最终模型结构的复杂性一直是GMDH算法研究的重点[4].由于建立输入变量在100以内的线性模型通常只需要几秒钟时间,因此本文的改进算法主要针对非线性建模.

1 GMDH理论概述

在GMDH算法中,通常用K-G多项式作为参考函数,其表达式为

其中,y为输出向量,x1,x2,…,xn为输入向量,a是系数或权值向量.

假设自变量数量为2,取二次K-G多项式为参考函数,则其参考函数为

可得到GMDH初始模型集合

通过传递函数生成新的模型集,产生第一层中间模型.按传递形式的不同,可分为线性传递和非线性传递.对于非线性模型,传递函数最常见的形式为yk=a1vi+a2vj+a3v2i+a4v2j+a5vivj,i≠j,即对上一层产生的m个输入项进行两两配对,创造新的中间层模型.如式(1)初始模型的输入项数设为5,可生成10个非线性的中间备选模型,以外准则从这10个备选模型中挑出最好的N个,通过传递函数生成新的中间层备选模型,重复这个过程直到满足停止法则.

GMDH算法产生下一层中间模型的方式存在3个缺点:①中间备选模型的数量庞大,每一个备选模型所含的信息量太少;②所含信息量太少,在最初几层各变量之间很难充分组合,很难达到停止法则的要求,而GMDH非线性模型的复杂度随中间模型层数的增加而增加,因此GMDH多变量非线性建模的结果通常比较复杂,难以重构;③由于每个备选模型所含信息量太少,使得进入下一层的备选模型数量的确定十分困难,常需要在节省时间与提高精度中做出抉择.

2 改进算法设计

GMDH改进算法首先将模型的参考函数形式作了数学变换,假设自变量数量为2,则其参考函数的形式应为y=a0+a1x1+a2x2+a3(x1+x2)+a4x21+a5x22+a6(x1+x2)2+…;其次将模型的传递方式作了改进,将数据进行多次随机分组,每一组建立一个中间模型,并利用这些中间模型挑选出影响较大的一些输入元素进入下一层建模.

本文提出的GMDH改进算法如下:

初始设置:迭代次数generation=0,模型适应度连续无改进代数w gjds=0,最佳适应度bestfitness= 1/H(H为足够大的正数),模型适应度改进程度φ为一个接近于0的正数,S为空集.

停止法则:适应度连续无改进代数达到预设值,或者迭代次数达到预定最大迭代次数M G,或者bestfitness达到预定值λ.

1)令generation=generation+1,i=generation,设自变量数量为n,令N=n＊(n+1)/2.令Vi={v1, v2,…,vN},其中,v1=,v2=(x1+x2)i,…,vn=(x1+x2+…+xn)i,vn+1=,vn+2=(x2+x3)i,…,v2n-1=(x2+x3+…+xn)i,…,vN-2=,vN-1=(xn-1+xn)i,vN=.然后,令V={Vi,S}.为了与“模型”及“变量”区分,将V中每个vi都称为元素,则V可称为第i层备选元素集合.

以这种方式产生备选元素集有2个优点:以各种方式表达了变量之间组合的可能性,容易在较低的复杂度上得到合适的模型;由于各元素之间存在着大量重复信息,每一个元素几乎都可以由其他元素线性组合得到,减少了重要信息丢失的可能性.

2)将备选元素集中的元素随机排列,并对其进行分组.预先设定一个值M,若备选元素集中元素的数量大于M,则进行分组.本文建议将M的值设为大于或等于自变量数目n,以尽量减少组合成同一个元素的自变量的系数都相同所带来的影响.如果出现备选集中元素的数目不是n的整数倍,并且余下的元素数量较多,则可将这些元素单独作为一组;否则,将这些元素随机插入其他组中,扩充其他组的容量.

3)对各组元素分别进行线性拟合.将各组所得模型表达式中系数不为0的元素vi放入一个新的备选元素集合G1,并计算每一组所得模型的适应度.

在进行线性拟合时,吸收GMDH外准则思想,将用来建模的数据分为学习集和检测集2部分,学习集部分用来进行拟合,而检测集部分则用来帮助评价每一组所得模型的优劣.在学习集上用最小二乘法或加权最小二乘法对各组元素分别进行线性建模之后,计算各模型在检测集上的估计标准误差,其倒数即为该模型的适应度.

4)将每一组淘汰下来的元素放入一个新的集合B1,然后对B1重复第2)步1次,并对各组元素分别进行线性拟合.将各组所得模型表达式中系数不为0的元素放入一个新的备选元素集合BG1,并计算每一组所得模型的适应度.将淘汰下来的元素再次拟合的目的是为了避免过早淘汰重要信息,给那些被淘汰的元素一次与其他元素充分组合显示其重要性的机会,第5)～8)步也是出于同样的目的.

5)对在第1)步中得到的备选元素集V重复第2)～4)步1次,得到G2和BG2.

6)将G1和G2组合成新的集合N1,G1和BG2组合成新的集合N2,G2和BG1组合成新的集合N3,BG1和BG2组合成新的集合N4.

7)对于N1,N2,N3和N4,检查其各自的集合内部是否有重复的元素,如果有,则除去重复元素.

8)对N1,N2,N3和N4分别重复第2)～4)步1次.

9)比较第3)～8)步中所得所有模型的适应度,记录最大适应度为bf,对应的模型表达式为bm,将bm中系数不为0的元素放入集合S1.

10)令gjd=(bf-bestfitness)/bestfitness,如果gjd<0,则w gids=w gjds+1,并执行第12)步;否则令bestfitness=bf,bestmodel=bm,S=S1,并执行第11)步.

11)判断gjd>φ是否成立,如果成立,令w gjds=0;否则w gjds=w gjds+1.

12)判断是否满足停止法则,如果满足,则停止迭代,输出最佳模型bestmodel,否则执行第1)步.

3 实证分析

以资本存量、能源消费等18个变量对GDP建立非线性预测模型.资本存量数据参见文[9],其余所有数据均来源于《中国统计年鉴》.计算机配置为AMD Semp ron(tm)899 M Hz CPU,内存为256 MB.输出变量x1表示中国GDP,输入变量x2表示社会职工工资总额,x3表示资本存量,x4表示煤炭消费量,x5表示石油消费量,x6表示天然气消费量,x7表示水电、核电和风电消费量,x8表示国际旅游(外汇)收入,x9表示规模以上工业企业个数,x10表示居民消费水平,x11表示出国留学人员学成回国人数,x12表示研究生毕业人数,x13表示商品零售价格指数,x14表示农业生产资料价格指数,x15表示第一产业就业人数,x16表示第二产业就业人数,x17表示第三产业就业人数,x18表示货物周转量,x19表示政府R&D投入经费.

为消除价格因素的影响,所有涉及到货币价值的指标一律按1978年不变价计算.为消除量纲的影响,以1978年为基年,将各指标数据均折成指数.2种算法均以1978～2004年各指标的数据进行建模.其中,1978～2001年的数据作为学习集,2002～2004年的数据作为检测集,2005～2007年的数据作为预测集,取最大时滞为2,用来检验所得模型的预测效果.

以xi(t-1)和xi(t-2)分别表示变量xi的一阶滞后变量和二阶滞后变量,用GMDH算法和改进GMDH算法对其进行建模.将GMDH算法的中间模型选取个数CN分别取为26,45,75时,发现随着中间模型选取个数的增加,预测精度增加了,但同时预测时间也变长了.当中间模型选取个数CN=26时,建模时间为16 m in,但预测精度较差;当CN=45时,建模时间为52 m in,预测精度提高,但仍不理想;当CN=75时,建模时间为283 min,模型精度得到了很大提高,但所花费时间太长.相信当中间模型选取个数更多时,可以达到更高的精度,同时也将花费更长的时间.

当CN=75时,所建立的模型长达50多行,限于篇幅,本文不将其列出.当CN=45时,GMDH建立模型为

从这个模型可知,除了耗时长之外,GMDH算法建立的非线性模型还存在模型重构问题.在中间模型选取个数为45时,少量时间便可重构其模型.但当中间模型选取数为75甚至更大时,试图在短时间内重构模型几乎是不可能的.

改进算法设置最大迭代次数M G=500,φ=0.05,λ=1,w gjds达到25时即停止算法.利用M atlab 7.0软件进行5次计算的平均时间为38.11 min.由于改进GMDH算法中引入了随机分组方法,所以,每次计算的结果和计算时间并非完全相同,但相差较小,其中精度最高的一次模型表达式为

传统GMDH算法和改进GMDH算法的预测结果(1978年为100)见表1(GMDH预测值1和GMDH误差1分别为GMDH算法选取中间模型数为45时的预测值和误差;GMDH预测值2和GMDH误差2分别为GMDH算法选取中间模型数为75时的预测值和误差).由表1可以看出,与传统GMDH算法相比,改进GMDH算法不仅提高了建模效率,而且提高了预测精度.同时,应该注意,GMDH改进算法在模型重构上也存在着一定困难,但相对于GMDH算法模型套模型的形式,改进GMDH算法的建模结果在一定程度上更简单明了.

4 结论

GMDH算法利用外准则来选择最佳模型的思想,使它在众多的建模方法中独具特色,但非线性建模耗时问题和模型重构问题始终是无法回避的缺陷.本文在初始模型集的产生和传递函数的形式上对其加以改进,通过实证分析证明,改进算法可以在一定程度上提高模型的收敛速度,在模型重构方面也更加简单.如何使模型的表达方式更加简洁,将是下一步研究的方向之一.

[1] Ivakhnenko A G.Heuristic self-organizing in p roblem s of engineering cybernetics[J].Automatic,1967,6:207-219.

[2] Ivakhnenko A G.The review of p roblem s solvable by algo rithms of the Group Method of Data Handling(GMDH)[J]. Pattern Recognition and Image Analysis,1995,5(4):527-535.

[3] 陈文伟,黄金才.可拓知识与可拓数据挖掘[J].广西师范大学学报:自然科学版,2001,24(4):159-162.

[4] 鲁茂.改进的GMDH算法及其应用[J].软科学,2008,22(4):17-20.

[5] Ko rd IP.Modified GMDH model and models quality evaluation by visualization[J].Control System s and Computers, 2003(2):23-28.

[6] 邹昊飞,夏国平,杨方廷.基于两阶段优化算法的神经网络预测模型[J].管理科学学报,2006,9(5):28-34.

[7] 陈洪,陈森发.基于免疫遗传算法的GMDH网络模型及其应用[J].江苏大学学报:自然科学版,2009,30(6):610-613.

[8] 鲁茂,贺昌政,李慧.线性GMDH参数模型的无偏估计研究[J].统计研究,2009,26(6):92-97.

[9] 张军,章元.对中国资本存量K的再估计[J].经济研究,2003(7):35-43.

An Improved GMDH Algorithm

ZHANG Qiu-ju, ZHU Bang-zhu
(Institute of Systems Science and Technology,W uyi University,Jiangmen 529020,China)

GMDH algorithm takesmuch time to obtain the final solutionsw hen building nonlinear modelsw ith many variables,so its app lication is limited.Aimed at this p roblem,some imp rovements are imp lemented on the transfer functions of classical GMDH algo rithm.Mo re info rmation is added to every initial input,and a stochastic way instead of the emumerating way is used to create the nextmiddle layer models in order to decrease the number of middle layer models and enhance the modeling efficiency.Finally,through building a p rediction model both w ith the classical GMDH algo rithm and imp roved GMDH algo rithm to fo recast Chinese GDP,it is p roved that the latter can be more efficient.

GMDH;transfer function;comp lex system;p rediction modeling

TP 18;F 270

A

1671-6841(2010)01-0009-05

2009-11-12

国家自然科学基金资助项目,编号70471074;广东省自然科学基金资助项目,编号9452902001004060.

张秋菊(1983-),女,讲师,硕士,主要从事自组织数据挖掘理论、算法及应用研究,E-mail:apollo5234@126.com;通讯联系人:朱帮助(1979-),男,副教授,博士,主要从事复杂系统分析与建模、智能信息处理理论与应用研究,E-mail:wpzbz@126.com.