变窗口神经网络集成预测模型

收稿日期: 2007208224;修回日期: 2007211219 基金项目:国家自然科学基金资助项目(60574078) 作者简介:杨沛(19742 ) , 男,博士,主要研究方向为机器学习、 数据挖掘(yangpeiscut . edu. cn) ;谭琦(19772 ) , 女,硕士,主要研究方向为人工 智能、 数据挖掘等. 变窗口神经网络集成预测模型 3 杨 沛 1 ,谭 琦 2 (1 1华南理工大学 计算机应用研究所,广州510640; 21华南师范大学 计算机学院,广州510631) 摘 要:针对时间序列问题,提出了一个变窗口神经网络集成预测模型。利用自相关分析方法挖掘时间序列本 身蕴涵的变化特性,并利用这些变化特性构造差异度较大的个体神经网络。变窗口集成预测模型在应用于时间 序列预测的同时,还可以有效地对异常序列进行筛选和分离。将该模型应用于移动通信话务量的预测。实验分 析表明,该预测系统具有较高的预测精度,并能有效地对异常序列进行分离。 关键词:神经网络集成;时间序列;预测;异常检测 中图分类号:TP38911 文献标志码: A 文章编号: 100123695(2008) 0822355202 Neural networks ensemble based on variable2window model YANG Pei 1 , TAN Qi 2 (1.Research Institute of ComputerApplication, South China University of Technology, Guangzhou510640, China;2. School of ComputerSci2 ence time series; forecasting; outlier detection 国内外研究者已经提出了众多时间序列预测的方法,如 Box2Jenkins1法、 神经网络方法 2, 3、 遗传算法4和卡尔曼滤 波法 5等。这些方法在广泛应用的同时 ,也表现出很多缺陷 和局限性。以上方法在对复杂系统的建模时往往建立一个单 一模型,通过复杂参数来表征模型特征。但是,单一模型的泛 化能力往往较差,预测的鲁棒性没有保障,预测的精度不能满 足实际工程的要求。 集成学习能有效提高机器学习系统的泛化能力。1990 年,Hansen等人 6提出了一种开创性的方法 ,即神经网络集成 (neural network ensemble)。Krogh等人 7通过理论分析得到 如下神经网络集成泛化误差的计算公式E=E-A。神经网络 集成的差异度A是神经网络集成中各个网络相关程度的度 量。若集成的各个网络个体是相似的,则神经网络集成的差异 度A接近于0,此时其泛化误差E接近于各神经网络泛化误差 的加权平均E;若集成中各个网络个体是相互独立的,则集成 的差异度A较大,其泛化误差远小于各神经网络泛化误差的 加权平均E。因此,神经网络集成构造方法的研究工作主要集 中在如何增大集成中各个体学习器的差异度,如Bagging8、 Boosting9等。 如何有效地度量和产生泛化能力强、 差异大的个体学习 器,仍然是集成学习的一个还没有被很好地解决的问题 10。 为了增加所构造的神经网络个体之间的差异度,针对时间序列 问题,本文提出了一种基于变窗口的神经网络集成模型。利用 时间序列的自相关特性,构造出差异度较大的个体神经网络, 并将个体网络进行集成。 变窗口神经网络集成模型 所谓变窗口,是指集成中各个神经网络个体的输入和输出 窗口是各不相同的。如图1所示,fi表示神经网络个体; xip是 神经网络fi的输入节点;p表示对应神经网络fi的输入层节点 数,它根据自相关系数来确定;y表示集成输出。变窗口体现 了从不同角度和不同的尺度去分析问题的思想。需要指出的 是,变窗口神经网络集成模型主要是针对时间序列预测,因为 在一个时间序列中,可以很自然地切分出不同的输入和输出窗 口。 时间序列本身蕴涵了客观世界及其变化的信息,表现着变 化的动态过程。分析时间序列特性的最有效工具是自相关分 析 11。笔者利用自相关分析将时间序列预测与集成学习这两 个问题有机地结合起来。根据自相关系数来决定输入和输出 窗口大小。 首先,计算时间序列的自相关系数。如果已获得时间序列 yt的n期观测值y1, y2, yn,将它们视为来自 yt的样本, 则将自相关系数表示为 rk= n-k l=1 (y l-y) (yl+k-y) / n l=1 (y l- y) 2 其中:n为样本个数; k为滞后期;y为样本均值。自相关系数 反映了时间序列的项与其后第k项之间线性关系的性质和强 弱相关程度。 第25卷第8期 2008年8月 计 算 机 应 用 研 究 Application Research of Computers Vol . 25 No. 8 Aug .2008 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. 其次,对自相关系数进行排序。选择前p个最大的自相关 系数,构成一个自相关系数集合R= rk1, rk2, rkp。通过以 下两种方式构造不同的输入和输出窗口: a) n2i2l网络结构。输入窗口xw和输出窗口yw满足以下 关系: xw=a, raR yw=1 b) n2i2m网络结构。 输入窗口xw和输出窗口yw满足以下关系: xw=a, raR yw=b, rbR ab 组成神经网络集成中的个体学习器采用BP神经网络。 在BP神经网络中,输入信息从输入层经隐藏层传到输出层。 如果输出层没有得到期望的输出,则计算输出层的误差,然后 将误差进行反向传播,利用梯度下降算法,修改各层神经元的 权值,直至达到期望目标。 假设学习任务是利用n个神经网络通过加权平均组成的 集成对进行学习f: RmRn。假设输入xRm按分布p(x)随机 抽取,个体学习器fi的输出为fi (x) , 则集成在输入x上的实际 输出为 f(x) = n i=1wifi (x)。其中个体学习器fi的权值wi满足 0wi1 n i=1wi =1 异常序列筛选 变窗口集成预测模型可以用于时间序列预测,同时,还可 以有效地对异常序列进行筛选和分离。真实世界中的时间序 列数据往往受到多种因素的影响。例如,通信话务量就受到各 种节假日(如春节、 国庆)的影响。节假日的话务量与平常的 话务量的数据分布并不相同。 异常点(outlier)检测有很多种方法。常规的异常值检测 是根据当前的观测值是否超出预先设定的阈值而作出判定。 该方法存在几个问题 : a) 如何设定恰当的阈值是个难点 ; b) 难 以发现一些细微的流量异常行为 ; c) 由于网络中的流量在不 同的时间有很大的差距,对不同的时间采用同一个阈值显然过 于粗糙。 笔者认为,异常点并不单纯指某个观测值超出预设的阈 值,同时也包括某一段时间的数据分布不符合常规规律。因 此,单纯依靠阈值来判断,并不能找出所有的异常点。但是,如 果换一个角度,从神经网络集成的预测误差的角度出发,则很 容易检测出所有的异常点。原因在于,神经网络能捕获数据的 基本分布规律,而异常序列并不符合基本规律,因此神经网络 对其的预测误差很大。如果多个神经网络对同一部分的数据 样本的预测误差均很大,则可以判断该部分数据样本为异常序 列。 设x为训练样本,Ei(x)为第i个神经网络在x上的预测 误差,假设误差阈值为(0 1),令: (E i(x) ) = 1 ifEi(x) 0 else 集成时采用多数投票方式,如果多数的神经网络对样本x 的预测误差均超出阈值,则认为样本x为异常样本,即1/n n i=1 (E i(x) ) 。其中:n为集成中的个体神经网络的个数; (015 1)为比例阈值。 实验分析 基于以上模型,笔者设计了一个通信话务预测系统。数据 集是广东某小区从2006年4月到2007年3月共一年的话务 量数据。集成中各个神经网络个体的参数设置如表1所示。 表1 神经网络个体参数设置 神经 网络 输入 窗口 输出 窗口 隐层 节点数 神经 网络 输入 窗口 输出 窗口 隐层 节点数 NN1 714, 13 NN2 1415, 14 NN32116, 15 NN42817, 16 NN5 774, 13 NN6 1475, 14 NN72176, 15 NN82877, 16 隐藏层单元数的选择参考了文献12中提到的方案: h=x+y+a 其中:h是隐藏层单元数;x是输入窗口;y是输出窗口;常数 a=110。 当网络的训练阶段完成后,通过计算预测误差,对该网络 的性能进行评价。采用平均绝对百分率误差EMAP和均方根误 差ERMS这两个指标来评价预测精度。交叉验证是衡量一种学 习方案使用在某一数据集上的误差率的标准方法。本实验采 用10折交叉验证。 部分预测结果如图2、3所示。在图2中,横坐标是天,纵 坐标是话务量。图3是预测误差。从图3可以看出,前面大部 分样本的预测误差都很小,平均绝对百分比误差为4132% ,均 方根误差为5163%。从曲线走势来看,预测序列与实际话务 序列的步调基本一致,数据也比较接近。但是,在第28天到 34天这个区间内,预测误差都很大,全部大于20%。查看原始 数据,发现第28天到34天正好是国庆黄金周。从图2的实际 话务序列可以看出,该周的每天最大忙时话务量都比较低,数 据分布也与平常不一样,而神经网络拟合的只是大部分数据的 分布规律,对黄金周的预测误差则比较大。因此,可以将黄金 周等异常序列从中筛选和分离出来。与此同时,从图3还可以 看出,异常点并不一定是绝对值超过阈值的点,而是数据分布 与常规数据分布不一致的点。 结束语 时间序列具有一定的规律性、 突发性和偶(下接第2361页) 6532计 算 机 应 用 研 究 第25卷 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. 量化计算方法,并建立网格实体行为信任机制。在此基础上提 出基于信任DBC调度算法。算法主要分两阶段,即计算信任 开销和信任开销的优化调度。算法性能和模拟实验结果分析 表明与未考虑信任(DBC)调度算法相比,基于信任( Trust DBC)调度算法明显提高了算法的综合性能 ,可一定程度为网 格提供动态安全保证。 尽管本文在信任值量化计算方面提出了反映信任变化规 律函数,该函数可有效地实现信任值的精确计算,但由于信任 值的量化计算非常复杂,如何更精确地评测网格资源交易实体 间的信任值,尚待更深入的进一步研究。注意到网格计算不断 扩大的应用领域,旨在提高网格计算安全性的信任研究无疑具 有相当意义。 参考文献: 1BUTTA R, ADABALA S, KAPADI A N,et al. Grid2computing por2 tals and security issues J .Journal of Parallel and Distributed Computing, 2003, 63 (10) : 1006210141 2AV IE D, BASDEN W, ANDREW.Evaluating trust in a public key certification authority J .Computers and Security, 2001, 20 (7) : 59226111 3FOSTER I, KESSALMAN C.The grid: blueprint for a new compu2 ting infrastructureM .San Francisco: Morgan Kaufmann Publishers Inc, 1998: 2792309. 4 L I Chun2lin, L I La2yuan.The use of economic agents under price driven mechanis m in grid resource managementJ . Journalof Sys2 tem s Architecture, 2004, 50 (9) : 52125351 5BUYYA R, ABRAMSON D, GI DDYJ. Nimrod/G: architecture for a resource management and scheduling system in a global computational gridC / / Proc of the 4th International Conference on High Perfor2 mance Computing in the Asia2Pacific Region. S . l . :IEEE Com2 puter Society, 2000: 28322891 6 BUYYA R, ABRAMSON D, VENUGOPAL S .The grid economy J .Proc of the IEEE, 2005, 93 (3) : 69827141 7 BUYYA R.Economic2based distributed resource management and scheduling for grid computingD . Melbourne: School of Computer Science and Software Engineering, Monash University, 20021 8L IChun2lin, L ILa2yuan. A distributed utility2based two levelmarket solution for optimal resource scheduling in computational grid J . ParallelComputing, 2005, 31 (324) : 33223511 9AZZED I N F, MAHES WARAN M. A trust brokering system and its application to resource mana2gement in public2resource grids C / / Proc of the 18 International Parallel and Distributed Processing Sym2 posium.Santa Fe: IEEE Computer Society, 2004: 22232. 10 AZZED I N F, MAHES WARAN M.Integrating trust into grid resource management systems C / / Proc of Parallel Processing . Washington DC: IEEE Computer Society, 2002: 47254. 11 AZZEDI N F, MAHES WARANM. Towards trust2aware resourcemana2 gement in grid computing systemsC / / Proc of the 2nd IEEE/ACM International Symposium. Washington DC:IEEE Computer Society, 2002: 4192424. 12 GU I Xiao2lin, XIE Bing, L I Yi2nan,et al.Study on the behavior2 based trustmodel in grid security systemC / / Proc of ServicesCom2 puting(SCC 2004). WashingtonDC: IEEE Computer Society, 2004: 5062509. 13 L IKe2qin. Job scheduling and processor allocation for grid computing on metacomputersJ .Journal of Parallel and Distributed Com2 puting, 2005, 65 (11) : 140621418. 14 SUN H X, LASZEWSKIV. QoS guided min2min heuristic for grid task schedulingJ . JournalofComputer Science and Technolo2 gy, 2003, 18 (4) : 4422451. 15 BEAUMONTO, CASANOVA H, LEGRAND A. Scheduling divisible loadson star and tree networks: results and open problemsJ .IEEE Trans on ParallelDistrib, 2005, 16 (3) : 2072218 16 JORGENSEN S, ZACCOUR G . A differential game of retailer promo2 tionsJ . Automatica, 2003, 39 (7) : 114521155. 17 JORGENSEN S, TABOUB I S, ZACCOUR G . Retail promotionswith negative brand image effects: is cooperation possible? J . Europe2 an JournalofOperationalResearch, 2003, 150 (2) : 3952405. (上接第2356页)然性。真实世界中时间序列数据更是受多重 因素影响。例如,对于通信话务量,它不仅与本地区的经济发 展水平密切相关,而且受到市场竞争、 资费调整、 季节变动等因 素的影响。尤其是用户流动性大、 业务突发性强,给话务的预 测带来很大的困难。 同时,时间序列本身也蕴涵着丰富的有规律的信息,这些 都可以被加以利用。笔者通过自相关分析方法挖掘时间序列 本身蕴涵的变化特性,并利用这些变化特性来构造不同的神经 网络个体。由于每个个体学习器的网络结构各不相同,且蕴涵 了不同尺度的序列信息,这样构造出来的个体网络具有较高的 差异度。个体差异度的增大可以有效地提高预测系统的泛化 能力。现场的调试结果表明,该预测模型能有效地对移动通信 话务量进行预测。 参考文献: 1SHAUN N, RUEY P. Combining artificial neural networks and statis2 tics for stock2market forecasting C / / Proc of ACM Conference on Computer Science. New York: ACM Press, 1993: 2572264. 2CORTEZ P, R I O M, ROCHA M,et al.Internet traffic forecasting using neural networksC / / Proc of International Joint Conference on NeuralNetworks . 2006: 263522642. 3LEE R S T .iJADE stock advisor: an intelligent agent based stock prediction system using hybrid RBF recurrent network J .IEEE Trans on System s, Man, and Cybernetics, 2004, 34 (3) : 4212 428. 4I BA H, SASAKI T . Using genetic programming to predict financial dataC / / Proc of IEEE Congress on Evolutionary Computation. Pis2 cataway: IEEE Press, 1999: 2442251. 5McGON IGAL D, I ONESCU D. An outline for a Kalman filter and re2 cursive parameter estimation approach