（概率论与数理统计专业论文）用遗传算法估计tar模型及异常点挖掘.pdf

摘要 人们在对大量的数据进行分析的过程中经常发现一些异常的观测值，这些观 测值可能蕴含着大量有用的信息因此，异常点的探测和分析是一个有趣而重要 的数据挖掘任务 异常点在数据分析中很常见，非线性时间序列分析也不例外，异常点对于模 型的确立有着重要的影响这篇文章主要是对门限自回归模型( t a r ) 的估计，异 常点位置及其大小的确定在探测异常点的时候我们使用了透代方法它的主要 思想是先估计出t a r 模型，然后在此模型的基础上分别判断每一时刻出现异常点 的可能性，紧接着利用消除异常点影响后的观测值重新估计t a r 模型，如此迭代 直至不出现异常点为止 这里遗传算法被引入用来估计t a r 模型的门限，选择算子按照达尔文的适者 生存的机制进行选择，交叉和变异算子由基因的变异和染色体的组合引入为了使 算法每一步的最优解不被破坏，本文使用最优保留策略；为了增加群体的多样性 同时抑制早熟现象本文采用可变的变异算子这里充分运用了遗传算法是一种全 局优化概率搜索算法的特性 最后将我们的方法应用于几组模拟数据以证明我们方法对于探测异常点的类 型位置和大小是有效的 关键词：异常点门限自回归模型遗传算法适应度函数 中圈分类号，0 2 1 2 2 a m s ( 2 s 0 0 ) 主题分类；6 2 m 1 0 a b s t r a c t a b e r r a n to b s e r v a t i o n sa r eo f t e ne n c o u n t e r e di nd a t aa n a l y s i s t h e s eo b s e r v a t i o n sm a yi n - e l u d e8g r e n td e a lo fu s e f u li n f o r m a t i o n d e t e c t i n ga n di n d e n t i 聊n gt h e s eo b s e r v a t i o n sj s 缸 a t t r a c t i v ea n di m p o r t a n tt a s k o u t l i c r s & r eo f t e ne n c o a n t e di nd a t aa n a l y s i s ，n o n f i n e a rt i m es e r i e si sn oe x c e p t i o n ，a n do u t - h e r sh a v eas i g n i f i c a n ti m p a c t0 1 1t h em o d e mi d e n t i f i c a t i o n t h ep r o b l e mo fe s t i m a t i n gt a r m o d e l s ， i d e n t i f y i n gt h et i m el o c a t i o na n de s t i m a t i n gt h ea m p h t u d eo fo u t l i e r si nt h e r e s h o l d a u t o r e g r e s s i v em o d e l si sa d d r e s s e d a ni t e r a t i v em e t h o di su s e dt od e t e c to u t l i e r s t h em a i n i d e ao ft h em e t h o di sa sf o a o w s ：g i v e ni n i t i a lt a rm o d e i s ，a n a l y s et h ep o s s i b i l i t yt h a to u t f i e r s o c c u ra te a c ht i m ea n dr e m o v et h ee f f e c to ft h ei d e n t i f i e do u t h e r t h e ne s t i m a t ea g a i nt h em o d e l p a r a m e t e ro nt h ec o r r e e t e ds e r i e s ，a n di t e r a t et h ef o r e g o i n gs t e pu n t i lt h e r ei sn oo u t l i e r h e r eg e n e t i ca l g o r i t h mi sp r o p o s e dt oi n d e n t i f yt h et h e r e s h o l dp a r a m e t e r s ，a n dt h es e l e c t i o n o p e r a t o ri sf o r m u l a t e df o l l o w i n gd a r w i n sp r i n c i p l eo fs u r v i v a lo ft h ef i t t e s tt og u i d et h et r e k t h r o u g has e a r c hs p a c e t h ec r o s s o v e ra n dm u t a t i o no p e r a t o r sh a v eb e e ni n s p i r e db yt h em e c h - a n i s m so fg e n em u t a t i o na n dc h r o m o s o m er e c o m b i n a t i o n t h ea d o p t i o no ft h es o - c a l l e d ”e l i t i s t s t r a t e g y i sr e c o m m e n d e ds ot h a tt h eb e s ts t r i n go fe a c hg e n e r a t i o nc a n n o tb ed e s t r o y e db y t h em u t a t i o no re r o s s o v e ro p e r a t o r s m e a n w h i l ev a r i a b l em u t a t i o no p e r a t o ri su s e dt op r o d u c e d i v e r s es t r i n g sa n dt or e s t r a i nt h ea l g o r i t h mf r o mc o n v e r g i n gt ot h el o c a ls o l u t i o n g e n e t i ca l g o - r i t h me m b o d i si t sp r o p e r r i so f g l o b a lo p t i m i z a t i o ns e a r c h i n ga l g o r i t h mw i t hr a n d o mp r o b a b i l i t y s o m ec a s es t u d i e ss h o wt h a tt h ea l g o r i t h mi se f f e c t i v ei nd e t e c t i n go n t l i e r s l o c a t i o na n d t y p ea n di ne s t i m a t i n gt h e i rs i z e k e y w o r d s ：o u t l i e r s ；t h r e s h o l da u t o r e g r e s s i v em o d e h ；g e n e t i ca l g o r i t h m s ；f i t n e s sf u n c i o n ； 东南大学学位论文 独创性声明及使用授权的说明 一学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果尽我所知，除了文中特别加以标明和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意 二、关于学位论文使用授权的说明 东南大学，中国科学技术信息研究所国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印缩印或其他复制手段保存论文本人电 子文档的内容和纸质论文的内容相一致除在保密期内的保密论文外，允许论文 被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容论文的公布( 包括刊 登) 授权东南大学研究生院办理 签名：导师签名：日期： 第一章引言 二十一世纪是以电子信息技术为主流的时代，在日常的商业运作中蕴涵着大 量的商业信息，需要我们进行挖掘人们在对大量的关于时间序列数据处理的过 程中，所谓的关于。异常点研究也越来越受到重视 在各种各样的数据分析中，人们经常遇到一些与其它观测值相比较很不一致 的观测值，时间序列也不例外一个用作说明的例子就是发生在1 9 8 7 年l o 月1 9 的 股票市场上的大崩盘，这就是所谓的黑色星期一”，作为个特别的事件显然与 其它一大堆数据在某种程度上是不一致的时间序列中的观测值经常受到一些无 法预料的异常事件的影响，它们可能引起观测值的突变观测值的突变可能是由 数据的测量、收集和整理所产生的误差；也可能是由不寻常的事件影响了观测值 的分析，如；战争，罢工等政治或商品市场机制的突然改变及突发的经济现象( 东 南亚经济危机所带来的股票价格的剧烈波动) 、物理系统的突变等这些数据会造 成虚假的后果导致某些观测值出现异常，我们称这些非正常的观测值为时间序列 的异常点 、 异常点的探测和分析是一个有趣而重要的数据挖掘任务，识别这些异常点及 其类型具有重大意义，原因如下t 首先，异常点对于分析数据的结果具有重要影 响；比如电信行业通过识别异常点可以探寻不寻常的信用卡和电信服务等其次， 尽管有些数据经常是由测量或记录误差造成，它们可能代表一种现象，从应用领 域角度来说这一点很重要；比如医疗行业采用一种新的仪器测量人体肝功能时， 多次将肝功能正常的人诊断为异常，从仪器准确性角度说明了这种仪器的不稳定 需要改进这种最后，经过探测所确认的异常点可以导出令人意想不到的发现 自从f 奴【1 】于1 9 7 2 年首次在时问序列中提出异常点的概念以来已有许多学者对 于探测和分析时间序列中的异常点等相关问题进行了深入的研究，并取得了许多 实际效果较好的研究成果c h e na n dh u l 2 】及c h a n 3 ，给出了存在于时间序列中的四 种典型的异常点；可加性异常点( a o ) ，新生性异常点( i o ) ，水平漂移异常点( l s ) ， 暂时性异常点( t c ) 当然还存在其它类型的异常点，但基本都是这四种基本异常 点的组合异常点对于模型的参数估计有重要影响，如d e u t s c h l 4 研究了异常点对于 a r m a 模型的确认的影响，c h e na n d l i u n 研究了异常点对预测的影响等在对异常 点的理论研究中，对异常点进行探测和确定其类型是其中一个重要的研究分支 对于异常点位置已知的情形，b o xa n dt i a o n ，b e v e r i d g e 7 分别用干扰分析数 值删除的方法对异常点进行分析研究；当异常点的位置未知时，对于这种情形的异 常点的分析主要基于两种框架种是基于模型建立起来的方法，也就是说序列潜 在的模型是已知的从f o x l l 】在1 9 7 2 年对自回归模型的异常点进行探测后，c h e na n d 东南大学硕士学位论文 第一章2 l i u 2 将其方法拓展到a r m a 模型b a r n e t t 等i s 】用m c m c 的方法对异常点进行研 究另一种是基于异常点和线性插值之间的联系的非参数的方法( l j u n g l g j ；p e f i a 1 0 ) 然而在实际应用中这种使用有限插值的方法对异常点进行挖掘分析在实质上等价 于用含有充分大阶数的自回归模型对异常点进行探测 直到近年来对时间序列异常点的研究注意力才转移到对非线性时间序列异 常点的挖掘，且大多数处理非线性时间序列中异常点的方法是稳健的递归的方 法g a b r 1 1 1 对用于线性时间序列异常点挖掘的方法进行改进，并将其用于b i l i n e a r m o d e l s 对于门限模型，c h a r ta n dc h e u n g l z q 将常用于线性时间序列中的m 估计给 予改进并将其用于此类门限模型取得了很大成效本文所将要探讨的就是这种门 限模型，对门限自回归模型( t a r ) 进行异常点探测挖掘和参数估计 目前对于时间序列的研究大多限于a o 和i o 的情形，我们也将重点放在这两 种类型的分析上现实中的时间序列数据多种多样，仅仅假定其中只含单一的异 常点a o 或i o 是值得怀疑的本文我们将采取一种迭代方法首先对给定的观测值 建立一个初始模型，然后再判断可能性最大的异常点直至探测出所有的异常点， 这里我们采用由c h e n & l i u 2 1 提出的改进了的迭代方法 对于t a r 模型由于要估计的参数空间很大，我们采用遗传算法来估计t a r 模 型的参数自h o l l a n d 于1 9 7 5 年提出遗传算法以来，遗传算法已经取得了长足的发 展遗传算法是人们模拟生物在自然环境中的遗传和进化过程而形成的一种自适 应全局优化概率搜索方法它利用某种编码技术，作用于称为染色体的数字串，模 拟由这些串组成的群体的进化过程 为了阐明我们的问题，文章的结构安排如下；第二章我们将首先介绍t a r 模 型，然后给出该模型的异常点定义及挖掘方法；第三章先介绍遗传算法，然后具体 阐述如何用遗传算法估计t a r 模型；最后在第四章我们采用随机模拟的方式检验 我们方法的有效性；第五章概括本文结论，提出一些值得继续关注的问题 第二章t a r 模型异常点的定义及挖掘方法 由引言可知。识别时间序列中的异常点具有重要的意义，但对于t a r 模型究 竟什么样的点是异常点? 这是本章要阐明的问题下面我们将在第一节揭示异常 点的本质，然后在第二节给出t a r 模型的异常点的严格数学定义及其探测方法 2 1 异常点的本质 现实世界数据异常点产生的原因多种多样，通过引言可知它们可归结为以下 两类一类是在数据的度量或执行过程时由人为的因素造成的，对于这种异常点 它本身不含有有用的商业信息，就时间序列而言，这类异常点是非本质的，这时因 为它并不涉及到时间序列的内在结构另一类异常点是真正意义上的异常点，它 是真实数据的观测值，但从某种意义上它又比其它数据显得更为奇特，我们认为 它是数据变异的结果一个比较经典的例子就是一个公司的首席执行官或一个项 目经理远远高于其他雇员的工资，从而成为一个异常点这类异常点包含有用的 商业信息，是我们真正关心的我们工作的重点就在于探测出这一类的异常点， 并从中获得经验制定相应的对策 要探测异常点就要首先知道什么是异常点，这是必须弄清楚的在数据的分 析和处理过程中，经常遇到这样一些数据，它们不符合数据的一般模型在这种情 况下，我们可以用聚类分析的方法将怀疑对象与其它观测值的距离远近来判断它 是否为异常点，或者从统计诊断的角度来判断( 韦博成) 在时间序列中观测变 量相关的情形下，观测值的绝对值的大小并不是评判它为异常点的充分条件，此 时异常点的定义必须根据数据的其它特性 对非平稳序列异常点问题的处理，我们必须十分谨慎例如下面的图( 2 1 ) ， 在时刻t = 6 6 的观测值的绝对值比其它观测值的绝对值显然要大的多，但该时刻并 不是异常点，而是来自如下a r c h 模型的观测值； = 毋唧，砰= 0 0 3 + 0 9 + 象l 其中 e t ) 为服从n ( 0 ，1 ) 的独立白噪声 对于非线性的时间序列，由于它们的非线性性质，即使有些观测值与其它的 观测值有很大的差别也很难说明这些点就是异常点本文将主要研究t a r 模型的 异常点 3 东南大学硕士学位论文 第二章4 图2 1 ：a r c h 模型的1 0 0 个模拟数据 2 2t a r 模型异常点的挖掘 本节将给出t a r 序列中异常点的数学定义及其分类，然后给出如何探测t a r 序列中的异常点的类型及其异常度的大小，本文主要讨论a o 和i o 两种类型的异 常点 2 2 1t a r 序列中异常点的模型及分类 门限自回归模型( 即t a r 模型) 是由t o n g ( 1 9 7 7 ) 首先提出并应用于实际问题的， 并于1 9 8 3 ，1 9 9 0 年详实的介绍了这一类模型的实际应用背景1 1 4 1 ，l “尽管在大量 的科学研究中线性逼近起到了强大的作用，但是它在处理一些非线性问题时这种 全局性的线性逼近法则经常不恰当这时一个好的想法就是打破全局线性逼近的 法则，转向状态空间的子区间用线性逼近t a r 模型就是建立在这种。分段。线 性的基础上，实现了对其它非线性时间序列的逼近 由于t a r 模型实际上可以看成是分段的自回归模型( a r ) ，且是s d m ( s t a t e - d e p e n t e n tm o d e l s ) 模型的一种特殊形式，从而在介绍t a r 模型之前我们先引进 a r m a 模型和s d m 模型 ( a ) a r m a 模型： 来南大学硕士学位监皇 第二童5 设i x , 满足p 阶平稳自回归q 阶可逆滑动平均模型，简记为a r m a ( p ，q ) 模型 即i x , ，t = o ，4 - 1 ，为零均值平稳对问序列，适合线性随机差分方程 妒( b ) 置= o ( b ) e t ，( 2 1 ) 其中 ( b ) = 1 一咖1 口一2 8 2 一一如矿， o ( b ) = 1 0 1 b 一口2 8 2 一一如伊， b 为后移算子，即b 五= 五 b 矗= e t - k ，k = 0 ，1 ，2 ；佃) 为正态白噪声序列， 即缸独立同分布，服从n ( o ，矿) ；且庐( 口) ，o ( b ) 满足如下条件： ( 1 ) ( 曰) 与o ( b ) 无公因子； ( 2 ) 毋( b ) 的根全在单位圆外，通常称为平稳性条件； ( 3 ) o ( b ) 的根全在单位圆外，通常称为可逆性条件 其中当口= 0 时，称为p 阶自回归模型a r t ( p ) ；当p = 0 时，称为口阶滑动平均模型 b l v ( q ) ( b ) s d m 模型； 状态相依模型( s d m ) 最早由p r i e s t l e y l l q 提出，设 矾 为服从s d m 模型的时问 序列，则具有以下的形式； pq 瓤= 南( 施一1 ) x t - j + e t 一易一1 ) e t - j ， ( 2 2 ) j = 1j = l 其中向量一1 称为在t 一1 时刻的状态向量，具有下面的形式 z t 一12 ( 6 t ，- 1 ，z 1 1 ，魏一1 ) 通过对( 2 2 ) 式给与一定的限制条件，我们可以得到许多有用的模型，t a r 模 型就是s d m 模型的一种特殊形式 令巩( ) = o , j = l ，口，取状态向量z t 一1 = 飘一d ，d 称为滞后参数( d e l a yp a r a m e t e r ) 为某一固定的整数，并取奶( ) ，j = 1 ，p 如下的形式； c j c t - a ) = 拶，若n l z t d r i ，i = 1 ，k 这里正整数p 要被预先恰当的确定。且当我们取7 o = 一，仇= + o o 时，开区间 眩i ，n ) 是实轴的一个划分即此时的t a r 模型具有下面的形式， p = 母z t 。+ 缸，若r t 一1 z t d r i ( 2 3 ) j = x 为了下面章节讨论方便我们预先给出与上式等价的模型： 五= ，暖( “) ) + e t ，x ( “) = ( 置- l ，x t p ) 在这个t a r 模型中滞后参数d 。集团( r e g i m e ) 的个数k 门限n 以及a r 的 阶教p 被称为结构参数( s t r u c t u r a lp a r a m e t e r s ) ，只要这些结构参数确定了，那么我 们就可以标准的最小二乘估计得到a r 的系数c 一个最基本的问题就是( 2 3 ) 式在满足什么条件下才能产生一个平稳的遍历 解，下面的定理给出了问题的答案 令。勺= m i c i ，i 学i ，j = 1 ，p ，则有如下的定理； 定理；若 n 的密度函数在实数轴上处处为正，且如下特征函数 妒一c c l a p 一1 一一吻= 0 的根全在单位圆内，那么( 2 3 ) 式产生的时间序列是几何遍历的 在给出上述定理的证明前有必要先给出如下的预备定义和引理，为叙述方便 给出下面的记号令 同时取 毋= ( 以，一p + 1 ) ，= ( 旬，0 ，o ) 唧( u ) = 毋，若勺一1 0 ，o ra l lz x 定义2 3 ；马尔科夫链 墨们) 称为是非周期的，如果存在可测集 ( ( ) o ) ， 对于a 的任何子集b ( o ( b ) 0 ) 存在一个正整数n 使得下式成立 p x 9 ) 口i x 乒= ， o p 工艘1 b i 砖= z ) 0 下面两个引理对于确立时间序列的遍历性是很有用的，引理1 来自n m d j e l l l ； 引理2 来自t j 批h e i m ；引理3 来自c h a r ta n dt o n g t s i 理2 1 令 五) 是赋范拓扑空间上的毋不可约的马尔科夫链若转移概率 p 缸，) 是强连续的，也就是说p ( z ，a ) 从z 到任意可测集a 在$ 都是连续的。那么我 们就能得到几何遍历的一个充分条件如果存在一个紧凑集k ，正常数p 1 满足 下式 r e ( 1 l x t + 川 x t = x ) 圳，搿 引理2 2t 令 x t ) 是非周期的马尔科夫链，m 是正整数那么 ) 的几何 遍历性体现着初始序列 五) 的几何遍历性 引理2 3t 若e t 有一绝对连续的支，且密度函数处处为正，( ) 在某一有界集 上有界，则马尔科夫链 耐力) 是非周期的测度静为l e b e s g u e 测度) 不可约的 下面我们就是上述定理的具体证明： 证明；令0z i f 是如下的范数；i lz i i = 霹+ + 娣，矩阵c 具有下面的形式 c = c c ic c 2 。唧一1 唧 1000 00 10 东南大学硕士学位塑 第二章8 首先根据引理2 3 ，马尔科夫链 母) 是非周期测度不可约的从而我么 可以应用引理2 1 2 2 ，下面我么先给出俨的一个上界 令j 是阶数为p 的单位矩阵，那么矩阵 j c 的行列式为， m e l = 妒一c c l 妒一1 一一一一。印 所以上述特征函数的根式矩阵c 的特征值，令a 。是矩阵c 的晟大的特征值，那 么有0 伊i 1 ”一l k 。i 1 于是存在正常数6 1 正整数m 使得0 0 6 对于字链 ，t = 1 ，2 ，) 现在我们证明引理2 1 中的矩多满足的条件，利用 ( 2 3 ) 1 中的迭代公式，得下式 瑞+ 1 ) ：丑高，a ( 堪；) 堪，+ m - 1 畔i - a ( ) 忙臻；+ e 鼽。， ( a 1 ) 对于任何向量b = 帆，6 p ) ，令( d l ，而) = a ( x ) b ，于是 l d l i = i n l ( x ) 6 1 + + o p ( x ) b f so q l 6 l i + + 。印i b i 同时i d l = i 蚓，i = 2 ，p ，令1 6 l = ( i b d ，1 6 p i ) ，我们得下式 0 a ( x ) b l i 0 c l b 将上式重复运用于( a 1 ) 式得 i ij 曝+ 1 ) i i 1 1c i j 魄+ i i g ”一陋慰“ii i ，( a 2 ) i = 1 根据前面的0 口刈 m ， 叫f i 瑞+ i ) 础= z - p ) ，这就要求序列噩，蜀 为已知值( 未被污染) 设七0 时旬= 0 和忍= 0 ，则e 1 ，如，可由岛= 五一，( ) ) 得到 在以上条件下，条件极大似然函数为= f ( 引u ) = j 扛) f ( e ) = n ：卅1 ( 2 口矿) 一1 2 唧 卵1e 2 ) ( 2 9 ) = ( 2 丌一) 一加一2e 】【p ( 一主1 z 计1 ( e t ) 2 ， 从上式可以看出只要最小化叁p + t e t 2 ，就得到岫的极大似然估计但上式对 于线性模型更有效( p r i e s t l e y ( 1 6 】) ，这里只能渐近成立 在给定观测值及确定模型的参数的情况下，我们可以得到如下的观测误差 班= k 一，( y ( 扣1 ) ) ，t = p + 1 ，一，n( 2 1 0 ) 接下来我们分别讨论探测i o ，a o 异常点的方法，这里我们不讨论在同一时 刻同时出现这两种异常点的情形为了更明确的阐述问题，定义下式 毋= 妒4 ，l ，缸一d r ( 0 ( a ) l o 型异常点的探测 东南大学硕士学位论文 第二章1 1 得 如果 k ) 中没有异常点出现，则啸= e t ；若在t = q 时刻出现i o ，则由等式( 2 6 ) 所以得 琅= e t ，t p 东南大学硕士学位论文 第= 章1 2 从( 2 1 4 ) 式，我们可以得到 嗬 一g 岂一峋徊+ j ) = 嘞峋，j = 1 ，n q ( 2 1 5 ) 由于铀一白= 峋，令d o = 1 ， d j = 一巧蜥+ ，一”，j = 1 ，一，n q 于是有下式 嘞十j 一州垒d j 山，歹= 0 ，1 ，一，n q 由于岫的极大似然估计只需通过最小化器计l ) 2 ，从而有 ” q - 1 ” ( 缸) 2 型( 啦) 2 + ( 珊一“- ) 2 + 【债一( 债一t ) 】2 = ( 恤) 2 + ( 埒h 一而c 山) 2 ( 2 1 6 ) 要求( 2 1 6 ) 式的最小值，只需求如下关于方程的解； 皇圣草! 螳：o 仇咱 即 2 ( 嘞钾一吗c 咱) ( 一吗) = 0 整理得 喝= 紫， ( 2 1 7 ) 窿劫：从上式可以看出的估计是观测误差从t = q 向后的加权平均，但是这里 的。权可能是t a r 模型的参数，观测值以及真实误差缸的复杂函数，这在计算时 要谨慎处理 对于上面的估计，我们有以下的假设检验； t o ：观测值在t = q 时刻不出现a o 型异常点；h 1 ：观测值在t = 口时刻出现a o 型异常点 有似然比统计量 码= 东南大学硕士学位论文第二章1 3 其中 吒2 南 。，】 一田薹审 这样用假设检验的方法在给定某一置信水平下，我们就可以判断出该点是否 为a o 型异常点事实上根据f r a n c e s c ob a t t a g l i aa n dl i ao r f e i 2 1 】在原假设凰下统计 量岛渐近服从n ( 0 ，1 ) ，这样我们可以取咳。作为时问序列在第q 时刻出现i o 时的 标准误差 接下来根据( 2 1 4 ) 式，导出，k 埘一5 州的具体形式 对于出现a o 型的异常点的时间序列，在第t 时刻的。集团。( r e g i m e ) 依赖于门 限向量在第t d 时刻的值，此时对于观测值误差类似的模型为t 忱：础一皆一一p 妒一班。 3 = i 由( 2 3 ) 式及上式得 ，醅h 一。+ j ：c 3 ”一“一罐* + ，一一) + pc ，+ ，一一+ j 一。 = 1 一挚”一蜘j 幽 j = 1 ，p ( 2 1 8 ) = l 而当j p + 1 时t 黯州一5 什j = 0 ，下面我们分情况推导出嘞 一钿+ j 的具体形式： ( 1 ) j d 时，由于第t 时刻的。集团。( r e g i m e ) 依赖于门限向量在第t d 时刻的值， 所以铀j ，帅属于同一个。集团，此时有 斯“一白十，= 一巧( y q + j - d ) ，j = 1 ，一，p ( 2 ) j = d 时，此时有 嘞“一= 毋“一挚+ 窆毋一z 州一k 一壹挚蚺扛， ( 1 ) k = l k = l 对于( + 1 ) 式，若d p ，则d = 女时( 1 ) 式包含受到污染的观测值，令d p 则 嘞+ d 一钿+ d = 毋”一皆+ 蛳+ d 一 ( 毋”一挚) i d + 舶( 毋”一皆) 一岫c 2 c ”，( 2 1 9 ) 事实上c o = 0 ，p ) 是未知的，这是因为 以 在t = q 是观测不到的，那 么( 2 1 z ) 式中岫就无法得出 为了解决这个问题，我们给出两种方法； 东南大学硬士学位论文 第二童1 4 ( i ) 取也= 一c 妒，然后代入( 2 1 7 ) 式得到岫的初始估计； ( n ) 在( 2 1 7 ) 式去除第口时刻的影响得到岫的初始估计 瞄= 写d ：- 0 1 吗嘞钾+ 知d 吗啦钾 j d ：- 0 1 呼+ 譬“l 呼 在给定岣的初始估计之后通过类推的方法给出的估计z ；= 蜘一岣，进而 得到如下8 升d 近似的残差： 白= 蚺d 一铲一妒蚺州一0 ；粕 j # d 进而( 2 1 9 ) 式近似为t 嘞+ d 一白+ d 。挚一皆+ 壹虮枞( 毒；) 一挚) i d ( 2 ) + 铀( 0 ：) 一皆) 一岫毋；) ( 2 2 1 ) 不妨取砌= 0 一皆+ 蹬i d ( 毒釉一旁) + 铀( 者釉一旁) 最后当j d 时，取“= 嘞卅，而，4 d = 一d d ，得到最终的岫估计为t 岛= 舒 这样就可以求出任一时刻出现异常点时的异常度的大小，再由上面提出的迭 代算法就可以挖掘出t a r 模型的异常点及大小 第三章用遗传算法估计t a r 模型 遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法本章 首先对其作简要的介绍，然后将遗传算法引入我们讨论的问题，并具体阐述如何 用遗传算法估计t a r 模型 3 1 遗传算法 遗传算法( 简称g a ) 起源于对生物系统所进行的计算机模拟研究，最早由美国 m i c h i g a n 大学的h o l l a n d 教授发现它与传统的算法不同，大多数古典的优化算法 是基于一个单一的度量函数( 评估函数) 的梯度或较高次统计，以产生一个确定性 的试验解序列；遗传算法不依赖于梯度信息，而是通过模拟自然进化过程来搜索 最优解，它利用某种编码技术，作用于称为染色体的数字串，模拟由这些串生成的 群体的过程嘲 本质上生物进化过程就是生物体在其生存环境的约束下，通过个体的竞争， 自然选择杂交变异等方式所进行的。适者生存。的进化过程g a 正是模拟生 物的这种自然选择和群体遗传机理的数值优化方法具体的说，g a 就是把一组随 机生成的可行解作为父代群体，把适应度函数( 目标函数) 作为父代个体适应环境 能力的一种度量，经选择，杂交生成子代个体，子代个体再经过变异，优胜劣汰。 使个体的适应能力不断提高 遗传算法与其它的一些优化算法相比具有以下独特的性能： 1 ) 对可行解表示的广泛性遗传算法处理的对象不是参数本身，而是针对那 些通过参数集进行编码得到的基因个体此编码操作使得遗传算法可以直接对结 构对象进行操作所谓结构对象，泛指集合序列，矩阵，图等各种一维或二维甚 至多维结构形式的对象这一特点使得遗传算法具有广泛的应用领域 2 ) 群体搜索性许多传统的搜索算法都是单点搜索，这种点对点的搜索方 法，对于多峰分布的搜索空间常常会陷于局部的某个单峰的极值点相反，遗传算 法采用的是同时处理群体中多个个体的方法，即同时对搜索空间中的多个解进行 评估这一特点使得遗传算法具有较好的全局搜索性能也使得遗传算法本身易 于并行化 3 ) 不需要辅助信息遗传算法仅用适应度函数的数值来评估基因个体，并在 此基础上进行遗传操作更重要的是，遗传算法的适应度函数不受连续可微的限 制，其定义域可以任意设定对适应度函数的惟一要求是，编码必须与可行解空间 对应由于限制条件的减少，使得该算法的应用范围大大扩展 4 ) 遗传算法在搜索过程中不容易陷于局部最优解，即使在所定义的适应度 函数是不连续的、非规则的或有噪声的情况下，也能以很大的概率找到全局最优 东南大学硕士学位论文第三章1 6 解 5 ) 遗传算法具有固有的并行性和并行计算的能力若算法在每一代对群体 规模为n 的个体进行操作，实际上处理了大约o ( n 3 ) 个模式 表3 一l ：生物进化过程与遗传算法的对照表 自然遗传算法人工遗传算法 染色体( c h r o m o s o m e ) 解的编码( 数串( s t r i n g ) ) 基因( g e n e ) 解中每一分量的特征( 字符) 等位基因( a l l e l e )字符值( c h a r a c t e rv a l u e ) 基因座( 1 0 c u s )数串位置( s t r i n gp o s i t i o n ) 基因型( g e n o t y p e )数串空间( s t r i n gt y p e ) 表现型( p h e n o t y p e )候选解( s o l u t i o ns p a c e ) 个体( i n d i v i d u a l ) 解 适者生存在算法停止时，最优目标值的解有最大可能被留住 适应性( a d a p t a b i l i t y )适应度函数( f i t n e s sf u n c t i o n ) 群体( p o p u l a t i o n )选定的一组解( 其中解的个数为群体的规模) 复制( r e p r o d u c t i o n ) 根据适应度函数值选取的一组解 变异( m u t a t i o n ) 编码的某一个分量发生变化 交配( c r o s s o v e r )杂交算子( c r o o v e ro p e r a t o r ) 遗传算法就是在。优胜劣汰。这一自然规律指导下的一类随机并行自适应优 化方法所编的编码串相当于某群体的个体，目标函数解变量的约束条件相当于 个体所处的环境，遗传算法的运行过程就是基于个体和环境的作用进行的表3 1 的内容就是自然遗传学与人工遗传算法中所使用的基本用语的对应关系 3 1 1 编码方案和初始化 编码是应用遗传算法时要解决的首要问题，也使设计遗传算法时的一个关键 步骤在遗传算法执行过程中，对不同的具体问题进行编码，编码的好坏直接影响 选择，交叉，变异等遗传运算 在遗传算法中把一个问题的可行解从其解空间转换到遗传算法所能处理的搜 索空间的转换方法就称为编码例如，在四维特征空问中的点( 8 ，加，7 ，1 2 ) ， 东南大学硕士学位论文 第三童1 7 其每一维的范围是【o 。1 5 l ，这个点可以用一个串接起来的二进位串来表示； ( 8 ，1 0 ，7 ，1 2 ) 考( 1 0 0 0 1 0 1 0 0 1 1 1 1 1 0 0 ) 其中每个特征的十进制值通过二进制值编码，成为一个四位的基因被编码成一个 位串的所有特征的值的集合代表一个染色体既然我们有对数值的编码，那么也 就有对数值的解码，由遗传算法解空间向问题空间的转换就成为解码( d e c o d i n g ) 设得到的染色体串为z ，先将z 转化为十进制数f ，可通过解码方案把z 变为参数 解z tz = ( t m r a i n ) x 格+ r a i n ，其中m 为参数解空间的上界，r a i n 为解空 间的下界，z 为参数对应的染色体串的位数 在遗传算法中我们处理的不是一个染色体，而是一个染色体的集合，称为群 体要对群体初始化，我们可以简单的随机设定初始群体，也可以根据实际问题进 行设置群体规模( p o p u l a t i o n ) 的大小直接影响到遗传算法的收敛性或计算效率 规模过小，容易收敛到局部最优解；规模过大，会造成计算速度减低群体规模可 以根据实际情况在1 0 0 2 0 0 之间选定 3 1 2 选择操作 遗传算法使用选择算子( 复制算子) 来对群体中的个体进行优胜劣汰操作，它 是建立在对个体的适应度进行评价的基础之上选择操作的主要目的是为了避免 有用遗传信息的丢失，提高全局收敛性和计算效率选择算子的好坏直接影响到 遗传算法的计算结果 遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取那些 个体遗传到下一代群体中的一种遗传运算，用来确定重组或交叉个体，以及被选 个体将产生多少个子代个体选择操作的策略与