（模式识别与智能系统专业论文）时间序列数据挖掘的研究以及在交通流预测上的应用.pdf

摘要 摘要 交通流预测是交通诱导系统和交通控制系统的重要前提与关键，而交通流 预测问题从本质上讲是时间序列分析问题。对于时间序列，现在已经有很多种 研究和分析方法，常见的以建模分析为主，但是由于时间序列自身的复杂性和 不稳定性，传统的建模方法无法获得精确的时序系统的模型，这样便使预测变 得困难。 数据挖掘是近些年发展起来的多学科融合的数据分析技术，它从面世以来 便被应用到各个学科领域，几乎所有的数据都可以进行数据挖掘，这便给研究 者提供了一个非常好的思路，同时对时间序列进行数据挖掘也正成为当前研究 的热点之一。以交通流为代表的时间序列数据具有时变、非线性的特点，传统 方法无法获得满意结果，利用数据挖掘来找出研究对象内部的演化规律也不失 为种很好的想法。 本文在分析国内外对时间序列的研究的基础上，提出了时问序列特征模式 挖掘的框架，同时结合交通流的特点提出有效的挖掘算法，并且进行了算法实 现。框架的基本思路是将数值型的时间序列转化为易于进行挖掘的符号序列， 然后运用合适的挖掘方法对符号序列进行挖掘。将挖掘出的模式根据实际要求 进行裁减，最后提取出预测规则。 本文给出了单一时间序列特征模式挖掘t s f p m 的相关概念与定义，并对挖 掘过程作了分析与研究，在以交通流数据作为研究对象的实验中，验证了t s f p m 的有效性，并分析了算法中关键参数对算法性能的影响。 关键词时间序列；特征模式；数据挖掘；线性分段化：聚类 a b s t r a c t h b s t r a c t t h et r a f f i cf l o wf o r e c a s t i n gw h i c hi sc r i t i c a lp r o b l e mo ft r a f f i cg u i d i n gs y s t e m a n dt r a f f i cc o n t r o ls y s t e mi ni n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m s ( i t s ) l e a d st og r e a t e f f e c to nt r a f f i cg u i d i n ga n dc o n t r 0 1 i ti st h et i m es e r i e sa n a l y s i sp r o b l e mi nn a t u r e t h e r eh a v eb e e nm a n yr e s e a r c hm e t h o d sf o rt i m es e r i e sn o h a n dt h ec o m m o no n ei s m o d e l i n gm e t h o d b e c a u s eo ft h ec o m p l e x i t ya n du n s t a b i l i t yo ft i m es e r i e s ，t h e t r a d i t i o n a lm o d e l i n gm e t h o di su n a b l et oo b t a i nt h ea c c u r a t em o d e lo ft i m es e r i e s s y s t e m ，s of o r e c a s t i n gb e c o m e sm o r ed i f f i c u l t d a t am i n i n gw h i c hi sd e v e l o p i n gi nr e c e n ty e a r si sm u l t i s u b j e c td a t aa n a l y s i s t e c h n i q u ea n di ti sa p p l i e dt ov a r i o u ss t u d yf i e l d ss i n c ei te m e r g e d d a t am i n i n gc a n b ea p p l i e dt oa l o m o s ta l ld a t a ，s ot h eg o o dt h o u g h t w a yi sp r o v i d e dt or e s e a r c h e r s ， a n da tt h es a m et i m ed a t am i n i n gf o rt i m es e r i e si sb e c o m i n gr e c e n tr e s e a r c hf o c u s e s t h e r ea r et i m ev a r i e t ya n dn o d - l i n e a rc h a r a c t e r i s t i ci nt r a f f i cf l o wr e p r e s e n t i n gt i m e s e r i e sd a t a t h es a t i s f i e dr e s u l t sc a n tb ea c h i e v e db yt r a d i t i o n a lm e t h o d i ti sag o o d i d e at h a tu t i l i z e sd a t am i n i n gt e c h n i q u et os e e kt h ee v o l u t i o nl a ww i t h i nt h er e s e a r c h o b j c o t t h i sp a p e rp u tf o r w a r dt h ef r a m eo f t i m es e r i e sf e a t u r ep a t t e mm i n i n g ( t s f p m ) o nt h eb a s i so fd o m e s t i ca n di n t e r n a t i o n a lr e s e a r c ho l lt i m es e r i e sa n dp u tf o r w a r d t h es u i t a b l em i n i n ga l g o r i t h mb a s e do nc h a r a c t e r i s t i co ft r a f f i cf l o wa n dr e a l i z e di t t h eb a s i ct h i n k i n go ft h ef r a m ej st h a tt r a n s l a t e sn u m e r i c a lv a l u et i m es e r i e si n t o s y m b o ls e r i e se a s yt om i n ea n dt h e nu t i l i z es u i t a b l em i n i n ga l g o r i t h mt om i n et h e s y m b o ls e r i e s t h ep a t t e r n s w h i c ha r em i n e dw i l lb ec u td o w na c c o r d i n gt o p r a c t i c a l i t ya n df o r e c a s t i n gr u l e sw i l le x t r a c tf i n a l l y ， t h i sp a p e rp r o v i d e dr e l e v a n tc o n c e p t sa n dd e f i n i t i o n so ft i m es e r i e sf e a t u r e p a t t e r nm i n i n g ( t s f p m ) a n da n a l y z e da n dr e s e a r c h e d t h em i n i n gp r o c e s s i nt h e e x p e r i m e n t a t i o nw i t ht r a f f i cf l o wd a t at h ev a l i d i t yo ft s f p mw a sv a l i d a t e da n dt h e i m p a c to np e r f o r m a n c eo ft h ea l g o r i t h mo ft h ek e yp a r a m e t e ri na l g o r i t h m sw a s a n a l y s e d k e y w o r d t i m es e r i e s ；f e a t u r ep a t t e r n ；d a t am i n i n g ；l i n e a rs u b s e c t i o n ；c l u s t e r i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均己在论文中作了明确的说明并表示了谢意。 签名 日期： 关于论文使用授权的说明 红炉f g 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部 或部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 繇辫臀名：宴爻吼迫“一 第1 章绪论 i 第1 章绪论 1 1 课题背景和课题意义 1 1 1 课题背景m ”1 在一些大中型城市，随着城市的发展和扩充，道路拥堵的状况愈加严重，从 根本上讲，这个主要矛盾是交通上的供给和需求之间的矛盾，换句话说，现有城 市交通上的供给无法满足当前城市对交通的需求。要解决这个矛盾，可以归纳成 几种方法：扩展现有的道路来增加交通供给；通过政策减少交通规模的扩大来降 低交通需求；通过智能交通来协调供求关系，提高交通系统的效率和服务水平。 这几种方法是并行的，但前两种方法比较容易受到经济或者政治上的制约， 所以智能交通系统i t s ( i n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m s ) 就成为研究的首选。智 能交通系统已经成为近年来迅速发展的城市道路交通控制管理的新技术。它是 将先进的信息技术、数据通讯传输技术、电子传感技术、电子控制技术及计算 机处理技术等有效的集成运用于整个地面交通管理系统而建立的种在大范围 内、全方位发挥作用的，实时、准确、高效的综合交通运输管理系统，它可以 最大限度的发挥现有道路承载能力，从而减轻城市交通拥挤的现状。 交通流诱导是智能交通系统的主要研究内容之一，它的含义是对下一阶段 可能出现的交通供需不配对矛盾预先主动采取定措施予以缓和或化解。该理 论的主要功能是：预测交通运输系统状况，提供道路引导系统，引导车辆在最 佳线路上行驶；提供诱导系统与交通控制系统的相互联系；为出行者提供出发 时间和选择方式：为先进的交通管理系统和先进的出行者信息系统奠定重要的 理论基础。 有效的交通诱导是以准确的交通流量预报为前提的，所以交通流预测成为 国内外专家关注的热点。最新的交通运输研究成果表明交通流量预测在各种交 通控制系统中同样起着相当重要的作用。主要体现在：交通参数的准确预测 是城市集成交通控制系统中的信号控制子系统和动态导引子系统的前提。递 阶分层控制中的战略控制层和决策层也需要各种交通参数。在智能交通系统 北京工业大学工学硕士学位论文 中，营运车辆调度管理系统，先进的驾驶员信息系统，先进的交通管理系统等 子系统以及自动高速公路系统的网络层和连接层对流量进行控制也需要准确的 流量预测值。 所以，无论是对于交通诱导系统还是交通控制系统来说，实时准确的交通 流量预测是这些系统实现的前提及关键，交通流量预测结果的好坏直接关系到 交通诱导与控制的效果。 1 1 2 课题意义 众所周知，道路交通系统是一个有人参与的，时变的，复杂的非线性大系 统，它的显著特点之一就是具有高度的不确定性。这种不确定性不仅有来自自 然界的原因( 季节和气候等) ，也有来自人为因素的原因( 如交通事故、突发 事件、司机的心理状态等) 。这些因素都给交通流量的预测带来了困难，尤其是 短时交通流量预测受随机干扰因素影响更大，不确定性更强，规律性更不明显， 这也就是短时交通流量预测相对于中长期预测更难的原因所在。 这个领域研究虽然活跃，但缺少实质上的进展。很多研究者利用各种理论 来进行尝试，所以本课题是从另一个侧面数据挖掘来对这个课题进行研究， 具有一定的理论意义。 1 2 时间序列数据挖掘技术及其交通流预测技术的现状 1 2 1 时间序列数据挖掘技术的现状 时间序列数据挖掘是时态数据挖掘的一种，与时态数据挖掘的其他种类挖 掘不同，它所处理的数据是具有时间维的实数数据。时间序列挖掘是数据挖掘 在时间序列分析中一种典型运用。数据挖掘( d a t am i n i n g ) 是9 0 年代中后期兴 起的一门跨学科的综合研究领域，它综合计算机机器学习、统计学、数据库管 理、数据仓库、可视化、并行计算和决策支持为一体，利用数据库，数据仓库 技术存储和管理数据，利用机器学习和统计学方法分析数据，旨在发现大量复 杂数据中蕴涵的有价值的知识和信息。d m 是在数据集中进行知识发现 ( k n o w l e d g eb i s c o v e r yi nd a t a b a s e ) 的关键步骤。 第1 章鳍论 数据挖掘因其深刻的科学理论知识和巨大的商业前景，引起了学术界和工 业界的广泛关注，已经成为国际上数据库和信息决策领域最前沿、最热门的研 究方向之一。目前形成多种数据挖掘方法，例如关联规则挖掘，序列模式挖掘， 分类算法，聚类算法等。 时间序列是一种常见而又重要的数据类型，在海量的时间序列中发现其背 后隐藏的知识对分析时问序列变化规律，科学地做出决策具有重要的意义。因 此在数据挖掘概念提出不久，就有不少研究人员“2 “”1 。“1 把数据挖掘的思想 运用至时间序列分析中来。 g d a sc 4 3 1 等人通过一个移动窗口将序列分割成若干子序列，利用聚类方法对 这些子序列分类为特定的变化模式，然后按照关联规则的方式来发现频繁出现的 特征变化模式。该方法的主要问题在于窗口宽度的选取没有一个明确的标准，很 难确定一个合理的窗口宽度使得所有时间序列片段都具有相对独立的变化模式。 此外，d a s 不经过任何特征提取与转换直接对时间序列数据进行聚类，计算数据 量大且聚类效果不理想。 s z l a d o w z i a r k o 等人”基于租集理论，将移动窗用于时序数据，然后经 过计算转化成各种新的条件与决策属性标记，并利用成熟的数据挖掘方法进行 挖掘。这种方法的主要缺点是只有对落入窗口内的时间依赖性才被列入考察范 围，这样造成挖掘结果不完全。 m a n n il a 等人“2 1 则将a g r a w a l 等人。”的关联规则发现算法的核心思想推广 到时间序列，提出了事件序列中频繁事件的发现算法。事件序列与常见的时序 并不相同，它是离散的、分布不规则的序列。 从上面的研究可看出，时间序列挖掘方法基本上分为两个过程：序列特征描 述和挖掘算法设计。目前研究主要是采用了线段化的描述方式和基于传统的关 联规则挖掘算法，如类a p r i o r i 算法等。 本文也是采用了线性分段化的描述方式，线性化分段可以根据时序曲线变化 形态很自然地分割提取出本文所需要的独立状态模式，每一个分段都简洁直观地 表达了时间序列在该段时间内的变化特征，并且不同分段在形态上相对独立。然 后，利用聚类的方法将这些变化特征归类，并且给予独立的标识，最后通过序列 模式挖掘中比较成熟有效的方法进行挖掘，获得有趣的模式以及预测规则。 北京工业大学工学硕士学位论文 1 2 2 交通流预测技术的现状州 国内外关于交通流动态预测理论的研究目前还处于发展阶段，还没有较成熟 的预测理论。在以往的研究中，交通流的中长期预测已取得了较好的研究结果， 但是由于短时交通流量预测受随机干扰因素影响更大，不确定性更强，规律性更 不明显，所以关于短时交通流量实时预测的研究还无法取得令人满意的结果。交 通流预测研究分为基于确定的数学模型的方法和无模型的两大类，基于确定的数 学模型的方法“5 ”1 有历史趋势模型，神经网络模型，k r t m a 模型，k a l m a n 滤 波模型等。下面分别作以简要介绍： 历史趋势模型假设交通状况是间断性发生的，即具有相同历史趋势的一天里 各路段在同一时段具有相同的行程时间。建立该模型的关键是对于具有相似历史 趋势的工作日的分类。假如实时交通数据没有集成或检测器数据不可靠，历史趋 势模型可能是唯一的选择，虽然历史趋势模型可以在一定程度虑解决不同时间、 不同时段里的交通流变化问题，但静态的预测不足取，因为它不能解决非常规和 突发的交通状况，如交通事故等。 目前，国内外关于神经网络预测模型研究的比较多，也取得了一定的成果， 预测的平均误差大概为7 1 2 。但是，神经网络预测模型建模过程相对比较复 杂，模型的拟合速度较馒，不能很好地适应短时间实时预测的要求，而且神经网 络需要大量自我学习数据，数据不足会导致不好的预测结果。 时间序列分析最主要的应用就是预测。目前已广泛应用于气象预测、水文预 测、商品销量预测、股市行情预测、短期电力负荷预测等实际问题，其理论相对 比较成熟，但理论研究的多是线性模型，参数估计时必须依赖大量的不问断的时 间序列，而实际情况中，经常由于各种各样的原因造成数据遗漏，导致模型精度 降低，这也就限制了a r i m a 模型的应用范围。 卡尔曼( k a l m a n ) 滤波是一种比较先进的数据处理方法，是以6 0 年代 k a l m a n 提出的滤波理论为基础的。在应用于短时交通流量预测之前，已成功应 用在交通需求预测领域，预测精度较高。总的来说，k a t m a n 滤波法是针对线性 回归分析模型的一种矩阵迭代式的参数估计方法，具有预测因子选择灵活，精度 较高的优点，但是由于它需要作大量的矩阵和向量运算，导致算法较为复杂，难 以用于实时在线预测。 第1 章绪论 1 3 本文的主要研究结果 原有的时间序列分析方法有很多不足，例如很难用纯数学模型精确的表达 非线性系统、针对某些系统还需要多种手段的综合等，为了克服这些不足，将 数据挖掘的思想引入到时间序列分析中，对时间序列数据进行适当的挖掘，从 中找到蕴含的规律，并且将其运用在时间序列系统中进行分析和预测，便可以 很好的弥补原有方法的一些问题，也给时间序列问题的研究提供了一种新的思 路。 在实际研究中，不可能对时间序列演化做出非常精确的预测，这是由研究 对象内部的复杂程度所决定的。由于无法建立研究对象精确的数学模型，可借 助其他的途径进行预测，例如利用数据挖掘找出对象内部的演化规律，做出区 域性的预测，这对问题的分析具有很大的意义。 关于时间序列有两种典型的实例：股票和交通流，如果能够找出它们在一 些特定状态下发生的未来走势，将具有很重要的价值。 因此，本文的研究目标是利用数据挖掘工具，并结台时序分析对交通流演 化的趋势做出合理的预测和分析。具体结果有： ( 1 ) 分析了现有时间序列模型，指出各种模型的局限性。 ( 2 ) 详细介绍数据挖掘及其与时间序列相关的挖掘现状，并作出分析，阐 述该研究的价值与意义。 ( 3 ) 结合国内外的研究成果，提出了时间序列特征模式的挖掘框架，同时 结合交通流的特点提出一种合理的挖掘算法，并且进行了算法实现。 ( 4 ) 针对一组实测的交通流数据，运用本文所提出的挖掘框架及算法进行 分析，论证算法的有效性，并分析了关键参数对算法性能的影响。 北京工业大学工学硕士学位论文 1 4 本文结构安排 第1 章绪论 第2 章时间序列分析 第3 章数据数据与时序数据挖掘研究 第4 章时间序列特征模式挖掘t s f p m 框架 第5 章基于t s f p m 框架的交通流预测研究 第2 章肘间序列分析 2 1 时间序列模型 第2 章时间序列分析 时间序列是指按照时间顺序获得的一系列观测值。时序分析不仅可以从数 量上揭示某一现象的发展变化规律，也可以从动态的角度刻画某一现象与其他 现象之间的内在数量关系及其变化规律性，从而达到认识客观世界的目的。其 基本思想是根据系统有限长度的运行记录( 观测数据) ，建立能够比较精确的反 映时间序列中所包含的动态依存关系的数学模型。 通常的时间序列有水文信息、某只股票的股价、交通流量和商店中商品的 销售状况等等。针对于不同种类的时间序列，选择的分析方法也会有所差别， 本文中主要介绍的是在交通流预测中的应用。时间序列有个本质性的特征就是 相邻观测值是具有依赖性的，也就是具有根据某种规律演化的特点。正因为具 有这种演化规律，才能够建立合理的动态模型，进而利用这个模型进行预测。 时间序列传统上是采用自回归模型( a r ) ，滑动平均模型( 姒) 和自回归平 均模型( a r m a ) 来建模。4 ”，参数估计一般采用最小二乘( l m s ) 估计。时间序 列 y ( r ) ) 的自回归模型的数学表达式为： 爿( 日抄( f ) = e ( f ) ( 2 - 1 ) 其中， 4 ( b ) = 1 - a z b 一口2 8 2 一a p b ( 2 2 ) p 是自回归模型的阶数，e ( f ) 是零均值的白噪声，b 是后移算子，即满足表达 式：b ”y ( f ) = y ( f n ) ， = 1 ， 则( 2 - 1 ) 式还可写成： y ( t ) = 1 2 1 y ( t 1 ) + d 2 y o 一2 ) + + d 。y 0 一p ) + e ( t ) ( 2 - 3 ) 滑动平均模型的数学表达式为： y ( o = c ( b ) e ( t 、 ( 2 4 ) 其中， 北京工业大学工学硕士学位论文 c ( 占) = 1 一c 】b 一。2 口2 一- r - 一c 。b 9 ( 2 - 5 ) q 是滑动平均模型的阶数，e ( t ) 是零均值的白噪声，b 是后移算子，则( 2 4 ) 式还可写成： y ( f ) = e ( t ) 一c l e ( t 一1 ) 一c 2 p 0 2 ) 一一c 。p o g ) ( 2 6 ) 自回归滑动平均模型的数学表达式为： 4 ( b ) y ( f ) = c ( b ) e q ) ( 2 7 ) 其中，a ( b ) 同( 2 2 ) 式，c ( b ) 同( 2 5 ) 式，则( 2 7 ) 式还可写成： = a o ( t d + 吃m 一2 ) + + 础p ) + e 一q 雄一1 ) 一c 翘一2 一泸0 一曲 ( 2 8 ) 自回归求和滑动平均模型( a r i m a ) 是一个重要的预测工具，是时间序列分 析中许多基本思想的基础，它的含义是：如果对原序列经过d 次差分后得到的 新序列的模型为a r 姒( p ，q ) 模型，则原序列的模型即是a r i m a ( p ，d ，q ) 模型。它 的数学表达式为： a ( b ) v 4 y ( f ) = c ( b ) e ( f ) ( 2 9 ) 其中，彳( b ) 同( 2 2 ) 式，c ( b ) 同( 2 5 ) 式，v 4 = ( 卜功4 是d 阶差分。 d = - i ，进行一次差分处理，即令2 i ( ，) = 默f ) i “矿。y ( t - 1 ) ；d = 2 ，进行两次差分 处理，b j + z 2 ( t ) = v 2 y ( t ) = v z l ( t ) = z i ( t ) 一z , ( r - 1 ) ，依此类推。 这类方法一般称为经典方法，对数据的分析包括：建模、模型识别、模型 参数估计。这种模型是确定性的，演化的规律由初始条件决定。模型设计可能 是一个迭代、重复的过程，也可能是一个长期过程，常常需要推导、实现和选 型，最后才能得到与实际相匹配的模型。 由这类方法所得到的模型的优点是易于理解分析和实施，但缺点是它必须 基于两个假设才能成立，也就是：线性性和静态性，而实际系统具有很强的非 线性特点；同时进行参数估计时必须依赖大量的不间断的时间序列，而实际情 况中，经常由于各种各样的原因造成数据遗漏，导致模型精度降低，这便限制 了a r i m a 模型的应用范围。 第2 章时间序列分析 2 2 新型的时间序列分析方法 2 ，21 神经网络技术m ”2 町 神经网络可分为生物神经网络及人工神经网络。生物神经网络一般指动物 及人体中大脑和脊髓中有高级神经反射的神经组织。在工程中常称的神经网络 则是指用电路或软、硬件结合实现的具有模拟大脑功能的系统。神经网络技术 通过模仿大脑神经元工作的机制对系统历史、经验的数据进行学习，从而建立 研究系统的等价模型。 单个神经元在计算及表达方面的能力是有限的，但是它们之间相互连接后， 则可以体现非常复杂的非线性函数。神经网络是由大量的神经元广泛互连而成 的网络。根据联接方式的不同，神经网络可分成两大类：没有反馈的前向网络和 相互结合型网络。前向网络有输入层、中间层( 或称隐层) 和输出层组成，中间 层可有若干层，每一层的神经元只接受前层神经元的输出。而相互连接型网 络中任意两个神经元件都可能有联接，因此输入信号要在神经元之间反复往返 传递，从某一初态开始，经过若干次的变化，渐渐趋于莱一稳定状态或进入周 期振荡等其他状态。 k o l m o g o r o v 连续性定理为神经网络奠定了坚实的理论基础。它证明了存在 一个三层网络，其隐单元输出为非线性函数，输入及输出单元函数为线性函数， 此网络的总输入输出关系可以逼近任意一个非线性函数。如果将时间序列看作 一个由非线性机制确定的输入输出系统，那么对时间序列预测使用神经网络技 术是可行的。 已有的神经网络分为四大类：前向型网络，典型的有b p 网络、r b f 网络； 反馈型网络，典型的有h o p f i e l d 网络等；随机型网络，典型的有波耳兹曼机； 自组织竞争型网络，典型的有a r t 网络，自组织特征映射和c p n 模型。它们都 可以对时间序列进行预测，网络输入是时间序列的一个窗口，输入的形式为： x ( i ) = x ( t it ) ，其中x 表示训练使用的窗口选择是随机的。 神经网络的时序预测不需要对时序做出线性假设，也不要求时间序列数据 具有随机性等传统时间序列模型必需的条件。这对于一些特殊的时间序列是很 具启发性的，尤其是一些非常复杂和具有非线性特点的序列。同时，神经网络 北京工业大学工学硕士学位论文 还有如下优点：利用神经网络可以任意精度的逼近非线性函数，同时建模的时 候还可以省去建立数学模型的步骤。但是它存在一个不可忽视的缺点，就是神 经网络学习获得的系统知识是由网络结构及其网络中的参数所决定的，研究者 并不能够从这些参数中直接获得系统的物理信息，而且神经网络的学习中会出 现学习不足或者过度适应的问题，这都极大的影响了预测的稳定性。 2 2 2 混沌动力学方法。0 。”_ “1 混沌( c h a o s ) 可理解为确定系统产生的对初值极端敏感的非周期态行为。 混沌一般具备两个主要特征： 1 对于某些参量值，在几乎所有的初始条件下都将产生非周期动力学过程。 2 ，随着时间的推移，任意靠近的各个初始条件将表现出各自独立的时间演 化，即存在对初始条件的敏感依赖性。 对这两个特征的描述或判别证据，有四个基本判别尺度： 1 存在正的李雅普洛夫指数。 2 刻画系统在相空间的运动或结构复杂性的维数为分数维。 3 ，用来反映动力学系统非线性状况，复杂性程度和运动不稳定的拓扑熵 ( t c p o l o g i c a le n t r o p y ) 非负。 4 功率谱连续。 混沌按照不同的标准可分为： 1 时间混沌和空间混沌，时间混沌即系统状态具有初始条件敏感性，空间 混沌即系统状态具有边界条件敏感性。 2 完全混沌和有限混沌。e n l o r e n z 认为如果在该系统中大多数轨道显 示出敏感依赖性，即为完全混沌。如果在该系统中只有某些轨道是非周期性的， 但大多数轨道是周期性的或准周期性的，即为有限混沌。 3 强混沌和弱混沌，这是按照有无一个时间尺度，从而是否可以对系统的 演化行为做出预测来划分的。强混沌中存在一个时间尺度，一旦超越这一尺度， 系统演化就不可预测：而弱混沌则不存在这样一个尺度，它可以进行长期预测。 科学家已经发现，目前说找到的自组织的l 临界现象都是弱混沌因而自然界存在 着大量的s b 混沌现象，而弱混沌是可以长期预测的。 第2 苹时f 司序列分析 随着非线性科学的发展，混沌理论表明即使系统初始状态条件细微差异， 系统演化也可能导致显著差异，这便是混沌系统的蝴蝶效应。因而对混沌系统 的长期演化结果不可预测，但由于混沌是由确定系统的内在特性引起的，短期 行为又是完全确定的，即可预测，这就是混沌时间序列预测的物理基础。 混沌一方面指出了原本认为不可预测的复杂事物具有可预测性，另一方面 也指出了原本认为可预测的简单事物的预测具有局限性。从些前人经验中， 可以看到一些系统之所以预测不准确，除了有外界干扰和随机性的问题，更多 的是源于系统内部的动力学特性。混沌时间序列的预测，以重构相空间理论为 基础。混沌时间序列的预测问题可以理解为动力系统研究的逆问题，即如何为 给定相空间中的一串迭代序列构造一个非线性映射来表示这一动力系统，这样 所构造的非线性映射就作为预钡4 模型。 到目前为止，已经发展了许多的混沌时间序列建模和预测方法，这些预测 方法大致分为全局预测法、局域预测法和非线性自适应预测法。全局预测法指 对重构相空间中的所有状态点拟合出一个光滑函数作为预测模型；局域预测法 不是对相空间的所有状态点进行拟合，而只是选出需要预测状态点最邻近的几 个状态点来拟合预测函数；自适应预测就是自适应调整某些参数来跟踪混沌的 运动轨迹。 2 3 时序技术分析 由前面的介绍可知，各种现有的时序分析技术有一个共同的特点，那就是 绝大多数算法都是从纯数学的观点出发，也就是说都是构造一个全局的或者局 部的数学模型来拟合实际系统的观测数据，并利用这个模型对未来某个时刻的 值进行预测，这种预测只是对未来的时间点进行预测，而不是对未来的趋势或 者周期做出预测。换句话说，这种模型只对系统进行点预测，而不是区间预测。 另外，在建立模型的时候，为了确定模型参数，也要将所有历史数据一起进行 求解，即模型要拟合所有历史数据。 从另一个角度讲，随着各种技术的发展，时间序列分析的方式也越来越多， 从最初的统计数学模型发展到人工智能，机器学习和混沌，解题的对象系统由 当初的简单的线性假设发展到了针对于非线性的系统。而实际的时间序列随着 北京工业大学工学硕士学位论文 系统的复杂化，也是呈现出非线性的特点，这些非线性特征对系统分析再也不 能被简单的忽略掉。分析方法也不再是单一的纯数学模型，而是多种方法相结 合的综合性方案。 2 4 本章小结 本章对传统的时序分析技术进行了介绍，然后对目前较新的时序分析技术 做了概括，针对现有的时间序列分析方法做出了分析，揭示了它们在区间预测 和综合性上的不足。 第3 章数据挖掘与时序数据挖掘研究 第3 章数据挖掘与时序数据挖掘研究 3 1 数据挖掘 3 1 1 数据挖掘的产生背景和定义 数据挖掘”是信息技术自然演化的结果。整个演化过程由数据库业界开发 出的功能作为见证。这些功能有：数据收集和数据库建立、数据管理以及数据 分析与理解。数据收集和数据库创建机制的早期开发已经完成，并为后来的数 据库管理( 存储与查询、检索与事务处理等) 的开发奠定了必备基础。丽提供 数据库管理的的大量数据库系统广泛的被开发出来，并且投入到使用中，那么 下一个目标就成为业界所研究的重点。这个目标就是数据分析与理解，从目前 看，主要指数据挖掘和知识发现。 在过去的3 0 年里，计算机硬件稳定的、令人吃惊的进步导致了功能强大的 计算机、数据收集设备和存储介质的大量供应。这些技术大大的推动了数据库 和信息产业的发展，使得大量数据库和信息存储用于事务管理、信息检索和数 据分析。 现在，数据可以存放在不同类型的数据库中，最近经常被人提起的是数据 仓库，它可以将多种异种数据源以统一的模式进行组织存储，可以采用的技术 有数据清理、数据集成和联机分析处理( o l a p ) 。o l a p 是一种流行的分析技术， 具有从不同角度观察信息的能力，但是对于多维，深层次的数据分析，比如数 据分类，模式提取等，仍然需要其他工具的帮助。 海量数据被收集到大型的数据库中，如何理解这些数据显然已经不是人力 所能为的，决策者无法从这些大量的数据中找到决策依据，只好依照自己的直 觉进行分析来作出决定。专家系统虽然可以利用已有的知识进行决策，但是它 必须通过用户或者专家将知识专门的输入知识库系统，而这个过程代价很高， 也易出错。利用数据挖掘工具来分析这些海量数据，可以找到定的模式，对 决策、知识库建立、各种科学研究起到很大的作用。 数据挖掘没有统一的定义，简单的讲就是从大量的数据中提取知识。它与 北京工业大学工学硕士学位论文 另一个概念知识发现难以做很准确的区分，一般来讲，都认为数据挖掘是 知识发现的一个步骤。而知识发现的过程有以下步骤组成：数据清理、数据集 成、数据选择、数据变换、数据挖掘、模式评估和知识表示。而数据挖掘的步 骤主要是利用智能方法来寻找数据模式。 数据收集和数据库创建 ( 2 0 世纪6 0 年代和更早) 原始文件处理 数据库管理系统 ( 7 0 年代) 层次和网状数据库系统 关系数据库系统 数据建模工具：实体一联系模型 索引和数据组织技术：b + 树，散列 查询语言：s q l 等 用户界面：表单、报告等 查询处理和查询优化 事务管理：恢复和并发控制等 联机事务管理( o l t p ) 高级数据库系统 ( 8 0 年代中期一现在) 高级数据模型：扩充 关系、面向对象、对 象一关系、演绎 面向应用：空间的、 时间的、多媒体的、 主动的、科学的、知 识库 基于w e b 的数据库系统 ( 9 0 年代一现在) 基于x m l 的数据库系统 w e b 挖掘 数据仓库和数据挖掘 ( 8 0 年代后期现代) 数据仓库和o l a p 技术 数据挖掘和知识发现 新一代综合信息系统 ( 2 0 0 0 _ ) 图3 1 数据库技术的演化 f i g 、3 1t h ee v o l u t i o no f d a t a b a s et e c h n o l o g y 第3 章数话挖掘与时序数据挖掘研究 3 1 2 数据挖掘的预处理 由于现实的数据库通常很容易受到噪声数据、空缺数据和不一致数据的影 响。因而为了提高数据挖掘过程的效率和结果的质量，需要进行数据的预处理。 常用的预处理技术有数据清理、数据集成、数据变换和数据规约等。 数据清理技术可以对不同情形的缺失情况作出适当的处理，常用的方法有 空缺值填充、区别孤立点、噪声消除等；数据集成主要是指将数据从多个数据 源抽出融合在一起，这些源数据可能包括多元数据库、数据立方体或者一般文 件；而进行数据变换的目的是将变化后的数据转化为更适于进行数据挖掘的形 式。常用的技术有平滑、聚集、数据概化、规范化和属性构造等。数据规约是 在尽量保持源数据的完整性的同时，去除数据集中相对挖掘目标而言冗余的信 点，方法主要包括数据立方聚集、维规约、数据压缩、数值压缩和离散化等。 本文中用到的数据预处理方法主要是数据变换中的规范化和数值规约中的 聚类，下文中将给予详细介绍。 3 1 3 数据挖掘的一般过程 娟。l 图3 - 2 数据挖掘的通用过程 f i g3 - 2t h eu n i v e r s a lp r o c e s sf o rd a t a m i n i n g 北京 ：业大学工学硕士学位论文 图3 2 是数据挖掘的通用过程，一般由以下步骤组成： 数据清理：消除噪音或者不一致的数据。 数据集成：将多种数据源组合在一起。 数据选择：从数据库中检索与分析任务相关的数据。 数据交换：数据变换或统一成适合挖掘的形式。 数据挖掘：利用智能手段提取数据中的特征模式。 模式评估：根据某种兴趣度度量，识别表达知识的有趣模式。 知识表示：从模式中提取用户可以直接采用的知识。 首先将各种数据采集到数据库中，通过数据清理和集成把数据库中这些数 据有用的部分提取出来，然后放到一个大的数据仓库中；在数据仓库中根据挖 掘的目标选择或变换相关的数据集，采用某种挖掘算法对数据集进行挖掘，由 挖掘得出的模式数量一般很大，通过模式评估获得有趣的模式，最后从这些模 式中提取出人们用于决策或者研究的知识。 3 1 4 数据挖掘的主要技术 数据挖掘是一个交叉学科领域，受多个学科影响，包括数据库系统、统计 学、机器学习、可视化和信息科学。此外，它还依赖于所用的数据挖掘方法， 以及可以使用的其他学科的技术，如神经网络、模糊或粗糙集理论、知识表示、 归纳逻辑程序设计或高性能计算；依赖于所挖掘的数据类型或给定的数据挖掘 应用。数据挖掘系统也可能集成空间数据分析、信息检索、模式识别、图像分 析、信号处理、计算机图形学、w e b 技术、经济、商业、生物信息学或心理学 领域的技术。 数据挖掘有多种不同的分类方法。从挖掘技术的角度考虑，有机器学习、 统计学、可视化、模式识别、神经网络以及面向数据库或数据仓库的技术等， 对于复杂的数据挖掘系统可能同时运用多种数据挖掘技术，或者采用有效的、 集成的技术；从应用的角度分析，不同的应用领域需要集成针对该应用特别有 效的方法，而普通的、全能的数据挖掘系统可能无法胜任特定领域的挖掘任务。 第3 章数据挖掘与时序数据挖掘研究 ，、 3 2 时序数据挖掘研究 3 2 1 时态数据挖掘概述 时态数据挖掘是数据挖掘研究中的重要的组成部分。在数据挖掘这门学科 里，针对不同的数据集会有不同的挖掘办法，时态数据集是其中的一种。这种 数据集要求挖掘时必须考虑数据与时间的紧密关系，所有针对这种数据集的数 据挖掘又被称为时态数据挖掘。与数据挖掘中较成熟的序列模式挖掘相比，时 态数据挖掘是数据挖掘中一个较新的研究方向。本文所研究的时间序列数据挖 掘即时态数据挖掘的一部分。 目前，时态数据挖掘在国际上逐渐成为一个新的热点，但国内的研究相对 比较落后。下面将结合目前时态数据挖掘研究的进展情况，对其研究内容进行 了系统分类，并对其主要分支进行了总结和分析。首先对几种系统进行阐述。 因为针对不同的研究对象将形成不同类型的问题，故在阐述之前先确定研究对 象。时态数据挖掘的研究对象主要分为以下几类： ( 1 ) 数值型序列。也就是一般所指的时间序列，构成序列的元素是数值型 的。比如股票交易数据、电力负载数据和交通流量数据。对时间序列而言，我 们可将单时间序列或多时间序列作为挖掘对象进行研究。 ( 2 ) 事务型序列。构成序列的元素是事务型( t r a n s a c t i o n a l ) 的，称这种 序列为事务序列。这种数据以超市里顾客某一段时间买卖纪录为代表，对事务 序列而言，一般都是这类序列的一组集合构成挖掘的对象。 ( 3 ) 事件性序列。构成序列的元素是事件( e v e n t s ) ，这种序列称为事件序 列( e v e n t ss e q u e n c e s ) 。比如事故时间序列、交易行为时间序列。大多数事件 序列的挖掘研究是对单个事件序列进行的。 3 2 2 时态数据挖掘的分类。- ” 目前，国内外研究资料中时态数据挖掘的研究内容还比较零散、并没有系 统的理论框架。j i a w e ih a n 的著作把时态数据挖掘归为复杂类型数据的挖掘， 同时将时态数据挖掘分为趋势分析、相似性搜索和序列模式挖掘。 北京工业大学工学硕士学位论文 现在对时间序列的趋势分析已经有了一些研究成果，基本都以建模为主， 多数是在传统的线性自回归模型的基础上，对其他各个方面进行改进，以期达 到更好的效果。有几种代表性的研究方法： 基于形态的趋势分析，利用时间序列的几何属性对趋势进行研究，主要的 优点是简单易操作，而且可视化的效果明显，但是缺点也很明显，对于趋势变 化很大的非线性系统，得出的结论往往和实际有很大偏差，这也是由于系统的 非线性造成的。 用神经网络来近似的模拟非线性系统，将非线性系统与传统的自回归模型 结合，优点是准确度高，但是网络模型与传统模型的匹配问题，神经网络的计 算速度，权系数和训练不足与训练过度的问题都是制约这种方法解决问题的重 要因素。 当小波的理论逐渐被人们接受以后，一些人把小波应用到趋势分析中。利 用小波将时间序列进行多尺度分解，然后利用模型效率标准对时间序列的趋势 成份进行分析，来确定多分辨分析分解尺度，再根据小波系数的重建公式进行 序列重构，根据得到的各层的低频系数重构的时间序列来判断时间序列的变化 趋势。与传统的方法相比，小波方法更直观，计算速度快，而且能从时、频两 方面表现出时间序列的统计特征。不过在小波函数的选择上是个待研究的问题， 而且小波理论还远未成熟，仍有待研究。 在趋势分析上还有一些方法被应用，比如说灰色理论、分形理论、相空间 重构等，这里不进行一一分析。 在时间序列相似性搜索算法的研究里，比较早出现的是基于离散傅立叶变 换的相似性比较方法，主要做法是将时间序列通过d f t 由时域空间映射到频域 空间，保留前k 个傅立叶系数，将序列变成k 一维空间中的点，再用r 一树作为其 索引结构。对于不同的时序和对时序不同的研究角度，可采取不同的相似性定 义和不同的序列变换办法。 根据研究方向的不同，最有代表性的相似性搜索可分为以下两种： 基于序列变换的相似往搜索，这种相似性搜索是在离散傅立时变换上，引 入序列变换的方法概念，也就是说通过序列变换，可以将比较序列进行幅度调 整变换、去掉g a p 、平移变换