（计算机应用技术专业论文）符号化高维时间序列的检索算法研究.pdf

大连理工大学硕士学位论文 摘要 大规模的时间序列的数据挖掘问题在近些年的关注程度逐渐升高，其中高维时间 序列的检索算法更是难点。由于数据维度的增多，大大增加了数据挖掘算法的复杂性， 一些学者认为将时间序列符号化是十分必要的。 在符号化方面，很多当今成型的算法大都是针对一维序列的，无法很好的应用于 高维时间序列的符号化。本文提出一种基于多级k 均值聚类的高维时间序列的符号化 方法。通过定义最大允许的平方误差，来决定符号化的粒度。 在符号序列检索方面，以倒排表数据结构为基础设计出一套针对符号化时间序列 的检索算法。首先将倒排表查询的粗筛选算法转换成界限t 集合求交问题，并提出一 种基于堆的完全划分方法，使得算法在原有的基于堆的不完全划分的方法上有了较大 提高。 采用最长公共子序列( l c s s ) 作为度量序列间距离的方法。不同于传统的l c s s 算法，本文提出了一种限制最小匹配率风衲的l i m i t e d l c s s 算法，并在此基础上针对 倒排表的数据结构特点对算法进行了优化，显著的提高了算法的效率。并实现了时间 轴的弹性匹配。定义了高维字符的匹配方法，使得算法适用于高维的字符化时间序列 的检索。最后针对人体动作序列这一典型的高维时间序列进行索引实验，证明算法具 有较高的运算效率，在数据引入噪声的情况下，依然有这较高的正确性。 关键词：高维时间序列；降维；符号化；检索；弹性匹配 符号化高维时间序列的检索算法研究 t h es t u d yo f i n d e x i n ga n dr e t r i e v a la l g o r i t h mf o rs y m b o l i c m u l t i d i m e n s i o n a lt i m e s e r i e s a b s t r a c t d a t am m m gt e c h n i q u e st h a tf o c u so nm u l t i - d i m e n s i o n a lt i m es e r i e sa t t r a c t sm o r ea n d m o r er e s e a r c h e r s ，a n dt h ei n d e x i n ga n dr e t r i e v a lm e t h o d si st h eo n eo ft h em o s ti m p o r t a n t p a r t ，w i t ht h ei n c r e a s i n go ft h ed i m e n s i o no fd a t a ，d a t am i n i n ga l g o r i t h mg e t sm o r ea n d m o r ec o m p l i c a t e d ，m a n yr e s e a r c h e r ss u g g e s t e dt h a ti ti si m p o r t a n tt ou s i n gs y m b o l i z a t i o n m e t h o dt os o l v et h ep r o b l e m f o rt h ep u r p o s eo fs y m b o l i z a t i o n ，m a n ya l g o r i t h m sw e l lk n o w ni s d e s i g n e df o r o n e - d i m e n s i o n a ls e q u e n c e ，w h i c ha r en o ts u i t a b l ef o rm u l t i - d i m e n s i o n a ld a t a a d v a n c e sa m e t h o do fm u l t i d i m e n s i o n a l s e q u e n c es y m b o l i z a t i o nb a s e do nm u l t i l e v e lk - m e a n s c l u s t e r i n g g r a n u l a r i t yo fs y m b o l i z a t i o ni sd e t e r m i n e db yt h em a xs q u a r ee r r o rr 懈 f o rt h ep u r p o s eo fi n d e x i n ga n dr e t r i e v a lo fs y m b o l i z a t i o ns e q u e n c e ，a d v a n c e sa m e t h o db a s e do ni n v e r t e di n d e xd a t as 仃u c t l l r e f i r s tc o n v e r s i o nc o a r s ef i l t r a t i o np r o b l e mt o t - t h r e s h o l ds e tp r o b l e m t h e na d v a n c e sac o m p l e t ep a r t i t i o nm e t h o db a s e do nh e a pd a t a s t r u c t u r e ，w h i c hi m p r o v et h ee f f i c i e n c yo fa l g o r i t h mf r o mi n c o m p l e t ep a r t i t i o nm e t h o d u s i n gl o n g e s tc o m m o ns u b s e q u e n c e ( l c s s ) a st h em e a s u r e ，w h i c hi m p r o v e st h e o r i g i n a ll c s sa l g o r i t h mb yd e f i n e 以n i n a st h em i n i m a lm a t c h i n gr a t ea n du s i n g c h a r a c t e r i s t i co fi n v e r t e di n d e xm o d e l t h em e t h o da l l o w sa ne l a s t i cs h i f t i n go ft h et i m e a x i s d e f i n et h em a t c ho fm u l t i - d i m e n s i o n a ls y m b o l ，s oi tc a nb eu s e d0 1 1i n d e x i n ga n d r e t r i e v a lm u l t i d i m e n s i o n a ls e q u e n c e a tl a s t ，u s i n gt h ee x p e r i m e n to ni n d e x i n gh u m a n s p o r t sd a t at os h o wt h a th i g he f f i c i e n c yo ft h ea l g o r i t h ma n da l s ot h ec o r r e c t n e s s ，e v e n w h e na d d e dn o i s ed a t a k e yw o r d s ：m u l t i d i m e n s i o n a lt i m es e r i e s ；d i m e n s i o n a l i t yr e d u c t i o n ；s y m b o l i z a t i o n ； r e t r i e v a l ；e l a s t i cm a t c h i n g i i 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体己经发表的研究成果，也不包含其他己申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目： 益墨j 塑盘翌羔塑i 叠庭至尘坠蕉塞簦! 幺驾盗 作者签名：查兹日期：丝! 全年垒月- 日 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 笥圭j 鱼童垒盟圃垦刭竺蕉盘簋i 主堑! 歪 作者签名： 导师签名： o ， ，盔j 7 l ，一_ e 二一1 、 e t 期：宝! ! 呈年生月二日 日期：兰! 竺里年生月二l 日 大连理工大学硕士学位论文 1 绪论 1 1研究背景 随着计算机技术的发展和应用的普及，人类社会已经进入一个信息化时代，信息 技术在金融、经济、工农业生产、科学实验和人类生活的各个领域都得到了广泛应用。 信息技术的应用产生了大量的各种类型的数据，呈爆炸式增长。数据挖掘正是为了解 决这种问题而提出的。数据挖掘目前已是信息产业界的关注热点，主要原因在于数据 挖掘算法可将这些数据转换成更加有用的信息和知识。 数据挖掘( d a t am i n i n g ，d m ) 【l 】是从大量的、不完全的、模糊的、随机的数据中， 提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。数据 挖掘将人们对数据的应用从低层次的简单查询，提升到从数据中挖掘有用的信息和知 识，提高决策水平，其主要任务包括聚类分析、分类和预测、关联分析和异常检测等。 数据挖掘也称为数据库中的知识发现( 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 ) ，即从 大规模的数据中抽取非平凡的、隐含的、未知的、有潜在使用价值的信息的过程 2 】。 作为一门交叉学科，数据挖掘集成了许多学科中成熟的工具和技术，包括数据库技术、 统计学、机器学习、模式识别、人工智能等。数据挖掘技术一般与数据库的相关技术 紧密结合，更加侧重于对海量数据的多种模式的自动发现，因此具有更广泛的应用前 景。 时间序列上的数据挖掘研究自从2 0 世纪9 0 年代以来发展迅速，时间序列来源于 实际生活中的各个应用领域，采样方法和测量标准都不一致，具有短期波动频繁、大 量噪声干扰以及非稳态的特点，使得相似性查询变得非常困难。相似性度量是时间序 列的相似性查询的基础，时间序列的索引技术则可以提高相似性查询的效率。时间序 歹l j ( t i m es e r i e s ) 普遍存在于许多重要应用领域中，i ：l - j t nd n a 序列、金融数据、传感器 网络监控数据、移动对象跟踪数据以及运动捕获结果等都可以视为时间序列。时间序 列是指按时间顺序排列的一种数据，在“时间序列”这一学科所研究的范围内，是广义 地指一组有序的随机数据【3 】。时间序列分析起源于预测，自从1 9 7 0 年g e p b o x 和 g m j e n k i n s 的( ( t i m es e r i e sa n a l y s i s f o r e c a s t i n ga n dc o n t r 0 1 ) ) 一书问世以来，时间 序列分析方法的研究和应用发展迅速，其应用的范围日益扩大。 近些年来，针对时间序列数据库的数据挖掘则受到了更加广泛的关注。数据挖掘 领域中的大多数问题所研究的对象通常是静态的数据，即欲挖掘的模式与数据库中信 息呈现的顺序无关。然而，在一些与时间紧密相关的领域，例如股票趋势预测、入侵 符号化高维时间序列的检索算法研究 检测、通信数据流分析、多媒体信息检索以及关键设备运行状态的监控等，采用与时 序无关的数据挖掘技术并不能最大程度地提取到有价值的信息，而此时引入时序信息 往往可以有效地改善挖掘的结果。随着此类应用的范围不断扩大，尤其是对多媒体等 信息进行深层次处理的需求不断增加，针对时间序列数据库的数据挖掘引起了广泛的 关注。 时间序列是由单个或多个实数变量构成的具有时间信息的序列。由这样的序列构 成的数据库叫做时间序列数据库( t i m es e r i e sd a t a b a s e ，t s d b ) 。对于此类问题的研究， 主要集中在对时间序列的分块表示、索引建立、相似性检索、模式分析、异常事件检 测等方面。根据每一个时刻对应的数据不同，其又可划分为一维时间序列和多维时间 序列。一维时间序列，即每个时刻只包含一个单实数变量，由于仅具有一个维度且研 究时间较早，因此在索引建立及相似性检索等方面已经出现了些较为成熟的算法。 而随着技术的发展以及需求的增加，出现了许多更加复杂庞大的时间序列数据库： 即与一个时刻对应的是多个实数变量或者描述性的属性，而非简单的单实值变量；其 相互之间的关系也不仅仅是变量与时间之间的相关性，变量与变量之间也会具有一定 的联系，以至有时需要用图而不仅仅是多维向量来表示变量之间的关系。这样的时间 序列被称为高维时间序列。由于每一时刻对应数据的维度膨胀所带来的计算复杂度的 激增，使得大部分成功应用于一维时间序列的挖掘技术，诸如发掘时间序列中的主旨 模式、检测时间序列中的异常事件以及时间序列的分类和聚类等技术，都无法应用在 高维时间序列的挖掘上。因此在各方面尤其是模式提取、异常检测等高计算复杂度问 题上，都需要寻找新的有效算法。近年来需要进行深层次分析的数据，如航天飞船等 重要仪器的运行状态数据、互联网中关键服务器的通讯流量数据、高新生物医学实验 中的测量数据、地震以及天文方面的重要测量数据、应用于多种行业的人体运动捕捉 数据等，都是复杂的高维时间序列，因此研究对高维时间序列进行数据挖掘的有效算 法是很有意义的。本文主要针对高维时间序列的符号化和相似性检索这两个方面进行 了研究。 1 2 时间序列数据挖掘的研究现状 目前，国内外对一维时间序列研究已经比较成熟，但对高维时间序列的研究还不 够深入，仅在相似性检索方面有一些进展，对于高维序列的符号化和检索等方面问题 还有待于更好的解决。 大连理工大学硕士学位论文 1 2 1 时间序列符号化现状 一直以来，时间序列处理都沿着两条平行方向前进，一条是符号序列的处理，另 一条是实数序列处理。过去，符号序列处理主要局限于研究混沌行为的符号动力学。 随着计算机的发展，数据流( 如多媒体、文本) 的处理大行其道，出现许多新的实用算 法。符号序列模型很多，如哈希表、马尔可夫模型、后缀树、决策树等。相对于神经 网络之类的实数序列模型，符号序列模型的结构简单明了，更容易被人理解。这也体 现出符号序列处理的主要目的是提取系统的隐含特征，强调对系统的深入理解，而不 是精确预测。 h a d a m a r d 4 】最早对符号化动力学进行研究，后来m o r s e 5 】和h e d l u n d 6 】对其研究进 行拓展。之后c o l l e t 和e c k m a r m 7 】完整的定义了动力学系统行为符号化的可行性。 j a c k s o n 8 】给出了现代符号化方法的起源论述和其相关领域。c r u t c h f i e l d 9 a o 幂l j 用了著名 的理论优化无噪声确定性系统的分割，r e c h e s t e r 1 1 1 ，g r a s s b e r g e r 1 2 1 ，d a v i d c h a c k 1 3 1 等 人提出了一些产生分割度估计方法。t a n g 等人 1 4 j 5 设计了一套可以解决有噪声的非线 性动态模型的二值符号法。尽管己经有许多成型的字符分割方法，但评估分割结果的 灵敏度是十分必要的。很多算法的分割结果都较差，b o l l t 等人【1 6 , 1 7 在若干非线性模型 上强有力的证实了这一点。k u r t h s 1 8 】等人设计了基于一阶或高阶差分系统的符号化方 法。g a u t a md a s 1 9 】提出了一个基于固定窗口分割时间序列的符号化方法，该方法的主 要问题在于窗口宽度的选取没有一个明确的标准，所以很难确定一个合理的窗口宽度， 使得所有时间序列片段都具有相对独立的变化模式。t a n g 2 0 】提出了轨道符号化的一种 方法，并在存在噪声的混沌信号上做了统计实验。l i n e 2 l 】提出一种基于查概率分布表 的方法来确定符号区间的划分。a r a y 2 2 】提出一种小波空间法。 针对高维时间序列的符号化，采用传统的方法将各个维度分量逐一符号化往往不 合适，这意味着必须将各分量看作相互独立的随机过程并且必须单独为每一个分量建 立概率模型。但事实上多维时间序列数据的各个分量间通常是相关的【2 引。 王晓晔等人【2 4 】提出了一种f u z z ya r t 聚类法的多维时间序列符号化方法。 1 2 2 时间序列的相似性检索研究现状 相似性查找是时间序列挖掘的一个最重要研究方向。对于给定的目标序列q 和相 似性度量函数d i s ( q ，c ) ，相似性查找指的是在时间序列数据库t d b = q l ，0 2 ，q ) 中，寻找与q 最相似的那个序列q 嘲。目前常用的衡量相似性的方法有m i n k o w s k i 距离、动态时间形变距离( d t w ) 、编辑距离以及最长公共子序列距离( l c s s ) 等，其中 后三种方法因在时间轴上具有弹性伸缩性质，且对噪声具有一定的鲁棒性，而被广泛 符号化高维时间序列的检索算法研究 的应用。另外，在检索过程中，为了能够有效地进行剪枝从而加快检索速度，需要引 入一些空间数据结构来组织索引，目前常用的结构有r t r e e 2 6 1 、r 木t r e e 2 7 1 、m t r e e 2 8 1 、 a 船e 【2 9 】及其变形，然而这些索引结构在数据维度过高的情况下，由于维灾”的影 响，性能会急剧下降。因此大多数相似性查找方法都是先采用某种降维手段对时间序 列进行维度约减，在此基础上再进行相似性计算。 国外对这两个问题的研究大约开始于2 0 世纪9 0 年代。早期对于时间序列的检索 的研究多采用欧式距离的度量方法【3 0 。3 3 1 ，这种度量方法的主要问题是无法匹配时间轴 的伸缩，同时对于噪音非常敏感。基于形状的时间序列相似性度量的方法主要还有动 态时间弯曲距离( 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 tc o m m o n s u b s e q u e n c e ，l c s s ) 。这两种方法均可以实现时间轴的弹性匹配。b e r n d t 和c l i f f o r d 首先将d t w 这种技术应用于时间序列特征提取 ”】。r a f i e i ”】等提出了在相似性比较 中允许形变的索引算法，c h a n 3 6 】等证明了离散小波变换可以替代离散付立叶变换来提 取频域标志，并且具有更低的复杂度。另一些学者则从序列在时域的特征入手，y i l j j 等、k e o g h 3 8 】等研究了基于分段常数近似( p c a ) 的标志提取算法，并分别证明了这种 方法可以适用于多种相似性度量而无需改变索引结构。k e o g h 3 9 等针对p c a 进行了改 进，提出了自适应长度的p c a 算法，克服了传统p c a 需要将序列分割成等长子序列 的缺陷。在分段线形近似的基础之上，k e o g h 【4 0 】等提出了基于地标( 1 a n d m a r k ) 的技术， p e m g 4 l 】等提出了更具通用型的地标模型，具有在时间轴上伸缩、振幅伸缩等性质。 k i m 4 2 】等提出了一个简化的地标模型，通过提取一个序列中的最小、最大、最初和最 末的元素，来解决在由时间轴上的形变所引起的匹配问题。其他一些改善查询性能的 技术也被提出。b a e z a 4 3 】等和p a r k 4 4 】等分别独立地提出利用后缀树来避免重复求解基 于动态规划的相似性度量问题。k e o g h 4 5 】等提出了分段线形近似算法来约简时间序列 的维数，这种算法能有有效应用于包括动态时间变形等数种相似性度量，并且已被证 明优于基于离散付立叶变换的标志提取算法。在此基础上，k e o g h 4 6 】等提出了一种基 于哈希的索引方法。k e o g h 【4 7 】等在2 0 0 2 年提出了计算d t w 距离精确下界的算法，这 是目前性能最好的d t w 下界算法。由于l c s s 算法在时间序列受随机尖锐噪声干扰 情况下匹配的准确程度要高于d t w 算法【4 8 1 ，因此更适合工程应用。v l a c h o s 之后又 将d t w 度量应用于多维时间序列的检索中，并定义了适用于实数的相似性度量的 l c s s 模型【4 9 1 。 人体动作序列作为一种典型的高维时间序列，近年来成为高维时间序列研究的热 点问题。对于高维信息的处理，降维是一种常用的手段。刘丰等人1 5 0 】提出了基于动态 大连理工大学硕士学位论文 聚类算法的运动检索树，通过比较动作间的关键帧，从而达到降维目的。杨涛、庄越挺 等【7 3 】引入骨骼夹角作为运动特征，并以此确定候选关键帧。采用分层曲线简化算法精 选候选关键帧获得最终关键帧集合。 m e i n c a r dm i i l l e r 等【5 l 】首先将倒排表这种高效的字符索引数据结构应用于人体动 作序列的检索中，并提出了基于几何关系的人体动作符号化方法。文章中首先采用了 布尔逻辑的完全匹配方式作为相似性度量标准，但由于这种方式与欧式距离度量有着 类似的缺点，无法反应时间轴的伸缩，对噪音敏感。为了解决这一问题，文章中又定 义了基于模糊搜索模型( f u z z ys e a r c h ) 的匹配定义，这种匹配虽然在一定程度上解决了 时间轴局部上的弹性匹配，但其实现方法不仅大大增加了索引的字符数，并且在匹配 过程中引入了大量的集合运算，影响了算法的效率。然而面对存在时间轴上较大尺度 的弹性匹配，又不得不在局部匹配的外层采用d t w 算法，这使得匹配算法整体显得 不直观，且使得系统过于复杂。 1 3 本文工作及组织结构 本文首先介绍了时间序列的符号化方法，着重研究了高维时间序列的符号化方法， 并提出了一种基于多级k 均值聚类的高维时间序列的符号化方法。 文章重点介绍了高维时间序列的检索算法，并提出一种适合符号序列的检索算法。 算法采用倒排表数据结构，首先将倒排表查询的粗筛选算法转换成界限t 集合求交问 题，并提出一种基于堆的完全划分方法。算法效率相对比已有的基于堆的非完全划分 方法有了较大提高。 文章还对相似性算法进行了深入研究，最终采用最长公共子序列算法进行相似性度 量。提出一种基于最低匹配率的l i m i t e d l c s s 算法，该算法有较高的运算效率并保证 较好的检索准确性。 全文的组织结构如下： 第1 章绪论部分：主要介绍了数据挖掘的基本概念、任务和主要研究问题。指出研 究高维时间序列数据挖掘相关算法的重大意义和价值。并介绍了高维时间序列的符号化 与检索算法现状。 第2 章时间序列符号化：给出了序列符号化的含义和符号化的意义。介绍了序列符 号化算法的分类，和常用的几种符号化方法。提出了基于多级k 均值聚类算法的高维序 列符号化方法。 符号化高维时间序列的检索算法研究 第3 章时间序列相似性：说明时间序列相似性查询在实际应用中具有重要的意义。 并给出了时间序列的相似性概念和相似性查询的完备性定义。详细的介绍了常用的几种 时间序列的相似性算法，并深入分析各算法的优缺点。 第4 章基于倒排表结构的符号化时间序列检索模型：本文最核心章节，介绍了符号 时间序列的检索算法。详细介绍了粗筛选方法：基于堆的完全划分界限f 集合求交算法； 详细介绍了序列相似度算法：l i m i t e d l c s s 算法；并定义了高维符号的匹配方式。 第5 章符号化时间序列检索实验：以典型的高维时间序列人体动作库作为实验数据， 进行了符号化检索实验，证明本文算法能够保证了较高的效率及较好的检索准确性，并 给出了实验结果以及分析。 最后在结论部分，总结了本文的研究成果，指出下一步的研究方向。 大连理工大学硕士学位论文 2 时间序列的符号化 2 1 符号化的含义 符号化并不是对实数序列对应的系统特征做过多分析，而是直接依据实数序列的 数值特征对其作粗粒化处理，获得符号序列后，再做各种推理计算，以理解系统特征。 正所谓“先划分、后理解”。符号化首先按照一个统一的简单规则将系统划分成大量的 小颗粒，然后应用符号动力学方法或统计力学方法推理出系统的隐含“模式”。所谓“模 式”，就是对系统特征的理想划分【5 2 1 。符号化的目的在于简化系统，便于研究，对系 统的理解是在后续过程中推理得到的符号化的主要任务是用最小的符号集尽可能多 的保留系统的有效信息。 2 2 符号化的意义 针对时间序列的数据挖掘，通常要先将数据点密集的长时间序列转换成相对稀疏 的具有特定含义的符号序列，即转化为相对简单且易于分析处理的形式，从而可以进 一步应用诸如时态关联规则挖掘、序列模式发现等方法进行挖掘及知识发现。对于较 高维度的时间序列，采用合理的符号化方法也是一种有效的降维手段，同时也为后续 处理提供便利条件。一些学者认为将时间序列符号化是十分必要的，这样可以利用丰 富的文本处理算法和数据结构解决时间序列问题【5 3 】。如哈希算法，马尔科夫模型，后 缀树，决策树等方法目前仅适用于符号序列。随着符号化方法的研究日渐深入，以符 号化序列为基础的研究也逐步开展起来【5 4 1 。 2 3 常见的时间序列符号化方法 符号化方法主要分为两大类：1 1 直接根据序列的数值特点进行符号划分，不作任 何预处理，可称其为直接法；2 ) 首先对序列做适当变换，然后再划分。 过去，符号序列处理主要局限于研究混沌行为的符号动力学。随着计算机的发展， 数据流( 如多媒体、文本) 的处理大行其道，出现许多新的实用算法。符号序列模型很 多，如哈希表、马尔可夫模型、后缀树、决策树等。相对于神经网络之类的实数序列 模型，符号序列模型的结构简单明了，更容易被人理解。下面列举一些近年内较常用 的和本文实验中将采用到的符号化方法。 符号化高维时间序列的检索算法研究 2 3 1 静态法 假设有时间序列而( f = o ，l ，忉，它对应的符号序列为s i ( i = o ，1 ，) 。一种最 简单的静态符号化方法为： 岛= 怯。蒜 b ， 其中x 为一个设定的门限值，一般设为x i 的期望。静态法在应用中，符号集的大 小是可以随意调整的，例如： s f2 一1 ， 2 ， 1 ， 0 ， x l 耳一l 五 x i 置 ( 3 2 ) 五 五 x l x 此时符号集大小为，从这个角度来讲，静态法可以通过增大符号集来无限逼近 原实数序列。但实际使用时却没有必要，符号集太大就丧失了符号化处理的意义。最 常用的还是式( 3 1 ) 的方法，符号集为 o ，l ，大小为2 。 使用静态法时最大的不便之处在于如何确定一系列x 的值，通常的办法有两种： 等区间法和等概率法。等区间法就是让划分的各个区间大小相等，操作相对简单。而 等概率法是让落入各个区间的数据点数基本相等，即不同符号出现的概率大致相等， 这样做有利于保留序列的有效信息。等概率法的操作相对麻烦，在离线算法中，可以 通过反复调整区间大小来满足等概率要求；在线算法中，只能首先假定实数序列满足 某种概率分布，并估计相应的概率分布参数，通过查概率分布表的办法来确定区间划 分【5 3 。 s a x 方法【5 3 】就是一种典型的等概率算法。作者通过统计一些常见的时间序列数 一v 据集，发现它们基本满足正态分布规律n ( t ，仃2 ) 。并通过z ：2 二磐n ( o ，1 ) 将概率 a | 4 n 。 分布转换为标准正态分布。再对待符号化时间序列数据集进行分析，统计出其数学期 望和方差c l r 2 。并通过等概率的划分对实数区间分配字符。 为了更有效的降低时间序列的维度，s a x 方法采用p a a 分段线性近似的方法将 长度为的时间序列缩减成m 个线性段，每一段用原实数区间的平均值表示。如图 2 1 ，为采用p c a 算法将长度为n = 1 3 0 的时间序列用m = 8 个线性段来表示。 大连理工大学硕士学位论文 r 1 一_ ，l 一一 r 1 一i r 1 一f ， l 一 r l 一_ r 1 一 一 图21 采用p c a 算眭将长度为1 3 0 的时间序列用8 个线性段水表示 f i g2 1u s i n g p c ar e p r e s e n t a t i o n i n t h i sc a s eas e q u e n c eo f l c n g t h l 2 8 i sr e d u c e d t o8s e g m e n t s 图2 2 为一时问序列通过p c a 分段近似后，再绎s a x 进行符号化后的结果，其 q i 符号集的大小为3 。 c 、 c c c ) 百 上霄b 各， a 0 2 0 4 06 01 i12 0 图2 2 符号集大小为3 的s a x 符号化 f i g 2 2s a xs y m b o l i z a t i o n ，w i t ht h ea l p h a b e ts i z e3 2 32 动态法 假设有时问序列( 仁0 一i ，n ) ，它埘心的符号序列为- “= 0 “i ，) 。一种最 简单的动态符号化方法为： r 型 符号化高维时间序列的检索算法研究 果。 岛= 锰三焉p n 3 ， 图2 3 采用公式2 3 中描述的符号化方法，对一组一维时间序列进行符号化的结 lo0lo1o0 图2 3 采用动态法符号化时间序列 f i g 2 3d y n a m i cm e t h o ds y m b o l i z a t i o n 动态法也可以调整符号集大小，这需要不仅考虑序列的一阶差分，还考虑二阶差 分，甚至三阶、四阶，所对应的符号集大小依次为2 、4 、8 、1 6 。与静态法不同，动 态法中符号集不能为任意大小。由于高阶差分的物理意义不明显，很少被使用，一般 只考虑一阶和二阶。 s i2 3 ，五 t l ， 2 ，蕾 薯一i ， 1 ，x t _ l ， 0 ，而薯一l ， 而+ l + 而一l b o ，因此 其符号化结果均为“1 ”，也将被混淆。 、| 7 - ，o - - j - - 一 ， b ? 、 图2 5 采用p c a 方法无法区分序列彳和b f i g 2 5s e q u e n c eaa n dba r et h es a m eu n d e rp c am e t h o d 曩， 月 ， 6 ， b 兢一一 矿 岛专 1 图2 6 采用公式2 3 符号化方法无法区分序列么和曰 f i g 2 6s y m b o lo fs e q u e n c eaa n dba r et h es a m eu n d e re x p r e s s i o n s2 3 针对上面提到的这两点问题，本文尝试采用聚类的方法进行字符分配，设计一套 针对高维时间序列降维及符号化的通用方法。 2 4 1k 均值聚类 设k 是k 均值算法的输入参数，代表该算法在数据集上分割并计算后输出的聚类 的数量。数据集是有刀个模式组成的，在高维时间序列的聚类应用中，模式为高维时 符号化高维时间序列的检索算法研究 间序列上的若干规定长度的子段。在初始化时，根据输入参数k 随机性地从刀个模式 ，之，) 中找到k 个原型 嘭，嵫) 。因此形，= ，j 1 ，2 ，七) ，1 l ，2 ，甩 。 聚类的质量由式( 2 5 ) 的错误函数确定。 k e = y l - - , 卜1 2 ( 3 5 ) 一 o j i 、7 j = li t e c j k 均值的算法如下： 表2 2k 均值算法 t a b 2 2a l g o r i t h mo f k m e a n sc l u s t e r i n g a l g o r i t h m1k - m e a n s ( 尼，d a t a ) 输出：k 个簇，使平方误差最小。 任意选择k 个对象作为初始的簇中心 r e p e a t 根据簇中的对性的平均值，将每个对象重新赋给最类似的簇： 更新簇的平均值，即计算每个簇中对象的平均值： u n t i l 不在发生变化 2 4 2 符号分配 这里提到的符号化方法是针对整个高维时间序列的数据库的。对于长度为刀的时 间序列，可将其分成等长度的小段。这些等长度的小段为符号化的最小单位，即每 一小段对应字符化后的一个字符单元。因此首先将数据库中所有的时间序列分割成等 长度的小段，这些小段组成了待符号化的模式集合。 对于高维时间序列需要首先将其转换为高维向量。如果时间序列的维度为沙，长 度为，则转换为空间向量的维度为，。 符号分配过程采用m 级k 均值聚类，每一级聚类分为k 个聚类中心。序列在每一 级聚类上都属于某一原型形，i m ，k ，因此对于m 级的聚类过程每个符号隶属于m 个聚类集合，即符号在每一级聚类中均属于某一个聚类集合。且在每一级中，符号有 k 个可选标号。类似k 进制数，将序列在各级上的标号加权求和为其符号化结果。定 义序列在第m 级聚类上标号为s ，则有： k 一1 序列的符号为：y 墨k 。 大连理工大学硕士学位论文 如图2 7 所示，为对1 1 个时间序列小段 a ，b ，c ，d ，e ，f ，g ，h ，f ，j ，k ) 进行符号化。过 程采用2 级2 均值聚类。符号化结果见表2 3 。 0 哆，塑) ：哆竺) 图2 72 级2 均值聚类符号化 f i g 2 72 - l e v e l2 - m e 趾sc l u s t e r i n gs y m b o l i z a t i o n 表2 32 级2 均值聚类符号化结果 t a b 2 3r e s u l t so f 2 - l e v e l2 - m e a n sc l u s t e r i n gs y m b o l i z a t i o n 对某给定时间序列数据库进行符号化，需要人工给出聚类参数k ，然而如何决定 聚类级数m 的选取是一需要讨论的问题。考虑式子( 3 5 ) 描述了k 均值聚类的质量，即 聚类样本相对与聚类中心的平方误差。这里定义最大允许的平方误差，当聚类节 点的平方误差e k 。，时，节点停止继续通过聚类方式分裂成子节点，而是将节点中 的成员直接复制到其标号为0 的子节点中。这样做的目的是为了保证所有符号的聚类 级数均相同。 考虑图2 8 中情况，如果聚类集合 6 ，d ，巳f ，) 相对于其聚类中心r e 0 ，的平方误差 e z m a x ，则该节点集合停止继续通过2 均值聚类分裂，而是将该聚类集合 6 ，d ，e ，i ，歹) 直接复制到其标号为0 的子节点中，符号化结果见表2 4 。 符号化高维时间序列的检索算法研究 0 图2 8 聚类集合 6 ，d ，e ，f ， 节点成员直接复制到标号为0 的子节点中 f i g 2 8n o d em e m b e ro fc l u s t e r i n gs e t 6 ，d ，p ，f ，_ ， i sc o p yt oi t sc h i l dn o d ew h i c hm a r k e d0 表2 42 级2 均值聚类符号化结果 t a b 2 4r e s u l t so f 2 l e v e l2 - m e a n sc l u s t e r i n gs y m b o l i z a t i o n 通过调整的取值可以决定高维时间序列的符号集大小。通常取值越大符 号化粒度越大，符号化后序列维度越低，反之取值越小符号化粒度越小，符号化 后序列维度越高。其中两种极端情况：当= 佃时，字符集大小为l ；当= 0 时， 字符集大小为数据库分段后所有模式的个数。 因此通过选取不同的可以使该算法表现出不同的属性，因此选取合适的 值也是该符号化算法的重要方面。 2 4 3 。的选取 可度量的字符间距离是字符化算法中的重要方面，并默认相同符号间距离为0 。 在符号化前通常除了应规定符号化的粒度，还应该针对时间序列的匹配的特性规定子 串最大匹配距离。这里的距离指的是欧式距离，由于参与符号化的子串长度均较短， 因此可以忽略子串间的弹性匹配。假设期望字符集大小为输入的模式个数为且 大连理工大学硕士学位论文 字符内最大的距离为。由式( 3 5 ) 可得后缶。2 ，其中o k l 为经验参数，针 对不同的数据集k 的取值略有不同。 在实验中随机产生1 0 0 0 0 组长度为1 0 0 帧的时间序列，在实验中输入模式中每小 段的长度为1 0 帧。取不同的值统计产生的字符集大小( 见图2 9 ) ，可见通过调 整的取值可以控制字符集大小。 口 e ， z o o 口 c ， 气搬 图2 9 不同取值的产生的字符集大小 f i g 2 9a l p h a b e ts i z ew i t hd i f f e r e n tz m 2 4 4 多级k 均值聚类的符号化算法 多级k 均值聚类符号化方法的k 、为输出参数，其中k 决定了每级k 均值聚类 的聚类集合个数，是符号划分的终止条件，间接的决定了符号化算法的符号集大 小。算法的伪代码见表2 5 。 符号化高维时间序列的检索算法研究 表2 5 多级k 均值聚类符号化算法 t a b 2 5m u l t i l e v e lk - m e a n sc l u s t e r i n gs y m b o l i z a t i o n a l g o r i t h m3k - s y m b o l i c ( k ，d a t a ) 输出：符号化后的字符序列。 建立任务队列o ： 将d a t a 中所有序列按照等长度分段，并加入聚类集合s ； 将s 加入任务队列q 中； r e p e a t 取出q 首元素到s ，并计算s 的平方误差e 9 i fe t h e n 将s 进行k 均值聚类，并聚类结果各子集加入q 尾； 更新各聚类子集的符号e = e k + 置； e l s e 将s 直接压入q 尾； 更新各s 的符号e = c f k + s ； e n d i f u n t i l 所有的聚类集合都满足e ； 根据分级聚类树各节点聚类中心值，对d a t a 中时间序列进行符号： 一1 8 一 大连理工大学硕士学位论文 3 时间序列的相似性 时间序列相似性查询最早是由i b m 公司的a g r a w a l 等人1 9 9 3 年提出的【5 5 1 ，这一 问题被描述为：给定一个时间序列，从时间序列数据库中找出与之相似的序列。时间 序列相似性查询在实际应用中具有重要的意义。例如，发现价格波动相似的股票，分 析具有相同销售模式的商品等。同时，时问序列相似性查询也是时间序列挖掘的重要 工具，是解决聚类、分类、关联规则等其它数据挖掘任务的基础和关键问题。因此， 时间序列相似性查询问题受到研究者的普遍重视，成为当前时间序列挖掘中的热点问 题。 时间序列属于数据挖掘中的复杂类型数据，除具有一般复杂类型数据的特点外， 甚至在某些方面更加复杂。其复杂性主要表现在以下几个方面： ( 1 ) 数据规模大。时间序列的数据随着时间不断变化的，一般的时间序列数据 库数据规模都非常大，如股市数据、气象预报数据等，数据存储容量都在g b 以上； ( 2 ) 维数高。在时间序列挖掘中，通常需要比较两个时间序列的相似性，一般 的时间序列长度都在十几以上，特殊情况下甚至成百上千。例如，找出上月与i b m 公司股票价格变化模式相似的股票，即使按每日收盘价比较，序列的长度也在2 5 以 上： ( 3 ) 结构复杂。同其它复杂类型数据相比，时间序列结构复杂化特别突出。一 方面，时间序列来源于实际生活中的各个应用领域，不同的时间序列采样方法和测量 标准都不统一，而且具有波动频繁、噪声干扰以及非稳态等特点；另一方面，时间序 列的其数据是按时间有序的，使挖掘方法受到限制；特别是时间序列存在各种变形， 包括振幅平移、伸缩，时间轴伸缩、弯曲和线性漂移等，时间序列挖掘中必须考虑到 各种变形对挖掘结果的影响