（管理科学与工程专业论文）时间序列挖掘中索引与查询技术的研究.pdf

中文摘要 索引和查询是数据挖掘中各项任务的基础和关键问题。本文对时间序列挖 掘中的索引和查询技术进行了研究，比较系统地研究了时间序列的查询方式、 表示与索引和相似性度量等问题；提出了计算几何应用到时间序列挖掘的方法， 实现了时间序列全序列匹配查询、模式查询、反向查询和异常检测，查询效率 和准确性都有了比较大的提高。主要研究成果如下： 1 时间序列查询方式 利用计算几何中邻近问题的原理和方法，根据时间序列的构成要素，对时 间序列的查询方式进行了系统地分类。按查询对象将时间序列查询分为点查询、 模式查询和序列查询；按查询方式将时间序列查询分为范围查询、邻近查询和 点对查询，拓宽了时间序列查询的方式，为序列挖掘提供了更加有力的工具。 2 时间序列表示与索引 在基于重要点分段的基础上，主要研究了时间序列的k l 表示方法。利用 v o r o n o i 图对数据进行组织和管理，为时间序列查询提供了一种新的索引方法。 同时，针对时间序列原始数据的反向查询，提出了一种瓤的时间序列索引方法 一i c - 索引。 3 时间序列相似性查询 系统地研究了时间序列各种查询方式的实现算法。提出了k l 相似性度量， 实现了全序列匹配查询；利用计算几何方法，实现了线性模式的邻近查询、最 近模式对查询和最远模式对查询，算法在时间上都是最优的；提出了一种新的 时间序列反向查询方法，查询效率和准确性都有比较大的提高。 4 时间序列异常检测 利用v o r o n o i 图的基本原理，提出了一种基于密度的异常检测方法v o d ，并 应用到时间序列的线性模式异常检测，将现有算法的复杂性从d ( h 2 ) 降低到 o ( n l o g n ) ，检测效率和性能都有了很大的提高。 图 关键词：数据挖掘，时间序列，索引，查询，异常检测，计算几何，v o r o n o i a b s t r a c t i n d e x i n ga n dq u e r y i n ga r e f u n d a m e n t a lp r o b l e m si nd a t am i n i n g t h i s d i s s e r t a t i o na d d r e s s e st h ep r o b l e mo fi n d e x i n ga n dq u e r y i n gf o rt i m es e r i e s ，a n d d i s c u s s e st h er e l a t e dp r o b l e m so ft h eq u e r ym e t h o d s ，r e p r e s e n t a t i o na n ds i m i l a r i t y m e a s u r e so ft i m es e r i e s b ym a k i n gu s eo ft h ep r o x i m i t yq u e r ym e t h o d i n c o m p u t a t i o n a lg e o m e t r y ，t h ew h o l em a t c h i n gq u e r y ，p a t t e r nq u e r y ，i n v e r s eq u e r y a n do u t l i e rd e t e c t i o ni nt i m es e r i e sa r es t u d i e d t h em a i nr e s u l t so ft h i sd i s s e r t a t i o n a r ea sf o l l o w s ： 1 q u e r ym e t h o d so f t i m es e r i e s a c c o r d i n gt ot h ec o m p o n e n t so ft i m es e r i e s ，t h r e ec a t e g o r i e so fq u e r y i n ga r e p r o p o s e d ，i n c l u d i n gp o i n tq u e r y i n g ，p a t t e r nq u e r y i n g ，a n dt i m e s e r i e sq u e r y i n g a c c o r d i n gt op r o x i m i t yd e f i n i t i o ni nc o m p u t a t i o n a lg e o m e t r y ，t h eq u e r y i n go f t i m e s e r i e sh a sb e e ne x p a n d e dt or a n g eq u e r y ，p r o x i m i t yq u e r y ，a n dc l o s e s tp a i rq u e r y t h ed e v e l o p m e n to ft i m es e r i e sq u e r y i n gc a np r o v i d ee f f e c t i v et e c h n i q u e sf o rd a t a m i n i n g 2 r e p r e s e n t a t i o na n di n d e x i n go f t i m es e r i e s b a s e do nt h ei m p o r t a n tp o i n ts e g m e n t i n go ft i m es e r i e s ，an e ws i m i l a r i t y m e a s u r eb ys l o p ea n dl e n g t ha r ed e v e l o p e d f o rt h ei n d e x i n go ft i m es e r i e s ，t h e v o r o n o id i a g r a mh a sb e e nu s e df o rt h eo r g a n i z a t i o no ft i m es e r i e s ，a n dan e w i n d e x i n gs t r u c t u r en a m e di c i n d e x i n g i sp r o p o s e df o rt h ei n v e r s eq u e r yo ft i m e s e r i e s 3 s i m i l a r i t yq u e r y i n gi nt i m es e r i e s w i t ht h ek ls i m i l a r i t ym e a s u r e ，an e wa l g o r i t h mf o rw h o l em a t c h i n go ft i m e s e r i e sh a sb e e nd e v e l o p e d t h ep a t t e r nq u e r y i n gp r o b l e mi ss o l v e di no p t i m a lt i m e b a s e do nt h ev o r o n o id i a g r a m 4 o u t l i e rd e t e c t i o ni nt i m es e r i e s b ym a k i n gu s eo ft h ev o r o n o id i a g r a m ，an e wd e n s i t y 。b a s e d o u t l i e rd e t e c t i o n a l g o r i t h mi sp r o p o s e d ，w h i c h r u n si nc o m p u t a t i o na so ( n l o g n ) ，a n dh a sb e e nu s e di n t h el i n e rp a t t e r no u t l i e rd e t e c t i o ni nt i m es e r i e s k e yw o r d s ：d a t am i n i n g ，t i m es e r i e s ，i n d e x i n g ，q u e r y i n g ，o u t l i e rd e t e c t i o n ， c o m p u t a t i o n a lg e o m e t r y ，v o r o n o id i a g r a m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人己经发 表或撰写过的研究成果，也不包含为获得苤鲞盘堂或其他教育机构的学位 或证书而使用过的材科。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意。 学位论文作者签名：明东彳卜签字日期： 2 0 0 66 月2 0 日 学位论文版权使用授权书 本学位论文作者完全了解鑫洼盘鲎有关保留、使用学位论文的规定。 特授权叁壅盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：妒禾毕 导师签名： ， 瑶础 签字日期：2 0 0 6 年6 月2 0 日签字日期：2 0 0 6 年6 月2 0 日 第一章绪论 1 1 研究背景和意义 1 1 1 数据挖掘概述 第一章绪论 随着计算机技术的发展和应用的普及，人类社会已经进入一个信息化时代， 信息技术在金融，经济、工农业生产、科学实验和人类生活的各个领域都得到 了广泛应用。信息技术的应用产生了大量的各种类型的数据，自2 0 世纪8 0 年 代起，全球信息量每隔十几个月甚至几个月就要增加一倍，呈爆炸式增长。面 对浩瀚的数据，人们难以找到合适的方法和工具，发现隐藏在这些数据背后的 知识，出现了“数据爆炸，知识贫乏”的现象。数据挖掘正是为了解决这种问题 而提出的。 数据挖掘( d a t am i n i n g ，d m ) l l j 是从大量的、不完全的、模糊的、随机的 数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知 识的过程。数据挖掘将人们对数据的应用从低层次的简单查询，提升到从数据 中挖掘有用的信息和知识，提高决策水平，其主要任务包括聚类分析，分类和 预测、关联分析和异常检测等。 数据挖掘是知识发现( 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 ，k d d ) 的关键步骤 ”l ，在许多领域得到了广泛的应用，几乎涉及到各个行业，包括经济管理、金 融、保险、电力、石油化工、地理地质、天文学、生物学等领域。例如，在财 务金融方面，预测市场动向，防范犯罪欺诈；在企业营销方面用于识别客户和 客户行为分析等。 目前，数据挖掘已经引起了学术界和工业界的广泛关注，成为国际上数据 库和信息决策领域最前沿、最热门的研究方向之一1 2 】- i ”。 1 1 2 复杂类型数据挖掘问题 随着信息技术、数字化和互联网技术的迅速发展，大量形式各异的复杂类 型的数据不断涌现。因此，数据挖掘面临的一个重要课题就是针对复杂类型数 据的挖掘f 2 1 1 5 1 ，包括空间数据、多媒体数据、时间序歹f j 数据、文本数据和w e b 第一章绪论 数据等。 ( 1 ) 空间数据 空间数据库中存储了大量与空间有关的数据，如地图，遥感数据，医学图 象数据，以及芯片设计数据等。空间数据结构一般由点、线、矩形等组成，同 一般的数据相比，具有非结构、高维等特点 6 - f j 。空间数据挖掘主要包括空间 数据描述、分类、关联分析、聚类和空间趋势与孤立点分析等为了对这些数 据进行挖掘，通常需要采用特殊的数据结构和多维索引方法，如k d 树、r 树、 r 帅日等。 ( 2 ) 多媒体数据 多媒体数据库是指存储和管理大量多媒体对象的数据库，包括音频数据、 图像数据、视频数据等。多媒体数据挖掘的基础是其数据描述问题【s 】饲如对 于图像数据库，通常提取其颜色、纹理和形状等底层特征，用特征向量描述哪， 其数据呈现高维、海量等特点。多媒体数据挖掘研究的主要问题包括基于内容 的检索和相似度检索、分类、聚类和关联规则挖掘等。 ( 3 ) 时序数据 时序数据库中的数据是随时间变化的，其主要的特点是维数高，数据规模 大。时序数据挖掘研究的主要内容包括相似性查询、聚类、频繁模式挖掘和异 常检测等。 ( 4 ) 文本数据 文本数据库中存在着大量以文本或文档形式存储着的信息，如新闻文章， 技术论文，书籍，电子邮件等信息。其数据呈半结构化，索引方法也与一般数 据不同，主要包括互关联后继树、h a s h 表、倒排索引等【1 0 l n 1 传统的信息检索 技术难以适应大容量文本数据的处理要求，超出了基于关键字和基于相似度的 信息检索范畴，一般利用基于关键字的关联和文档分类等方法从半结构化的文 本数据中发现知识。 ( 4 ) w e b 数据 w w w 是一个巨大的广泛分布的全球信息服务中心，包含了丰富和动态的 超链接信息和访问及使用信息。同文本数据类似，w e b 数据也属于半结构化数 据，w e b f 2 捌e 要包括对w e b 链接结构、w e b 内容g f l w e b 访问模式的挖掘， 如用于识别权威页面的w e b 链接结构挖掘，w e b 文档的自动分类，多层次w e b 第一章绪论 信息库的建立，以及w e b 日志挖掘等。 这些复杂类型的数据类型不同，结构各异，但其共同的特点是：数据高维 化、结构复杂化、存储海量化。 ( 1 ) 数据高维化 复杂类型数据一般具有几十、几百甚至成千上万个属性【1 3 1 【14 】【1 5 1 。例如，时 序数据、文本词频数据和多媒体数据等。 随着数据维数的升高，高维索引结构的性能急剧下降，这就是所谓的“维灾 f 司题( c u r s e o f d i m e n s i o n a l i t y ) f j6 】【3 8 】。w e b e r 等在文献【1 6 】中指出，随着维数的升 高，索引结构的修剪效率迅速下降，当维数增加到一定的数量，采用索引结构 进行查询反而不如顺序扫描，这就给数据挖掘提出了严峻的挑战，如何采用特 征提取等方法，降低数据的维数，成为解决数据高维化的主要方法。 ( 2 ) 结构复杂化 随着网络技术和多媒体等技术的发展，出现了大量结构各异的复杂数据类 型，如空间数据、多媒体数据、时序数据和文本数据等 1 8 l 。这些数据不像传统 数据那样，利用关系数据库的定长记录来保存，其长度不定、结构复杂，如时 间序列，g i s 系统中的线段、多边形或多面体，以及x m l 文件等，这些数据都 是非结构化或半结构化的。 结构复杂化给数据的描述、索引和查询都带来了很大的困难。这些数据不 能像传统的数值型数据那样直接进行排序，一般是提取其主要特征，采用空间 数据结构进行描述，针对具体的数据类型设计不同的索引和查询方法。 ( 3 ) 存储海量化 随着信息技术应用的发展，g b 量级数据库已经普遍存在，t b 量级数据库 也已经出现，如股市交易数据、g i s 空间数据、气象数据等。 海量数据增大了搜索空间，导致传统的数据处理方法在查询时间上难以接 受【。在保证算法正确的前提下，衡量一个问题解决方法优劣的主要指标是算 法的时间复杂性。时间复杂性通常表示为问题规模”的函数，如o ( n l o g n ) 和o ( n 2 ) ， 在处理少量数据时二者相差不大，但随着 的增大，从其函数曲线可以看出二 者差别很大因此，面对海量数据必须设计新的算法，提高数据挖掘的效率。 从复杂类型数据的特点可以看出，复杂类型数据挖掘面i 临的主要问题是如 何提高查询效率，而索引是提高查询效率的主要方法。数据索引和查询不仅是 第一章绪论 数据挖掘中聚类、分类、关联分析和异常检测等其它任务的基础。实际上也是 整个信息技术领域的基本问题。本文以时间序列挖掘为例，研究索引和查询技 术在数据挖掘中的应用问题，具有比较重要的理论和现实意义。 1 1 3 时间序列挖掘中的关键问题 时间序列在商业、经济以及科学研究等人们生活的各个领域中普遍存在。 例如，金融证券市场中每天的股票价格，商业中某项商品的周期销售额等。 时间序列挖掘是数据挖掘技术在时间序列分析中的具体应用。其目的是在 时间序列中发现隐藏的知识，分析时间序列变化规律，帮助人们科学地做出决 策。例如： ( 1 ) 在证券市场，找出上月与i b m 公司股票价格变化模式相似的股票， 从中可以分析产生这种变化的原因。 ( 2 ) 在金融领域，跟踪信用卡顾客的使用情况，当顾客在某段时期内的信 用卡使用情况异常时，能够及时报告。预防信用欺诈。 ( 3 ) 在天气预报中，找出在一段时间内频繁出现的温度的变化模式，从中 归纳出温度变化的规律等。 2 0 世纪9 0 年代以来，时间序列挖掘的研究和应用发展迅速，成为数据挖掘 领域的一个重要分支。时间序列挖掘的任务主要包括 2 3 1 【2 4 】以下几个方面： ( 1 ) 相似性查询。给定两个时问序脚y ，定义一个相似性度量标准d ( 五 ，如果d ( 墨” ，则称肺y 是相似的。相似性查询就是在时间序列数据库 中找出与给定的衙目似的时间序列。例如，找出上月与i b m 公司的股票价格交 化模式相似的股票等。 ( 2 ) 聚类。聚合那些具有相似模式的时间序列，例如，根据上月股价变化 模式对股票聚类等。 ( 3 ) 分类。根据时间序列的变化模式将其划分到不同的类中。例如，根据 上月股价变化模式，将其分为涨、跌、平三类。 ( 4 ) 频繁模式挖掘。找出在一段时间内频繁出现的模式。例如，找出上月 i b m 公司股票频繁出现的变化模式。 ( 5 ) 异常检测。找出一个时间序列，其在一时间段内的变化模式同其它序 列存在明显的差异。例如，在某一周内所有i t 公司的股票都上涨，而唯有一家 第一章绪论 公司的股票下降等。 从时间序列挖掘的任务可以看出，时间序列查询不仅是时间序列数据挖掘 的一项重要任务，同时也是聚类、分类、频繁模式挖掘和异常检测等其它任务 的基础1 2 4 】，而索引是提高时间序列查询效率的关键。 例如，在时间序列的聚类分析中，将时间序列分为多个类或簇，同一个簇 中的时间序列相似性比较大，而不同簇的序列之间相似性比较小，如图1 1 【“】。 图i - i 时间序列挖掘与查询 规则挖掘 由于时间序列挖掘的各种任务都是建立在相似性比较的基础上，因此，时 间序列查询是时间序列挖掘中的关键问题 时间序列属于数据挖掘中的复杂类型数据，除具有一般复杂类型数据的特 点外，甚至在某些方面更加复杂。其复杂性主要表现在以下几个方面： ( 1 ) 数据规模大。时间序列的数据随着时间不断变化的，一般的时间序列 数据库数据规模都非常大，如股市数据、气象预报数据等，数据存储容量都在 g b 以上； ( 2 ) 维数高。在时间序列挖掘中，通常需要比较两个时间序列的相似性， 一般的时间序列长度都在十几以上，特殊情况下甚至成百上千。例如，找出上 月与i b m 公司股票价格变化模式相似的股票，即使按每日收盘价比较，序列的 长度也在2 5 以上； ( 3 ) 结构复杂。同其它复杂类型数据相比，时间序列结构复杂化特别突出。 一方面，时间序列来源于实际生活中的各个应用领域，不同的时间序列采样方 法和测量标准都不统一，而且具有波动频繁、噪声干扰以及非稳态等特点；另 一方面，时间序列的其数据是按时间有序的，使挖掘方法受到限制；特别是时 间序列存在各种变形【6 3 j ，包括振幅平移、伸缩时间轴伸缩、弯曲和线性漂移 入几 淌 套张 第一章绪论 等，时间序列挖掘中必须考虑到各种变形对挖掘结果的影响。 这些问题使得时间序列相似性的定义、相似性度量、索引和查询都非常困 难。尽管国内外研究者提出了各种各样的方法，但目前在时间序列的查询效率 和准确性等方面至今没有得到很好地解决。 数据索引一直是信息技术领域的基本问题，是提高查询效率的主要途径 l 明【蛳。例如，在行个数的集合中查找给定的数据，采用顺序查找平均需要( 时1 ) ，2 次比较，如果通过二叉树建立索引采用折半查找，则最多需要o ( 1 0 9 n ) 次比较。 特别是在数据挖掘中，数据本身是海量的，算法的时间复杂性尤为重要，索引 对查询效率的影响更加明显。国外一般将数据的组织、索引和查询方法称为存 取方法( a c c e s sm e t h o d ) 【嘲【s 7 1 ，可以看出索引和查询是密不可分的。 因此，研究时间序列的索引与查询技术问题具有重要的理论意义和实际应 用价值。 1 2 国内外研究现状 1 2 1 传统的时间序列分析方法 传统的时间序列分析建立在概率统计的基础上，研究对象着重于随机性的 动态数据，研究方法着重于全局模型的构造。模型法是目前对时间序列进行深 层次分析的主要方法，经典的时间序列分析模型主要有a r m a 、a r 、a r c h 和 g a r c h 等【2 l 】【2 6 】。 模型法中的理论模型是在数学理论和假设基础上，通过演绎推理的方法建 立起来的各种模型都有坚实的数学基础，只要假设合理，所得出的结论就是 合理的。但如果所提出的假设不合理，模型法将会严重失真。这样，模型的构 建就非常重要，如果对系统认识不够和不具备良好的建模技巧，很难构建出一 个好的模型。例如很多金融计量模型，常常基于平稳性假设、正态分布假设、 线性假设等，但实际上金融时间序列具有信噪比低、非平稳、非正态、非线性 的特点。另一方面，模型法反映的是序列的总体的特征，对序列中隐含的一些 局部的细节特征很难表现出来。然而，在实际应用中，往往需要对时问序列局 部特征进行分析，如发现频繁出现的变化模式，两个时间序列相似性比较等。 数据挖掘是基于归纳的方法，从大量的、不完全的、模糊的、随机的数据 第一章绪论 中，提取隐含在其中的信息和知识的过程，与模型法的主要区别是可以撇开假 设，通过数据归纳出结论。数据挖掘建立在大量数据的基础上，依靠更多的是“经 验”，这就决定了数据挖掘对数据的质量要求比较高，否则就会产生“垃圾进、 垃圾出”的现象。 时间序列挖掘并不是对传统的时间序列分析方法的完全否定，而是补充、 完善和发展。实际上，数据挖掘的许多方法也都是建立在统计学的基础之上， 如贝叶斯、粗糙集和支持向量机等，a r m a 、a r c h 等一些建模方法也都被应 用到时间序列挖掘中。因此，时间序列挖掘在传统的时间序列分析方法基础上， 借助信息技术领域一些新的方法和技术，如机器学习，神经网络，数据库技术 等，对大规模的时间序列数据进行分析和处理，提出隐含在其中的知识，为分 析决策提供更加有力的技术支持。 1 r 2 2 时间序列的索引与查询 时间序列相似性查询最早由i b m 公司的a g r a w a ! 等人1 9 9 3 年提出。十 几年来，国内外学者对时间序列相似性查询进行了深入的研究，成为数据挖掘 领域的热点一个问题。特别是k e o g h 及其研究小组提出了分段线性表示法网， 在动态时问弯曲距离等关键闯题的研究方面也取得了一系列成果f 1 2 2 1 。尽管国内 外研究者提出了各种各样的方法，但从目前的研究现状来看，时间序列的查询 至今仍然没有很好地解决，难以满足实际问题的需要。 1 研究现状分析 时间序列查询主要涉及时间序列表示、索引、相似性度量等问题，下面分 别讨论。 ( 1 ) 时间序列表示 时间序列数据具有海量性、复杂性和噪声干扰等特点，直接在原始序列上 进行查询不仅计算量大，而且影响算法的准确性和可靠性。因此，国内外学者 提出了许多时间序列表示方法，提取时间序列的主要特征，将时间序列变换到 低维特征空间，在此基础上采用索引来组织时间序列的数据，提高时间序列的 查询效率。时间序列表示是索引、相似性度量和查询的基础。 目前，时间序列表示的主要方法有离散傅立叶变换( d f d 【加j * n d , 波变换 ( d w t ) 1 4 3 1 、奇异值分解法( s v d ) 【“、界标模型( l a n d m a r k s ) 【6 3 】、分段线性表示 第一章绪论 ( p l r ) l 叨和符号化方法( s a ) 【6 0 1 等，其中分段线性表示( p l r ) 法包括分段线性表示 法( p l a ) s s l 、分段累积近似法( p a a ) 1 4 8 】和适应性分段常数近似法( a p c a ) 吲。 近期，r a t a n 踟a 1 1 a 协n a 和- 目一 3 5 1 等根据其原理对各种表示方法进行了分 类，m i c h e l 等d s 对各种序列表示方法进行了比较和评价，z h u 捌在其博士论文 中介绍了各种方法的原理，并进行了比较和评价。从总体上看，各种表示方法 都有其优势和不足，离散傅立叶变换d f t 和p a a 、a p c a 等方法平滑掉了原始 序列中的局部极值点，导致许多重要信息丢失；离散小波变换( d w t ) 无法处理 任意长度的序列；奇异值分解法( s v d ) 、界标模型和p l a 表示法计算复杂性过 高等。 特征提取是以信息丢失为代价的，无论采用何种方法，都难以避免这种问 题，关键是如何在准确性与效率之间权衡。如果要求误差尽可能小，则可以选 择奇异值分解法( s v d ) 、界标模型和p l a 表示法，这些方法都能够保证每个分 段的误差小于给定的阈值，但时间复杂性比较高，至少为o ( n z ) ，其中i 为原始 序列的长度，三为各子段的平均长度；如果主要考虑效率，则应当选择p a a 、 a p c a 和基于重要点的分段方法其中，p r a t t 和f i n k l 6 4 提出的基于重要点的分 段方法具有明显的优势，一方面可以通过控制参数选择分段精度，达到控制误 差的目的，另一方面其时间复杂性比较低，是目前采用的主要方法。 时间序列表示的另外一个问题是特征点如何表示，即如何表示特征点或分 段的特征，这一问题直接影响到相似性度量方法的选择。目前主要有坐标表示 法i 蚰】、符号表示法【6 9 1 、趋势表示法1 7 q 和斜率表示法等。 坐标表示法是最基本的表示方法，适用于欧式距离、动态时间弯曲距离等 相似性度量，但不够直观；符号表示法和趋势表示法是将每个分段映射到有限 的符号表上，比较直观，利用字符串匹配和索引方法可以实现查询，但现有的 字符串匹配和索引效率都比较低，只适用于小规模的时间序列；斜率表示法是 用线段的斜率或倾角来表示每个分段，其主要优势是真实地反映了序列的趋势 变化，是近年来广泛采用的一种方法但根据我们的分析，这种表示方法也存 在许多缺陷，其中最主要的是斜率只是反映了时间序列在一段时间内的变化趋 势，却没有表示这种趋势持续的时间，因此容易造成查询错误。 ( 2 ) 时间序列索引 在时间序列表示的基础上，提取其主要特征，将时间序列映射到高维空间 第一章绪论 中的点，通过建立索引可以提高查询效率。 a g r a 、v a l 等【删最早提出了时间序列的f 索引，s a l z b e r g 等【“川对时序数据库的 索引方法进行了比较和评价。目前，时间序列索引主要有两种方法，一是直接 利用高维数据索引方法，如r 树等；二是针对时间序列的具体特点和要求，对 高维数据索引方法加以改进，或设计专门的索引方法。 由于索引方法是目前整个信息技术领域研究的热点问题，近年来国内外研 究者提出了一系列索引方法【”】- 1 9 1 1 。直接利用高维数据索引可以充分利用现有 技术，但由于时间序列的维数比较高，如何避免“维灾问题”是需要解决的主 要问题。针对时间序列的索引实际上都建立在高维数据索引方法的基础上，也 面临同样的问题。 ( 3 ) 时间序列相似性度量 相似性度量是衡量时间序列相似性的标准。相似性度量的选择决定了查询 算法的性能，影响到查询的完备性、对时间序列各种变形的支持等。当然，相 似性度量标准的选择也受时间序列表示方法的制约。 目前，时间序列相似性度量主要有：欧氏距离1 2 8 1 、动态时间弯曲距离【1 捌 和编辑距离1 1 3 9 等，其中欧氏距离是m i n k o w s k i g l i 离的一种特例。m i n k o w s k i 距 离计算简单，复杂性为0 ( 帕，支持各种索引方法，但对时问序列的各种变形都 不支持；动态时间弯曲距离是目前相似性度量中的研究热点，其主要优点是支 持时间序列的时间轴弯曲，但其计算比较复杂，时间复杂性为o ( m n ) ；编辑距 离支持时间轴的伸缩，但其计算复杂性也比较高。 从上述分析可以看出，目前相似性度量问题还没有很好地解决，特别是时 间序列变形对相似性查询的影响，各种相似性度量只支持其中的几种变形。 时间序列相似性度量是一个比较模糊的问题【”，并没有一个公认的相似标 准，同时又是一个具有挑战性的问题，需要在查询精确度和效率之间权衡。 ( 4 ) 时间序列异常检测 异常检测( o u t l i e rd e t e c t i o n ) l i 】是在数据库中找出明显偏离其它数据，不 满足数据的一般模式或行为，与其它数据不致的数据。在许多领域中，异常 数据的发现往往能带给我们更有价值的知识。例如在金融领域，异常数据可能 意味欺诈行为的发生，在入侵检测中异常数据可能意味入侵行为的发生等。且 前，异常检测已经成为数据挖掘的一个重要分支。从广义上讲，异常检测与异 第一章绪论 常挖掘是有区别的，异常检测也可以看作是一种满足特殊条件的查询。 1 9 7 2 年f o x l l 6 3 1 将统计诊断的思想引入时间序列分析，提出了异常点的概念， d o n g 等 7 3 1 将异常点定义为新颖点，k e o g h 等1 删提出了奇异模式( s u r p r i s ep a t t e r n ) 的概念，肖辉1 2 3 1 将时间序列异常分为点异常，模式异常和序列异常，并提出了 线性模式异常的检测算法。 目前，国内外对时间序列异常的研究还比较少，还处于起步阶段1 1 期一方 面，时间序列异常还没有一个公认的定义；另一方面，现有算法的复杂性也比 较高1 ，都在d ( 矛) 以上。 2 目前研究的局限性 h e t l a n d l l 2 1 1 和k e o g i l 等【1 2 2 】分别对近年来时间序列的性查询方法进行了比较 和评价，其中k e o g l l 等l m 】分析了3 0 0 多篇论文的结果，对其中的2 5 种算法进 行了实验，认为目前算法存在两方面缺陷：一是算法只是针对特定的数据查询 效率比较高，二是在索引和精确度方面还有待于提高。除此之外，我们认为目 前时间序列查询还存在以下局限性： ( 1 ) 从查询对象看，目前只考虑了时间序列本身的查询，分为全序列匹配 和子序列匹配两种方式。而没有对各种模式和状态点查询进行深入的研究 ( 2 ) 从查询方式看，目前主要研究时间序列的相似性查询，查询对象是时 间序列，查询方式属于礤b 域查询。对于其它方式的查询，只有文献【2 7 】对序列 的七邻近查询进行了讨论，文献 2 8 1 提到了所有邻近查询但没有进行研究。因此， 目前对喝序歹l j 的查询以序列的相似往查询为主，还有很多其它查询方式值得研 究 1 2 1 】【1 2 2 1 ，如在时间序列数据库中找出两个最相似的时间序列等，这些都是时 间序列挖掘的基础。 ( 3 ) 从实现技术看，目前许多方法只注重查询的实现，而忽视算法的时间 复杂性，查询效率比较低。这些算法在小规模数据下是有效的，对于大规模的 时间序列查询，这些算法难以发挥作用。 总之，目前的时间序列查询在查询方式上有还待于进一步扩展，在查询效 率和准确性等方面还有待于进一步提高。 第一章绪论 1 3 本文研究的主要内容与创新 1 3 1 主要研究内容与创新 本文针对复杂类型数据挖掘面临的问题，根据时间序列的特点，利用计算 几何方法，对时间序列数据挖掘中的索引和查询技术进行研究。首先，系统地 研究了时间序列的查询方式，然后讨论了时间序列查询中涉及的时间序列表示： 索引、相似性度量等一系列问题，在此基础上提出了时间序列模式查询、全序 列匹配查询、反向查询和异常检测算法，查询效率和准确性都有了比较大的提 高。主要创新点有以下几个方面。 1 时间序列的查询方式 利用计算几何中邻近问题的原理和方法，根据时间序列的构成要素，对时 间序列的查询方式进行了系统地分类。按照查询对象将时间序列查询分为点查 询、模式查询和序列查询，按照查询方式分为范围查询、邻近查询和点对查询， 并提出了利用v o r o n o i 图实现时间序列查询的方法，进一步拓展了时间序列查 询的方法，为时间序列挖掘提供了更加有力的工具。 2 时间序列的表示与索引 在基于重要点分段的基础上，提出了时间序列的k l 相似性度量。利用计 算几何中v o r o n o i 图对数据进行组织和管理，为时间序列的查询提供了一种新 的数据索引方法。同时，针对时间序列原始数据的反向查询，提出了一种新的 时间序列索引方法l c 索引，查询效率有了比较大的提高。 3 时间序列的相似性查询 利用计算几何中邻近问题的方法，系统地研究了时间序列各种查询方式的 实现方法。提出了k l 相似性度量方法，实现了时间序列全序列匹配查询；利 用计算几何中的v o r o n o i 图，实现了线性模式的最近邻近查询、最近模式对查 询和最远模式对查询，这些算法在时间上都是最优的；同时，提出了一种新的 时间序列反向查询方法，查询效率和准确性都有比较大的提高。 第一章绪论 4 时间序列的异常检测 利用计算几何中v o r o n o i 图的基本原理，提出了一种新的基于密度的异常检 测方法v o d ，并应用到时间序列的点异常和线性模式异常检测，算法的复杂性 从d ( ”2 ) 降低到0 ( l o g 彤，检测效率和性能都有了很大的提高。 1 3 2 研究方法 目前，数据挖掘的方法主要有1 1 h 5 1 ：统计方法、机器学习方法、神经网络 方法、面向数据库方法和面向属性的归纳方法等。其中统计方法包括回归分析、 判别分析、聚类分析以及近年来发展起来的粗糙集和支持向量机等；机器学习 方法主要包括决策树、规则归纳、基于范例学习和遗传算法等。本文提出了将 计算几何方法应用到数据挖掘的方法。 计算几何( c o m p u t a t i o n a lg e o m e t r y ) 是1 9 7 5 年s h a m o s 在一篇关于点集最 近点对的论文例中提出的计算机科学中的一个分支。其主要研究对象是点集、 线段、多边形和多面体等；研究内容主要包括凸包闯题、邻近问题、搜索闯题、 几何运算、几何优化、碰撞检测和运动规划等【2 9 】【3 i 】；研究方法主要有分治法、 裁剪与搜索、扫描算法、几何变换、动态算法、随机方法等。近年来，计算几 何在计算机图形学、模式识别、图像处理和g i s 等领域得到了广泛的应用。例 如，v o r o n o i 图在邻近查询、凸包、最小树、s t e i n e r 树、货郎担、三角剖分等组 合优化问题中的应用等。为区别以数值分析为基础研究样条函数等问题的计算 几何，一般将s h a m o s 提出的计算几何称为晰算几何口9 】【3 ”。 目前，计算几何方法应用于数据挖掘还没有得到系统地研究和应用，只有 个别文献提到将最近邻近方法用于聚类分析【3 2 】和g i s 中的空间关系分析【6 1 ，计 算几何应用于时间序列挖掘还没有研究。 本文将计算几何方法应用到数据挖掘的基本思路是；梅数据挖掘中的数据 对象作为空间中的点，利用计算几何中关于点集问题的方法解决数据挖掘中的 问题，主要解决以下三个方面的问题： ( 1 ) 时间序列的查询方式 利用计算几何中点集邻近问题的原理和方法，系统地研究了时间序列的查 询方式问题，分为范围查询、邻近查询和点对查询三类，共十种查询方式。 ( 2 ) 时间序列的模式查询 第一章绪论 利用计算几何中v o r o n o i 图的基本原理，以时间序列的线性模式查询为例， 提出了最近邻近查询、最远模式对查询：利用提出的确定点集最远点对算法， 实现了最远模式对查询，这些算法在时间上都是最优的。 ( 3 ) 基于v o r o n o i 图的异常检测 利用v o r o n o i 图，提出了一种基于密度的异常检测方法v o d ，将现有算法的 复杂性从d ( 矛) 降低到0 ( n l o g n ) ，并应用于时间序列的线性模式异常检测。 1 3 3 论文结构 本文主要研究时间序列挖掘中的索引和查询问题，主要研究内容包括时问 序列查询方式、表示方法与索引、相似性度量、相似性查询、反向查询和异常 检测等，全文分为七章，各章主要内容安排如下： 第一章绪论。针对数据挖掘中目前面l 临的复杂类型数据挖掘问题，分析了 复杂类型的数据的特点，针对时间序列挖掘，指出提高降维、索引和查询的效 率是解决当前问题的关键。 第二章时间序列查询概述。对目前时间序列的查询方式进行了分析，利用 计算几何中邻近问题的原理，对时间序列的查询方式进行了系统地研究，根据 查询对象和查询方式对时间序列的各种查询进行了分类。 第三章时间序列的表示与索引。分析了目前的时间序列表示和索引方法， 在基于重要点分段的基础上，主要研究了时间序列的k l 表示方法。 第四章时闻序列相似性查询。对时间序列相似性查询的概念、相似性度量 和查询方法进行了系统地研究。在k l 表示方法及其相似性度量的基础上，实 现了时间序列全序列匹配查询；利用v o r o n o i 图对数据进行组织和管理，实现 了线性模式的最近邻近查询、最近模式对查询和最远模式对查询。 第五章时间序列反向查询。研究了时间序列的反向查询问题，提出了一种 新的时间序列动态索引方法一l c 索引，给出了时间序列反向查询的实现方法。 第六章时间序列异常检测。对现有的异常检测方法进行了分析，利用计算 几何中v o r o n o i 图的基本原理，提出了一种新的基于密度的异常检测方法，并 应用到时间序列的线性模式异常检测。 第七章总结与展望。对全文进行了总结，提出了进一步的研究方向和需要 解决的闷题。 第二章时间序列查询概述 第二章时间序列查询概述 时间序列查询不仅是时间序列数据挖掘的一项重要任务，同时也是聚类、 分类、频繁模式挖掘和异常检测等其它挖掘任务的基础。目前，时闻序列查询 主要是针对时间序列本身的相似性查询，分为全序列匹配和子序列匹配两种方 式，而对其它查询方式研究很少，难以满足时间序列分析的要求根据时间序 列的构成要素，利用计算几何的有关知识，本章对时间序列的查询方式进行了 系统地研究，按照查询对象和查询方式对时间序列的查询进行了分类，并对其 实现方法进行了探讨。 2 1 时间序列的概念 时间序列在商业、经济以及科学观测等各个领域普遍存在。例如，证券市 场中每天的股票价格，商业零售行业中某项商品的周期销售额，气象预报中的 气温和气压，以及医学中病人的心跳变化等。如图2 - 1 所示1 3 4 】。 时间序列( t i m es e r i e s ) 是按时间顺序排列的一系列数据的集合。从广义上 讲，时间序列是时态数据( t e m p o r a ld a t a ) 3 7 j 的一种特殊类型。时态数据是一系 列存在一定时间关系的数据的集合，根据其数据类型的不同，时态数据主要分 为三种类型：时间序列、事务序列和事件序列。 图2 1 时问序列 ( 1 ) 时间序y l j ( t i m es e r i e s ) 。即传统意义上的时间序列，构成时间序列的 数据是数值型的，如股票价格等。 第二章时间序列查询概述 t i m es e r i e s 和t i m es e q u e n c e s 虽然都指时间序列，但从严格意义上讲二者是 有一定区别的f 2 0 】。t i m es e q u e n c e s 是时问序列的统称，分为规则时问序列和不 规则时间序列两类，其中规则时间序列中数据的采样时间具有相等的间隔，而 不规则时间序列数据的采样时间是任意的，t i m es e r i e s 特指规则的时间序列。 ( 2 ) 事务序列( t r a n s a c t i o n a ls e q u e n c e s ) 。构成序列的数据是事务型的，如 顾客在超市中购买商品的记录序列。 ( 3 ) 事件序y l j ( e v e n t ss e q u e n c e s ) 。构成序列的数据是事件，如无线通信网 中的故障序列、用户的界面交互行为序列。 根据上述讨论，本文对时间序列定义如下。 定义2 - 1 ( 时间序列) ：时间序列( t i m es e r i e s ) 是按时间顺序排列的、具有 相等时间间隔的一系列数据的集合，记为：j ，- 协，x 2 ，) 。 其中：j i - ( ，v i ) 为时间序列的状态点，表示在t i 时刻时间序列的值为v i ，v i 为数值型数据；n y o 时间序列的长度。时间序列中的时间是严格递增的，即： 蚵铮t i t j 由于时间序列的数据具有相等的时间间隔，一般规定a t = t i + l t i - - 1 ，t l = l 。这 样，时间序列就可以直接表示为x = x l ，x 2 ，x n ) ，这里为为i 时刻时间序列的值。 时问序歹g 肿从f 她的子序列用砸f 刃表示，1 s i 每勤。 时间序列的数据通常存储在文件中，一般以数据库的形式存放，这种数据 库称为时间序列数据库。例如在股票数据库中，数据分为静态记录和动态记录 两类，静态记录是与时间无关的数据，包括上市公司的基本信息，如股票代码、 主营项目等，动态记录是指与时间相关的数据，如每日的开盘价、收盘价、成 交量等，其中动态记录构成时间序列，如每日收盘价等。 时间序列数据库用s - 蜀，硷，) 表示，其中置为一个时间序列，脚表示其 中时间序列的