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

交通流时间序列符号化方法研究 交通流时间序列符号化方法研究 专业：计算机软件与理论 硕士生；何武 指导教师：印鉴 摘要 摘要：作为一类重要的复杂类型数据，时间序列已成为数据挖掘领域的热点研究 对象之一。针对时间序列的数据挖掘在智能交通控制中有着十分重要的作用，其 通常首先需要将时间序列分段并转变为种类有限的符号序列，以利于进一步进行 时间序列模式挖掘。 本文针对当前时问序列分段方法复杂度较大，效果不佳等问题，提出了一种 简单高效的基于累积和控制图( c u s u m ) 拐点检测的时间序列分段方法，并且采 用动态时间弯曲度量计算不等长子序列的相异度，最后运用层次化聚类算法实现 子序列的分类及符号化。实验表明，本文所提出的方法切实可行，实验结果具有 较为明显的意义。 关键词：时间序列拐点符号化累积和控制图动态时间弯曲 塞望堕堕塑壁型笪兰些查鲨堕塞 t r a f f i cf l o wt i m es e r i e ss y m b o l i z a t i o n 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 ：h ew u s u p e r v i s o r ：y i nj i a n a b s t r a c t a so n eo ft h ei m p o r t a n tf o r m so fc o m p l e xd a t a ，t i m es e r i e si sah o t s p o ti nd a t a m i n i n ga r e a t i m es e r i e sd a t am i n i n gi sv e r yn e c e s s a r yi ni n t e l l i g e n tt r a n s p o r ts y s t e m s e q u e n c ep a t t e r nm i n i n gi sb a s e do nt i m es e r i e ss y m b o l i z a t i o n , w h i c hs e g m e n t st h e t i m es e r i e si n t os u b - s e r i e sa n dl a b e i st h e m m o s tc u r r e n tt i m es e r i e s s e g m e n t a t i o na l g o r i t h m sa r ew i t hl a r g ec o m p u t a t i o n c o m p l e x i t y i nt h i sp a p e r , w ei n t r o d u c e a l lo n l i n em e t h o df o rt i m es e r i e ss e g m e n t a t i o n b a s e do nc h a n g ep o i n td e t e c t i o nw h i c hu s e sc u m u l a t i v es l i mc h a r t s ( c u s u m ) ，a n d d y n a m i ct i m ew a r p i n g ( d t w ) m e t h o di su s e dt oc o m p u t et h ed i s t a n c eo ft h e s u b s e r i e s l a t e rt h eh i e r a r c lc l u s t e r i n gi su s e dt og r o u pt h es u b - s e r i e sa n dh b e l t h e m t h ee x p e r i m e n t ss h o wt h ep r o p o s e dm e t i l o di sf e a s 曲l ea n dt h er e s u l t sa r e m e a n i n g 血l k e yw o r d s ：t i m es e r i e s ，c h a n g ep o i n t ，s y m b o l i z a t i o n , c u s u m ，d t w h 交通流时间序列符号化方法研究 刖吾 随着社会经济和交通事业的发展，交通拥挤和交通事故等诸多交通问题越来 越凸现出来，成了全球共同关注的难题。自上世纪8 0 年代以来，发达国家开始投 入大量人力物力进行道路交通运输系统的管理与控制技术的开发。于是，运用各 种高新技术系统地解决道路交通问题的思想就应运而生了，这就是智能交通系统 i t s ( i n t e l l i g e n tt r a n s p o r ts y s t e m ) 。 交通控制与诱导系统是i t s 研究的热门核心课题，而实现交通流诱导系统 的关键问题是实时准确的交通数据分析，即如何有效地利用实时交通数据信息去 分析现在和预测未来的交通状况。其结果可以直接送到先进的交通信息系统 ( a t i s ) 和先进的交通管理系统( a 删s ) 当中，给出行者提供实时有效的信息，帮 助他们更好地进行路径选择，实现路径诱导，以缩减出行时间，减少交通拥挤。 然而，交通数据往往是海量的。一条路上数以万计的交通检测站点每分钟都 在传递着数百兆的数据，面对这些浩如烟海的信息，单纯依靠传统的数据库技术 对数据进行查询、检索等操作已经不能有效地提取带有结论性的有用信息。如何 解决这个困难? 数据挖掘技术的发展为人们解决这个问题提供了可能。数据挖掘 就是从海量数据中提取或挖掘知识。应用数据挖掘工具对数据进行分析，可以发 现重要的数据模式，对商务决策、知识库、科学和医学研究作出重大贡献。因此， 数据挖掘一开始就引起业界广泛关注，并得以蓬勃发展，越来越显示出其强大的 生命力。 智能交通系统的最主要数据高速公路的交通流数据是一种典型的时间 序列。交通流时间序列的挖掘是智能交通研究的重要内容。而作为一类重要的复 杂类型数据，时间序列也是数据挖掘领域的热点研究对象之一。时间序列分析源 于许多研究领域，如统计学，数据挖掘，生物学等。在数据挖掘领域，主要是用 数据挖掘的方法来对时间序列进行“趋势分析”、“相似搜索”、“序列模式挖掘”、 “时段模式挖掘”等。分类，聚类分析，关联规则，内容查询等都可以用于时间 序列挖掘。 交通流数据是十分巨大的，如何才能高效地对它们进行挖掘? 正如很多计算 机科学问题一样，数据的表示形式是能否高效准确处理的关键。人们研究发现， 对时间序列的数据挖掘，如果先将数据点密集的长时间序列转换成相对稀疏的具 有特定含义的符号序列，即转化为相对简单且易于分析处理的形式，从而在进一 步应用诸如时态关联规则挖掘、序列模式发现等方法进行挖掘及知识发现时就可 以获得更好的效率和更好的结果。时间序列符号化的主要方法为：一、对时间序 列分段；二、对分好的时间序列片段分组并分配标志符，一般使用聚类分析的方 交通流时间序列符号化方法研究 法。 本文介绍了对交通流时间序列符号化的方法。对符号化的两个主要步骤：分 段和聚类进行了分析和研究后，本文提出了一种时间序列实时分段( s w c u s u m ) 及符号化方法，其基本思想是：首先使用本文提出的s w c u s u m 算法将原时间 序列转换为一系列分段，然后利用动态时间弯曲算法计算分段后得到的子序列的 相异度并通过一定的转换构造出相似度矩阵，接着采用层次化聚类算法对各子序 列聚类，根据聚类结果为每类子序列赋予相应的类别标签，最后用类别标签序列 代替原始数值序列，从而得到原耐间序列的符号化表示。实验结果表明，这种方 法得到的符号化的时间序列具有较为明显的物理意义。 本文的组织 本文组织如下： 第一章介绍了数据挖掘知识，包括数据挖掘的产生、应用与当前研究现 状，并着重介绍了时间序列数据挖掘的应用与发展。 第二章介绍了时间序列符号化的方法，包括一些经典的时间序列分段方 法，聚类方法，以及时间序列聚类分析中相似性度量方法的介绍。 第三章介绍本论文的研究课题交通流时间序列的符号化问题。针对 交通流数据和交通流数据挖掘的特征，提出了一种基于滑动窗口 ( s l i d i n gw i n d o w ) 以及累积和控制图( c u s u m ) 拐点检测相结合的 时间序列实时分段方法( s w c u s u m ) ，并讨论针对交通流时间序 列的聚类方法和相似性度量，提出了一个时间序列片段相似性度 量的方法，在此基础上应用层次化聚类方法得到符号化时问序列。 第四章介绍了实验的数据集，详细说明了实验的方法和实验结果。实验 结果表明，新的实时分段算法比滑动窗口法有大约2 0 精度的提 高，且分段后符号化数据有明显的物理意义。 2 交通流时间序列符号化方法研究 第一章时间序列数据挖掘研究 1 1 数据挖掘概述 1 1 1 数据挖掘的产生背景和研究现状 随着计算机技术的飞速发展和应用的普及，人类社会进入了一个信息化的 时代，人们利用信息技术生产和搜集数据的能力大大提高。一方面在商业管理、 政府办公、科学研究和工程开发等各个领域中，每天都会产生大量的数据，这些 数据以数字化的形式存储起来，并根据需要以电磁媒介加以传播。另一方面，支 持信息若享和传播的互联网技术近年来在世界范围内发展十分迅速，互联网加速 了信息在世界范围内的流动，形成了信息的海洋。这一方面使得越来越多的个体 可以享有网上的共享信息，另一方面也使得个体所拥有的信息量以指数级的速度 增加。 激增的数据信息背后隐藏着许多重要豹信息，人们希望能够对其进行更高层 次的分析，以便更好地利用这些数据。目前的数据库系统可以高效地实现数据的 录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有 的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致了“数 据爆炸但知识贫乏”的现象。 与此同时，计算机技术的另一领域人工智能白1 9 5 6 年诞生之后取得了 重大进展。经历了博弈时期、自然语言理解、知识工程等阶段，目前的研究热 点是机器学习。机器学习是用计算机模拟人类学习的一门科学，比较成熟的算法 有神经网络、遗传算法等。 用数据库来存储数据， 用机器学习的方法来分析数据，挖掘大量数据背后 的知识，这两者的结合促成了数据库知识发现( k d d ，k n o w l e d g ed i s c o v e r yi n d 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 l 届国际人工智能 联合会议的专题讨论会上。之后，于1 9 9 1 ，1 9 9 3 和1 9 9 4 年又接着继续举行 k d d 专题讨论会。发展到现在，k d d 国际研讨会已由原来的专题讨论会发展到 国际学术大会，研究重点也逐渐从发现方法转向系统应用，注重多种发现策略和 技术的集成，以及多种学科之间的相互渗透。1 9 9 5 年在加拿大召开了第一届知 识发现和数据挖掘国际学术会议。从1 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 am i n i n g ) ) ，国外在这方面发表了众多的研究成 果和论文。此外，在i n t e r n e t 上还有不少k d d 电子出版物，其中以半月刊 交通流时间序列符号化方法研究 k n o w l e d g ed i s c o v e r yn u g g e t s ) ) ( h t t p ：w w w k d n u g g e t s c o r n s u b s c r i b e h t m l ) 最为 权威。在网上还有许多自由论坛，如d me m a i lc l u b 等。目前已经有很多数据挖 掘软件系统出现，比较有影响的典型数据挖掘系统有：s a s 公司的e n t e r p r i s e m 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 t m 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 e q u e s tr e s e a r c h 公司的s e e 5 、 还有c o v e r s 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 yw o r k b e n c h 、d b m i n e r 、q u e s t 等。对k d d 和数据挖掘的研究已成为国际计算机领域的一个热门课题。我国 近几年也逐渐跟上国际步伐，国内的许多科研单位和高等院校竞相开展知识发现 的基础理论及其应用研究，许多计算机、数据库、人工智能、机器学习领域的专 家学者投入到k d d 和数据挖掘的研究中，并已取得了一定的成果。 最近，g a r t n e rg r o u p 的一次高级技术调查将数据挖掘和人工智能列为“未来 三到五年内将对工业产生深远影响的五大关键技术”之首，并且还将并行处理体 系和数据挖掘列为未来五年内投资焦点的十大新兴技术前两位。根据最近 g a r t n e r 的h p c 研究表明，“随着数据捕获、传输和存储技术的快速发展，大型 系统用户将更多地需要采用新技术来挖掘市场以外的价值，采用更为广阔的并行 处理系统来创建新的商业增长点。” 1 1 2 数据挖掘的定义 数据挖掘通常又称为数据库中知识发现，就是从存放在数据库、数据仓库或 其他信息库中的大量数据里挖掘有趣知识的过程“1 ，这些知识是隐含的、事先未 知的、对决策有潜在价值的有用信息。还有很多近似的术语，如从数据库中发现 知识( k d m 、数据分析、数据融合( d a t af u s i o n ) 以及决策支持等。人们把原 始数据看作是形成知识的源泉，就像从矿石中采矿一样。原始数据可以是结构化 的，如关系型数据库中的数据，也可以是半结构化的，如文本、图形、图像数据， 甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以是非 数学的；可以是演绎的，也可以是归纳的。知识用概念、规则、模式、规律等方 式来表示。发现了的知识可以被用于信息管理、查询优化、决策支持、过程控制 等，还可以用于数据自身的维护。 数据库中的知识发现是一个多步骤的处理过程，一般分为： ( 1 ) 数据清理：消除噪声或不致数据； ( 2 ) 数据集成：多种数据源可以组合在一起； ( 3 ) 数据选择：从数据库中检索与分析任务相关的数据； ( 4 ) 数据变换：数据变化或统一成适合挖掘的形式，如通过汇总或聚集操 作： 4 交通流时间序列符号化方法研究 ( 5 ) 数据挖掘：基本步骤，使用智能方法提取数据模式； ( 6 ) 模式评估：根据某种兴趣度度量，识别表示知识的真正有趣的模式； ( 7 ) 知识表示：使用可视化和知识表示技术，向用户提供挖掘的知识。 数据挖掘步骤可以与用户或知识库交互，有趣的模式提供给用户，或作为 新的知识存放在知识库中。由此可见，数据挖掘只是数据库中知识发现的一个步 骤，但又是最重要的一步。因此，往往可以不加区别地使用k d d 和数据挖掘。 一般在研究领域称之为数据库中知识发现，在工程领域则称之为数据挖掘。 数据挖掘是一门广义的交叉学科，涉及多学科技术的集成，包括数据库技术、 人工智能、统计学、机器学习、高性能计算、模式识别、神经网络、数据可视化、 信息检索、知识库系统、图像与信号处理和空间数据分析。机器学习和数据分析 的理论及实践是数据挖掘研究的基础，极大的商业应用前景又是数据挖掘研究工 作的巨大推动力。传统的数据库查询和统计、报表的处理方式都是对指定的数据 进行简单的数字处理，而不能对这些数据所包含的内在信息进行提取，因此只能 够提供用户想要的信息，而数据挖掘技术则可以发现用户没有意识到的未知的有 价值倍息。作为一种在海量数据中发现知识的手段，与传统的数据分析( 如查询、 报表、联机应用分析o l a p 等) 的本质区别在于数据挖掘是在没有明确假设的前 提下去挖掘信息、发现知识的，它可以从大型的数据库或数据仓库中提出隐藏的 预测性信息，从浩如烟海的企业信息资料库中挖掘出更有价值的信息。数据仓库 技术的发展与数据挖掘有着密切的关系。数据仓库的发展是促进数据挖掘越来越 热的原因之一。但是，数据仓库并不是数据挖掘的先决条件，因为有很多数据挖 掘可直接从操作数据源中挖掘信息。因此，数据挖掘技术具有十分广泛的应用前 景。 1 1 3 数据挖掘的方法 数据挖掘的方法“1 很多，从不同的视角看，数据挖掘有几种分类方法：根据发 现知识的种类分类；根据采掘的数据库的种类分类和根据采用的技术分类等 根据挖掘的数据库分类，数据挖掘基于的数据库类型有：关系型 ( r e l a t i o n a l ) 、事务型( t r a n s a c t i o n a l ) 、面向对象型( o b j e c t e d o r i e n t e d ) 、主动 型( a c t i v e ) 、空间型( s p a t i a l ) 、时间型( t e m p o r a l ) 、文本型( t e x t u a l ) 、多媒 体( m u l t i - m e d i a ) 、异质( h e t e r o g e n e o u s ) 数据库和遗留( l e g a c y ) 系统等。 根据采用的技术分类有：人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k s ) 、决策 树( d e c i s i o nt r e e s ) 、遗传算法( g e n e t i ca l g o r i t h m s ) 、最近邻技术( n e a r e s tn e i g h b o r m e t h o d 、可视化技术( v i s u a l i z a t i o n ) 等。 5 交通流时间序列符号化方法研究 最常用的分类方法是根据发现知识的种类不同来分类，主要有如下的几种分 析方法： ( 1 ) 概念类描述 用汇总的、简洁的、精确的方式描述每个类和概念称为类概念描述 ( c l a s s c o n c e p td e s e r i p t i o n ) 。这种描述可以通过下述方法得到；第一、数据特征化， 一般地汇总所研究类的数据；第二、数据区分，将所研究类与一个或多个比较类 进行比较；第三、数据特征化和比较。 ( 2 ) 关联分析 关联分析是指大量数据中项集之间有趣的关联或相关联系。随着大量数据 不停地收集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越来越感 兴趣。从大量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制 定。如购物篮的例子：在销售食品柜台发现，在购买牛奶的客户中，有8 0 的人 同时也购买了面包和饼干，用规则：牛奶 面包+ 饼干表示。发现这样的规 则可以设计方便顾客购物的商品货架、指导商家进货，对于确定市场策略是很有 价值的。关联规则还可以应用到附加邮递、仓储规划以及基于购买模式对用户进 行分类等方面。 ( 3 ) 分类和预测 分类和预测是两种数据分析形式，可以用于提取描述重要数据类的模型或 预测朱来的数据趋势。其中，分类是预测分类标号( 或离散值) ，而预测是建立 连续值函数模型。例如，可以建立一个分类模型，对银行贷款的安全或风险进行 分类；同时可以建立预测模型，给定潜在顾客的收入和职业，预测它们在计算机 设备上的花费。 ( 4 ) 聚类分析 聚类与分类的不同之处在于，它要划分的类是未知的。聚类就是将数据对 象分组成为多个类或簇( c l u s t e r ) ，在同一个簇中的对象之间具有较高的相似度， 而不同簇中的对象差别较大。在许多应用中，可以将一个簇中的数据对象作为一 个整体来看待。聚类分析在市场营销、生物学、交通等领域都有广泛的应用。例 如在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且 用购买模式来刻画不同的客户群的特征；在生物学上，聚类能用于推导植物和动 物的分类，对基因进行分类，获得对种群中固有结构的认识。 ( 5 ) 孤立点分析 经常存在一些数据对象，它们不符合数据的一般模型，这样的数据对象被 称为孤立点( o u t l i e r ) 。孤立点可能是度量或执行错误所导致的，也可能是固有 的数据变异的结果。许多数据挖掘算法试图使孤立点的影响最小化，或者排除它 们。但是，孤立点本身可能就是非常重要的，孤立点探测和分析是一个有趣的数 6 交通流时间序列符号化方法研究 据挖掘任务，被称为“孤立点挖掘”。孤立点挖掘有着广泛的应用，例如在欺诈 监测中，孤立点可能预示着欺诈行为，可用来探测不寻常的信用卡使用或电信服 务。 ( 6 ) 演变分析 数据演变分析( e v o l u t i o na n a l y s i s ) 描述行为随时间变化的对象的规律或趋 势，并对其建模。例如你有纽约股票交易所过去几年的主要股票市场数据，并希 望投资于高科技工业公司的股票。股票交易数据的挖掘研究可以识别整个股票市 场和特定公司的股票演变规律。这种规律可以帮助预测股票市场价格的未来走 向，帮助你对股票投资作出决策。 1 1 3 数据挖掘的热点和未来研究方向 就目前来看，数据挖掘的几个热点包括基于w e b 的数据挖掘( w e b d a t a m i n i n g ) 、时空数据挖掘( s p a t b - t e m p o r a ld a t a m i n i n g ) 、生物信息或基因 ( b i o i n f o r m a t i c s g e n o m i c s ) 的数据挖掘及其文本的数据挖掘( t e x t u a l m i n i n g ) 。 1 2 时间序列数据挖掘 数据挖掘技术开始主要面对的是以结构化数据为主的关系数据库、事务数据 库，和数据仓库。随着数据处理工具、先进数据库技术以及万维网( w w w ) 技 术的迅速发展，大量的形式各异的复杂类型的数据( 如结构化与非结构化数据、 超文本与多媒体数据等) 不断涌现。因此数据挖掘面临的一个重要的课题就是针 对复杂类型数据的挖掘，这包括复杂对象、空间数据、多媒体数据、时间序列数 据、文本数据和w e b 数据。本论文所要研究的就是时间序列数据的挖掘，下面 我们将讨论时间序列数据挖掘的一些基本情况，包括研究背景、基本概念、技术 以及研究现状。 1 2 1 时间序列挖掘的研究背景 在现实生活中，大量数据集中的数据都带有时间特征。时间序列随处可见， 遍及经济、气象、通信、医疗等多个领域。w e b 页的访问量，广深铁路每天的 人流量，深圳证券交易每天产生的股票收盘价格，广州每天的气温变化情况，医 7 交通流时间序列符号化方法研究 院每月的病人数等都是比较常见的例子。 对时间序列进行分析，从中获取所蕴涵的关于生成时间序列的系统的演化规 律，以形成对系统的观测以及未来的预测，这在工程应用中具有重要的价值和意 义，时间序列分析技术就起源于对市场经济的预测。经过近一个世纪的发展，时 间序列分析技术己取得长足的成果。但是随着现代科学技术的发展，社会、科学、 经济、技术等领域中广泛存在着大量的时间序列数据有待进一步的分析和处理， 人们希望通过对时间序列的分析，从大量的数据中发现和揭示某一现象的发展变 化规律或从动态的角度刻画某一现象与其他现象之间的内在数量关系及其变化 规律，尽可能多的从中提取出我们所需要的准确信息，并将这些知识和信息用于 预测，以掌握和控制未来行为。面对这一需求，将数据挖掘的思想引入到时间序 列分析中，时间序列数据挖掘技术( t i m es e r i e sd a t am i n i n g 简称t s d m ) 应运 面生。 时间序列数据挖掘通过研究信息的时间特性，深入洞悉事物进化的机制，帮 助人们获取时间信息背后事物随时间变化发展的规律，对于进去信息时代的我们 具有十分重大的意义。时间序列数据挖掘就是要从大量的时间序列数据中提取人 们事先不知道的、但又是潜在有用的与时间属性相关的信息和知识，或用于分析 或用于预测，指导人们的社会、交通、经济和生活等行为。自从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 v c 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 9 9 5 年至今，历届 k d d 会议和噩太地区的p a k d d 会议中收录的t s d m 的论文呈现一种明显的上升 趋势，时间序列数据挖掘已成为数据挖掘的研究热点之一。 1 2 2 时间序列的分类和变动特点 时间序列最普遍的定义为。1 ：以固定时间为间隔，且依顺序先后排列的一连 串数值数据。根据其所研究的依据不同，对时间序列有很多的分类方法，主要的 有：按所研究的对象的多少，可分为一元时间序列和多元时间序列；按时间的连 续性，可将时间序列分为离散时间序列和连续时间序列两种：按序列的统计特性， 可分为平稳时间序列和非平稳时间序列；按序列的分布规律来分，可分为高斯型 8 交通流时间序列符号化方法研究 ( g u a s s h n ) 和非高斯型( n o n g u a s s h n ) 时闾序列。 时间序列分析中比较关心它的变动特点，这主要有以下几个方面： ( 1 ) 趋势性：某个变量随着时间进展或自变量变化，呈现一种比较缓慢而长 期的持续上升、下降、停留的同性质变动趋向，但变动幅度可能不等。 ( 2 ) 周期性：某因素由于外部影响随着自然季节的交替出现高峰与低谷的规 律。 ( 3 ) 随机性：个别为随机变动，整体呈统计规律。 ( 4 ) 综合性：实际变化情况一般是几种变动的叠加或组合。 1 2 3 时间序列挖掘的主要方向 理论上说，数据挖掘的方法可以处理各种数据，因此数据挖掘的一般方法都 可以应用于时间序列的挖掘。而针对时间序列的特点，趋势分析、相似性搜索、 与时间有关数据的序列模式挖掘、周期模式挖掘这几个方向是研究的重点。 1 趋势分析 时间序列的趋势分析主要有这个比较关注的方面 1 ) 长时间的走向：比如在很长一段时间内道路占有率总的走向趋势， 2 1 周期的走向与周期的变化：比如说周期的拉长，延迟趋向等， 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 ) 。其中子序列匹配是找出 与给定序列相似的所有数据序列，而整体序列匹配是找出彼此间相似的序列。时 间序列分析中的相似性搜索在金融市场的分析( 如股票数据分析) ，医疗诊断分 9 交通流时间序列符号化方法研究 析( 如心电图分析) ，和科学与工程数据库分析( 如能量消耗分析) 等都大有用 武之地。 3 序列模式挖掘 序列模式挖掘( s e q u e n c ep a t t e r nm i n i n g ) 是指挖掘相对时间或其他模式出现 频率高的模式。由于很多商业交易、电话记录、天气数据和生产过程都是时间序 列数据，在针对目标市场、客户吸引、气象预报等的数据分析中，序列模式挖掘 是很有用的。一个典型的序列模式的例子是：两天前购买电脑客户很可能在一个 月内定购新的打印机。 4 周期分析 周期分析是指对周期模式的挖掘，即在时间序列数据库中找出重复的模式。 周期模式可以应用于许多重要的领域，例如季节，潮汐，行星轨道，每日能源消 耗，每日交通模式，和每周特定时间的所有t v 节目等等。周期分析的一个典型 的例子是“基于每天的交通统计数据，若周末上午天气好的话，则晚上的城市道 路占有率也会比较高”。 1 0 交通流时间序列符号化方法研究 第二章时间序列符号化方法 一般而言，数据挖掘所分析的资料可分为静态资料及动态资料两种主要类 型。l a s te ta 1 。3 认为静态资料库与动态资料库的差别在于，在静态资料库中， 一项记录内的某属性值与其他记录中同个属性值的关系相互独立；而在动态资料 库中，某些属性是把记录依时间排列才有意义。时间序列便是一种动态资料库中 的资料，其最普遍的定义嗍为：以固定时间为间隔，且依顺序先后排列的一连串 数值数据。针对时间序列的数据挖掘研究，从大量的时间序列数据中发掘有价值 的规律性信息的算法及实现技术，也是一个新的、极具挑战性和有重要应用前景 的研究领域。 数据挖掘关注规则( 也称为知识) 的发现，而规则总是用符号表示的，所以 针对时间序列首先就必须研究如何将以连续的数值形式表示的时间序列转换成 相对抽象的符号表示的符号序列( s y m b o ls e q u e n c e ) 。h a n & k a m b e r “1 认为，通 过将时间序列从时间领域( t i m ed o m a i n ) 转换成频率领域( f r e q u e n c yd o m a i n ) ， 则可以利用欧氏距离为度量方式来计算时间序列的相似度( 参见2 2 4 节) 。也就 是说，利用一些频率领域的数据表示方法，比如说傅立叶变换( d i s c r e t ef o u r i e r t r a n s f o r m , d f i ) 、离散小波变换( d i s c r e t ew a v e l e tt r a n s f o r m , d w t ) 等处理时间 序列数据，就可以利用一些距离度量的方法来对时问序列的相似度做简单有效的 运算。 另外，g a v r i l o ve ta l “1 针对历史股价所形成的时间序列资料进行研究后，认 为在将数据库中的时间序列数据依其转变过程的相似度分类时，若将原为一整段 的时间序列切割成数个片段后，再进行分类，则其效果比未分段的时间序列好得 多。 本文所讨论的时间序列符号化，就是一种基于以上思想将时间序列转换的方 法。为实现时间序列符号化，通常需要两个主要步骤：一、首先需要采用一定的 方法将时间序列分段；二、采用聚类的方法将分段后得到的子序列( 片段) 进行 分类，为每类赋予相应的类别标签，并用类别标签序列代替原始数值序列，从而 实现时间序列的符号化。其中，对时间序列进行分段的方法尤为重要。 2 1 时间序列分段 l a s tc t a 1 “以信号处理( s i g n a lp r o c e s s i n g ) 和信息理论模糊方法 ( i n f o r m a t i o n - t h e o r e t i cf u z z ya p p r o a c h ) 为基础，提出了个时间序列数据挖掘的 方法。这种方法将时间序列数据挖掘的过程分为三大步骤，即：数据预处理、数 据挖掘以及后期处理。其中数据预处理阶段有两大目标，分别为数据清理和特征 交通流时间序列符号化方法研究 提取。而时间序列分段便是一种特征提取的技术。 以时间序列分段后的长度为标准，可以将时间序列分段的方法分为两大类。 第一类，各片段等长的分段方法，顾名思义，这类时间序列样式描述方式，是将 时间序列分割为数个等长的片段，并利用距离计算的方式来度量不同时间序列的 相似度1 。第二类为片段不等长的分段方法，这类方法主要用于对特定的时间序 列做特征提取，因而对不同的应用数据往往有不同方法来达到满意效果。 2 1 1 片段等长的分段方法 片段等长的分段方法。“1 中，最简便的就是片段聚合趋近法。1 ，它的思想如 下： ( 1 ) 将长度为1 1 的时间序列x 分为n 等分，使每一个片段的长度相等。 r 2 ) 使用每段内资料的平均值来代表该片段资料的特征。 另外，h a a r 离散式小波变换的计算方式是一种层次化的分段方法，即不断地将 时间序列分为两等分，每分割一个层次，片段地数量就变为原来的两倍，片段的 长度同时缩减为原来的二分之一长嘲。在分割的时候，同时记录每两次做等分切 割时所造成的平均值差额，做为新序列的特征数，且第i 层会产生2 1 个特征值， 最多可以达到第l o g n 层。然而，层数越高，代表着越短时间内的特征值，反之， 越低则代表更短时间内的特征值。 2 1 2 片段不等长的分段方法 片段不等长的时间序列分段，一般来说有两种切入方法“1 。第一种，就是从 时间序列的众多数据中，找出几个特别的数据，把它们看成是不同时间序列片段 之间衔接的转折点，或拐点。r a b i n e r ”1 便提出了一种拐点的选取方法，将拐点看 成为邻近的一些数据中的最大值或最小值。另外，m a n w o n g8 1 利用一个重要 性评价函数来衡量每个数据点对于时间序列的重要程度，该重要点则为特定长度 内区域内的最大值或最小值。其中，重要性较高的数据， 被看作是转折点。 第二种，是从统计的角度，将具有相同性质的数据同其他数据区别开来。这 类方法通常是利用某种概率分配来将时间序列尝试不同的分段，直到达到某个特 定的域值。而利用概率分配的方法将一连串的时间序列数据分段，最简单的方法 就是利用简单线性回归来描述时间序列，这类时间序列分段的方法有很多，思想 都是基于递归( r e c u r s i v e ) 的方法重复计算，直到达到某个特定的域值。而这些域 值可以是分段后各片段成本函数的上限值，分段后总体成本函数的上限值，或是 交通流时间序列符号化方法研究 分割后形成的时间序列片段数量。其中，成本函数可以是任意函数，可以用来度 量时间序列特征与原数据之间的适合度。对于简单线性回归的方法，则成本函数 可以是分段内差异( r e s i d u a le r r o r ) 、误差平方和( s u mo fs q u a r e de r r o r ) ，或是均方 差( m e a no fs q u a r e de r r o r ) 。主要有以下几类： 自顶向下法( t o p d o w n ) 9 3 ：将初始时间序列看成一个整体，采用递归与分治 的策略，针对一时间序列，不断地基于拐点进行二分，直到达到某个设定的阈值 为止，从而实现对该时间序列的有效分段。它的算法描述如下： 图2 1 自顶向下法 以上程序段中，c a c u l a t e e r r o “a 3 为计算成本函数。 自底向上法a b 0 t t o 肌u p ) 9 1 ：将初始时间序列分成一个个最小的单位，然后根 据一定的策略两两合并，直到达到某个设定的阈值为止，从而实现对该时间序 列的有效分段。它的算法描述如下： 交通流时间序列符号化方法研究 图2 2 自底向上法 以上程序段中，c a c u l a t e - e r r o r 0 为计算成本函数。 滑动窗口法( s l i d i n gw i n d o w ) ”：选定一个固定宽度的窗口，从时间序列的一端 开始滑动，当滑动到某一点，使得已扫描的时间序列片段的段内成本达到某一个 设定的域值，以当前点数据点作为片段间的分割点。继续滑动直到所有序列都扫 描完成。这是一种实时( o n l i n e ) 的方法，它的算法描述如下： 图2 - - 3 滑动窗口法 以上程序段中，c a c u l a t e - e r r o r 0 为计算成本函数。 1 4 交通流时间序列符号化方法研究 全局反复取代法( g l o b a li t e r a t i v er e p l a c e m e n t ，g i r ) “”：在确定时间序列分 段的数目的情况下，可以采取这种方法。其主要思想如下： ( 1 ) 在时间序列上随机选取一些分割点； f 2 ) 根据已选取的分割点计算成本函数； 将造成误差最大的分割点删除； m 重新搜寻一个造成误差最小的分割点： f 5 、重复步骤2 至4 ，直到满足某个设定的域值雨不再有分割点需要更换位置 时为止。 以上这些方法( 自顶向下法，自底向上法，滑动窗口法，滑动窗口法， 全局反复取代法) 中，只有滑动窗口法是一种实时( o n l i n e ) 的方法。根据文 献【9 1 的研究指出，自顶向下法和自底向上法在几乎所有情况下效果要优于滑 动窗口法。而在很多实际应用中，滑动窗口法由于其实时性，应用很广。 2 2 时间序列聚类 将时间序列分段后，要迸步实现符号化，就需要采用聚类分析方法，对这 些分段进行分组，然后对被分到各个组的时间序列进行标记，从而实现时间序列 的符号化。 2 2 1 聚类分析简介 将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程被称 为聚类“”。由聚类所生成的簇是一组数据对象的集合，这些对象与同个簇中 的对象彼此相似，与其他簇中的对象相异。在许多应用中，可以将一个簇中的数 据对象作为一个整体来对待。 “聚类的典型应用是什么? ”在商务上，聚类能够帮助市场分析人员从客 户基本库中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。在 生物学上，聚类能用于推导植物和动物的分类，对基因进行分类，获得对种群中 固有结构的认识。聚类在地球观测数据库中相似地区的确定，汽车保险单持有者 的分组，及根据房子的类型、价值和地理位置对一个城市中房屋的分组上也可以 发挥作用。聚类也能用于对w e b 上的文档进行分类，以发现信息。作为一个数 据挖掘的功能，聚类分析能作为一个独立的工具来获得数据分布的情况，观察每 个簇的特点，集中对特定的某些簇做进一步的分析。此外，聚类分析可以作为其 他算法( 如特征和分类等) 的预处理步骤，这些算法再在生成的簇上进行处理。 数据聚类正在蓬勃发展，有贡献的研究领域包括数据挖掘，统计学，机器学 习，空间数据库技术，生物学，以及市场营销。由于数据库中收集了大量的数据， 交通流时间序列符号化方法研究 聚类分析已经成为数据挖掘研究领域中一个非常活跃的研究课题。 作为统计学的一个分支，聚类分析已经被广泛地研究了许多年，主要集中在 基于距离的聚类分析。基于k - m e a n s ( k 平均值) 、k - m e d o i d s ( k 中心点) 和其他一些 方法的聚类分析工具已经被加入到许多统计分析软件包或系统中，例如s - p l u s ， s p s s ，以及s a s 。在机器学习领域，聚类是无指导学习( u n s u p e r v i s e dl e a r n i n g ) 的一个例子。与分类不同，聚类和无指导学习不依赖预先定义的类和带类标号的 训练实例。由于这个原因，聚类是观察式学习，而不是示例式学习。在概念聚类 ( c o n c e p t u a lc h s t e r m g ) 中，一组对象只有当它们可以被一个概念描述时才形成 一个簇。这不同于基于几何距离来度量相似度的传统聚类。概念聚类由两个部分 组成：( 1 ) 发现合适的簇；( 2 ) 形成对每个簇的描述。在这里，追求较高类内相 似度和较低类问相似度的指导原则仍然适用。 在数据挖掘领域，研究工作已经集中在为大型数据库的有效和实际的聚类分 析寻找适当的方法。活跃的研究主题集中在聚类方法的可伸缩性，方法对聚类复 杂形状和类型的数据的有效性，高维聚类分析技术，以及针对大型数据库中混合 数值和分类数据的聚类方法。 聚类是一个富有挑战性的研究领域，它的潜在应用提出了各自特殊的要求。 数据挖掘对聚类的典型要求有：可伸缩性、处理不同类型属性的能力、发现任意 形状的聚类、用于决定输入参数的领域知识最小化、处理噪声数据的能力、对于 输入记录的顺序不敏感、高维性( h i g hd i m e n s i o n a l i t y ) 、基于约束的聚类、可解 释性和可用性。 2 2 2 聚类分析的数据结构 假定初始数据集合包含n 个数据对象，这些数据对象可能表示人、房子、文 档、国家等。许多基于内存的聚类算法选择如下两种有代表性的数据结构“1 ： 数据矩阵( d a t am a t r i x ，或称为对象与变量结构) ：它用p 个变量( 也称 为度量或属性) 来表现n 个对象，例如用年龄、身高、体重、性别、种族 等属性来表现对象“人”。这种数据结构是关系表的形式，或者看成n x p ( n 个对象p 个变量) 的矩阵。 x l l x v x l p ： x i l x i f x i p x n l x n f x n p 相异度矩阵( d i s s i m i l a r i t ym a t r i x ，或称为对象对象结构) ：存储n 个对 象两两之间的近似性，表现形式是一个n x n 维的矩阵。 交通流时间序列符号化方法研究 0 d ( 2 山0 d ( 3 ，1 ) d ( 3 ，2