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

时间序列分类的研究摘要 题目：时间序列分类的研究 专业：计算机应用技术 硕士生：曾苗 指导教师：刘玉葆副教授 摘要 时间序列分类是时间序列数据挖掘的重要任务之一。它比普通分类问题困难 的主要原因是时间序列数据长度不一致，而一般的分类算法只能处理长度相等的 数据。即使是长度相等的时间序列，因为不能直接比较时间序列在相同位置上的 数值，还是不能直接使用一般的分类算法。解决这几个难点通常有两种方法：第 一，定义适合分类的距离度量，使得在此度量意义下相近的序列有相同的分类标 签，这类方法称为领域无关的方法；第二，先利用时间序列中前后数据的依赖关 系建立模型，再利用模型参数来表示每条序列，最后用一般的分类算法进行训练 和分类，这类方法称为领域相关的方法。 本论文分别从这两方面进行了研究，针对这两类方法提出了相应的改进方 法，并对提出的两类改进算法进行了比较研究。主要工作有： ( 1 ) 人们常常会用不同的“分辨率 来分析时间序列数据，而基于点距离 的度量不具备这种的能力，无法有效反映不同时间尺度下时间序列的相似性。时 间序列分类的第一类方法目前大都是基于点距离的方法，对股票价格这种人们比 较关心走势的时间序列的分析存在不足。变化趋势反映了时间序列的动态特性， 具有更高的使用价值。本论文针对已有的时间序列趋势化表示算法t r 对时间序列 信息描述不完整的缺陷，提出了基于均值的时间序列趋势化算法i t r ，并重新定 义了距离度量方法。该距离度量结合了趋势距离和点距离的优势，比传统的趋势 化算法提供了更多的描述信息，因而能够获得比传统的趋势化算法更精确的结 果。实验结果表明，基于均值的趋势距离度量的分类器比基于传统趋势距离度量 的分类器具有更高的分类精度。 ( 2 ) 时间序列分类的第二类方法当前大多是采用( 主成分分析) p c a 、( 保 局部投影) l p p 等对1 一n n 分类器进行优化。通过l p p 得到的映射简单并且是线性的， 能够表示数据的非线性结构，因此l p p 算法应用广泛。然而l p p 算法是一种无监督 的学习算法，未能充分地利用样本的类别信息，求取的并不是判别意义上的最优 的投影向量，而且所找出的投影矩阵的列向量并不是两两正交的，数据重构比较 困难。本论文通过引入l d a ( 线性判别分析) 的思想，充分利用样本的类别信息， 求取判别意义上最优的投影向量，将l p p 算法扩展为一种有监督的学习算法，同 时采用一种简单的正交化方法使投影矩阵的列向量两两正交，消除冗余特征，从 而获得更好的卜n n 分类器。 ( 3 ) 长期以来，研究者往往只倾向于使用其中的某一类算法，而对这两类 算法的对比研究却比较缺乏。我们采用丰富的分类数据集对提出的算法i t r 和 s l d p p 进行了深入的比较和分析。通过比较，我们发现领域相关的算法s l d p p + i n n 比较有优势，但受噪声的影响相对较大。另一方面，在一些比较规则的样本上， 领域无关的算法i t r + i n n 比较合适。 关键词：时间序列，分类，距离度量，l d a ，l p p ，趋势 i i 时间序列分类的研究 a b s t r a ( 玎 t i t l e ：r e s e a r c ho nt i m es e r i e sc l a s s i f i c a t i o n m a jo r ：c o m p u t e ra p p l i c a t i o nt e c h n o l o g y n a m e ：z e n g m i a o s u p e r v i s o r ：l i uy u b a o a b s t r a c t t i m es e r i e sc l a s s i f i c a t i o ni sa ni m p o r t a n tt a s ko ft i m e - s e r i e sd a t aa n a l y s i s i ti s m o r ed i f f i c u l t yt h a ng e n e r a lc l a s s i f i c a t i o nm a i n l yd u et ot h ed i s c r e p a n c yo ft h ed a t a l e n g t h ，w h i c hm a k e sg e n e r a lc l a s s i f i c a t i o na l g o r i t h m sc a nn o tb ea p p l i e dd i r e c t l y e v e ne q u a ll e n g t hs e r i e s ，d u et ot h ev a l u eo fd i f f e r e n ts e q u e n c e si nt h es a m el o c a t i o n c a nn o tb ec o m p a r e dd i r e c t l y , g e n e r a lc l a s s i f i c a t i o na l g o r i t h m sa r es t i l ln o ts u i t a b l e t os o l v et h e s ed i f f i c u l t i e s ，t h e r ea r et w ow a y s ：t h ef i r s to n e ，d e f i n eas u i t a b l ed i s t a n c e m e t r i cw h i c hm a k e ss i m i l a rs e q u e n c e sh a v es a m ec l a s s i f i c a t i o nl a b e l ，t h e s em e t h o d s a r ed o m a i n - i n d e p e n d e n tm e t h o d ；t h es e c o n dw a y , u s et h es e q u e n c ed e p e n d e n c y r e l a t i o n s h i pb e t w e e n t h ep r e v i o u sa n dt h en e x tt ob u i l dm o d e lf o rt i m es e r i e sf i r s t ，a n d t h e n ，r e p r e s e n te a c hs e q u e n c eu s i n gt h em o d e lp a r a m e t e r s ，f i n a l l y , u s eg e n e r a l c l a s s i f i c a t i o na l g o r i t h mt oc l a s s i f i c a t i o n ，t h e s em e t h o d sb e l o n gt of i e l d r e l a t e d a p p r o a c h w eh a v es t u d i e dt h et w oa s p e c t s s e p a r a t e l y , p r o p o s e dt w oc l a s s i f i c a t i o n a l g o r i t h m s ：i t ra n ds l d p p , a n dh a v em a d eac o m p a r a t i v es t u d yo ft h et w ot y p e so f a l g o r i t h m s m a i nt a s k sa r e ： ( 1 ) t i m es e r i e sd a t ao f t e nu s e sd i f f e r e n t ”r e s o l u t i o n ”t oa n a l y s i s d i s t a n c e b a s e d m e a s u r ec a nn o te f f e c t i v e l yr e f l e c tt h es i m i l a r i t yo ft h es a m et i m es e r i e su n d e r d i f f e r e n tt i m es c a l e s t h ef i r s tc l a s s i f i c a t i o nm e t h o dm o s t l yb a s e do nt h e d i s t a n c e b a s e da p p r o a c h ，h a v ee s s e n t i a l l yd e f e c t si nt h et i m e - s e r i e sm a t c h i n go f w h i c h ”t r e n d ”a st h ec h a r a c t e r i s t i c s t r e n d si nt i m es e r i e sr e f l e c tt h ed y n a m i cn a t u r e o ft h e s e q u e n c e o u rs t u d yh a v eo v e r c o m e dt h e t r a d i t i o n a lt i m es e r i e st r e n d i i i r e p r e s e n t a t i o na l g o r i t h mt rd i s a b l et or e p r e s e n tt h ew h o l ei n f o r m a t i o no ft h et i m e s e r i e s ，a l g o r i t h mi t ri sp r o p o s e db a s e do nt h em e a no ft h es u b s e q u e n c e ，a l s o ，t h e t r e n dd i s t a n c eh a sb e e nr e d e f i n i t i o n b e c a u s et h ea l g o r i t h mi sac o m b i n a t i o no ft r e n d d i s t a n c em e t h o da n dp o i n td i s t a n c e ，i tp r o v i d e sm o r ed e s c r i p t i v ei n f o r m a t i o nt h a nt h e t r a d i t i o n a lt r e n da l g o r i t h m ，a n dt h u sa b l et oo b t a i nm o r ea c c u r a t er e s u l t st h a nt h e t r a d i t i o n a lt r e n da l g o r i t h m s t h ee x p e r i m e n tw ed o n eh a v ep r o v e di t se x c e l l e n c e ( 2 ) t h es e c o n dc l a s s i f i c a t i o nm e t h o df o rt i m es e r i e sm o s t l yc l a s s i f i c a t i o na f t e r u s i n gp c a 、l p pe t ct oo p t i m i z et h e1 - n nc l a s s i f i e r s i n c em a p p i n ga f t e rl p pt h e s e r i e sa r es i m p l ea n dl i n e a r , w o u l db ea b l et oe x p r e s st h en o n l i n e a rs t r u c t u r eo ft h e d a t as t r e a m h o w e v e r , l p pa l g o r i t h mi sa nu n s u p e r v i s e dl e a r n i n ga l g o r i t h m ，d i dn o t m a k ef u l lu s eo ft h el a b e li n f o r m a t i o nw h i c ht h ep r o j e c t i o nv e c t o ri sn o tt h eb e s ti n d i s c r i m i n a t es e n s e ，a n dt h ep r o j e c t i o nm a t r i xo fc o l u m nv e c t o r si sn o to r t h o g o n a l 谢t h e a c ho t h e r , t h ef e a t u r e sa r es t i l lr e d u n d a n t ，w h i c hm a k e st r o u b l et or e c o n s t r u c tt h e d a t a b yi n t r o d u c i n gt h ei d e ao fl d aa l g o r i t h m ，u s i n gt h el a b e li n f o r m a t i o nt os t r i k e t h ed i s c r i m i n a t eo p t i m a lo fp r o j e c t i o nv e c t o r , l p pd e v e l o p sa sas u p e r v i s e dm a n i f o l d l e a r n i n ga l g o r i t h m a l s o ，w eu s eas i m p l em e t h o dt om a k et h ec o l u m nv e c t o r o r t h o g o n a lw i t he a c ho t h e r , s ot h a tc r e a t ea b e t t e ro p t i m i z a t i o no f1 - n nc l a s s i f i e r ( 3 ) f o ral o n gt i m e ，r e s e a r c h e r so f t e np r e f e rt ou s i n go n l yo n ea l g o r i t h m ，w h i l e c o m p a r i s o no ft h et w ot y p e so fa l g o f i t h m si sr e l a t i v e l ys c a r c e w eu s er i c hd a t as e t st o d ot h ec o m p a r i s o na n da n a l y s i s w ef o u n dt h a tt h ef i e l d - r e l a t e da l g o r i t h m ss l d p pi s m o r ea p p r o p r i a t e l y ；b u tt h ea f f e c tb yn o i s ei sr e l a t i v e l yb i g i nt h eo t h e rh a n d ，t h e d o m m n - i n d e p e n d e n ta l g o r i t h mi t rf o rt h ec l a s s i f i c a t i o nh a sc e r t a i na d v a n t a g e si n s o m er u l e dd a t as e t s k e yw o r d s ：t i m es e r i e s 、d i s t a n c em e t r i c 、l d a 、l p p 、t r e n d 、c l a s s i f i c a t i o n i v 论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：唔侈 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名：曾谄 日期：山c 晖( 月中日 导师签名：夏婢讥。 日期尹i o 年6 月日 时间序列分类的研究第1 章绪论 1 1 引言 第1 章绪论 在过去的二十年中，数据采集、存储与管理技术的进步与企业界迫切需求的 结合，使得数据库技术得到了广泛的应用。当今世界同新月异，数据量不断增长， 越来越多的商业数据库容量达到海量的水平，很多数据库中已经存储了上万亿字 节的数据。如何从这些海量数据中发现隐藏的规律和知识，已经成为当今计算机 界特别是数据库领域研究者的一个相当重要的研究方向，我们称之为数据挖掘。 什么是数据挖掘呢? 或者说怎么定义数据挖掘呢? 文献中给出了广义的 定义：数据挖掘是从存放在数据仓库、数据库或其它信息库的大量数据中挖掘有 趣知识的过程。 近十几年来，数据挖掘技术越来越引起信息产业界的关注，其主要原因是存 在大量可广泛使用的数据，并且将这些数据转换成有用的信息和知识的需求越来 越迫切。因为用户需要将获取的这些信息和知识反馈到应用领域，并及时指导他 们，使他们具有更多的领域“智能 。目前在市场分析、商务管理、国家安全等 领域都已广泛应用到数据挖掘的相关成果。同时，作为一个新起的交叉学科，数 据挖掘涉及多学科技术的集成，包括人工智能与机器学习、数据库技术、统计学、 模式识别、高性能计算、神经网络、信息提取、图象与信号处理和空间数据分析、 数据可视化、生物信息学、社会学n 1 ，涉及的范围广泛到从基础的算法理论到具 体的实际应用。文献中提n - 信息产业界认为数据挖掘是数据库系统最重要的 前沿之一，是信息产业最有前途的交叉学科。当然了，任何人都不可能深入的研 究所有的这些方面，这也使得数据挖掘的研究过程中存在着许多不同的角度。 1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会议上首次提出了数据挖 掘与知识发现这个概念，自此树立了数据挖掘研究的新的里程碑。上世纪9 0 年 代早期，数据挖掘主要还是停留在为数据库系统建立有效的数据分析工具，大部 分的数据挖掘研究者来自数据库领域。随着越来越多的领域专家加入数据挖掘的 行列中，数据挖掘考虑问题的角度也被极大的拓宽，提出的一些研究方向主要包 括关联规则、聚类、分类、异常检测等，这些方向的建立也进一步地推动了数据 挖掘的发展。数据挖掘技术一般与数据库的相关技术紧密结合，相对传统的知识 发现技术( 如统计方法、机器学习等) 而言，它更加侧重于自动发现海量数据的 多种模式，应用前景更加广泛。 文献中为我们介绍了数据挖掘的过程，一般可以分为三个阶段：数据预处 理、模式发现与知识表示。数据预处理阶段会消除噪音、除去不相关的数据等， 保证后续阶段的输入数据的质量，主要包括数据的清理、集成与选择三个子任务。 数据挖掘过程的核心阶段是模式发现，该阶段综合运用多种数据挖掘算法对历史 数据进行分析，获取供决策的有用的规则与模式。知识表示阶段，即如何将得到 的规则与模式以一种直观的、易理解的方式告诉给用户，主要关注的是规则和模 式的可视化表示。 本章主要介绍和本文研究相关的一些概况，主要包括：1 、时间序列挖掘的 相关研究；2 、分类算法的相关研究；3 、时间序列分类的相关研究。在后面的章 节中，我们将根据实际的问题域进行进一步的介绍。 1 2 时间序列挖掘的相关研究 文献中提到：可以在任何类型的信息存储上进行数据挖掘，包括关系数据 库、事务数据库、数据仓库、高级数据库系统、平面文件和w w w 。在这些数据集 之中，有一类数据集我们称之为时间序列数据库。时间序列数据库是指有随时间 变化的值组成的数据库，而时间序列就是存在着时间上的关系的这类数据。这类 存在着时间上的关系的数据的挖掘称为时问序列数据挖掘。现实生活中存在很多 时间序列，例如股票市场的每日波动，动态产品的加工过程，医学治疗等等。而 这些时间序列数据与一般的数据有很多不同之处，因此，研究如何从这些复杂的 时间序列中挖掘知识，也是具有相当大的理论价值和现实意义的。 在一个时间序列中，每个数据点都可以被认为是一个二元组n ( v ，f ) ，其中： 变量1 ，反映数据单元的实际意义，如股票的价格、某种商品的销售额等；，表示 与时间相关的变量。文献瞳3 对时间序列给出了如下定义： 定义1 ：时间序列是由记录值和记录时间组成的元素的有序集合，记为 x = 而= ( v i ) ，x 2 = ( v 2 ，t 2 ) ，= ( ，) ) 元素= ( v ，) 表示时序列在时刻的 2 时问序列分类的研究 第1 章绪论 记录值为哆，记录时间是严格增加的( f ，) 。 始于2 0 世纪9 0 年代的数据库相似性搜索的研究揭开了时间序列数据挖掘的 序幕。1 9 9 3 年r a g r a w a l 等人。”发表了第一篇关于时间序列数据库相似性搜索的 论文，次年c f a l o u t s o s 等人n 1 提出了一种关于子序列相似性查询的方法。这两 篇文章引起了广大时间序列数据挖掘研究者的注意，他们提出的时间序列数据库 相似性搜索算法应遵循的原则已被普遍接受瞳1 。经过十多年的发展，时问序列数 据挖掘已成为国内外学术界研究的热点之一，国际上许多著名的学术会议和期刊 每年都有不少关于时间序列数据挖掘的报道。总的来说，时间序列数据挖掘研究 的主要内容包括以下七个方面：时间序列表示、相似性搜索、聚类与分类、模式 挖掘、异常检测、时间序列预测、可视化。 1 2 i 时间序列表示 时间序列类型复杂且数据量庞大，同时可能会存在大量的噪声，如果直接挖 掘原始数据，不但效率低下，甚至会影响挖掘的可靠性和准确性，而且会影响后 续的分析工作。正确、简洁的离散化原有序列，并正确度量其相似性是提高挖掘 效率和效果的关键，也是进一步处理分类与预测、聚类分析、关联分析、异类分 析及演化分析的基础。因此，需要在时间序列数据进行挖掘之前对原始数据进行 变换，即对时间序列进行抽象和概括，在高层次的数据上进行挖掘。 目前比较常用的时间序列数据表示主要有奇异值表示法、频域表示法、符号 表示法以及分段表示法。 ( 1 ) 奇异值分解 奇异值分解( 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 ) 是一种最可靠的正交 矩阵分解法，但是它比q r 分解法要多花上近十倍的时间。例 u ，s ，v 】= s v d ( a ) ， 其中u 和y 代表二个相互正交的矩阵，而s 代表一个对角矩阵，原矩阵彳不必为 正方矩阵。使用s v d 分解法的用途是解最小平方误差法和数据压缩。虽然它能够 线性的减少时间序列的数据维度，但是它计算开销比较大，不能应用在大型数据 集中。 ( 2 ) 频域表示 3 频域表示的本质是将时间序列从时间域映射到频率域，改用频谱来表示时间 序列畸1 ，通过频域变换能有效解决高维特征向量的降维问题。频域表示常用的方 法是离散小波变换( 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 ) 、离散傅里叶变换 ( 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 ) 。d w t 方法利用少数小波参数近似模拟原 始时间序列实现线性变换，w a v e l e t 的多层解析属性很有用，但是只对长度是2 的整数次幂的时间序列起作用。d f t 方法方便、快捷，在变换过程中保证特征抽 取的完整性，在保持序列主要形态的同时实现了数据压缩。 ( 3 ) 符号化表示 时间序列的符号化表示就是将连续的时间序列映射到有限的离散的符号表 上，将时间序列转换为有限符号的有序集合。用途最广的是e k e o g h 1 等人提出 来的s a x ( 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 ) 算法，允许下界来约束原始数 据的距离测量，同时允许实时数据在有限时空内转换成流动的数据。 鉴于字符串研究的广泛性，符号化表示利用许多现成的成果，但如何选择合 适的离散化算法，如何有效的定义符号也是一个难点。 ( 4 ) 分段表示 时间序列的分段表示，是时间序列的模式表示法中研究最多和最早的方法之 一。分段表示常用方法包括分段合计近 以( p i e c 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 ) 、分段多项式表示( p i e c e w i s ep o l y n o m i a lr e p r e s e n t a t i o n ，p p r ) 、分段 线性表示( p i e c e w i s el i n e a rr e p r e s e n t a t i o np l r ) 等。 分段线性表示试图用一系列的直线来模拟原始数据，是一种高层次的数据表 示方法，对原始序列的近似粒度取决于线段的数目。 1 2 2 时间序列相似性搜索 时间序列的相似性查询的一般定义是指从某个时间序列数据库中找出与给 定时间查询序列q 在相似性度量d ( q ，t ) 范围内与q 最匹配的那些时间序列。判 断两个时间序列的相似程度需要一个测量时间序列相似性的距离度量方法。目前 时间序列数据挖掘中用到的距离度量大致分为e u c l i d e a n 距离、非e u c l i d e a n 、 d t w 等。 时间序列的相似性搜索包括子序列匹配和整体序列匹配，子序列匹配是指找 4 时间序列分类的研究第1 章绪论 出与给定序列相似的所有数据序列，而整体序列匹配是指找出彼此间相似的序 列。其中，子序列匹配，一般都是使用滑动窗口来对整个序列进行分割。对金融 市场的分析，医疗诊断等来说，时间序列相似性搜索大有用武之地。 值得一提的是，在时问序列的相似性搜索研究中，r a g r a w a l 和c f a l o u t s o s 等人口1 提出的相似搜索算法应满足非漏报性质非常值得我们关注，即只要是满足 相似条件的序列算法都应该能检索出来。只有算法所采用的数据表示法满足如下 条件驯： 啡( q ，c ) d ( q ，c ) ， 才能满足非漏报原则。其中：d 。表示采用数据表示法后的两个序列之间的 距离，q 表示待查询的时间序列，c 表示数据库中的任意一个时间序列， d 表 示两个序列之间的真实距离。 1 2 3 时间序列聚类与分类 由于时间序列特有的属性，不能直接用一般的算法来对时间序列进行聚类和 分类。首先需要根据用户指定的规则对时间序列进行预处理( 规则主要包括时间 粒度和模式长度) ，一般是对时间序列的长度进行处理，将原序列化分为不重叠 的或者等长的子序列的集合，然后再对这些子序列进行聚类和分类。 目前比较常用的时间序列聚类的算法包括基于模型的、基于相似性和基于特 征的这几类。欧几里德距离是基于相似性的方法中距离度量的典型代表，其它基 本上是基于欧几里德距离的一些改进。由于欧几里德距离适用于确定性向量空 间，而传统的聚类算法大多是基于向量的，不能很好地应用到时间序列聚类中。 近年来更多的是使用基于模型的聚类算法来对时间序列的进行聚类研究，基于模 型的聚类方法试图优化给定的数据和某些数据模型之间的适应性，主要包括神经 网络方法和统计学方法。 分类可以认为是聚类的一种比较特殊的情况，时间序列分类就是把一个未知 类别的时间序列划分到某些预定义的或者是已知的类别之中，称作有指导的学 习；而聚类可以看作是划分到一个未知的类别中，是无指导的学习。分类和回归 是两类主要预测问题，不同的是，分类是预测离散或标称值，而回归用于预测连 续或有序值。虽然时问序列比较特殊，但普通数据库中的许多分类算法在时间序 列中都有应用，如决策树、神经网络等。近年来基于模型的、用分类器融合对时 间序列进行分类成为了热门研究方向之一。 1 2 4 时间序列的模式挖掘 时间序列模式挖掘是指挖掘相对时间模式出现频率高的模式。例如：一年以 前购买了p c 机的客户很可能在最近一个月内订购同品牌的内存条。现实生活中 的很多商业交易，如商品购买记录，产品处理，天气数据都是时间序列数据，在 进行市场分析、客户吸引中，时间序列模式挖掘是很有应用前景的。 对时间序列模式挖掘，时间序列的持续时间、事件重叠窗口以及被发现的模 式中时间之前的间隔这三个参数的取值，严重影响挖掘的结果。关联规则挖掘中 的常用的a p r i o r i 算法也可以应用于时间序列模式挖掘，另一种方法就是基于数 据库的序列模式生长技术。 1 2 5 时间序列异常检测 现实生活中，经常存在这样一些数据对象，它们不符合数据的一般模型，与 数据中的其它部分存在着较大差异，这些数据对象称为异常，有时也被称为孤立 点、离群点等等。异常挖掘有着广泛的应用，它能用于欺诈监测，例如探测不寻 常的信用卡使用或电信服务，此外，它在医疗分析中用于发现对多种治疗方式的 不同寻常的反应，或者在市场分析中可用于确定极低或极高收入的客户的消费行 为。 文献中给出了孤立点挖掘的描述：给定一个甩个对象的集合以及预期的孤 立点的数目k ，发现前k 个与剩余的数据相比是相异的、例外的或不一致的对象。 孤立点的检测算法大致可分为三类：统计学方法、基于距离的方法和基于偏移的 方法。 1 2 6 时间序列预测 如果，我想知道个在某公司工作了五年的硕士生的工资，我们就要用到时 6 时问序列分类的研究第1 章绪论 问序列预测，它可以用于预测数据的未来趋势。在许多方面，时间序列数据挖掘 研究中关心的时间序列预测问题与理论中关心的时问序列预测问题是相似的，因 而时间序列预测在现实中应用广泛，例如，天气预报。要进行时问序列预测，首 先要根据时间序列建立相关模型，然后根据历史的和当前的数据来推测未来的数 据。时间序列预测技术大体可分为： a ) 传统的线性回归 数据用直线建模，线性回归是最简单的一种回归形式，被广泛使用。双变量 回归是将一个随机变量视为另一个随机变量的线性函数。多元回归是线性回归的 扩展，涉及多个预测变量。 b ) 非线性回归 与线性回归不同的是，这类方法主要多项式回归进行建模，通过对变量进行 变换，我们将非线性的模型转换成线性的，然后用最小平方方法求解。 c ) 其他回归模型 其它的回归模型还有广义线性模型，常见的形式包括对数回归、泊松回归等。 1 2 7 时间序列可视化 一般来说，相对于形象化了的数据而言，复杂的时间序列数据是比较难于理 解的。这也是为什么时间序列可视化越来越受到时间序列数据挖掘研究领域的研 究者们关注。时间序列可视化挖掘就是充分利用现代的图形图像技术、虚拟现实 技术以及数据挖掘技术，将挖掘出来的知识以直观的、易于理解的方式呈现给用 户。就目前来看，国内这方面的研究成果相对较少，国外的研究偏多，也开发出 了相应的可视化工具，如t i m es e r i e ss p i r a l s 、t h e m er i v e r 、t i m es e r i e s b i t m a p s 等口】。 1 3 分类的相关研究 数据的分类可分为两步，第一步，建立一个模型，描述预定义的数据类别。 一般情况下，每个时间序列属于个预定义的类，由一个称作类标号属性的属性 确定。为建立模型而被分析的时间序列形成训练数据集，训练数据集中的单个时 间序列称作训练样本，是随机的从样本群中选取的。第二步，使用模型对待测试 7 的样本进行分类。待测试的时间序列形成测试数据集，测试数据集中的单个时间 序列称作测试样本，也是随机选取的，但独立于训练样本。 在现实生活中，分类具有广泛的应用，包括医疗诊断、选择购物和信誉证实 等。 一般不是直接对原始数据进行分类，通过采用数据清理、相关性分析、数据 变换能消除或减少噪音，除去与任务不相关的属性，将数据泛化到高层概念，可 以在一定程度上提高分类过程的准确性、有效性和可规模性。 分类的方法主要有归纳分类法、统计方法和神经网络方法等，还有一些在商 品化的数据挖掘系统中应用较少的方法，包括k 一最邻近分类、基于案例的推理、 遗传算法、粗糙集和模糊集方法。归纳分类法比较有代表性的是决策树法，也叫 判别树法，统计方法包括贝叶斯法和朴素贝叶斯法。神经网络方法最主要是b p 算法，它用前向反馈神经网络模型( 这种体系结构由代表神经元的节点和代表联 接权值的边组成) 来表示，b p 算法本质上是一种非线性判别函数。下面介绍几 个流行的分类方法 1 ) 决策树分类法 决策树( d e c i c s i o nt r e e ) 是一个类似于流程图的树结构，其基本原理是利 用递归思想来划分变量。在一个属性上的测试由一个相应的内部节点来表示，每 一个分支表示一个测试输出，而每个叶子节点代表了类或者类分布，树的最顶层 结点是根结点。 在决策树构造时，可以通过树剪枝来提高在未知数据上分类的准确性。最著 名的决策树算法是i d 3 ，文献口1 中q u i l a n 提出了c 4 5 算法，是i d 3 的改进算法。 但是当这些算法应用于现实世界中的数据库时，有效性的可规模性就成了关注的 问题，因为大部分的决策树都限制训练样本驻留主存。 2 ) 贝叶斯分类法 贝叶斯分类法是基于贝叶斯定理的一种统计分类方法，可以用来预测类成员 关系的可能性，如给定样本属于一个特定类别的概率。朴素贝叶斯分类假定一个 属性值对给定类的影响独立于其它属性的值，该假定称作类条件独立。文献n 1 中 提到：朴素贝叶斯分类算法可以与决策树和神经网络分类算法相媲美，用于大型 数据库时朴素贝叶斯分类也表现出高准确率与高速度。 8 时问序列分类的研究 第1 章绪论 3 ) 神经网络分类法 朴素贝叶斯分类的类条件独立的假定简化了计算，然而，在实际环境中，变 量之间的依赖可能存在。 网络是一个有向无环图，每个结点代表一个随机变量，而每个弧代表一个概 率依赖。文献中定义如下：神经网络是一组连接的输入输出单元，其中每个 连接都与一个权相联。在学习阶段，通过调整神经网络的权，使得能够预测输入 样本的正确类标号来学习。 神经网络需要很长的时间来进行训练，因而对有足够长时间进行训练的应用 更加合适。神经网络对噪音数据的承受能力较强，并且对未经训练的数据的分类 效果比较好。最流行的神经网络算法是后向传播算法。 1 4 时间序列分类相关研究 近年来基于时间序列的数据挖掘方面的研究工作有很多，其中时间序列的分 类问题是个热点问题，也是一个广泛应用的问题，时间序列数据分析在机器学习、 数据挖掘以及数据仓库等领域中日益重要。时间序列分类是时间序列数据分析中 的重要任务之一。 本文研究的时间序列分类问题定义如下国1 ： 一一个表示动态系统轨迹的对象域u 。对象0 在某个有限的时间段中被观 测【d ，t f ( d 为。 对象基于时间的属性来描述( 属性都是对象和时间的函数) ，因此定义 在ux o , + o o 】。我们用口( d ，) 来表示对象d 在时间，时的属性。 一每一个对象被进一步划分到某一个类别c ( d ) 中( c ( d ) c l ，一，) ) 。 给定域中对象的随机采样丛，分类的目标就是找到一个尽可能的接近真实 的分类c ( d ) 的函数厂( d ) ，即( o ) = 厂g ( o ，) ) ，其中口表示属性向量协1 。 我们从上面的定义可以看出，属性被定义成关于时间变量，的连续函数。然 而，在实际环境中，计算机存储器中表示的经过采样后的信号，是离散的。因此， 是用向量序列( 如，。( d ) ) 如， ( d 巍，( 0 ，。( o ) ) ) 来描述轨迹的，其中 9 ，。( o ) - - f ，( d ) ，江o ，1 ，( d ) 。时间采样数目刀( d ) 可以是对象相关的。 时间序列分类已经应用到很多不同的领域。最早的是文献睁1 0 1 中提到的h m m 和d t w 在语音处理和语音识别领域上的应用。在1 9 9 4 年，b e r n d t 和c 1 i f f o r d 在文献1 中首先把d t w 算法引入了数据库领域。近十几年来，时间序列分类被研 究人员应用到了更多的领域中。例如，生物信息学中的r n a 数据的分类n 别、心电 图e c g 的模式匹配n 3 1 以及手写识别n 钔等。 时间序列的分类问题与传统的分类问题的区别主要在两点： ( 1 ) 时间序列 的长度不相等，不能直接把每条序列看作是一个属性向量作为一般分类算法的输 入。因而，一般的分类算法不能直接应用。( 2 ) 对于所有序列长度都相等的时 间序列分类问题，由于不同序列的相同的属性值( 不同序列在相同位置的数据值) 不一定可进行比较，如果直接套用一般的分类算法，效果也不一定好n 5 | 。 我们可以把这些研究工作分为两大类：第一类，定义适合分类的距离度量， 使得在此度量意义下相近的序列有相同的分类标签，这类方法属于领域无关的方 法。有效和高效的处理时间序列数据的两个关键方面是：数据表示方法和相似度 搜索策略，时间序列本质上是高维的数据，直接处理原始形式的数据是非常占用 内存和c p u 时间的，因此迫切的需要发展数据表示方法来降低数据的维度，同时 始终保持数据的基本特性，在文献资料中有很多降低时间序列数据维度的数据表 示方法经常被提到，如d f t 、s v d 、d c t 、d w t 、p a a 、c h e b 、a p c a 、s a x 、p l a 等。 目前比较常用基于这些数据表示法的几类距离如下： ( 1 ) 欧几里德距离 欧几里德距离是时间序列相似性研究中提出最早的算法，也是应用最广泛的 相似性度量。欧几里德距离的优点是容易理解，计算简单，运行速度快而且能支 持多维空间索引，也能应用到时间序列的预测和分类等多个研究领域。缺点是受 噪声和短期波动的干扰比较大，对序列在时间轴上的轻微变化相当敏感。文献n 町 提到，虽然基于欧几里德距离的一些改进算法可以支持时间序列的伸缩和振幅平 移，但仍然不支持时间弯曲和线性漂移。 ( 2 ) d t w 距离 d t w 距离是针对欧几里德距离的不支持时间弯曲和线性漂移的缺陷提出来 的，但是计算量很大，运算速度比欧几里德距离差很多，不适合直接用于时间序 l o 时间序列分类的研究第1 章绪论 列的挖掘。许多研究者的一些工作都是为了改进d t w 算法的性能，其中最值得 提的是文献n 7 。1 8 1 提出了d t w 距离的下界( l o w e rb o u n d i n g ，l b ) 的思想，先利用 l b 距离运算速度快的特点，快速过滤掉部分不满足要求的时间序列，再计算余 下的时间序列的d t w 距离。因为l b 距离的计算比d t w 距离要简单的多，其运行 速度要快的多，因此这种方法能够大大提高基于d t w 距离的相似性查询效率，并 保证查询的完备性，但其速度仍然无法与欧几里德距离相比较。同时这种利用下 界函数的优势无法体现在时间序列的聚类和分类算法中。 ( 3 ) 编辑距离 编辑距离( e d i t i n gd i s t a n c e ) ，也叫模式距离，是度量一个模式近似出现 的标准。两个时间序列a 和b 之间的编辑距离定义为将序列a 转换为序列b 所需 的最小编辑步数，即将a 转换为b 付出的最小代价。有如下三种形式的编辑方式： 删除、插入和改变。可以按照时间序列的上升、平稳和下降的变化率，将序列转 换为一系列离散的字符串，用编辑距离作为相似标准进行串的近似搜索匹配。编 辑距离的优点是支持时间序列在时间轴上的伸缩，缺点是很难定义一个合适的标 准字符串，计算的代价比较高。 ( 4 ) 其它距离度量 还有许多其它的距离度量，如对予序列进行d t w 距离计算后再进行距离累 积，利用高斯分布来定义各时间数据点之间的距离等1 。 距离度量如此丰富，那如何来设计一个适合时间序列分类的距离度量呢? 这 是一个值得关注的问题。 第二类，首先利用序列中前后数据的依赖关系对时间序列建立模型，再用模 型参数来表示每条序列，最后用一般的分类算法来进行训练和分类，我们称这类 方法为领域相关的方法n 叼。模型法中的理论模型一般是通过推理演绎的方法在假 设基础和数学理论上建立起来的。理论上来说，只要模型的假设是合理的，所得 出来的结论就是合理的。但如果所提出的假设并不合理，模型法将会严重失真。 一方面，大部分的时间序列分析模型都假定数据对象为某一类的时间序列数据， 如满足平稳性假设、线性假设、正态分布假设等。而在实际应用中，时间序列数 据往往具有非平稳、非线性、非正态的特点。另一方面，模型法反映的是时间序 列的总体特征，对隐含在序列中的某些局部特征则难以体现。然而，在实际应用 中，经常需要我们分析时间序列的局部特征，如两个时间序列的子序列相似性比 较，挖掘出频繁出现的模式等。如果不具备良好的建模技巧或对系统认识不够， 很难构建出一个比较理想的模型来。 目前比较常用的算法有p c a 、l d a 、l p p