（计算机应用技术专业论文）多维时间序列分类技术.pdf

浙江大学硕士学位论文摘要 摘要 时间序列问题广泛存在于诸多应用领域中，因此近年来获得了数据挖掘领域 研究者的普遍关注。多数应用领域中，随着多媒体技术的迅速发展，产生了越来 越多的多维时间序列数据，其中包括动作捕捉数据，生物信息序列，金融数据， 移动对象跟踪，人机交互接口等许多类别的多维时间序列数据。然而，目前该领 域所取得的大多数研究成果基本都是面向一维时间序列的。因此，数据挖掘领域 十分需要一种为时间序列处理，尤其是模式识别应用提供的面向多维时间序列这 种数据形式的解决方案。 针对多维时间序列的特性，本文提出了一种简单而有效的基于c 4 5 决策树的 分类模型，命名为c m m ( c l a s s i f i c a t i o nm o d e lf o rm u l t i v a r i a t et i m es e r i e s ) 。c m m 包含数据预处理和模型分类两个部分。其中，数据预处理由两个阶段组成，即特 征提取和维度分级及选择两个阶段。在特征提取阶段，我们首先采用c h e b y s h e v 拟合主导的自底向上的分段算法对时间序列施行多维分段，即综合考虑全部维度 的形态，而不是将各维度割裂开来独立对待。然后c m m 从每段的每一维度中只 提取一个c h e b y s h e v 系数作为该段该维度的局部特征，生成特征矩阵。维度分级 及选择采用监督模式。c m m 使用c o m b i n e di n f o r m a t i o ng a i nr a t i o 作为每一维度的 分级标准，c o m b i n e di n f o r m a t i o ng a i nr a t i o 量化了该维度的分类能力。c m m 选择 前k 个分类能力最强的维度，使用这k 个维度中的特征来构成特征向量，对原始 多维时间序列向量化。数据预处理阶段获得的特征向量将作为下面分类阶段决策 树的输入。实验证明，与传统算法比较，c m m 在分类精度和c p u 处理时间方面 的性能都获得了较大改进。 关键词：多维时间序列，分类，决策树，多维分段，切比雪夫系数，维度分级 与选择。 浙江大学硕士学位论文 a b s 仃a c t a b s t r a c t t h ep r o b l e mo ft i m es e r i e sp a t t e r nr e c o g n i t i o nh a sd r a w ni n t e n s i v ea t t e n t i o n 舶mt h e d a t am i n i n gc o m m u n i t y , d u et oi t sp r e v a l e n c ei nn u m e r o u sa p p l i c a t i o n s i nm o s t a p p l i c a t i o n s ，e s p e c i a l l yw i t ht h ew i d e s p r e a dp r o l i f e r a t i o no fm u l t i m e d i at e c h n o l o g y , m o r ea n dm o r em u l t i v a r i a t et i m es e r i e sd a t ah a v ea p p e a r e d t h e s ei n c l u d em o t i o n c a p t u r ed a t a ，b i o i n f o r m a t i c ss e q u e n c e ，f i n a n c i a ld a t a ，m o v i n go b j e c t st r a c k i n g ，h u m a n a n d c o m p u t e ri n t e r f a c ea n dm a n yo t h e r s h o w e v e r , m o s tp r o g r e s sa c h i e v e di nt h i sa r e a h a sf o c u s e do na d d r e s s i n gu n i v a r i a t et i m es e r i e sp r o b l e m s t h e r e f o r e ，t h e r ei sa s t r o n g d e m a n df o rp r o v i d i n gs o l u t i o n st h a ta d d r e s st h e s et y p e so fm u l t i v a r i a t ed a t af o rt i m e s e r i e sr e t r i e v a l ，e s p e c i a l l yf o rp a t t e r nr e c o g n i t i o na p p l i c a t i o n s i nt h i st h e s i s ，w ep r o p o s ec m m ，a s i m p l ey e te f f e c t i v ec l a s s i f i c a t i o nm o d e lt h a t a d d r e s s e st h ec h a r a c t e r i s t i c so fm u l t i v a r i a t et i m es e r i e sd a t a c m m ，w h i c hi sb a s e d o nd e c i s i o nt r e e ，h a st w op a r t s ：d a t ap r e p r o c e s s i n ga n dd e c i s i o nt r e ec l a s s i f i c a t i o n u n d e rc m m ，d a t a p r e p r o c e s s i n gc o n s i s t so ft w op h a s e s ，n a m e l yf e a t u r ee x t r a c t i o na n d d i m e n s i o nr a n k i n ga n ds e l e c t i o n i nt h ef e a t u r ee x t r a c t i o np h a s e ，r a t h e rt h a nt r e a te a c h d i m e n s i o no ft h em u l t i v a r i a t ed a t as e p a r a t e l ya so t h e rm e t h o d sd o ，c 3 mc o n s i d e r sa l l t h ed i m e n s i o n sa l t o g e t h e rw h e ns e g m e n t a t i o ni s p e r f o r m e dt ot h es e q u e n c e t h e nf o r e a c hs e g m e n t ，c 3 me x t r a c t so n l yo n ec o e f f i c i e n to ft h ec h e b y s h e vp o l y n o m i a l st h a t a r eu s e dt oa p p r o x i m a t et h a ts e g m e n ta st h el o c a lf e a t u r e d i m e n s i o nr a n k i n ga n d s e l e c t i o na d o p t sas u p e r v i s e dm a n n e r , i nw h i c hf e a t u r e d i m e n s i o n sa r er a n k e d a c c o r d i n gt ot h e i rc o m b i n e di n f o r m a t i o ng a i nr a t i o ，a ni n d i c a t o ro ft h e i rp r e d i c t i v e a b i l i t y c 3 mt h e ns e l e c t st h et o p - kp r e d i c t i v ed i m e n s i o n s ，a n df e a t u r e si nt h o s ek d i m e n s i o n sa r eu s e dt ov e c t o r i z et h eo r i g i n a lm u l t i v a r i a t ed a t a t h e s ef e a t u r ev e c t o r s o b t a i n e di nd a t ap r e p r o c e s s i n gp h a s es e r v ea st h ei n p u tt ot h ed e c i s i o nt r e ec l a s s i f i e r i nt h es u b s e q u e n tc l a s s i f i c a t i o np a r t e x p e r i m e n t a lr e s u l t ss h o wt h a tc 3 ma c h i e v e s s i g n i f i c a n tp e r f o r m a n c ei m p r o v e m e n t si nt e r m so fb o t hc l a s s i f i c a t i o na c c u r a c ya n d p r o c e s s i n gt i m ec o m p a r e dt oc o n v e n t i o n a ls c h e m a 浙江大学硕士学位论文 a b s t r a c t m u l t i v a r i a t et i m es e r i e s ，c l a s s i f i c a t i o n ，d e c i s i o nt r e e ，m u l t i v a r i a t e s e g m e n t a t i o n ， c h e b y s h e v ec o e f f i c i e n t s ，d i m e n s i o nr a n k i n ga n ds e l e c t i o n 浙江大学硕士学位论文图目录 图目录 图1 1 时间序列3 图1 2 时间序列映射3 图3 1c m m 数据变化示意图1 7 图3 2c m m 整体框架1 8 图4 1 对高度相关的多维时间序列进行分段的两种方式2 2 图4 2 多维时间序列高度相关的维度2 2 图4 3c h e b y s h e v 多项式曲线2 4 图4 4 特征模式提取算法2 6 图4 5 特征模式提取阶段数据变化示意图2 8 图4 6 维度分级与选择算法3 3 图4 7 维度分级及选择阶段数据变化示意图3 4 图5 1 概念p l a y的决策树一35tennis 图5 2 生成决策树的基本算法3 7 图5 3 根据分裂原则划分元组的三种可能性3 9 图5 4 决策树剪枝前后4 1 图5 5 决策树训练示意图一4 3 图6 1g u n p o i n t 数据曲线一4 5 图6 2h u m a n g a i t 数据集对象标记点设置4 6 图6 3c r o s sv a l i d a t i o n 简化示意图4 7 图6 4 分类精度实验一5 0 图6 5c p u 时间实验51 图6 6 维度选择算法的效果与成本。5 3 浙江大学硕士学位论文 表目录 表目录 表3 1 文中符号意义1 8 表6 1 实验数据集4 5 表6 2 使用不同幂次的c h e b y s h e v 系数获得的分类精度5 4 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得盘姿盘堂或其他教育机构的学位或证书面使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：0 寸取 签字日期： 口， 年f 月矿日 学位论文版权使用授权书 本学位论文作者完全了解澎江盘茔 有权保留并向国家有关部门或机构送交本 论文的复印件和磁盘，允许论文被查阅和借阅。本人授权盘垒筮生可以将学位论文的 全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期： d 苫年，月 扩日 日 浙江人学硕士学位论文 第一章绪论 1 1 研究背景 第1 章绪论 时间序列( t i m es e r i e s ) 普遍存在于许多重要应用领域中，比如d n a 序列、 金融数据、传感器网络监控数据、移动对象跟踪数据以及运动捕获结果等都可以 视为时间序列。研究发现，从1 9 7 4 年至1 9 8 9 年发行的十五种世界知名报纸中随 机抽取4 , 0 0 0 张图片，其中超过7 5 的图片都包含有时间序列。近年来，随着这 些领域的快速发展，用户越来越多地需要有效地存储和检索时间序列数据。例如， 在医学应用中，研究人员借助于安置在试验者颅部的电极收集e e g 数据序列，通 过对其进行分析，来研究基因遗传与嗜酒症的关系。 由于其广阔的应用前景，时间序列检索问题( t i m es e r i e sr e t r i e v a l ) 引起了数 据挖掘领域研究者的极大兴趣，并且一直是学术界所关注的热点。它被认为是未 来最有前景的技术之一，同时涌现出大量高水平的研究成果。自从1 9 9 3 年 r a g r a w a l 1 1 等人提出时间序列相似搜索技术和1 9 9 4 年c f a l o u t s o s 2 】等人提出子 序列相似搜索方法，许多研究机构和一些著名的大学纷纷参与到时间序列的研究 中来，其中m m 公司的a l m a d e n 和w a t s o n 研究中心，m a r y l a n d 大学，c a r l i f o m i a u n i v e r s i t y 的一些研究小组( i r v i n e 、r i v e r s i d e 和s a n t ab a r b a r a 等) ，l u r b a n a c h a m p a i g n 的j h a n 研究小组以及c a r n e g i em e l l o n 大学、韩国少数大学和 研究机构等是其中比较著名的，它们当中包括一些比较活跃的个人，例如：a g r a w a l 、 f a l o u t s o s 、p a r k 、k e o g h 、k i m 以及m o o n 等。在国内，复旦大学、浙江大学和中 国科技大学在2 0 0 0 年后较早地开展了这方面的研究，而近年来的研究机构主要 包括香港中文大学、香港科技大学、东北大学以及南京大学等，但总体来说我国 的研究成果相对零散。近十年来著名的国际学术会议如s i g m o d 、v l d b 、p o d s 、 i c d e 以及期刊如i e e et k d e 、v l d bj o u r n a l 等都呈现了大量高水平的研究成果。 目前在时间序列检索与分类技术方面，大部分研究成果集中在针对一维时间 塑望查堂婴主兰竺丝茎笙二兰堑笙 序列( u n i v a r i a t et i m es e r i e s ) 的处理上【1 】【2 】【3 】【4 】【5 】【6 】【7 】【8 】【9 】【1o 】【1 1 1 。然而，事实上，在 各领域的实际应用中，特别是由于多媒体数据在各领域中的大量出现，来自于 对多维时间序列( m u l t i v a r i a t et i m es e r i e s ) 处理的需求显得越来越重要。例如， 在移动计算领域，用户装备上移动设备在空间中移动，他们在不同时间通过无线 连接向时空数据库注册各自的位置。在环境信息系统中，诸如跟踪动物迁移、飓 风轨迹等应用保存被观察对象随着时间变动的位置，生成庞大的高维数据集【l2 1 。 在人体不同关节安置传感器，采样得到的动作捕捉数据也是多维数据。在计算机 图形学中，一个基本的操作是对相似的运动分聚类，并且这又可以产生一系列的 应用，比如交互式的动作生成【1 3 】。生命科学里的迁移物质也可以生成时空数据， 并集中在对细胞有丝分裂过程中细微模式的发现上。总之，任何包含多变量数据 存储的数据集都可以被视为多维时间序列来处理。在本文中，我们拟对多维时间 序列检索与分类技术进行深入地研究，以此对时间序列检索技术由单维向多维的 过渡进行进一步的探索。 综上所述，多维时间序列检索技术的研究具有现实的理论意义和广阔的应用 前景，但因多维时间序列的特性，使得这一问题的研究面临不小的挑战。 1 2 问题定义 1 2 1 时间序列 时间序列( t i m es e r i e s ) 是一组变量在连续的时间点上获得的一系列采样值。 长度为n 的d 维时间序列记为： 秘( t ) ；【f = 1 , 2 ，d ；t = 1 , 2 ，7 l 】 其中，i 索引时间点t 上第f 维变量x 的值。如果仅对单个变量进行采样，即d = 1 ， 那么所获得的时间序列称为一维时间序列( u n i v a r i a t et i m es e r i e s ) 。相反，如果采 样对象为多个变量，即d 1 ，那么所获得的时间序列则称为多维时间序列 ( m u l t i v a r i a t et i m es e r i e s ) 。一般地，一个长度为n 的d 维时间序列可以用一个d x n 矩阵k ， 如凡表示如下， 浙江大学硕j 二学位论文第一章绪论 雕麓 矩阵巾项亿砂为第i 维变量疋在时间点t 上的采样值。 这里定义的时间序列既包括按时f , - jj i d 序排列的数据列表，例如图1 1 ( a ) 中的 动作捕捉数据；同时包括现实世界对象或事件通过某种函数映射而来的时f , - - j 序列， 例如：图1 2 中( a ) 下面的曲线为图像形状映射的时间序列，图1 2 中( b ) 下面的曲 线为英文手迹映射的时f , - j 序列等。 叠蠢轧r 图1 1 时间序列 斌成撕山瓜 汁。，i 。一 ；r 面忑赢7 i - 02 0 04 0 06 0 08 0 01 0 0 0 1f 一 ( a ) 图1 2 时问序列映射 时间序列的数据通常存储在文件中，一般以数据库文件形式存放，这种数据 库称为时间序列数据库。 从时间序列的定义可知，时间序列并不是离散数据的简单排列，因此研究方 法绝不是离散数据研究方法的简单组合，时间序列研究有着它自身的特点和挑战。 主要表现在：首先，实际应用中的时间序列数据库往往相当庞大，所以需要一种 垦 浙江大学硕+ 学位论文 第一章绪论 易于存储、检索和传输的时间序列表示方式。第二，时间序列数据研究的核心概 念是“相似性 ，而“相似性”是一个比较主观的概念。时间序列相似性的定义 取决于用户、应用领域以及实际需求。此外，还存在其它烦杂但不可忽视的数据 处理问题，例如不同的数据表示形式，不同的采样率，噪音，漏值，等等。 对于上述难点，研究人员已经提出了面向一维时间序列的比较有效的解决方 案，能够在各自领域获得较为理想的效果。比如，k e o g h 提出的d y n a m i ct i m e w a r p i n g 算法l ，使时间序列检索的精度获得了很大的提高。但是，对于多维时 间序列检索的需求，实验证实将这些解决方案直接推广到多维时间序列并不能带 来期望的效果，因为多维时间序列有其自身的特点和挑战： 由于时间序列大多来源于传感器的记录，他们通常具有很高的维度和很 长的序列，并且包含大量噪音和错误。在众多维度中，部分维度是噪音 冗余不相关的，保留它们反而降低了整体检索模型的性能。 许多多维时间序列是集成数据，也就是说他们的各维度高度相关。因此， 数据处理技术应该综合考虑各维度的情况，以便于获得更有现实意义的 结果。将各维度分开考虑，将会导致有效信息的丢失。 多维时间序列数据集的规模能够迅速变大。加上很高的维度，即使经过 降低维度操作，多维数据往往仍然需要较大的存储空间，较高的传输带 宽。c u r s eo fd i m e n s i o n a l i t y 问题在这种情况下变得比较显著。因此，非 常需要一种高效的数据表示方法。 1 2 2 时间序列分类问题 时间序列分类问题由以下元素定义【1 4 】： 一个表示动态系统的轨迹或者场景的对象域u 。每个对象，o ，都在某 个有限的时间段内被观测 o ，争( d ) 】。 对象由一定数目的基于时间的属性来描述，这些属性都是对象和时间 的函数，因此定义在ux 【0 ，+ 】。我们用a ( o ，c ) 来表示对象0 在时间t 时的属性a 的值。 4 浙江大学硕士学位论文第一章绪论 每个对象被进一步划分到一个类别c ( d ) ( c 1 一，c m 。 给定域中对象的一个随机采样三s ，分类算法的目标就是找到一个函数厂( d ) ， 使它尽可能的接近真实的分类c ( d ) 。这个函数仅仅依赖于属性值，而不是依赖于 对象d ，即厂( d ) = f ( a ( o ，) ) ，其中a 表示属性向量。分类同样不能依赖于绝对时 间值，此性质要求构造的算法模型能够不受采样的时间区间的限制对每个场景加 以分类。 在上面的定义中，属性被定义为时间的连续函数。然而，在实践中，信号需 要采样以达到能够在计算机存储器中表示的目的。因此，每个场景都是用下面的 向量序列来描述的：( a0 1 t o ( o ) ) ，a ( d ，t 1 ( o ) ) ，a ( o ，t n ( d ) ) ) ，其中t f ( d ) = i - a t ( o ) ， i = o ，1 ，以俐。时间采样数目咒俐可以是对象相关的。 传统经典的时间序列分析主要包括模式识别和预测等方面。模式识别的范畴 包括比如判断一家公司在一年内的销售量成线性增长趋势( 趋势分析) ，也包括 比如分析出这家公司冬季的销售量是夏季的两倍( 季节性分析) 。关于预测范畴 的例子可以是根据过去以及目前的销售量推断出下个季度的预期销售量。近年来， 利用结合传统经典的时间序列分析方法，研究倾向于大规模时间序列处理方法的 需求获得了更加广泛的关注，主要包括以下方面： 分类( c l a s s i f i c a t i o n ) 。判断其他的基因是否也类似某种基因一样表达自身 属于此类。 分聚类( c l u s t e r i n g ) 。例如对机器人的经验进行归类。 相关规律性( a s s o c i a t i o nr u l e s ) 。例如获得“高峰相继高原，以信心指数 o 4 ，支持指数0 2 预示着下降趋势”这样的规则。 探索式数据分析( e x p l o r a t o r yd a t aa n a l y s i s ) 。通过数据交互了解数据的方 法属于此类。 本文关注的焦点拟限于研究时间序列的分类方法。主要基于以下考虑：第一， 分类问题的模型层次比较简单直观，使我们更容易看清问题本身，分析比较各部 分的性质。第二，分类问题可以看作其他复杂问题，比如查询问题，的简化，获 得分类问题的解决方法后能够比较容易的推广到其他问题。第三，现实应用领域 s 浙江大学硕士学位论文第一章绪论 中，往往关注研究对象的类别属性，人们往往只有在判定研究对象的分类的基础 上，才能根据类别采取相应的操作，解决问题。例如，股票分析师在提出投资建 议前，首先要经过观察股票市值走势提取特征，将走势归为某种特征类别，进而 预测未来走势。又如，临床诊断的重要依据e c g s ( e l e c t r o c a r d i o g r a m ，心电图) 数 据。病人胸腔疼痛，e c g 数据异常，医生搜索数据库( 这里当然是他个人的知识 积累和临床经验) 找到心电图走势类似哪类症状，是属于正常窦性心律，还是属 于恶性室性心律失常的走势，抑或是室上性心律失常的走势，进而获得诊断的线 索。第二，时间序列其他类型的研究问题，在某些情况下也可以转化为解决时间 序列分类问题，或者解决分类问题的研究方法。前面提到的根据“高峰”“高原 特征概率性的预测走势问题，从分类的角度考虑可以是这样的，将所有在某个概 率范围内预测为下降走势的目前特征归为一类，“高峰相继高原 应属于此类， 如果目前的时间序列符合“高峰相继高原 的特征，则预示了下降趋势。 1 3 研究内容 针对多维时间序列的特性，本文提出了一种简单而有效的基于决策树的分类 模型，称为c m m ( c l a s s i f i c a t i o nm o d e lf o rm u l t i v a r i a t et i m es e r i e s ) 。c m m 包含 数据预处理和模型分类两个过程。其中，数据预处理由两个阶段组成，即特征提 取和维度分级及选择两个阶段。在特征提取阶段，我们首先采用自下而上的分段 算法对时间序列施行多维分段，综合考虑全部维度的形态，而不是将各维度割裂 开来独立对待。然后c m m 从每一段的每一维度中只提取一个c h e b y s h e v 系数作 为该段该维度的局部特征。维度分级及选择阶段采用监督模式。c m m 使用 c o m b i n e di n f o r m a t i o ng a i nr a t i o 作为每一维度的分级标准，c o m b i n e di n f o r m a t i o n g a i nr a t i o 量化了该维度的分类能力。c m m 选择k 个分类能力最强的维度，使用 这k 个维度中的特征来构成特征向量，对原始多维时间序列向量化。数据预处理 阶段获得的特征向量将作为下面分类阶段决策树的输入。我们将通过实验，与传 统算法进行比较，评估c m m 的性能，证明c m m 的有效性。 6 浙江大学硕：f 学位论文第一章绪论 1 4 本文组织结构 根据上述研究问题和研究内容，文章其余部分内容组织如下： 第二章： 在本章中，我们从以下三个方面概括了近些年来国内外研究学者在多维时间 序列分析方面的研究成果和主要贡献：( 1 ) 时间序列转换，( 2 ) 时间序列相似度量和 ( 3 ) 多维时间序列扩展。为下面提出的模型提供了一些背景知识，也说明了本文研 究的分类技术具有广泛的学术意义和实际应用价值。 第三章： 本章首先介绍了多维时间序列的特点和研究现状，提出了c m m 模型的设计 动机和意图。然后，我们通过c m m 的整体框架图，从整体上总览了c m m 的设 计思路和涵盖的算法。 第四章： 本章详细描述了c m m 下数据预处理部分的算法。数据预处理部分由两个阶 段组成，即特征模式提取和维度分级及选择。经过数据预处理处理得到的特征矩 阵向量化后将作为后续决策树分类器的输入。 第五章： 本章详细描述了c m m 使用的分类器c 4 5 决策树算法。首先我们引入了决策 树并介绍了它的优点，以此说明c m m 引入c 4 5 决策树作为基本分类模型的原因。 然后我们详述了基本决策树的生成算法。最后，我们给出c 4 5 算法所使用的属性 选择标准和树剪枝策略。 第六章： 在本章中，我们通过实验在现实的多维时间序列数据集上进行测试我们的模 型，以证明c m m 的有效性。实验证明，c m m 在分类精度和处理时间两个方面 都优于以往的算法。同时，我们还通过对比维度选择前后的系统性能，说明了维 度选择算法的有效性和必要性。 第七章： 7 ! 坚查兰硕十学位论文 第一章绪论 本章对全文内容进行了总括，回顾了本文的主要研究内容，归纳了本文的主 要贡献以及创新点，并指出进一步可以进行研究的内容，作为下个阶段研究的重 点。 1 5 本章小结 在本章中，我们首先介绍了时间序列检索和分类技术的现实需求和研究情况， 提出了多维时间序列检索和分类技术的研究需求。然后，我们定义了研究问题一 一时间序列和时间序列分类，并介绍了它们各自的研究特性和所面临的挑战。最 后，我们概述了本文的主要研究工作及文章的组织结构。 浙江大学硕- 上学位论文 第二章相关工作综述 第2 章相关工作综述 在本章中，我们将具体地分析数据挖掘领域的研究学者近几年在时间序列检 索与分类方面的研究工作。关于时间序列的检索与分类问题，研究学者已经提出 了很多有效的解决方案，其中包括p i e c e w i s el i n e a rs e g m e n t a t i o n t 5 1 ，局部特征的 提取【2 1 或者局部特征与全局特征的结合【5 1 ，距离度量的定义【1 1 】【15 1 ，多维空间索引 改进【1 1 】，诸如d y n a m i ct i m ew a r p i n g 的各种变形技术【10 1 ，等等。这些技术可以 归纳为三个方面：时间序列转换，时间序列相似度量，多维时间序列扩展，多维 时间序列维度选择。 2 1 时间序列转换 由于时间序列是典型的高维数据，为了避免由于高维( 1 6 ) 而引起检索算法 性能急剧下降，即所谓的维度灾难( d i m e n s i o nc u r s e ) ，一般需要将时间序列降低 维度。时间序列转换是一类相对比较成熟的技术，也即降维技术。常见降维方法 主要有：d i s c r e t ef o u r i e rt r a n s f o r m ( d f t ) 【1 】【2 1 、d i s c r e t ew a v e l e tt r a n s f o r m ( d 、v t ) 【3 】、 s i n g u l a rv a l u ed e c o m p o s i t i o n ( s v d ) 【4 1 、p i e c e w i s el i n e a ra p p r o x i m a t i o n ( p l a ) t 5 1 、 p i e c e w i s e a g g r e g a t ea p p r o x i m a t i o n a a ) 【制、a d a p t i v e p i e c e w i s ec o n s t a n t a p p r o x i m a t i o n ( a p c a ) 7 1 、s y m b o l i ca g g r e g a t ea p p r o x i m a t i o n ( s a x ) t 8 】和 l a n d m a r k s 9 】等。 最先被用来对时间序列数据进行降维的是d i s c r e t ef o u r i e rt r a n s f o r m ( d f t ) ， 它计算并保留了前面的若干个f o u r i e r 系划1 】【2 1 。同样，c h a n & f u 将d i s c r e t eh a a r w a v e l e tt r a n s f o r m ( d w t ) t 3 1 引入降维方法中，使用h a a rw a v e l e tf u n c t i o n 通过 m o t h e rw a v e l e t 的和和差来表示时间序列数据，截取部分w a v e l e t 系数实现降维。 d w t 的缺点是要求数据序列的长度必须是2 的整数次幂，这个要求显然在实际 应用中比较难满足。s i n g u l a rv a l u ed e c o m p o s i t i o n ( s v d ) 是一种全局方法，它包含 空间的变换和裁剪【4 1 。k e o g h 证明s v d 能够提供比其他方法更强的裁剪能力【6 1 ， o 浙江大学硕上学位论文 第章相关工作综述 对数据库大小的扩展性更好。但是，s v d 的缺点是计算成本高，数据库的更新会 导致特征的重复计算。c a s t e l l i 使用s v d 及聚类来处理时间序列的近似相似检索 1 6 】。k e o g h 提出的p i e e e w i s ea g g r e g a t ea p p r o x i m a t i o n ( p a a ) 和a d a p t i v ep i e c e w i s e c o n s t a n ta p p r o x i m a t i o n ( a p c a ) 也可用于降低时间序列的维度【6 】【7 】，p a a 具有计算 速度快、易于实现、易于建索引等优点，在裁剪能力上也具有竞争力。尽管a p c a 的裁剪能力与s v d 比较尚不明朗，但是a p c a 在裁剪能力方面要优于d f t ，d w t ， p a a 。s a x 的设计基于p k a ，是时间序列的第一个符号表示方法，方法类似于 等频率直方图。第一个上面这些变换方法都是基于欧式距离的，p e m g 等人【9 】提出 的新的相似性模型l a n d m a r k s ，是一种非厶- n o r m 模型。这种模型很好地解决了 其它模型无法保留局部信息以及处理时间序列变形能力不够的不足。但其算法运 算复杂，降维能力也不如d f t 、d w t 等方法，而且不适合在线的实时分析。 降维方法要求能够保留大部分的时序特征信息，同时满足降维下界定理 ( 1 0 w e rb o u n d i n g ) ，即d 俐反( s q ) d ( s q ) 【2 】o 但不管那种技术和方法，我们都应该 从下面的因素去考虑：即，是否能够有效地降低数据的维度，且尽量保留原时间 序列中的信息；是否有利于索引的建立以及在索引中的搜索；是否剔除噪声和冗 余以利于算法的效率和精度；是否支持变长时间序列；是否采用符号表示法等。 2 2 时间序列相似度量 时间序列相似度量是高效时间序列相似搜索技术的基础。建立何种度量函数 来实现时序相似度量非常关键，我们不但要考虑各种度量函数的特性，还应该考 虑具体应用领域的实际需求。相似度量一般可分为基于形状的( s h a p e b a s e d ) 相似 度量、基于特征的( f e a t u r e b a s e d ) 相似度量、基于模型的( m o d e l b a s e d ) 相似度量以 及基于数据压缩的( c o m p r e s s i o n b a s e d ) 相似度量几种情形。已有的度量函数主要 包括： 上口n o 肌s 【1 1 、d y n a m i c t i m ew a r p i n g ( d t w ) t l o 】【11 1 、l o n g e s tc o m m o n s u b s e q u e n c e ( l c s s ) t 17 1 、e d i td i s t a n c eo nr e a ls e q u e n c e ( e d r ) 1 8 】和e d i td i s t a n c e w i t hr e a lp e n a l t y ( e r p ) t 1 9 1 等；而且，随着研究的深入必将出现新的时序相似度量 方法。 1 0 浙江大学硕士学位论文 第二章相关工作综述 d y n a m i ct i m ew a r p i n g 拥有将两个长度分别为n 和r n 的数据学列对齐。令 d i s t ( f ，力表示两个序列在位置i 和歹处的局部距离，d t w ( i ，力为两个序列在f 和 ，处积累的全局距离，则 d t w ( i ，力= n f i n 【d t w ( i 一1 ，歹1 ) ，d t w ( i - l ，d ，d t w ( i ，j 1 ) 】+ d i s t ( i ，力， 其中d t w ( j ，j ) = d i s t ( ，) 。为了提高计算速度，可以附加约束条件来限制 w a r p i n gw i n d o w 。 2 3 多维时间序列扩展 今年来，多维时间序列识别吸引了越来越多的研究学者的注意。面向多维数 据的距离度量被定义以反映多维数据的相似性。k a h v e c i 提出了处理等长度的多 维时间序列的方法【2 0 】，该方法定义序列距离时包含了对变形和位移的考虑，他同 时又提出了一种面向变形和位移的索引结构。但是距离定义和索引结构并不适用 于解决变化长度的多维时间序列问题。 l e e 将多维时间序列分割成为子序列【2 1 1 ，每个子序列包含在一个最小边界矩 阵( m i n i m u mb o u n d i n gr e c t a n g l e ，m b r ) 中。每个m b r 存储在数据库中，使用r - t r e e 或者它的变体对其索引。估算的m b r 被采用以加速相似动作的查询。如果两个 序列长度不等，两个序列比较时短序列从长序列的开头滑行到结尾。但是，如此 就使得方法不能识别两个不同时长或者有局部加速和减速的相似序列了。 k a t o u s 从多维时间序列中提取出参数化的事件( p a r a m e t e r i z e de v e n t s ) ，然后 在参数空间中对其分聚类【2 2 1 。获得的原型与同时从源数据中提取出的全局特征模 式组合一同作为训练数据，对下面的学习模型进行训练。 g e u r t s 提出用一种模式提取方法解决多维时间序列的分类问题，通过将模式 融入决策树来组合模式【2 3 】。 “等人提出了基于支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 的多时间序 列实是分类模型【2 4 1 。通过对时间序列进行奇异向量分解( s i n g u l a rv e c t o r d e c o m p o s i t i o n ，s v d ) 计算特征向量。这些特征向量与它们相对应的类别符号一起 输入支持向量机( s v m ) ，将其训练成为分类器。然而，此方法的缺点是，对奇异 浙江大学硕士学位论文第_ 章相关工作综述 向量分解的计算代价非常高。当新的时间序列加入到训练集中时，训练集中的全 部时间序列的特征向量都要进行重新计算。 v l a c h o s 和h a d j i e l e f i h e d o u 将d y n a m i ct i m ew a r p i n g ( d t w ) 和l o n g e s t c o m m o ns u b s e q u e n c e ( l c s s ) 扩展到多维时间序列的相似度量【2 5 1 。在执行精确的 l c s s 或者d t w 之前，序列被分段成为m b r 存储在r t r e e 中。根据m b r 的重 合，计算相似性以对不相关的序列进行裁剪。d t w 和l c s s 的计算复杂性都为 伙似聊切) ) ，其中w 是匹配窗口的大小，d 是维数，m ，刀是两个序列的长度。当 w 与m ，n 比增大时，计算复杂度接近序列长度的三次方，这使得该方法对长序 列的大数据库的扩展性比较差。同样，当弯曲路径变长时，索引的性能显著下降。 即使当每个长序列有少量的2 0 个m b r 时，索引的空间要求就达到了数据集大小 的四分之一。 隐马可夫模型( h i d d e nm a r k o vm o d e l s ，h m m s ) 也被用来处理语音【2 6 1 、笔迹识 别【2 7 1 以及美国手语( a m 甜c a ns i g nl a n g u a g e ，a s l ) t 2 8 1 。当使用m 心压s 时，需要为 每个手势或者动作单位指定不同的状态；在使用洲s 之前需要知道一个句子中 的词语数目以及语法规则。当没有遵守指定的状态，或者动作变换相对较大时， 识别的精度将大幅下降。甚至当为基于i - l m r s 的识别生成合法的或者有意义的动 作时，这种现象也存在。我们希望构建一个不受状态或者语法限制的模型，因此 h m m s 对于我们的要求不适用。 s h a h a b i 等人应用机器学习技术，包括决策树，贝叶斯分类器和神经网络， 识别静态手语，达到了8 4 6 6 的准确度2 9 1 。在另一篇著作中，他们为度量两个多 维动作时间序列的相似性定义了s v d 的加权和，相似性的定义采用了正确 s i n g u l a rv e c t o r 的两个内积加权和中较小的那个。 l i 等人