（计算机软件与理论专业论文）交通流时间序列分离方法研究.pdf

交通流时间序列分离方法研究 交通流时间序列分离方法研究 专业：计算机软件与理论 硕士生：谢琼琼 指导老师：印鉴教授 摘要 近年来，随着数据处理工具、先进数据库技术以及万维网( w w w ) 技术的 迅速发展，大量的形式各异的复杂类型的数据不断涌现，数据挖掘面临的一个重 要课题就是针对复杂类型数据的挖掘，其中包括时间序列数据。 时间序列在曰常工作和生活中是最为常见的数据形式之一，特别在智能交通 系统中，对交通流时间序列的分析就显得尤为重要。采用聚类分析方法对交通流 时间序列进行分析可以发现典型的交通流变化模式，可以实现对不同流量特性的 交通检测点所在路段进行合理分组，进而结合空间信息可以发现一些有意义的交 通时空分布规律。 本文在分析时间序列挖掘技术和实际应用需求的基础上，针对交通流时间序 列，主要做了如下几方面的工作：第一、详细讨论了时间序列相似性度量方法： 第二、针对传统的层次聚类算法在时间序列变化趋势上效果不佳的缺点，提出了 改进的层次聚类算法；第三、在研究中，采用将k 一平均算法和层次聚类算法结合 来实现不同变化趋势的交通流时间序列分离，并可视化聚类结果。 关键词：数据挖掘；交通流；时间序列；相似性：聚类 变通流时阿序列分离方法研究 t r a f f i cf l o wt i m es e r i e ss e p a r a t i o nm e t h o d s m a j o r ：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 ：x i eq i o n g q i o n g s u p e r v i s o r ：y i nj i a n a b s t r a c t r e c e n t l y , w i t ht h ed e v e l o p m e n to fd a t aa n a i y s i st e c h n o l o g y , a d v a n c e dd a t a b a s e t e c h n o l o g ya n d 、 r 、) l r 、v v a r i o u sc o m p l e xt y p ed a t ah a v ea p p e a r e d m i n i n ga m o n g t h e s ec o m p l e xt y p ed a t aw h i c hi n c l u d et i m es e r i e sd a t ab e c o m e sa ni m p o r t a n t d i r e c t i o no fd a t am i n i n g t i m es e r i e si so n eo ft h em o s tc o i t t l o nd a t at y p ei no a rd a i l yl i f e t h ea n a l y s i so f t r a f f i cf l o wt i m es e r i e st u r n s p a r t i c u l a r l yi m p o r t a n te s p e c i a l l y i n i n t e l l i g e n t t r a n s p o r t a t i o ns y s t e m u s i n gd a t am i n i n gt e c h n o l o g yt oa n a l y s i st i m es e r i e so ft r a f f i c f l o wn o to n l yc a nf o r e c a s tt h es h o r t t i m eo rl o n g t i m et r a f f i cv o l u m e ，b u ta l s oc a nj u d g e w h i c hc i t ys t r e e ti sb o t t l e n e c k s ot h a ti th e l p sal o tt oa n a l y s i st h et r a f f i cs i t u a t i o no f t h ec i t y f u r t h e r m o r e ，c o m b i n e dw i t hs o m es p a t i a li n f o r m a t i o n ，s o m eu s e f u ls p a t i a la n d t e m p o r a ld i s t r i b u t e dl a w si nt r a n s p o r t a t i o nc o u l db er e v e a l e d i nt h i sp a p e r ，s o m er e s e a r c hw o r ko nt r a f f i cf l o wt i m es e r i e sd a t am i n i n gh a sb e e n d o n e f i r s t l y , i n t r o d u c es o m es i m i l a r i t ym e t h o d so ft i m es e r i e si nd e t a i l s e c o n d l y ， p r o p o s ea l li m p r o v e d h i e r a r c h i c a lc l u s t e r i n ga l g o r i t h mf o rt h et r a d i t i o n a lh i e r a r c h i c a l c l u s t e r i n gm e t h o dh a sb a de f f e c t0 1 1 t h ev a r i a t i o nt e n d e n c yo ft i m es e r i e s t h i r d l y ， c o m b i n ek m e a n sm e t h o dw i t hh i e r a r c h i c a lm e t h o dt oa n a l y s i st r a f f i cf l o wt i m es e r i e s t h a th a v ed i f f e r e n tv a r i a t i o nt e n d e n c y m o r e o v e r ，v i s u a l i z a t i o no fc l u s t e r i n gr e s u l t s w o u l db ep r e s e n t e d k e yw o r d s ：d a t am i n i n g ；t r a f f i cf l o w ；t i m es e r i e s ；s i m i l a r i t y ；c l u s t e r i n g i i 交通流时间序列分离方法研究 前言 综合计算机技术、数据通讯技术、自动控制技术以及信息处理技术的智能交 通系统( 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 i t s ) 已得到了世界各国政府、 科研机构以及产业界的高度重视，因而在全世界范围内得到了迅猛的发展。在智 能交通系统中，信息是最为核心的内容，由于充分利用了当前迅速发展的信息技 术，信息的来源渠道和种类很多，如来自感应线圈、传感器的的交通流量信息， 来自摄像机的视频信息，来自g p s 定位系统的车辆方位信息，来自电子交警的车 辆违章信息，来自报警电话的交通事故信息等等，表现形式包含数据、图像、声 音、视频等，而且，这些信息都是实时获取的，在较短的时间内，信息量将会迅 速膨胀。此外智能交通系统中所提供的信息，大多数都是时间相关的，如道路占 有率和车流量，只有在与一定的时间联系才有意义，否则就不能为人们所理解和 利用。如何才能不被信息的汪洋大海所淹没，从中及时发现有用的知识，提高信 息利用率呢? 时间数据挖掘理论与技术的蓬勃发展恰好为进行交通数据分析提供 了坚实的理论基础及技术实现手段。 本文着眼于交通系统这个研究应用背景，详细介绍了作者在交通流时间序列 分离方法上所做的研究，包括如何分析时间序列的相似性：如何对传统层次聚类 算法的不足之处进行改进，使得新算法更准确的反映时间序列的变化趋势：以及 如何综合以上两方面因素，应用到交通流时间序列分离方法中。通过实验表明， 本文的方法可以发现一些有意义的交通流时空分布规律，可作为进一步进行交通 规划及控制优化的依据之一。 本文的组织结构 第一章时间序列数据挖掘概述 介绍时间数据挖掘的些相关知识，包括数据挖掘的简介和时间序列挖掘 的研究背景、技术、研究现状等。 第二章时间序列数据挖掘中的相似性度量 介绍了常用于时间序列分析的几种相似性度量方法，包括距离度量方法动 态时间弯曲、灰色关联度分析和位图方法。 第三章时间序列的聚类分析 首先概要介绍了聚类算法，然后着重探讨了k 一平均算法和层次聚类算法， 并且提出了基于时间序列变化趋势的改进的层次聚类算法。 第四章交通流时间序列分离方法 首先根据交通流时间序列这个研究对象，介绍了研究的意义及现有研究存 在的不足，然后给出了交通流时间序列分离方法，最后是实验部分。 第五章结论与展望 对全文进行总结，并指出需要进一步做的研究。 交通流时阀序列分离方法研究 第一章时间序列数据挖掘研究概述 1 1 数据挖掘概述 1 1 1 数据挖掘的产生背景及发展 随着计算机技术的飞速发展和应用的普及，人类社会进入了一个信息化的时 代，人们利用信息技术生产和搜集数据的能力大大提高。一方面在商业管理、政 府办公、科学研究和工程开发等各个领域中，每天都会产生大量的数据，这些数 据以数字化的形式存储起来，并根据需要以电磁媒介加以传播。另一方面，可以 支持信息共享和传播的互联网技术近年来在世界范围的发展十分迅速。互联网加 速了信息在世界范围内的流动，形成了信息的海洋。这一方面使得越来越多的个 体可以享有网上的共享信息，另一方面也使得个体所拥有的信息量以指数级的速 度增加。 面对这些浩如烟海的信息，单纯依靠传统的数据库技术对数据进行查询、检 索等操作已经不能有效地帮助用户从数据中提取带有结论性的有用信息，远远不 能满足数据分析和处理的要求。由于在拥有大量数据的同时我们对数据中所蕴涵 的信息和知识缺乏充分发掘和利用，从而造成了信息的浪费，由此也会产生大量 的数据垃圾。因此，人们迫切需要新的强有力的数据分析方法和技术以解决“数 据丰富，但信息贫乏”这一现象，帮助人们从繁杂的数据中挖掘出有用的信息， 发现其中存在的关系和规则，根据现有的数据来预测未来的发展趋势以辅助决策 的智能化自动化，以便带来商业上巨大的信息价值。在这种情况下，数据库知识 发现( k d d ，k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 和数据挖掘( d m ，d a t am i n i n g ) 技术应运而生并显示出强大的生命力。 k d d 这一术语首先出现在1 9 8 9 年在美国底特律召开的第1 1 届国际人工 智能联合会议的专题讨论会上，1 9 9 l ，1 9 9 3 和1 9 9 4 年又接着继续举行k d d 专 题讨论会。1 9 9 5 年在加拿大召开了第一届知识发现和数据挖掘国际学术会议。从 t 9 9 7 年开始，k d d 已经拥有了专门的杂志k n o w l e d g ed i s c o v e r ya n dd a t a m i n i n g ) ) ，国外在这方面发表了众多的研究成果和沦文，并且开发了一大批数据挖 掘软件，建立了大量的相关网站，对k d d 和数据挖掘的研究已成为计算机领域 的一个热门课题。我国近几年也逐渐跟上国际步伐，许多计算机、数据库、人工 智能、机器学习领域的专家学者投入到k d d 和数据挖掘的研究中，并己取得了 。一定的成果。表l l 显示了数据挖掘的进化历程”j 。 2 交通流时间序列分离方珐研究 表1 1 数据挖掘的进化历程 进化阶段商业问题支持技术 产品厂家 产品特点 数据搜集“过去五年我计算机，磁带， i b m c d c提供历史性 ( 6 0 年代)的总收入是多磁盘的，静态的信 少” 息 数据访问“在新英格兰关系数据库 o r a c l e在记录级提供 ( 8 0 年代) 的分部3 月份( r d b m s ) ，结构 i n f o r m i x 历史性的、动 的销售额是多化查询语言 s y b a s e 态数据信息 少” ( s q l ) ，o d b cm m i c r o s o f t 数据仓库，决 “在新英格兰联机分析处理 p i l o t 在各种层次上 策支持的分部去年三( 0 l a p ) 、多维c o m s h a r e 提供回溯的、 ( 9 0 年代) 月份的销售额数据库、数据仓 a r b o r 动态的数据信 是多少? 波士库 c o g n o s息 顿据此可以得 m i c r o s t r a t e g y 出什么结 论? ” 数据挖掘“下个月波士 高级算法、多处 p i l o t 提供潜在的、 ( 正在流行) 顿的销售额会理器计算机、海 l o c k h e e d 预测性的信息 怎么样? 为什量数据库i b m ，s g i 么? ” 其他初创公司 1 1 2 数据挖掘的定义和方法 数据挖掘通常又称为数据库中知识发现，就是从存放在数据库、数据仓库或 其他信息库中的大量数据里挖掘有趣知识的过程“3 ，这些知识是隐含的、事先未知 的、对决策有潜在价值的有用信息。还有很多近似的术语，如从数据库中发现知 识( k d d ) 、数据分析、数据融合( d a t af u s i o n ) 以及决策支持等。人们把原始数 据看作是形成知识的源泉，就像从矿石中采矿一样。原始数据可以是结构化的， 如关系型数据库中的数据，也可以是半结构化的，如文本、图形、图像数据，甚 至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也司以是非数 学的：可以是演绎的，也可以是归纳的。知识用概念、规则、模式、规律等方式 来表示。发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制等， 还可以用于数据自身的维护。 数据库中的知识发现是一个多步骤的处理过程，一般分为： ( 1 ) 数据清理：消除噪声或不一致数据： ( 2 ) 数据集成：多种数据源可以组合在一起： ( 3 ) 数据选择：从数据库中检索与分析任务相关的数据； 交通流时间序列分离方法研究 ( 4 ) 数据变换：数据变化或统一成适合挖掘的形式，如通过汇总或聚集操作： ( 5 ) 数据挖掘：基本步骤，使用智能方法提取数据模式； ( 6 ) 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式； ( 7 ) 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识。 数据挖掘步骤可以与用户或知识库交互，有趣的模式提供给用户，或作为新 的知识存放在知识库中。由此可见，数据挖掘只是数据库中知识发现的一个步骤， 但又是最重要的一步。因此，往往可以不加区别地使用k d d 和数据挖掘。一般在 研究领域称之为数据库中知识发现，在工程领域则称之为数据挖掘。 数据挖掘是- - i _ j 。义的交叉学科，涉及多学科技术的集成，包括数据库技术、 人工智能、统计学、机器学习、高性能计算、模式识别、神经网络、数据可视化、 信息检索、知识库系统、图像与信号处理和空间数据分析。机器学习和数据分析 的理论及实践是数据挖掘研究的基础，极大的商业应用前景又是数据挖掘研究工 作的巨大推动力。传统的数据库查询和统计、报表的处理方式都是对指定的数据 进行简单的数字处理，而不能对这些数据所包含的内在信息进行提取，因此只能 够提供用户想要的信息，而数据挖掘技术则可以发现用户没有意识到的未知的有 价值信息。作为种在海量数据中发现知识的手段，与传统的数据分析( 如查淘、 报表、联机应用分析o l a p 等) 的本质区别在于数据挖掘是在没有明确假设的前提 下去挖掘信息、发现知识的，它可以从大型的数据库或数据仓库中提出隐藏的预 测性信息，从浩如烟海的企业信息资料库中挖掘出更有价值的信息，具有广泛的 应用前景。 数据挖掘的方法很多，主要有如下的几种分析方法： ( 1 ) 概念类描述 用汇总的、简洁的、精确的方式描述每个类和概念称为类概念描述 ( c l a s s c o n c e p td e s c r i p t i o n ) 。这种描述可以通过下述方法得到：第一、数据特征化， 一般地汇总所研究类的数据；第二、数据区分，将所研究类与一个或多个比较类 进行比较；第三、数据特征化和比较。 ( 2 ) 关联分析 关联分析是指大量数据中项集之间有趣的关联或相关联系。随着大量数据不 停地收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越来越感兴 趣。从大量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定。 如购物篮的例子；在销售食品柜台发现，在购买牛奶的客户中，有8 0 的人同时 也购买了面包和饼干，用规则：牛奶 面包+ 饼干表示。发现这样的规则可以 设计方便顾客购物的商品货架、指导商家进货，对于确定市场策略是很有价值的。 关联规则还可以应用到附加邮递、仓储规划以及基于购买模式对用户进行分类等 方面。 ( 3 ) 分类和预测 分类和预测是两种数据分析形式，可以用于提取描述重要数据类的模型或预 测未来的数据趋势。其中，分类是预测分类标号( 或离散值) ，而预测是建立连续 4 交通流时间序列分离方法研究 值函数模型。例如，可以建立一个分类模型，对银行贷款的安全或风险进行分类： 同时可以建立预测模型，给定潜在顾客的收入和职业，预测它们在计算机设备上 的花费。 ( 4 ) 聚类分析 聚类与分类的不同之处在于，它要划分的类是未知的。聚类就是将数据对象 分组成为多个类或簇( c l u s t e r ) ，在同一个簇中的对象之间具有较高的相似度，而 不同簇中的对象差别较大。在许多应用中，可以将一个簇中的数据对象作为一个 整体来看待。聚类分析在市场营销、生物学、交通等领域都有广泛的应用。例如 在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用 购买模式来刻画不同的客户群的特征；在生物学上，聚类能用于推导植物和动物 的分类，对基因进行分类，获得对种群中固有结构的认识。 ( 5 ) 孤立点分析 经常存在一些数据对象，它们不符合数据的一般模型，这样的数据对象被称 为孤立点( o u t l i e r ) 。孤立点可能是度量或执行错误所导致的，也可能是固有的数 据变异的结果。许多数据挖掘算法试图使孤立点的影响最小化，或者排除它们。 但是，孤立点本身可能就是非常重要的，孤立点探测和分析是一个有趣的数据挖 掘任务，被称为“孤立点挖掘”。孤立点挖掘有着广泛的应用，例如在欺诈监测中， 孤立点可能预示着欺诈行为，可用来探测不寻常的信用卡使用或电信服务。 ( 6 ) 演变分析 数据演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时间变化的对象的规律或趋势， 并对其建模。例如你有纽约股票交易所过去几年的主要股票市场数据，并希望投 资于高科技工业公司的股票。股票交易数据的挖掘研究可以识别整个股票市场和 特定公司的股票演变规律。这种规律可以帮助预测股票市场价格的未来走向，帮 助你对股票投资作出决策。 1 1 3 数据挖掘的研究现状 数据挖掘在各个领域的研究和应用方面都发展迅速。近年来，根据国际上数 据挖掘的发展趋势，其研究主要有：对知识发现方法的研究进一步发展，如侧重 对b a y e s ( 贝叶斯) 方法以及b o o s t i n g 方法的研究和提高：传统的统计学方法在 数据挖掘中的应用：数据挖掘与数据库、数据仓库的紧密结合。在应用方面包括： 数据挖掘商业软件工具不断产生和完善，注重建立解决问题的整体系统，而不是 孤立的过程。用户主要集中在大型银行、保险公司、电信公司和销售业，制造业 的应用也正在逐步展开。 目前，国外有很多研究机构、公司和学术组织从事数据挖掘工具的研制和开 发。世界上比较有影响的典型数据挖掘系统有：s a s 公司的e n t e r p r i s em i n e r 、i b m 公司的i n t e l l i g e n tm i n e r 、s g i 公司的s e tm i n e r 、s p s s 公司的c l e m e n t i n e 、s y b a s e 公刮的w a r e h o u s es t u d i o 、r u l eq u e s tr e s e a r c h 公司的s e e 5 、还有c o v e rs t o r y 、 交通流时间序列分离方法研究 e x p l o r a 、k n o w l e d g ed i s c o v e r i n gw o r k b e n c h 、d b m i n e r 、q u e s t 等。数据挖掘实 验室( w w w d a t a m i n i n g l a b c o m ) 网址提供了许多数据挖掘系统的工具和性能测试 报告。 国内对数据挖掘的研究稍晚，1 9 9 3 年国家自然基金首次支持该领域的研究项 目。目前，国内的许多科研单位和高等院校竞相开展数据挖掘的基础理论及其应 用研究，他们所涉及的研究领域很多，一般集中于学习算法的研究、数据挖掘的 实际应用以及数据挖掘理论方面的研究。大量的文章已经在各级期刊，各种会议 发表，应用数据挖掘技术开发的产品日渐增多，己经有不少含数据挖掘功能的产 品问世，如用于对股票行情进行分析预测的指南针、神光、r m r 等智能股票分析 系统。 1 2 时间序列数据挖掘 数据挖掘技术开始主要面对的是以结构化数据为主的关系数据库、事务数据 库，和数据仓库。随着数据处理工具、先进数据库技术以及万维网( w w w ) 技 术的迅速发展，大量的形式各异的复杂类型的数据( 如结构化与非结构化数据、 超文本与多媒体数据等) 不断涌现。因此数据挖掘面临的一个重要的课题就是针 对复杂类型数据的挖掘，这包括复杂对象、空间数据、多媒体数据、时问序列数 据、文本数据和w e b 数据。本论文所要研究的就是时间序列数据的挖掘，f 面我 们将讨论时间序列数据挖掘的一些基本情况，包括研究背景、基本概念、技术以 及研究现状。 1 2 1 时间序列挖掘的研究背景 时间序列在各个应用领域和科学研究领域都是一种频繁产生的数据，最著名 的例子包括美国高速公路交通网每分钟的汽车流量，纽约证券交易每天产生的股 票收盘价格，美国和欧洲之间的每小时电话通量，以及太平洋表面温度的每日读 取数等等。所以它是一类重要的复杂数据对象。社会、科学、经济、技术等领域 中广泛存在着大量的时间序列数据有待进步的分析和处理，人们希望通过对时 间序列的分析，从大量的数据中发现和揭示某一现象的发展变化规律或从动态的 角度刻画某一现象与其他现象之间的内在数量关系及其变化规律，尽可能多的从 中提取出我们所需要的准确信息，并将这些知识和信息用于预测，以掌握和控制 未来行为。面对这一严峻挑战，时间序列数据挖掘技术( t i m es e r i e sd a t am i n i n g 简 称t s d m ) 应运而生。 在这个信息时代，对于事物随时间变化的理解将是十分宝贵的知识，时间序 列数据挖掘通过研究信息的时间特性，深入洞悉事物进化的机制，是获得这一知 识的有效途径。时间序列数据挖掘就是要从大量的时间序列数据中提取人们事先 不知道的、但又是潜在有用的与时间属性相关的信息和知识，或用于分析或用于 6 交通流时闻序列分离方法研究 预测，指导人们的社会、交通、经济和生活等行为。自从1 9 9 5 年8 月举行的k d d 会议上首次出现时间序列数据挖掘后，大量的工程技术人员和管理人员把目光的 焦点转向了时间序列数据挖掘，并对其进行了深入的研究。在历届会议上其讨论 范围也从原来的小组讨论发展到专题讨论会，研究重点也逐渐从发现方法转向系 统应用，注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。i e e e 、 a c m 、i f i s 、v l d b 、s i g m o d 等其他学会、学刊也纷纷收录了t s d m 的沧文，许 多网站如：w w w k d n u g g e t s t o m 和w w w s i n o k d d 1 6 3 n e t 等都开辟了专门的t s d m 讨 论组，还收录了相关的论文，技术资料等等。从图1 一l 可以看出，从1 9 9 5 年至今， 历届k d d 会议和亚太地区的p a k d d 会议中收录的t s d m 的论文呈现一种明显的 上升趋势，时间序列数据挖掘正成为数据挖掘的研究热点之一。 图1 - 1 历届k d d 和p a k d d 会议收录的t s d m 论文情况 1 2 2 时间序列的基本概念 1 时间序列的定义 我们可以从以下三个方面来了解时间序列的定义”1 ： 从统计意义上来讲，所谓时间序列就是将某一指标在不同时间上的不同数值， 按照时间的先后顺序排列而成的数列。这种数列由于受到各种偶然因素的影响， 往往表现出某种随机性，彼此之间存在着在统计上的依赖关系。 从数学意义上来讲，如果我们对某过程中的某一变量或一组变量进行x ( t ) 观察测量，在一系列时刻t t ，t 2 ，t n ( t 为自变量，j j _ t l t 2 t n ) 得到的离散有序 数集合x t l ，x t 2 ，x t i ，x t n 称为离散数字时间序列，即随机过程的一次样本实 现。设x ( t ：t t t ) 是一个随机过程，x t i ( i = 1 2 ，n ) 称为一次样本实现，也就是一个 时间序列。 从系统意义上看，时间序列就是某一系统在不同时间( 地点、条件等) 的响 应。这个定义从系统运行的观点出发，指出时间序列是按定顺序排列而成的。 交通流时间序列分离方法研究 这里的“一定顺序”即可以是时间顺序，也可以是具有各种不同意义的物理量， 如代表温度，速度或其它单调递增的取值的物理量。 可见，时间序列只强调顺序的重要性，而并非强调必须按时间序列排序。而 且时间序列是所研究系统的历史行为的客观记录，因而它包含了系统结构特征( 如 周期波动的周期、振幅、趋势的种类等) ；揭示其运行规律，进而用以预测、控 制其未来行为：修正和重新设计系统( 如改变其周期、参数) ，使之按照新的结 构运行。 2 时间序列的分类 时间序列有很多的分类方法，根据其所研究的依据不同，主要的有：按所研 究的对象的多少，可分为一元时间序列和多元时间序列；按时间的连续性，可将 时间序列分为离散时间序列和连续时间序列两种：按序列的统计特性，可分为平 稳时间序列和非平稳时间序列；按序列的分布规律来分，可分为高斯型( g u a s s i a n ) 和非高斯型( n o n g u a s s i a n ) 时间序列。 3 时间序列的变动特点 ( 1 ) 趋势性：某个变量随着时间进展或自变量变化，呈现一种比较缓慢而长 期的持续上升、下降、停留的同性质变动趋向，但变动幅度可能不等。 ( 2 ) 周期性：某因素由于外部影响随着自然季节的交替出现高峰与低谷的规 律。 ( 3 ) 随机性：个别为随机变动，整体呈统计规律。 ( 4 ) 综合性：实际变化情况一般是几种变动的叠加或组合。 1 2 3 时间序列挖掘的技术 时间序列数据挖掘主要有趋势分析、相似性搜索、与时间有关数据的序列模 式挖掘、周期模式挖掘和聚类分析这几大重要的技术。 1 趋势分析 目前还没有可以自动识别时间序列中趋势成分的技术：但是，如果趋势是单 凋的( 保持增长或者减少) ，那么趋势分析通常不是太难，否则应该先对数据做一 些处理，常用的技术包括平滑处理，最小二乘法，或者选取适应函数等。所有这 些技术都是为了滤掉噪声，将数据调整成一条平滑曲线，该曲线相对而言不太受 孤立点的干扰。 2 相似性搜索 通常数据库查询是要找出符合查询的精确数据相似性搜索与之不同，它是 找出与给定查询序列最接近的数据序列。它包括子序列匹配( s u b s e q u e n c e m a t c h i n g ) 和整体序列匹配( w h o l es e q u e n c em a t c h i n g ) 。其中子序列匹配是找出与 给定序列相似的所有数据序列，而整体序列匹配是找出彼此间相似的序列。时间 序列分析中的相似性搜索在金融市场的分析( 如股票数据分析) ，医疗诊断分析( 如 心电图分析) ，和科学与工程数据库分析( 如能量消耗分析) 等都大有用武之地。 8 交通流时间序列分离方法研究 3 序列模式挖掘 序列模式挖掘( s e q u e n c ep a t t e r nm i n i n g ) 是指挖掘相对时间或其他模式出现 频率高的模式。由于很多商业交易、电传记录、天气数据和生产过程都是时间序 列数据，在针对目标市场、客户吸引、气象预报等的数据分析中，序列模式挖掘 足很有用的。一个典型的序列模式的例子是：9 个月以前购买奔腾p c 的客户很可 能在一个月内定购新的c p u 芯片。 4 周期分析 周期分析是指对周期模式的挖掘，即在时间序列数据库中找出重复的模式。 周期模式可以应用于许多重要的领域，例如季节，潮汐，行星轨道，每日能源消 耗，每日交通模式，和每周特定时间的所有t v 节目等等。周期分析的一个典型 的例子是“基于每天的营业记录，若周末下午茶在3 ：0 0 一5 ：0 0 p m ，则晚餐最佳 营业时间为7 ：0 0 - - 9 ：o o p m 。 5 聚类分析 如果要对时间序列进行聚类分析，首先要知道什么样的时间序列是相似的， 这里又可以用到相似性搜索的一些知识来解决。从原则上来讲，一般数据挖掘中 的聚类算法都可以用于时间序列数据的聚类分析中。聚类分析在时间序列数据挖 掘中有很大的应用价值，例如在美国高速公路交通系统中，对交通流时间序列进 行聚类分析，可以获得一些典型的交通流变化趋势规律，对交通检测点所在路段 实现进行合理分组具有重要的意义。 1 2 4 时间序列挖掘的研究现状 时间序列分析在统计学中已有较充分的研究“3 。如a g r a w a l ，f a l o u t s o s 和s w a m i 研究了序列数据库中高效相似搜索的方法；f a l o u t s o s ，r a n g a n a t h a n 和m a n o l o p o u l o s 提出了在时序数据库中子序列匹配的方法；a g r a w a l ，l i n ，s a w h n e y 和s h i m 提出 了一种在时序数据库中出现噪声、伸缩和转换情况下的快速相似搜索方法： a g r a w a l ，p s a i l a ，w i m m e r s 和z a i t 提出了用于查询历史情况的语言元素；其他有 关时序数据的相似搜索的研究工作有r a f i e i 和m e n d e l z o n ，y i ，j a g a d i s h 和 f a l o u t s o s ，p a r k ，c h u ，y o o n 和h s u ，以及p e m g ，w a n g ，z h a n g 和p a r k e r 。 由文献 1 所提到的，针对序列模式挖掘，a g r a w a l 和s r i k a n t 提出了一种类 a p r i o r i 技术和一种一般的序列模式挖掘算法g s p ；m a n n i l a ，t o i v o n e n 和v e r k a m o 考虑了模式中的f r e q u e n te p i s o d e ：l u ，h a n 和f e n g 提出了事务间的关联规则，它 是蕴涵规则，其两端是具有时间间隔限制的有序的e p i s o d e s ：b e t t i n i 。w a n g 和j a j o d i a 考虑了事务间关联规则的概化：z a k i ，l e s h 和o g i h m a 提出了对p l a nf a i l u r e 的序 列模式挖掘；h a n ，d o n g 和y i n 提出了局部周期挖掘的最大子模式匹配集方法： g a r o f a l a k i s ，r a s t o g i 和s h i m 提出了一种基于约束的序列模式的有效挖掘方法： h a n ，p e i ，m o r t a z a v i a s l 等设计了一种高效的序列模式挖掘方法f r e e s p a n ，它基 于了数据库投影和分片挖掘：y i ，s i d i r o p o u l o s ，j o h n s o n ，j a g a d i s h 等给出了针对 9 交通流时问序列分离方恺研究 时间序列的联机挖掘方法。 针对时间序列聚类分析方面，d i m i t d o sg u n o p u l o s 和g a u t a md a s 。“对于时间序 列相似性度量做了一个完整的概述；e a m o n n ”和y i n g j u nw e n g 。3 在动态时间弯曲 的相似性度量上都做出了新的研究成果；d a x i nj i a n g ，j i a np e i 和a i d o n gz h a n g ”1 研究了关于基因时间序列的基于密度的层次聚类算法；a s h i s hs i n g h a l 和d a l e e s e b o r g ”1 研究了关于多变量时间序列数据聚类的方法；p e d o rr o d r i g u e s ，j o a o g a m a 和j o a op e d r op e d r o s o ”。关于时间序列流提出了一种在线凝聚和分裂的层次 聚类算法。 由此可见，时间序列上的广泛应用前景已经得到了国内外各个科研机构的关 注，这方面的研究也在逐步深入中。 0 交通流时间序列分离方法研究 第二章时间序列数据挖掘中的相似性度量 典型的时间序列应用分析包括了分类，聚类，相似性搜索，预言预测，孤立 点检测，噪声滤除等等。其中，如果要对时问序列进行聚类分析，首先要知道什 么样的时间序列是相似的。建立相似系数并对其分析与选择，正是聚类分析的基 础。时间序列的相似性并不好判断，它既取决于人们对于聚类现象本质认识的深 度，又取决于人们的实际工作经验，同时因为时间序列这种复杂对象的相似性定 义对于不同的应用领域和具体任务区别相当大，所以定义时间序列相似度的工作 很重要。在本章将讨论几种常用的时间序列的相似性度量方法。 2 1 距离度量方法 2 1 1 欧几里得距离 设有二个时间序列q 和c ，其数据长度分别为n 和i t i ，表示如下： q = l q l ，q 2 ，q 。 c = ( c 【，c 2 ，c 。 则由文献 1 】可知，这两个序列之间的欧几里得距离可定义如下： d ( q ，c ) = l q l c i1 2 十i q 2 一c ：1 2 + + i q 。一c 。1 2 ( n = m )( 2 1 ) 欧几里德以距离来衡量两个时间序列之间的相似度，d ( q ，c ) 越小则说明它们 之间的相似度越大，反之则反。 它的优点在于简单，容易计算，可以常常用于其他的问题比如说索引 ( i n d e x i n g ) ，聚类( c l u s t e r i n g ) 等等。但是它只适用于等长的时间序列，不适用 于非等长序列的情况；并且由于它只是把整个时间序列当作n 维欧几里德空间的 一个点，因而它不能找出时间序列曲线间的相似性，进而不能反映时间序列的变 化趋势；再者它对于不同基线或者不同数值范围的时间序列都是不适用的。 2 1 2 曼哈坦距离 另一个著名的距离度量方法是曼哈坦距离“1 ，其定义如下： d ( q ，c ) = q i c lj 十i 留2 一c 2j + + f 鼋。一c 。j ( n = m )( 2 2 ) 上面提到的两种距离度量方法都满足对距离函数的如下数学要求： ( 1 ) a ( q ，c ) 0 ：距离是个非负的数值： 交通流时间序列分离方法研究 ( 2 ) d ( q ，q ) = 0 ：一个对象与自身的距离是o ； ( 3 ) d ( q ，c ) 一d ( c ，q ) ：距离函数具有对称性； ( 4 ) d ( q ，c ) d ( q ，a ) + d ( a ，c ) ：从对象q 到c 的直接距离不会大于途经任何 其他对象a 的距离( 三角不等式) 。 2 1 3 明考斯基距离 明考斯基距离“1 是欧几里得距离和曼哈坦距离的概化，它的定义如下： d ( q ，c ) = ( 1 q 一c 。j + 1 日2 一c 2i + + l q 。一c 。f ) “ ( 2 3 ) 这里的t 是一个正整数。当t = l 时，它表示曼哈坦距离：当t = 2 时，它表示 欧几里得距离。 2 2 动态时间弯曲( d y n a m i ct i m ew a r p i n g ，d t w ) 动态时间弯曲”最初是应用于文本、字符串匹配及视觉模式识别等领域的相 似性度量方法，研究表明这种基于非线性弯曲技术的算法可以获得较高的识别及 匹配精度。其具体定义如下： 设现有两时间序列q 和c ，其数据长度分别为n 和m ，表示如下： q = q i ，q 2 ，q 。 ， c = c l ，c 2 ，c 。 。 为了利用d t w 将两个时间序列对准，事先给出两个定义：距离相异矩阵和弯 曲路径。 定义2 一l ：i i 行m 列矩阵，矩阵中的元素为不同时问序列数据对象之间的点的 欧几里的距离，即d ( q i ，c j ) = ( q i c j ) 2 ，为距离矩阵，记为d l m a t r i x 。 矩阵中的d ( q l ，c j ) 是两个时间序列数据点之间的距离值，可以看作是对象q 和对 象c 直接的相异性的量化表示。当对象q 和c 越相似或越接近，其值越接近0 ：两个 对象越不相同，其值越大。将两个时间序列分别置于二维坐标的两轴，如图2 一l 所示： 一一一 一 一一i j 干一一一一一一 霹一一斗一 ；壁一一_ 卜一一一一一一 图2 1 动态时间弯曲示例 1 2 交通流时间序列分离方法研究 定义2 2 ：在两个不同时间序列间的距离矩阵中，定义时间序列间相异性关系 的一组连续的矩阵元素的集合，称为弯曲路径。 w = w i ，w 2 ，”k ，w k 其中m a x ( m ，n ) k m + n l 由定义2 2 可知，弯曲路径满足以下条件： 1 ) 边界条件：w l _ d m a t r i x ( q l ，c 1 ) 与w k = d _ m a t r i x ( q 。，c m ) ，即弯曲路径 的起止元素为距离矩阵的斜对角线上的两端元素。 2 ) 连续性：给定w k = d m a t r i x ( q 。，c b ) ，w k l = d m a t r i x ( q 。一，c b ) ，必须满足 a - a 。1 和b b 1 ，即弯曲路径中的元素是相互连续的。 3 ) 单调性：给定w k = d m a t r i x ( q 。，c b ) ，w k 一1 = dm a t r i x ( 耻，c b ) ，必须满足 a - a 2 1 和b b l ，也就是说路径w 通过点( i ，j ) 同时必须至少通过点( i 一1 ， j ) ，( i l ，j 1 ) 或( i ，j 1 ) 中的一个，强制保证弯曲路径在时间轴上是单调的。 对距离矩阵分析可知，弯曲路径存在多解，但是我们关心的实际上仅仅是弯 曲路径总长度最小的，在逻辑意义上，两数据相似性程度最大( 距离值最小) 的作 为相似搜索的判据，如下式： 三 d t w ( q ，c ) = m i n ( ( ) k ) ( 2 4 ) 式中：分母k 是为了在比较不同长度的路径时有统一的标准。 理论上，可以利用穷举搜索法寻找满足条件的弯益路径，但是完全穷举在大 型数据库分析中往往是不切实际的，因为路径的解很多，且与距离矩阵中的元素 数成指数关系。由动态规划( d y n a m i cp r o g r a m m i n g ) 理论可知，设有点( i ，j ) 在最 佳路径上，那么从点( 1 ，1 ) 到( i ，j ) 的子路径也是局部最优解，也就是说从点( 1 ，1 ) 到点( m ，n ) 的最佳路径可以由时间起始点( 1 ，1 ) 到终点( i l l ，n ) 之间的局部最优解 通过递归搜索获得。即： s i l = d ( q l ，e 1 ) ： s = d ( q l ，c j ) + m i n ( s ( i 一1 ，j ) ；s ( i l ，j 1 ) ；s ( i ，j 1 ) ( 2 5 ) 最终时间序列弯曲路径最小累加值为s 。从s 。起沿弯曲路径按最小累 加值倒退直到起始点s 1 i 即可找到整个弯曲路径。而s 。就是所求的q ，c 两时 间序列的相似度。 一般情况下，动态时间弯曲的时间复杂度是o ( n 2 ) ，其中n 为时间序列的长 度，所以它在很多对时间复杂度要求不很高的领域都取得了不错的效果，比如说 语音处理、模式识别等等。 2 3 灰色关联度分析 灰色系统理论提出了对各子系统进行灰色关联度分析的概念，意图透过定 的方法，去寻求系统中各予系统( 或因素) 之间的数值关系。简言之，灰色关联 度分析( g r e y