（计算机软件与理论专业论文）基于模式的时间序列进化分割方法研究.pdf

基予模式静时阀序疑进化分裁方法研究 诗舞梳软终与攥论 硕士生：喻静文 指导教舞：窜鍪教授 摘要 数据挖掘是搔从大薰的数据中提取隐含的、事宠米知静、并篮潜奁有餍 的知识豹过程，怒目前国际上数据库和信息决策领域前沿的研究方向之一。 菝蔷露垮数据在金融稆辩按疲建孛静广泛使建，霹窝序露数据羧穗或鹭数据 挖掘领域孛个耢酌研究方翔。 对阕序捌分割楚憋长序列分割成不黧鬟的、有膨豹子序列檠合的过程， 是时间序列数据挖掘研究的熏螫任务之，其有广泛的应用空阏稻重癸懿磷 究价值。 嚣雩阉窿羁遴豫分害l 葵法凳搜溪逮蕊黪法耱辩阕黟瓤按舞绘豁准攘式集会 送行弹性地分割豹一种方法。在遗传算法中，适应魔函数是一个非常蘸要的 组成部分，它的设计对算法的i 殳敛速度以及最优解的静找有很大影响。粥此， 选择合适的距离魔瀑作为对闻净弼避纯分剿算法中适艨度的评嵇虢显褥至关 重要。现有豹时阙序列进化分割算法在时问序列的模式匹配上采用基于点对 意逮较瓣鞭离度蘩，这静距离度藿买蠢餐捧洼差，对镶啻数摄敏感等块点， 并怠无法处理时阕栩位差的情提。针对瑰雀距囊度爨棼在的闻慰，本文提出 三静有效的距离度攮一一包围矮积距离、时间弯曲躐璃和模式序列距离作为 适应魔的评信，并详细介缨了这三种距满度量静实现方式以及掰对应的对阕 序列表示方式。实验结果表明：基于这兰种距离度墩的方法在准确分割、收 敛速发熬及运嚣效攀上藏簸寒豹方法表魂疆鲟。 关键字。数据挖糕，酵闻序列分割，序别楣似度，模式莲配 r e s e a r c ho np a t t e r n - b a s e dt i m es e r i e se v o l u t i o n a r y 一 b e g m e n t a t i o n c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：y uj i n g w e n s u p e r v i s o r ：p r o f e s s o ry i nj i a n a bs t r a c t d a t am i n i n gi st h ep r o c e s so fe x t r a c t i n gn o n t r i v i a l ，i m p l i c i t ，p r e v i o u s l yu n k n o w n a n dp o t e n t i a l l yu s e f u li n f o r m a t i o no rp a t t e m sf r o md a t ai n1 a r g ed a t a b a s e n o wi t s c o n s i d e r e da so n eo ft h ea d v a n c er e s e a r c h e si nt h ef i e l d so fd a t a b a s em a di n f o r m a t i o n d e c i s i o ns u p p o r ti nt h ei n t e r n a t i o n a l a st h ei n c r e a s i n gu s eo ft e m p o r a ld a t ai nt h e f i n a n c i a la n dt e c h n o l o g i c a la p p l i c a t i o n s t i m es e r i e sd a t am i n i n gh a sb e e no n eo ft h e f o c u s e so fc u r r e n td a t am i n i n gr e s e a r c h a so n eo ft h ei m p o r t a n tt a s k si nt i m es e r i e sd a t am i n i n g t i m es e r i e ss e g m e n t a t i o n i st os e g m e n tl o n g t e r mt i m es e r i e si n t op i e c e so fs h o r t t e r ms e r i e s t h u si ti s s i g n i f i c a n ti nt h e o r ya n di sv a l u a b l ei na p p l i c a t i o n s t i m es e r i e se v o l u t i o n a r ys e g m e n t a t i o ni sam e t h o do fu s i n ge v o l u t i o n a r ya l g o r i t h m t os e g m e n tt i m es e r i e sf l e x i b l yw i t has e to fp a t t e mt e m p l a t e s f i t n e s sf u n c t i o ni sa n i m p o r t a n tc o m p o n e n ti nt h eg e n e t i ca l g o r i t h ma n di t sd e s i g nw i l lg r e a t l ya f f e c t st h e c o n v e r g e n c es p e e da n ds e a r c ho fb e s ts o l u t i o n t h u s i t sc r u c i a lt oc h o o s eas u i t a b l e d i s t a n c em e a s u r ef o rt h ef i t n e s se v a l u a t i o ni nt i m es e r i e se v o l u t i o n a r ys e g m e n t a t i o n t h ee x i s t i n gt i m es e r i e se v o l u t i o n a r ys e g m e n t a t i o na l g o r i t h ma d o p t st h ed i r e c t p o i n t t o p o i n tc o m p a r i s o n ( d i r e c tp o i n t t o - p o i n td i s t a n c e ，d p p d ) t oe v a l u a t et h e s i m i l a r i t yb e t w e e nt w os e r i e s t h i sd i s t a n c em e a s u r ei sb r i t t l ea n ds e n s i t i v et on o i s e d a t a m a t sm o r e i td o e s n tw o r kw h e nt h e r ei st i m ep h a s ei nt h et i m es e r i e s i nt h i s p a p e r , w ep r o p o s et h r e ee f f e c t i v ed i s t a n c em e a s u r e s - e n c l o s e da r e ad i s t a n c e ( e a d ) ， t i m ew a r p i n gd i s t a n c e ( t w d ) a n dp a t t e ms e r i e sd i s t a n c e ( p s d ) f o rt h ef i t n e s s e v a l u a t i o n 、i n t r o d u c et h ei m p l e m e n to ft 1 1 r e e d i s t a n c em e a s u r e sa n dt h e c o r r e s p o n d i n gt i m es e r i e sr e p r e s e n t a t i o nf o re a c hm e a s u r ei nd e t a i l e x p e r i m e n t a l r e s u l t ss h o wt h a t ：t h em e t h o d sb a s e do nt h r e ep r o p o s e dm e a s u r e so u t p e r f o r mt h e d p p d si na c c u r a t es e g m e n t ，c o n v e r g e n c es p e e da n dr u n n i n gt i m e k e y w o r d s ：d a t am i n i n g 、t i m es e r i e ss e g m e n t a t i o n 、s e r i e ss i m i l a r i t y 、p a t t e r n m a t c h i n g 基于模式的时问序列进化分割方法研究 第1 章引言 在本章，我们首先介绍数据挖掘技术的产生和发展，以及数据挖掘的基本步 骤和应用现状。然后阐述数据挖掘技术在时序数据中应用的价值和意义，并介绍 时间序列数据挖掘现在面临的主要问题。本章的最后介绍论文的研究方法、研究 成果以及论文的结构。 1 1 数据挖掘的产生与发展 在过去的三十年中，计算机硬件快速稳定的发展导致了功能强大的计算机、 数据收集设备和存储介质的大量供应。而这些技术大大地推动了数据库技术和信 息产业的发展，也使得人们可以方便地存储、管理和查询海量的数据。快速增长 的海量数据收集、存放在大量的大型数据库中。这些海量数据因缺乏强有力的分 析工具而无法有效地被人们理解和利用，有的甚至成为了“数据坟墓”一难得再 访问的数据档案。面对着浩如烟海的信息一个新的挑战提出了：“如何才能不被 信息的汪洋大海所淹没，从中及时发现有用的知识，提高信息利用率呢? ”。显 然传统的数据库检索和查询难以满足人们需要，虽然伴随着数据仓库出现的o l a p ( 联机分析处理) 技术具有总结、概化和聚集的功能，可以从不同角度观察数据， 支持多维分析和决策支持，但它不能进行更深层次的分析，挖掘出大量数据背后 所蕴藏的知识。在这样的背景下，数据挖掘技术应运而生并得到了蓬勃发展，逐 渐显示出其强大的生命力。 数据挖掘( d a t am i n i n g ，o m ) 又称为知识发现( k n o w l e d g ed i s c o v e r yf r o m d a t a b a s e ，l 【d d ) 是指从大量的、不完全的、有噪声的、模糊的、随机的数据中 提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程， 是目前国际上数据库和信息决策领域的最前沿研究方向之一 1 。作为一门交叉 学科，数据挖掘集成了许多学科中成熟的工具和技术，包括数据库技术、统计学、 机器学习、模式识别、人工智能等，具有广泛的应用背景。数据挖掘的主要过程 基于模式的时间序列进化分割方法研究 是将原始数据转化成为知识，其中包含了数据预处理和数据结果的后期加工等一 系列步骤。图1 - 1 为知识发现过程示意图。 一一1 i 一上j 一一土一j 图卜1 知识发现过程 数据挖掘的主要流程包括： ( 1 ) 数据清理：消除噪声或不一致数据。 ( 2 ) 数据集成：多种数据源可以组合在一起。 ( 3 ) 数据选择：从数据库中检索与分析任务相关的数据。 ( 4 ) 数据变换：数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作。 ( 5 ) 数据挖掘：基本步骤，使用智能方法提取数据模式。 ( 6 ) 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式。 2 据-ill姚一i l l 燃 基于模式的时间序列进化分割方法研究 ( 7 ) 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识。 k d d 一词在1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会议上被首次 提出之后，数据挖掘在学术界和工业界的影响越来越大。1 9 9 5 年国际k d d 组委 会把k d d 专题讨论会更名为国际会议，并在加拿大蒙特利尔市召开了第一届k d d 国际学术会议，以后每年召开一次。近年来，k d d 在研究和应用方面发展迅速， 尤其是在商业和银行领域的应用比研究的发展速度还要快。 目前，国外数据挖掘的发展趋势及其研究方面主要有：对知识发现方法的研 究进步发展，如近年来注重对 a y e s ( 贝叶斯) 方法以及b o o s t i n g 方法的研究 和提高；传统的统计学回归法在k d d 中的应用；k d d 与数据库的紧密结合。在应 用方面包括：k d d 商业软件工具不断产生和完善，注重建立解决问题的整体系统， 而不是孤立的过程。用户主要集中在大型银行、保险公司、电信公司和销售业。 国外很多计算机公司非常重视数据挖掘的开发应用，i b m 和微软都成立了相应的 研究中心进行这方面的工作，此外，一些公司的相关软件也开始在国内销售，如 p l a t i n u m 、b o 以及i b m 。国内从事数据挖掘研究的人员主要在大学，也有部分在 研究所或公司。所涉及的研究领域很多，一般集中于学习算法的研究、数据挖掘 的实际应用以及有关数据挖掘理论方面的研究。 1 2 时间序列数据挖掘 自然界以及我们社会生活中的各种事务都在运动、变化和发展着，将它们按 时间顺序记录下来，我们就可以得到各种各样的时间序列数据。作为一类重要的 高维数据类型，时间序列广泛应用于经济、科技、工业、教育、交通以及军事等 社会各个领域，如金融证券市场中每天股票的价格变化：商业零售行业中某项商 品每天的销售额；气象预报研究中某一地区的每天气温与气压的读数；以及生物 医学中某一症状病人在每个时刻的心跳变化等等。随着各种时间序列数据大规模 地增长，如何对这些时间序列数据进行分析，揭示其背后隐藏的价值信息，使其 帮助人们正确认识事务并据此做出科学的决策，已经引发了数据挖掘领域的广泛 关注，基于时间序列的数据挖掘成为一个新的热点。 基于模式的时间序列进化分割方法研究 从m i c h a e lt r o s e n s t e i n 2 1 等人提出了一种从时间序列中发现“概念 ( c o n c e p t ) ”的方法开始，这可以算得上一种时间序列数据挖掘的雏形，许多学 者开始了时间序列挖掘的研究。gd a s 等人【3 】研究从时间序列中发现规则的方 法；h a n j i a w e i 等人【4 】采用数据挖掘技术对时间序列数据库中的时序进行周期片 段和部分周期片段研究；h e i l d dm a n n i l a 等人【5 】在对无线通讯网络故障管理数据 库进行处理时提出了从事件序列进行模式发现的问题。随着人工智能、机器学习 等信息科学的飞速发展，越来越多的文献开始集中在时间序列的关联与序列分 析、聚类分析、异常检测、分割以及相似性查找等研究领域【6 1 2 。这些挖掘算 法在研究中主要面临时间序列表示方式、时间序列分割和时间序列相似性度量等 几个问题。 1 2 1 时间序列表示 时间序列表示是时间序列挖掘的一个基础和关键问题。选择合适的时间序列 表示方式一方面可以降低时间序列数据维度，为进一步的分析带来方便，另一方 面可以更容易反映序列的本质，比如表示方式能反映序列的幅度、波动频率、趋 势、极值点等特征，则可大大加深对序列的理解和把握，为进一步分析、比较奠 定基础。早期研究提出对序列进行时频变换，通过前面几个高能量的系数来刻画 序列【1 3 】，这么做丢失信息较少。后来k e o g h 1 4 ，y i 1 5 等人提出用滑动窗1 3 中 的均值表示时间序列的方法在一定程度上实现了时间序列的有效降维。常见的分 段线性近似及其变形利用线性拟合函数对分段进行近似【1 6 】【1 7 】。此外， l a n d m a r k s i s 、i m p o r t a n t p o i n t 1 9 等时间序列表示方法也能很好地突出序列中的 极值点等主要特征。 1 2 2 时问序列分割 所谓时间序列分割是将长序列分割成不重叠的、有序的子序列集合的过程。 在时间序列数据挖掘中有很多问题的求解过程都需要用到时间序列分割算法。时 间序列通常用连续数值的变量表示，针对时间序列的数据挖掘首先要面临的问题 就是如何将连续数值表示的时间序列抽象成符号表示的符号序列。简单的符号化 方法是将时间序列分割后用函数或符号来表示其分段【3 ，2 0 ，2 1 ，2 2 】。此外，时间序 4 基于模式的时间序列进化分割方法研究 列的事件点检测、建模表示、分类聚类、关联规则以及周期模式挖掘等问题 2 3 2 7 】 都需要用到时间序列分割算法。由此可见，时间序列分割是进行模式挖掘的一个 基础性问题，对挖掘的结果有着举足轻重的影响。但是如何合理的分割，却不是 一个容易的问题。目前采取的常见分割方法主要分为三类： ( 1 ) 滑动窗口方法：不断向子序列段填充数据，直至超过某个累计误差限制。 这种方法一个明显的缺点是不但效率低，而且由于事实上序列中的模式 长度是有长有短的，等宽度的一刀切方法过于武断。 ( 2 ) 自顶向下方法：考虑时间序列每种可能的分割并采用最佳分割方案。测 试每个分段是否满足用户定义的误差阈值，如果不满足则算法递归分割 时间序列直至到达某个终止条件。自顶向下分割方法及其变形被广泛地 应用于图像处理，分类、时间序列查询等方面。 ( 3 ) 自底向上方法：与自顶向下方法相反，算法从最小的符合要求的分段开 始，两两不断地合并，直至达到某个停止条件为止。在数据挖掘领域， 该方法被扩展用于支持不同类型的时间序列数据挖掘任务。 1 2 3 时间序列相似性度量 时间序列相似性度量是时间序列数据挖掘的一个重要问题，是整个时间序列 知识发现的基础性工作。时间序列索引、模式匹配、相似度搜索、聚类、关联规 则等许多挖掘工作都是建立在时间序列相似性度量问题基础上。 关于时间序列相似性度量方法的研究比较多。e u c l i d e a n 距离和坤距离因其 简单易算和适合大规模运算而常被人们用于计算序列的相似度。但是这些距离度 量鲁棒性差，对数据在时间轴的形变缺乏辨识能力以及对噪声数据敏感。为了解 决这些问题，a g r a w a l 等 2 8 1 在e u c l i d e a n 距离基础上进行扩展，给出了一种更广 义的时间序列相似性定义。时间弯曲距离最早被用在语音识别中【2 9 】，由于它允 许序列在时间轴上的偏移，即序列各点不要求一一对应，并且能够计算不同长度 序列之间的距离，有效地消除了欧氏距离的缺陷。为此，许多研究者提出使用时 间弯曲距离计算序列相似度。但是时间弯曲距离的计算量很大，需改进后用于时 间序列挖掘【3 0 】。此外，常用于时间序列相似性搜索的还有特征参数距离、相关 基于模式的时间序列进化分割方法研究 系数距离、模式距离等度量方法。 1 3 本文的主要工作 本文对时间序列挖掘中的股票时间序列分割问题进行研究。在证券交易中， 寻找并分析股票时间序列中出现的技术模式对于帮助证券投资者预测并指导其 投资有重要的价值和意义。因此，这就需要我们设计一个合适的分割算法，将股 票时间序列中出现的那些已知的技术模式准确地分割出来。股票时间序列分割问 题的求解涉及到全局优化的思想，即如何分割股票时间序列才能使得结果分段中 出现的技术模式最多。f u - l a i ，t a k - c h u n g , v m c e n t , r o b e r tw p l u k 等人【3 1 】提出 的时间序列进化分割算法使用遗传算法并采用基于点对点比较的距离度量作为 适应度函数评估对股票时间序列进行分割。针对现有的股票时间序列进化分割算 法，本文重点研究算法适应度函数中用于评估序列相似度的距离度量的选择以及 相应的时间序列表示等问题。 对于距离度量的选择，本文分析传统基于点对点比较距离度量的不足，提出 包围面积距离、时间弯曲距离、模式序列距离三种距离度量作为适应度函数对序 列的相似性进行评估，并对应这三种距离度量，给出相应的时间序列表示方式。 实验结果表明，基于这三种距离度量的方法比基于点对点比较距离度量的方法在 准确分割、收敛速度以及运行效率上表现要好。 本文以下章节的内容安排如下：第2 章简要介绍遗传算法的思想基础、基本 概念、一般流程和主要操作的设计；第3 章介绍时间序列进化分割算法的主要内 容，包括进化分割算法的框架流程、时间序列表示的方式和作为序列相似性度量 的距离公式，并分析现有股票时间序列进化分割算法的不足之处，给出改进分割 算法性能效果的三种距离度量作为适应度函数评估，及三种相应的时间序列表示 方式。第4 章给出基于三种新的距离度量的方法与原方法的对比实验和结果分 析。第5 章对本文所做的工作进行总结，并指出下一步研究的方向。 6 基于模式的时间序列进化分割方法研究 第2 章遗传算法概述 自然界的生物体在遗传、变异和选择的作用下，不断地从简单到复杂、从低 级向高级进化和发展。大自然是人类灵感的源泉，将生物界提供的方法应用于实 际问题求解已被证明是一个成功的途径。达尔文进化论中“优胜劣汰，适者生存” 的思想引发了许多科学家的兴趣，人们发现隐藏在自然选择背后的实质是一种优 化的思想。演化计算( e v o l u t i o n a r yc o m p u t a t i o n ，e c ) 就是基于这种思想而发 展起来的一种通用问题求解方法。演化计算具有三大分支，即遗传算法( g e n e t i c a l g o r i t h m , g a ) ，演化策略( e v o l u t i o n a r ys t r a t e g y ，e s ) 和演化规划 ( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 1 9 7 5 年h o l l a n d 在研究自然和人工系统的 自适应行为中，提出并逐渐发展起来一种广为应用，高效的全局优化搜索箕法。 以后，h o l l a n d 等人又对该算法加以推广，应用到优化及机器学习中，形成了遗 传算法。六十年代柏林工业大学的i r e c h e n b e r g 和h p s c h w e f e l 进行风洞 实验时，利用生物变异的思想来随机改变描述物体形状的参数，取得较好结果并 对此进行深入研究，形成了演化计算的另一分支一一演化策略。同年代，lj f o g e l 等人在设计有限态自动机时借用进化思想对一组有限自动机进行进化，并 ， 根据该方法提出了演化规划 3 2 。 遗传算法这一术语首次被提出是在b a g l e y 的1 9 6 7 年关于自适应下棋程序的 论文中，在这篇论文中b a g l e y 应用遗传算法来搜索下棋游戏评价函数的参数集， 但是他当时使用的遗传算法不同于我们现在使用的遗传算法。1 9 7 5 年h o l l a n d 出版了遗传算法历史上的经典著作“a d a p t a t i o ni nn a t u r a la n da r t i f i c i a l s y s t e m s ”，系统阐述了遗传算法的基本理论和方法，并提出了模式定理( s c h e m a t a t h e o r e m ) 3 3 】，证明在遗传算子选择、交叉和变异的作用下，具有低阶、短定 义距以及平均适应度高于群体平均适应度的模式在子代中将以指数级增长，这里 的模式是指某一类字符串，其某些位置有相似性。同年，h o l l a n d 的学生d ej o n g 完成了他的博士论文。a na n a l y s i so ft h eb e h a v i o ro fac l a s sg e n e t i c a d a p t i v es y s t e m s ” 3 4 ，将遗传算法应用于最优化问题，并将h o l l a n d 的模式 理论与他的计算试验结合起来，指出了选择、交叉和变异操作的重要性并进一步 7 基于模式的时间序列进化分割方法研究 完善了这三个操作，提出了一些新的遗传操作技术。 进入八十年代后，遗传算法得到蓬勃发展。以遗传算法，进化计算为主题的 多个国际会议在世界各地定期展开，有关遗传算法基础理论的学术活动也很活 跃。遗传算法不仅理论研究得到迅速发展，而且还被广泛地应用于社会和生活的 各个领域。1 9 8 3 年，h o l l a n d 的学生g o l d b e r g 将遗传算法应用于管道煤气系统 的优化，很好地解决了这一非常复杂的问题。1 9 8 9 年，g o l d h e r g 出版了“g e n e t i c a l g o r i t h m si ns e a r c h ，o p t i m i z a t i o na n dm a c h i n el e a r n i n g ”一书，这本书 对遗传算法理论及其多领域的应用展开了较为全面的分析和例证，被遗传算法领 域多次引用，为遗传算法领域奠定了坚实的科学基础。八十年代中期，a x e l r o d 和f o r r e s t 合作，采用遗传算法研究了博弈论中的一个经典问题一囚徒困境。在 机器学习方面，h o l l a n d 自提出遗传算法的基本理论后就致力于研究分类器系统 ( c l a s s i f i e rs y s t e m ) ，利用遗传算法技术作为规则发现方法应用于分类系统， 并和s a n t af e 的a r t h u r 等人合作，用分类器系统模拟了一些经济现象，得到了 满意的结果。 九十年代以后，随着遗传算法研究的不断升温，其理论不断成熟完善，遗传 算法在函数优化、自适应控制、组合优化、模式识别、机器学习、规划策略、信 息处理和人工生命等领域的应用取得了令人瞩目的成果，展现了它的优越性和魅 力，从而也确定了它在现在的智能计算技术中的关键地位。 2 1 遗传算法的思想基础和基本概念 遗传算法的基本思想起源于d a r w i n 进化论和m e n d e l 的遗传学说。d a r w i n 进化论最重要的思想是“适者生存”。它认为每个物种在进化的过程中会越来越 适应环境。后代既继承父代的基本特征又会产生一些异于父代的新变化。在环境 变化时，只有那些能适应环境的个体特征才会被保留下来。m e n d e l 遗传学说最 重要的理论是基因遗传原理。它认为遗传是以密码的方式存在于细胞之中，并以 基因的形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质，所以， 每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应 8 基于模式的时问序列进化分割方法研究 于环境的后代。经过存优去劣的自然淘汰，适应度高的基因结构得以保存下来。 2 i 1 遗传算法的基本概念 由于遗传是由进化论和遗传学机理而产生的直接搜索优化方法，因此遗传算 法中要用到进化论和遗传学中的概念，主要的概念包括如下： 染色体( c h r o m o s o m e ) ( 又称个体) ：它是遗传算法中运行的最基本的单位，是 个体的表现形式。染色体由多个遗传因子( 基因) 组成，在算法中表现形式为二 进制串。 基因( g e n e ) ：染色体中的元素，表示不同的特征。在二进制串中基因由一个数 位来表示。 种群( p o p u l a t i o n ) ：个体的集合称为种群。种群中个体的数目称为种群规模。 适应度( f i t n e s s ) ：个体对环境的适应程度。 适应度函数( f i t n e s sf u n c t i o n ) ：染色体到适应度的映射关系。 选择( s e l e c t i o n ) ：遵循选择优胜个体，淘汰劣质个体的原则，以一定概率从 种群中选若干个体的操作。 复制( r e p r o d u c t i o n ) ：细胞在分裂时，新细胞继承旧细胞中某些性状的过程。 交叉( c r o s s o v e r ) ：是模仿自然界有性繁殖的基因重组过程，即在两个染色体 的某一个相同位置处d n a 被切断，其前后两串分别交叉组合形成两个新的染色 体。其作用是将优良的基因传递给下一代，并且生成结构更为复杂的新个体。 变异( m u t a t i o n ) ：细胞复制中产生新个体的现象。变异源自于自然界生物体进 化过程中染色体某一位基因发生改变的现象，其实质是子代基因按小概率扰动产 生的变化。 2 1 2 遗传算法的基本原理 遗传算法是一种受生物进化启发的学习方法，它不是从一般到特殊或从简单 到复杂地搜索假设，而是通过变异和重组当前己知的最好假设来生成后续假设。 9 基于模式的时间序列进化分* 4 方法研究 每一步更新被称为当前群体的一组假设，方法是通过使用目前适应度最高的假设 的后代替代群体的某个部分。这个过程形成了假设的生成并测试柱状搜索，其中 若干个最佳当前假设的变体最有可能在下一步被考虑。遗传算法以编码空间代替 问题的参数空间，以适应度函数为评价依据，以编码群体为进化基础，以对群体 中个体位串的遗传操作实现选择和遗传机制，建立起一个迭代过程。 遗传算法把问题的解表示成。染色体”，在算法中也就是二进制编码的串。 并且在执行遗传算法之前，给出一组“染色体”作为假设解。然后，把这些假设 解置于所要解决问题的“环境”中，并按“适者生存”的原则，从中选择出较适 应环境的个体进行复制、交叉和变异操作以产生更适应环境的下一代群体。这样， 经过一代代进化后，群体最后就会收敛到一个最适应环境的个体上，它就是问题 的最优解。显然，遗传算法是一种全局最优的算法，它通过进化和遗传机理，从 给出的原始解群体中，不断进化产生新的解，最后收敛到一个特定的串，求得问 题的最优解。 2 2 遗传算法基本流程 遗传算法在整个进化过程中的遗传操作是随机的，但是在整个进化过程中它 有效地利用历史信息来推测下一代期望性能有所提高的寻优点集，不断进化，最 后收敛到一个最适应环境的个体上，求得问题的最优解。遗传算法涉及五大要素； 参数编码、初始群体的设定、适应度函数的设计、遗传操作的设计和控制参数的 设定。 标准遗传算法的基本流程如图2 - 1 所示： l o 基于模式的时问序列进化分割方法研究 图2 - l 标准遗传算法基本流程图 遗传算法基本流程如下： ( 1 ) 选择编码策略，对所要解决的问题进行编码，把参数集合x 和值域 转化为位串结果空间s 。 ( 2 ) 定义适应度函数f ( x ) ，适应度大小表示了该个体的好坏。 ( 3 ) 确定遗传策略，包括确定种群大小n 、选择、交叉、变异方法，以 及确定交叉概率r 、变异概率p - 等遗传参数。 ( 4 ) 随机初始化种群p 。 基于模式的时间序列进化分割方法研究 ( 5 ) 计算种群中个体位串编码后的适应度。 ( 6 ) 按照遗传策略，运用选择、交叉和变异算子作用于种群，形成下一 代种群。 ( 7 ) 判断群体性能是否满足某一指标，或者已完成预定最大遗传次数， 不满足则返回步骤( 6 ) ，或者修改遗传策略再返回步骤( 6 ) 2 3 遗传算法中关键操作设计 编码策略和适应度函数设计是遗传算法的两个关键的部分，对进化过程和结 果有着重要影响。虽然遗传算法具有鲁棒性，对编码的要求并不苛刻，然而，编 码的策略或者方法对于遗传算子，尤其是对于交叉和变异算子的功能和设计有很 大的影响。因此，作为遗传算法流程中第一步的编码是遗传算法中需要认真研究 的问题。适应度函数是用来区分群体中个体好坏的标准，是自然选择的唯一标准。 选择的好坏直接影响算法的优劣，因此适应度函数的设计至关重要，直接影响到 遗传算法的收敛速度以及能否找到最优解。下面我们具体介绍下这两个关键操作 的设计。 2 3 1 编码表示 在遗传算法中，染色体的表现形式通过编码机制来实现。编码就是将问题的 解用一种码来表示，从而将问题的状态空间与g a 的码空间相对应，这很大程度 上依赖于问题的性质，并将影响遗传操作的设计。由于g a 的优化过程不是直接 作用在问题参数本身，而是在一定编码机制对应的码空间上进行，因此编码的选 择是影响算法性能与效率的重要因素。 对于具体问题的编码，目前没有统一的编码方法。对于具体问题，如何设计 一个高效完美的编码方案是遗传算法的难点之一，也是当前遗传算法研究的重要 课题。d ej o n g 在 3 4 中提出了两个操作性强的实用编码原则： 编码原则一( 有意义的积木块编码原则) ：应使用能够易于产生与所求问题相关 基于模式的时间序列进化分割方法研究 的且具有低价、短定义长度模式的编码方案； 编码原则二( 最小字符集编码原则) ：应使用能使问题得到自然表示或者描述的 具有最小编码字符集的编码方案。 在原则一中所提到的模式是指具有某些基因相似性个体的集合，而具有短定 义长度、低价且适应度高的模式又称之为构造优良个体的积木块或基因块。这个 原则事实上是符合h o l l a n d 所提出的模式定理的。 原则二是从字符集的大小上考虑编码方案。常见的二进制编码方案是符合了 最小编码字符集原则，包含了最大的模式数，使得在确定规模的群体中参与算法 处理的模式数最多，一直为研究者所喜欢。 人们经常用到的编码方式如下： 1 二进制编码 二进制编码是遗传算法中最为常见的编码机制。它所用到的字符集是二进制 符号：0 和1 所组成的符合集 0 ，1 ) ，由二进制编码所构成的染色体是由一串0 、 1 符号所组成的符合串。 二进制编码步骤： ( 1 ) 根据具体问题确定待寻优的参数。 ( 2 ) 对每个参数确定它的变化范围，并用一个二进制数来表示。例如， 若参数a 的变化范围为。，口一】，用m 位二进制数b 来表示，则二 者之间满足： 口- 口- + 南( a m - - ) 这时参数范围的确定应覆盖全部的寻优空间，字长m 的确定应在满足 精度要求情况下尽量取小的m ，减小遗传算法计算的复杂性。 ( 3 ) 将所有表示参数的二进制字串接起来组成一个长的二进制字串。该字 串的每一位只有0 或1 两种取值。该字串即为遗传算法的操作对象。 二进制编码机制有着操作简单，便于交叉操作和变异操作，符合最小字符集 基于模式的时间序列进化分割方法研究 编码原则等优点。 2 实数编码 对于一些问题的表现形式是实向量的情形，如果使用二进制编码机制，会存 在效率低下，无法控制算法精度的缺陷，这时一般采用实数编码机制。实数编码 机制在解的表现形式上直观简单，便于遗传算法的操作，有利于引入问题相关领 域的启发信息以增强算法的搜索能力。 实数编码从理论上讲仍然可以沿用二进制编码下的各种遗传操作，因为实数 在机器中的最终表现形式仍是二进制数，但是实际应用时却很少使用这些基于二 进制编码的算子，而是针对实数编码的特性，引入其他一些遗传算子，而且实验 数据也表明，这些精心设计的针对实数编码提出的遗传算子比采用二迸制编码下 的遗传算子平均效率更高。 2 3 2 适应度函数 在生物进化过程中，“适者生存，优胜劣汰”的自然法则是通过生物物种的 环境适应能力作为衡量其质量优劣的标准来实现的。如果一个物种对周围环境具 有良好的适应能力，那么它即被认为具有优良的生存质量，则具有较大概率进行 繁衍和发展；相反一个物种对周围环境表现出不可适应性，这被认为具有较差的 生存质量，那么在物种的竞争中将处于劣势，整个物种趋向于衰退，直至消亡。 遗传算法中，衡量一个个体质量优劣的标准是适应度。如果一个个体对于所 求问题产生良好的求解结果，那么，我们就认为这个个体质量优秀，反映在适应 度上则具有较大的适应度。反之，该个体被认为是质量低劣，并具有较小的适应 度。遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数为依据，利用 种群中每个个体的适应度来进行搜索。因此适应度函数的选取至关重要，直接影 响到遗传算法的收敛速度以及能否找到最优解。 1 适应度函数的基本类型： ( 1 ) 直接以待求解的目标函数转化为适应度函数，即： 若目标函数为最大化问题 f i t ( f ( x ) ) = f ( x ) 1 4 基于模式的时间序列进化分割方法研究 若目标函数为最小化问题f i t ( f ( x ) ) 一f ( 】【) 这种适应度函数简单直观，但存在两个问题：其一可能不满足常用的轮盘赌 选择中概率非负的要求；其二是某些待求解的函数在函数值分布上相差很 大，由此得到的平均适应度可能不利于体现种群的平均性能，影响算法的性能。 ( 2 ) 若目标函数为最小问题，则 删咖卜了八蕊一 式中c 一为f ( x ) 的最大值估计。 若目标函数为最大问题，则 f i t ( f ( x ) ) = i f ( x ) o ，- 八帮 式中c 。为f ( x ) 的最小值估计。 这种方法是对第一种方法的改进，可以称为。界限构造法”，但有时存在界 限值预先估计困难、不可能精确的问题。 ( 3 ) 若目标函数为最小问题 崩叭砌2 赢珐蚧+ 卸 若目标函数为最大问题 鼢叭z ) ) 2 赢吃0 卜八功o 这种方法与第二种方法类似，c 为目标函数界限的保守估计值。 2 适应度函数设计应满足的主要条件 1 ) 单值、连续、非负、最大化。这个条件是容易理解和实现的。 2 ) 合理、一致性。要求适应度反映对应解的优劣程度。这个条件的达成往 往比较难以衡量。 3 ) 计算量小。适应度函数设计应尽可能简单，这样可以减少计算时间和空 间上的复杂性，降低计算成本。 基于模式的时间序列进化分割方法研究 4 ) 通用性强。适应度对某类具体问题，应尽可能通用，最好无需改变适应 度函数中的参数。 2 4 本章小结 遗传算法是模拟自然界的自组织、自适应、自学习过程的搜索算法，适合用 于解决全局优化问题。本章首先介绍了遗传算法的思想起源，发展过程以及基本 概念；紧接着对遗传算法的流程给出一般性的描述；最后详细介绍了遗传算法中 两个关键部分编码机制和适应度函数的设计，它们对遗传算法的搜索结果有 着至关重要的影响。 1 6 基于模式的时间序列进化分割方法研究 第3 章基于模式的时间序列进化分割方法 在证券交易中，股票市场对那些正确理解的读者的回报是巨大的，而对于那 些粗心的、麻痹的、或者“不幸运”的投资者的惩罚也是灾难性的 3 5 。正是如 此，人们一直致力于研究安全、可靠的评定市场状态及趋势的方法，以便找出正 确的股票并在适当的时间购买。技术分析是依据过去的证券交易资料( 如股票价 格曲线图) ，运用各种图形模式及量化指标，分析过去并预测未来。在数年的股 票市场研究中，技术分析越来越被专家所采用，并在股票交易市场中发挥着重要 作用。例如，在股票价格曲线中，如果局部将形成双重或多重顶( 底) 、“头肩顶” 或“头肩底”的技术模式时，此时则是买入( 或卖出) 的信号。然而，仅仅依靠 专家在曲线图中找出这些技术模式以确定交易点是非产低效的，因为每天股市都 会产生许多新的价格曲线图，而股市专家的精力是有限的。这就给我们提出一个 新的问题：能否运用先进的计算机技术让电脑代替专家帮我们从曲线图中分割出 这些重要的技术模式? 答案是肯定的。针对这一问题，f u l a ic h u n g 。t a k - c h u n g 和r o b e r t 等人 3 1 提出了一种基于进化算法的时间序列分割方法，根据用户所 给标准模式集合弹性地分割时间序列。本章首先将介绍时间序列进化分割基本算 法，然后详细分析现有算法中的关键部分一一基于点对点比较的距离度量所引发 的一些问题，最后为了解决这些问题，我们引入三种新的距离度量方法并给出其 对应的时间序列表示方式。 3 1 时间序列进化分割算法 为了形成多样的挖掘空间而从时间序列中寻找多个模式可以认为是一个最 优化问题。时间序列分割算法就是根据用户指定的一组标准模式集合，使用遗传 算法分割时间序列，使得分割的结果分段中出现的标准模式尽可能多。 1 7 基于模式的时问序列进化分割方法研究 3 1 1 时间序列进化分割算法框架 在本节中，我们将介绍用于股票数据的时间序列进化分割算法的框架。假设 ( q ) 表示用户指定的一组标准模式集合，也可以理解为股票时间序列中的技术模 式；u ( t ) 表示第t 代种群；c 。表示当前个体；p o p s i z e 表示群体规模；m a x g e n 表 示最大遗传次数；m i n f i t n e s s 表示预定义最小适应度，则时间序列进化分割算 法的框架如下： ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) 随机初始化种群u ( 1 ) ； f o rt = 1t om a x g e n ； 根据所给标准模式集合 q ) 评估当前种群u ( t ) 中每个个体c 。 的适应度； 如果当前种群中最小适应度小于m i n f i t n e s s ，则循环停止； 否则，则运用选择、交叉和变异操作产生下一代群体u ( t + 1 ) ； 以下介绍上面框架中各操作的具体实现： 1 染色体表示 标准的遗传算法通常采用二进制编码方式表示一个染色体。时间序列进化分 割算法采用了一种更为直观的编码方式，它定义一次分割中所有时间序列分割点 的集合为一个染色体，因此，染色体可以认为是时间序列一个分割方案。例如染 色体c i = 4 ，9 ，1 4 ，1 6 ，1 9 表示某个时间序列在4 ，9 ，1 4 ，1 6 和1 9 这几个时 间点被切为6 段的分割方案。也就是说，第一个分段是从时间点1 至时间点4 ， 第二个分段是从时间点5 开始到时间点9 结束，依此类推。这种灵活的编码方式 允许不同长度的染色体在进化过程中共同存在。 2 初始化群体 进化分割算法的第一步处理过程就是随机初始化一个时间点集合，以形成第 一代群体的个体。算法为了体现面向用户的特性而增加了一个用户自定义的参