一个基于基因表达式编程的时间序列预测新方法1ANovel

一个基于基因表达式编程的时间序列预测新方法1陈宇，唐常杰，钟义啸，段磊，乔少杰(四川大学计算机学院成都610065)[e-mail]摘要时间序列分析是数据挖掘和应用统计学中的一类典型问题。本文融合传统统计学方法与新的基因表达式编程（GEP）技术，提出了Fibonacci加权平均滑动窗口预测算法（FWASWPM）和差分平均预测算法（DAPM）算法，有效地解决了传统方法需要过多先验知识的不足及GEPSWPM算法嵌入维数难以制定的缺点。本文的主要贡献是：(1)根据自相关系数将时间序列划分为弱变化时间序列和强变化时间序列。(2)对弱变化时间序列提出了Fibonacci加权平均滑动窗口预测算法FWASWPM。(3)对强变化时间序列，提出了通过n步相关序列来指定嵌入维的差分平均预测算法DAPM。(4)通过详尽的实验验证了算法的有效性，在相同的进化代数中得到的预测结果精度比SWPM提高了约12.2%。关键词基因表达式编程自相关系数嵌入维滑动窗口ANovelApproachesforTimeSeriesPredictionBasedonGeneExpressionProgrammingCHENyu,TANGChang-jie,ZHONGYi-xiao,DUANLei，QIAOShaojie(SchoolofComputerScience,SichuanUniversity,Chengdu610065)AbstractTimeSeriesPredicationisatypicalandsignificanttaskindataminingandappliedstatistics.TraditionalstatisticalmethodsaswellasthenewlyemergingGEP(GeneExpressionProgramming)technologyhavebeenappliedtoit.However,statisticalwaylackspowerwithlimitedpriorknowledgewhilepureGEPmethodhasdifficultyindecidingtheembeddingdimension.Inviewofthesedefects,thispaperproposestwonovelapproachescombinedwiththestatisticalmethodsandGEP.Themaincontributionsinclude:(1)ClassifytimeseriesintoMildVibratedTimeSeriesandSevereVibratedTimeSerieswithrespecttotheirself-correlationcoefficient.(2)ProposeFibonacci-WeightedAverageSlidingWindowPredictionMethodtodealwithMildVibratedTimeSeries.(3)PutforwardDifferenceAveragePredictionMethodtocopewithSevereVibratedTimeSeries.(4)ConductaseriesofextensiveexperimentstoprovetheeffectivenessofthenovelapproachesandtheirsuperioritytotheexistingSlidingWindowPredictionMethod.KeyWords:GeneExpressionProgramming,Self-CorrelationCoefficient,EmbeddingDimension,SlidingWindow1引言11基金项目：国家自然科学基金(60473071)，高等学校博士学科点专项科研基金SRFDP(20020610007号)，四川省青年软件创新工程(350号)作者简介：陈宇(1981－)，男，硕士研究生，研究方向：数据库与知识工程；唐常杰，博士生导师，教授，研究方向：数据库与知识工程，数据挖掘，钟义啸、段磊，乔少杰：硕士研究生时间序列预测（TimeSeriesPrediction）是数据挖掘中的一类典型问题，被广泛地应用在金融经济，气象水文，信号处理，灾害预警等领域。作为概率统计学科中应用性较强的一个分支，时间序列分析有了比较完整的理论系统。人们提出了AR模型，MA模型以及ARMA模型等对于实践都有极为重要的指导意义。然而，上述已有的模型从本质上来讲都是线性模型，且统计学的方法大都需要一些难以证明的先验知识。因此，对于较为复杂的时间序列，这类模型的预测结果不能满足应用的需求。随着仿生计算的兴起，人们又提出了神经网络（NeutralNetwork），遗传算法（GeneticAlgorithm）和遗传编程（GeneticProgramming）等计算模型，并取得了可喜的成果。作为遗传算法和遗传编程融合的产物，基因表达式编程（GeneExpressionProgramming,GEP）以其较快的速度，较高的预测精度而成为近年来时间序列预测中的一个热点方法。但将GEP用于时间序列预测也有其自身的缺陷，如对嵌入维（EmbeddingDimension）数的指定较为武断，缺乏统计学理论的支持等。一个新的思路是：把GEP和传统统计学方法结合起来，用于时间序列预测，扬长避短，以期取得更好的效果。本文的主要工作在于：1)建立了时变强度概念。将时间序列分为弱变化时间序列和强变化时间序列。2)对弱变化时间序列提出了Fibonacci加权平均滑动窗口预测的方法（Fibonacci-WeightedAverageSlidingWindowPredictionMethod）；对强变化时间序列提出了差分平均预测的方法（DifferenceAveragePredictionMethod）。3)通过实验验证了这两种方法的有效性。本文的余下部分组织如下：第2节介绍GEP的基本概念及思想以及将GEP用于时间序列预测的相关工作；第3节介绍了一些基本概念及强变化时间序列和弱变化时间序列的分类。第4节介绍Fibonacci加权平均滑动窗口预测方法；第5节介绍差分平均预测方法；第6节用实验验证了这两个方法的有效性及优越性。第7节总结了本文的工作，并对未来的工作做出了展望。2相关工作2.1GEP简介基因表达式编程（GeneExpressionProgramming，GEP）由CandidaFerreira于2001年12月[4]首次提出。GEP在继承遗传算法（GeneticAlgorithm，GA）和遗传编程（GeneticProgramming）的思想的基础上，创新性地提出基因型（染色体）和表现型（表达式树）既分离又相互转化的模型，克服了GA和GP的不足，提高了解决问题的能力和效率。在GEP中，基因型即演化实体是染色体（Chromosome），染色体实际就是用连接运算符（LinkOperator）连接起来的多个基因（Gene）。基因即是定长的字符串，它由头部（Head）和尾部（Tail）组成。头部包含变量和运算符而尾部只包含变量。头尾长度（分别记为h，t）有如下关系：（图不要跨页，可移动到第二页）t=h(n-1)+1QQ*－+abcd图1代数表达式与表达式树)()(dcba+×-其中n为函数集合中所有运算符的最大目数。上面的公式保证了染色体总能解码成有效的表达式树（ExpressionTree）[8]。表达式树是GEP中的表现型，它和染色体可以互相转化。例如有如下的单基因染色体（基因头部长为4，Q代表开平方运算）：012345678Q*-+abcde其对应的代数表达式和表达式树如图1所示：从图中可以看出，对表达式树进行从上到下，从左至右的层次遍历就可以得到相应的字符串，反之将字符串进行逆操作即可解码成一棵表达式树。GEP的运行和GA，GP相差无几，都是由个体构成种群（Population）进行各种遗传操作，再进行自然选择，直到找到最优解或是预定的进化代数达到为止。2.2时间序列分析简介按时间次序排列的数据？？序列X1,X2,X3,……称为时间序列。如果用x1,x2,……,xN分别表示X1，X2，……XN的观测值，则称x1,x2,……,xN为X1，X2，……XN的N个观测样本。时间序列分析的主要任务是为数据建立尽可能合理的模型，然后用模型去解释数据的统计规律，预报未来的数据。其基本思想是“过去+现状à未来”。从本质上来说，时间序列分析问题是一类特殊的符号回归问题。旨在寻找一个模型，该模型是兼容于若干自变量的若干观测值多元函数。其中自变量的数目就称为嵌入维（EmbeddingDimension）数。在数据处理中，在两个被处理的观测数据之间忽略的观测数据的个数，称为时间延迟（DelayTime）。如果它等于1，表示时间序列的每个观测数据都会被处理，如果它大于1，表示一些观测数据将会被跳过。在本文中所有的时间序列分析问题都取时间延迟为1。嵌入维后是否需要加一个数？前一个“数目”是需要的时间序列分析是统计学的一类典型问题，人们提出了很多模型，如自回归模型（AR），滑动平均模型（MA）[2，3]等等。随着仿生计算的兴起，更多的模型和方法如人工神经网络（ANN）[5]，遗传算法（GA）和遗传编程（GP）都被运用于时间序列分析。CandidaFerreira在发明了GEP方法后也将其运用于时间序列分析[4，6]，其后又有研究者采用GEP预测微分方程的方法进行预测，提出了SWPM和ODEM等方法[9]，取得了不错的效果。上述方法一般都是根据经验选择嵌入维，而嵌入维的选择的不同很可能会影响试验的结果。因此本文提出了时序强度模型，其要点是根据自相关系数选择嵌入维，把时间序列分为两种：强变化时间序列和弱变化时间序列，针对其不同特点提出了相应的方法，实验结果表明新方法提高了计算效率。3相关概念及时间序列的分类在统计时间序列分析中，平稳时间序列的方差及其相关性是两个很重要的指标，本文将之引申到一般的时间序列中：定义1（自协方差函数）：对于时间序列{Xt}={Xt:t∈N},对任意的t,s∈N，设E[Xt]=μ,设E[(Xt-μ)(Xs-μ)]=γt-s，则称实数列γt为{Xt}的自协方差函数。定义2（自相关系数）：对于时间序列{Xt}，如果它的自协方差函数为γk，则称ρk=γk/γ0为{Xt}的自相关系数。自相关系数表示了这个带预测数据和其前的历史数据的相关程度。当自相关系数很小时，表示相关程度很小，即可以理解为不由该历史数据决定。从定义可知，ρ0一定为1。定义3（n步相关序列）：如果时间序列{Xt}的自相关系数ρk（k=0,1,2……）中，如果对于n∈N，|ρn|小于指定的（很小的）阈值ξ，则称{Xt}是n步相关序列。n步相关序列描述一个待预测的数据和几个历史数据相关的性质。从其统计学意义上我们就可以看出，n可以作为GEP时间序列预测中的嵌入维数。然而实践表明，并不是所有的时间序列都是能够找到一个比较小的n，满足ρnξ。因此，根据自相关系数的特点，本文提出两个新概念：弱变化时间序列和强变化时间序列，分而治之，提出了不同的解决方法。定义4（弱变化时间序列及强变化时间序列）：设m是由领域知识确定的阈值，m0.{Xt}是时间序列，ρk是{Xt}的自相关系数。如果对任意的k小于一个阈值m时，ρk=0.5，则称{Xt}为关于m的弱变化时间序列，否则称{Xt}为关于m的强变化时间序列。经验表明，阈值m一般取15较为合适。GEP时间序列预测常用的滑动窗口预测法并不区分弱变化时间序列和强变化时间序列，简单但效果不一定好。定义4表明，弱变化时间序列的自相关系数较大，意味着时间序列的变化幅度比较小。对于这类时间序列，嵌入维比较难制定。常用的方法是滑动窗口预测法，本文提出了Fibonacci加权平均滑动窗口预测法，取得了更好的效果。对于强变化时间序列，时间序