（计算机软件与理论专业论文）时间序列与聚类挖掘相关技术研究.pdf

摘要 数据挖掘及其应用已经渗透到多个学科，并在人工智能与机器学习、数据库、 模式识别、生物信息学、神经计算等领域取得了丰硕的成果。同时，数据挖掘也 不仅是科学家的兴趣所在，更多地得到了政府、工业界的密切关注。通过引入数 据挖掘，可以大大提高生产力，取得社会的更大进步。世界上许多国家和地区的 政府及工业界都希望掌握数据挖掘技术，提升国家和企业的科技含量，并最终取 得领先的地位。 数据挖掘涉及的研究范围较为广泛，本文主要讨论了序列数据与聚类挖掘相 关技术，主要的主要的研究成果如下： ( 1 ) 给出小波变换在时间序列相似性查找中对距离上下界的一个严格估计， 同时说明传统的算法只是本文下界的一部分。根据本文给出的小波变换的下界， 相对于传统的算法，可以排除更多的不相似序列。根据给出的上界，可以直接判 断出两条序列是否相似，进一步减少需要验证的原始序列的个数。 ( 2 ) 在使用小波变换缩减维度解决高维时间序列查询时，传统的算法均使 用变换后小波序列的前k 个系数作为原始时间序列的一个近似估计。但是由于选 择前k 个系数不一定能很好地近似原始序列集合，可能对于中间某些系数的选 取，可以更好的给出原始序列集合的一个表示。因此给出相关定理，说明选择小 波系数集合的列平方和最大的k 列，可以更好近似原始序列集合。 ( 3 ) 对允许时间偏移的序列间相似性搜索，由于可以处理异常数据以及允 许不同长度的时间序列间进行匹配，因此应用日益广泛。但是大部分研究都是基 于两条时间序列间的全相似性匹配。给出了基于动态规划的子序列相似性搜索算 法，对于给定的查询序列，可以搜索到长序列中和给定的查询序列最为相似的一 段子序列。并进一步给出了两种优化算法，以减少子序列相似性搜索中距离矩阵 需要计算的项的个数。 ( 4 ) 时间序列的相似性搜索可以看成度量空间搜索的一种特例。提出一种 新的度量空间索引数据结构，简称为b u t r e e ，它是基于自底向上的分层聚类来构 造索引结构，而传统的度量空间数据结构大部分是基于自顶向下构造的方法。相 对于传统的构造方法，b u t r e e 可以在更小的索引半径内包含更多的对象，这样有 利于查询的筛选。给出了b u t r e e 的构造算法以及相应的范围查询算法。 ( 5 ) 数据概要被用来压缩大规模的数据库，以便进行后续的分层聚类分析。 b u t r e e 中每个节点也可以看成是一种数据概要。讨论了另一种常用的数据概要： 数据泡。详细研究了递增数据泡的质量度量标准( 数据概要指标) 。当更新数据库 时，我们指出哪些因素会影响数据概要指标的期望与均方差。基于这些因素，给 出一个对数据泡进行递增维护的一个动态算法。 ( 6 ) 讨论了系统级故障诊断中对测试序列的聚类分析算法。在基于聚类的 集团理论的基础上，利用贪婪算法中不同贪婪准则提出了四个针对系统及故障的 概率诊断算法。每种算法在较少的测试数情况下，均表现出较高的诊断正确率， 且时间复杂度不高。 关键词：数据挖掘、时间序列、相似性查找、小波变换、度量空间、聚类 中图分类号：t p 3 9 i i a b s t r a c t r e c e n t l y , d a t am i n i n ga n di t sa p p l i c a t i o n s h a v e a l r e a d y c o m ei n t om a n y d i s c i p l i n e s a n da c h i e v e d p l e n t i f u lf r u i t s i n d i v e r s i f i e df i e l d s ，i n c l u d i n ga r t i f i c i a l i n t e l l i g e n c ea n dm a c h i n el e a r n i n g ，d a t a b a s e ，p a t t e r nr e c o g n i t i o n ，b i o i n f o r m a t i c s ， n e u r a lc o m p u t i n g , a n ds oo n i tn o to n l ya p p e a l ss c i e n t i s t sb u ta l s oc a t c h e st h e a t t e n t i o nf r o mg o v e r n m e n t sa n di n d u s t r i e s t h eg o v e m m e n t s ，i n d u s t r i a lc o m m u n i t i e s ， a n da c a d e m i cf i e l d sa r es ok e e no nm a s t e r i n gd a t am i n i n gt e c h n i q u e st h a tt h e yh a v e i n v e s t e dal a r g ed e a lo fm o n e ya n de n e r g yo nt h ec o r r e s p o n d i n gr e s e a r c h t h e r e f o r e ， t h ep r o g r e s so fd a t am i n i n gw i l lp r o m o t et h ed e v e l o p m e n to fs c i e n c ea n ds o c i e t y d a t am i n i n gh a v em a n yr e s e a r c hf i e l d s i nt h i sd i s s e r t a t i o n ，w ef o c u so nt i m e s e r i e sa n dc l u s t e rt e c h n o l o g y t h em a i nw o r k sa n dc o n t r i b u t i o n so ft h ed i s s e r t a t i o na r e s u l n m a r i z e da sf o l l o w s ： ( 1 ) w a v e l e tt r a n s f o r m sa r eu s e da s ad i m e n s i o n a l i t yr e d u c t i o nt e c h n i q u et o p e r m i te f f i c i e n ts i m i l a r i t ys e a r c ho v e rh i 【g h - d i m e n s i o n a lt i m e s e r i e sd a t a t h i s d i s s e r t a t i o np r o p o s e st h et i g h tu p p e ra n dl o w e rb o u n d so nt h ee s t i m a t i o nd i s t a n c e u s i n gw a v e l e tt r a n s f o r m ，a n dw es h o wt h a tt h et r a d i t i o n a ld i s t a n c ee s t i m a t i o ni so n l y p a r t o fo u i l o w e rb o u n d a c c o r d i n gt ot h el o w e rb o u n d ，w ec a ne x c l u d em o r e d i s s i m i l a rt i m es e r i e st h a nt r a d i t i o n a lm e t h o d a n da c c o r d i n gt ot h eu p p e rb o u n d ，w e c a nd i r e c t l yj u d g ew h e t h e rt w ot i m es e r i e sa r es i m i l a r , a n df u r t h e rr e d u c et h en u m b e r o ft i m es e r i e st op r o c e s si no r i g i n a lt i m ed o m a i n t h ee x p e r i m e n t sh a v es h o w nt h a t u s i n gt h eu p p e ra n dl o w e rt i g h tb o u n d sc a ns i g n i f i c a n t l yi m p r o v e f i l t e re f f i c i e n c ya n d r e d u c er u n n i n gt i m et h a nt r a d i t i o n a lm e t h o d ( 2 ) f o rw a v e l e tt r a n s f o r mu s e d i nd i m e n s i o n a lr e d u c t i o n ，t h et r a d i t i o n a l a l g o r i t h m su s et h ef i r s tkw a v e l e tc o e f f i c i e n t sa sa na p p r o x i m a t i o no ft h eo r i g i n a lt i m e s e r i e sd a t as e t b u ti ti sp o s s i b l et h a tc h o o s i n gf i r s tkc o e f f i c i e n t si sn o to p t i m a l ，a n d p e r h a p sc h o o s i n go t h e rkc o e f f i c i e n t si sb e t t e r t h a nt h ef i r s tk an e wm e t h o di s p r o p o s e dt ob e t t e ra p p r o x i m a t i n gt h eo r i g i n a lt i m es e r i e sd a t as e t t h em a i ni d e ao f t h em e t h o dj st oc h o o s et h es a m ekc o l u m n so ft h ew a v e l e tt i m es e r i e sd a t as e tw h i c h h a v et h em a x i m u ms q u a r es u m t h ee x p e r i m e n t sh a v es h o w nt h a to u rm e t h o dc a n r e d u c et h er e l a t i v ee r r o rc o m p a r e dt ot r a d i t i o n a la l g o r i t h m s ( 3 ) s i m i l a r i t ys e a r c hf o rt i m es e r i e su n d e rd y n a m i ct i m es h i f t i n gi sp r e v a i l i n g b u tm o s tr e c e n tr e s e a r c hf o c u s e do nt h ef i l l ll e n g t hs i m i l a r i t ym a t c ho ft w ot i m es e r i e s i i l an e wb a s i cs u b s e q u e n c es i m i l a r i t ys e a r c ha l g o r i t h mb a s e do nd y n a m i cp r o g r a m m i n g i sp r o p o s e d f o rag i v e n q u e r yt i m es e r i e s ，t h ea l g o r i t h mc a r tf i n do u tt h em o s ts i m i l a r s u b s e q u e n c ei nal o n gt i m es e r i e s f u r t h e r m o r et w oi m p r o v e da l g o r i t h m sa r ea l s o g i v e n t h e yc a nr e d u c e t h ec o m p u t a t i o na m o u n to ft h ed i s t a n c em a t r i xf o r s u b s e q u e n c es i m i l a r i t ys e a r c h e x p e r i m e n t so nr e a la n ds y n t h e t i cd a t as e t ss h o wt h a t t h ei m p r o v e da l g o r i t h m sc a ns i g n i f i c a n t l yr e d u c et h ec o m p u t a t i o na m o u n ta n d r u n n i n gt i m ec o m p a r e dt ot h eb a s i ca l g o r i t h m ( 4 ) s i m i l a r i t ys e a r c hi nm a n yn e wd a t a b a s ea p p l i c a t i o n s c a ng e n e r a l l yb e r e f e r r e da s s i m i l a r i t ys e a r c hi nm e t r i cs p a c e t i m es e r i e sc a l l b es e e na so n e a p p l i c a t i o ni nm e t r i cs p a c e an e wi n d e xc o n s t r u c t i o na l g o r i t h mi sp r o p o s e df o r s i m i l a r i t ys e a r c hi nm e t r i cs p a c e t h en e wd a t as t r u c t u r e ，c a l l e db u t r e e ( b o t t o m u p t r e e ) ，i sb a s e do nc o n s t r u c t i n gt h ei n d e x t r e ef r o mb o t t o m - u p ，r a t h e rt h a nt h e t r a d i t i o n a lt o p d o w na p p r o a c h e s t h ec o n s t r u c t i o na l g o r i t h mo fb u t r e ea n dt h er a n g e s e a r c ha l g o r i t h mb a s e do ni ta r eg i v e n a n dt h eu p d a t et ob u - t r e ei sa l s od i s c u s s e d t h ee x p e r i m e n t ss h o wt h a tb u - - t r e ei sb e t t e rt h a ns a - - t r e ei ns e a r c he f f i c i e n c y , e s p e c i a l l yw h e nt h eo b j e c t sa r en o tu n i f o r md i s t r i b u t e do rt h eq u e r yh a sl o w s e l e c t i v i t y ( 5 ) i nm a n yr e a lw o r l da p p l i c a t i o n s ，w i t ht h ed a t a b a s e sf r e q u e n ti n s e r t i o n sa n d d e l e t i o n s ，t h ea b i l i t yo fad a t am i n i n gt e c h n i q u et od e t e c ta n dr e a c tq u i c k l yt od y n a m i c c h a n g e si nt h ed a t ad i s t r i b u t i o na n dc l u s t e r i n g o v e rt i m ei s h i g h l yd e s i r e d d a t a s u m m a r i z a t i o n s ( e g ，d a t ab u b b l e s ) h a v eb e e np r o p o s e dt oc o m p r e s sl a r g ed a t a b a s e s i n t or e p r e s e n t a t i v ep o i n t ss u i t a b l ef o rs u b s e q u e n th i e r a r c h i c a lc l u s t e ra n a l y s i s w e t h o r o u g h l yi n v e s t i g a t et h eq u a l i t ym e a s u r e ( d a t as u m m a r i z a t i o ni n d e x ) o fi n c r e m e n t a l d a t ab u b b l e s w h e nu p d a t i n gd a t a b a s e s ，w es h o ww h i c hf a c t o r sc o u l da f f e c tt h em e a n a n ds t a n d a r dd e v i a t i o no fd a t as u m m a r i z a t i o ni n d e xo rn o t b a s e d0 nt h e s es t a t e m e n t s ， af u l l yd y n a m i cs c h e m et om a i n t a i nd a t ab u b b l e si n c r e m e n t a l l yi sp r o p o s e d a n e x t e n s i v ee x p e r i m e n t a le v a l u a t i o nc o n f i r m so u rs t a t e m e n t sa n ds h o w st h a tt h ef u l l y d y n a m i ci n c r e m e n t a ld a t ab u b b l e sa r ee f f e c t i v ei np r e s e r v i n gt h eq u a l i t yo ft h ed a t a s u m m a r i z a t i o nf u rh i e r a r c h i c a lc l u s t e r i n g ( 6 ) p r o b a b i l i s t i cd i a g n o s i sa l g o r i t h mi sv e r yi m p o r t a n ti nt h es y s t e ml e v e lf a u l t d i a g n o s i sr e s e a r c h b a s e do nc l u s t e rt h e o r y , w ep r o p o s ef o u rp r o b a b i l i s t i ca l g o r i t h m s u s i n gg r e e d ya l g o r i t h mf o rs y s t e m l e v e lf a u l td i a g n o s i s b yc o m p u t e rs i m u l a t i o n ，i ti s s h o w nt h a tt h e s ed i a g n o s i sa l g o r i t h m sc a na c h i e v eah i g hp r o b a b i l i t yo fc o r r e c tu n d e r l o wt i m ec o m p l e x i t y t h eg r e e d ya l g o r i t h mo n eh a st h eb e s tp e r f o r m a n c ei nt h ef o u r l v p r o b a b i l i s t i ca l g o r i t h m s t h er e s u l t sa l s oi n d i c a t et h a to u ra l g o r i t h m sh a v eb e t t e r p e r f o r m a n c et h a nt h ec o m p e t ea l g o r i t h ma n dm a j o r i t ya l g o r i t h m ，w h i c ha r ec l a s s i c p r o b a b i l i s t i ca l g o r i t h m si ns y s t e ml e v e lf a u l td i a g n o s i s k e y w o r d s ：d a t am i n i n g ，t i m es e r i e s ，s i m i l a r i t ys e a r c h ，w a v e l e tt r a n s f o r m ，m e t r i c s p a c e ，c l u s t e r i n g c l c ：t p 3 9 v 第一章绪论 1 1 研究背景 第一章绪论 数据采集、存储与管理技术的进步与企业界迫切需求的结合，使得在过去的 二十年中数据库技术得到了广泛的应用。现今众多商业数据库的容量已经达到了 海量的水平，很多数据库中已经存储了上万亿字节的数据。如何在这些海量数据 中发现隐藏的知识和规律，已经成为计算机界尤其是数据库领域研究者的一个重 要研究方向，我们称之为数据挖掘。 “需要是发明之母”，数据挖掘领域的先驱j i a w e ih a r t 在他的经典著作 h k 0 0 1 开篇中提到。“发明”和追求真知是人类特有的本质，无论在经济、金融等社会 学科领域，或是在计算机、数学等自然科学领域，处处闪耀着人类追求真理追求 知识的过程。很难想象当人类失去好奇的本能和发现的眼睛，世界将会变成何样。 “需要”则是促进社会与人类进步的源泉，当我们有了需要，我们就有了前进的 动力。 自2 0 世纪6 0 年代以来，数据库和信息技术已经系从原始的文件处理演化到 复杂而功能强大的数据库系统。尤其在e ec o d d 成功地提出了关系模型后，为 数据库的大发展奠定了坚实的理论基础。几十年过去了，随着计算机硬件存储能 力和软件环境的提高，数据膨胀的时代已经到来。数据的极大丰富带来了对强有 力的数据分析工具的需求，大量的数据被描述为“数据丰富，知识匮乏”。当我 们具有了先进的硬件存储设备和运算设备，同时也具有存储海量数据的数据库系 统，但如果系统没有分析数据的工具和能力，那么这对我们来说，也只是一个“数 据坟墓”。 近十几年来，数据挖掘已经引起了信息产业界的极大关注，其主要原因就是 存在大量数据，可以广泛使用，并且迫切需要将这些数据转换成有用的信息和知 识。获取的知识可以迅速地反馈到应用领域，并及时指导管理者，赋予了他们更 多的领域“智能”。目前数据挖掘的部分成果已经被广泛地应用于商务管理、生 产控制、市场分析、工程设计、科学探索和国家安全等领域。同时，作为一个新 兴的交叉领域，数据挖掘还受到了人工智能与机器学习、数据库、统计学、生物 信息学、社会学等多学科的关注，涉及从基础的算法理论到具体的实际应用这样 广泛的范围。任何人都不可能对所有的这些方面进行深入的研究，这也使得数据 挖掘的研究存在着不同的角度。 数据挖掘与知识发现这个概念在1 9 8 9 年8 月举行的第1 1 届国际联合人工智 第一章绪论 能学术会议上被首次提出，自此引发了数据挖掘研究的新篇章。上世纪9 0 年代 早期，大部分数据挖掘研究者来自于数据库领域，他们主要是为数据库系统建立 有效的数据分析工具。随后，更多领域的专家加入数据挖掘圈中，考虑问题的角 度也被极大的拓宽，提出了包括关联规则、聚类、分类、例外等等数据挖掘方向， 这些方向的建立也更好地推动了数据挖掘的前进。 数据挖掘也称为数据库中的知识发现( 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 ， k d d ) ，即从大规模的数据中抽取非平凡的、隐含的、未知的、有潜在使用价值 的信息的过程 f p s + 9 6 。作为- - f 3 交叉学科，数据挖掘集成了许多学科中成熟的 工具和技术，包括数据库技术、统计学、机器学习、模式识别、人工智能等。然 而与传统的知识发现技术( 如统计方法、机器学习、神经网络计算等) 不同，数 据挖掘技术一般与数据库的相关技术紧密结合，更加侧重于对海量数据的多种模 式的自动发现，因此具有更广泛的应用前景。 数据挖掘的一般过程可以分为三个阶段：包括数据准备、模式发现与结果表 达 h m s 0 1 。数据准备阶段用于为后续的模式发现提供高质量的输入数据，主要 包括数据的选择、净化与集成三个子任务。模式发现是数据挖掘过程的核心阶段， 该阶段运用各种数据挖掘算法，通过对历史数据的分析，得到供决策使用的各种 模式与规则，这是数据挖掘研究中最核心、难度最大的领域。结果表达阶段关注 于规则和模式的可视化表示，即如何将挖掘出来的模式与规则以一种直观、容易 理解的方式呈现给用户。 由于数据挖掘涉及的领域相当广泛，因此本章主要讨论和本文相关的一些研 究概况，主要包括：1 、时间序列挖掘中的相关研究：2 、聚类算法的相关研究。 在后续章节，将根据实际的问题域进一步介绍相关研究情况。 1 2 时间序列相关研究 时间序列上的数据挖掘研究自从2 0 世纪9 0 年代以来发展迅速，时间序列 来源于实际生活中的各个应用领域，采样方法和测量标准都不一致，具有短期波 动频繁、大量噪声干扰以及非稳态的特点，使得相似性查询变得非常困难。相似 性度量是时间序列的相似性查询的基础，时间序列的索引技术则可以提高相似性 查询的效率。 数据挖掘作为一种新兴的知识发现方法，近年来在时间序列数据分析方面也 得到了广泛的应用，许多文献讨论了如何将数据挖掘的各种方法运用于时间序列 。 数据的挖掘，f k k 0 2 对此进行了详细的介绍。在这一节，我们将介绍时间序列 挖掘的主要研究领域，包括关联与序列分析、聚类分析、异常检测、分割以及相 似性查找等。 第一章绪论 ( 1 ) 关联分析与序列分析 关联分析与序列分析的目的都是发现大量数据中项集之间的各种相关联系， 不同的是，关联分析一般用于发现同一时间段内的各种联系，而序列分析则用于 发现在时间上具有先后关系的项集间的各种联系 h k 0 1 1 。关联分析与序列分析 的典型应用包括购物篮分析、网络入侵检测等。 由r a g r a w a l 等人提出的a p r i o r i 算法与a p r i o r i t i d 算法是最早的关联的规 则发现算法 a i s 9 3 ，由于这两个算法需要频繁扫描数据库并且生成大量的候选 项集，因而效率较低。许多文献在此基础上进行了优化与改进，包括划分 【s o n 9 5 、采样 t o i 9 6 、哈希 p c y 9 5 、事务压缩 a s 9 4 、动态项集计数 b m u 9 7 】 以及f p g r o w t h 算法 h p y 0 0 等。 序列规则的发现算法最早也是由r a g r a w a l 等人提出的 a s 9 4 ，在 a s 9 4 】 中，r a g r a w a l 将关联分析中的a p 哟r i 算法思想用于序列规则的挖掘，提出了 a p r i o r i a l l 、a p f i o f i s o m e 、d y n a m i c s o m e 三种算法。其他主要的序列规则发现算 法还包括g s p 算法 s a 9 5 和p r e f i x s p a n 算法 p h m + 0 1 等。 与此同时，时间序列中的关联与序列规则挖掘也受到了普遍的关注。【m t v 9 5 1 将关联规则与序列规则发现算法的思想用于分析事件( e v e n t ) 序列，从事件序 列中发现频繁情节( e p i s o d e ) 。f d l m + 9 8 使用聚类的方法首先对时间序列符号 化，在此基础上采用序列模式的挖掘算法发现符号中的规则。o c 9 6 1 提出了从多 个同步数据流中发现数值型关联规则的算法。z s h 0 3 提出了一种基于互关联后 继树模型的时间序列关联规则发现算法。 ( 2 ) 相似性查找 相似性查找是时间序列挖掘的一个最重要研究方向。对于给定的目标序列q 和相似性度量函数d s ( q ，c ) ，相似性查找指的是在时间序列数据库t d b = q - ， q 2 ，么) 中，寻找与q 最相似的那个序列吼【k k 0 2 。 时间序列相似性查找的主要研究内容包括以下几个方面： ( a ) 由于时问序列一般都跨越较长的时间段，甚至可能具有无限长度，因 此这类数据都表现出高维甚至是超高维的特征，由于“维灾”的影响，许多原来 适用于低维数据的相似性查找方法并不能直接用于时间序列这种高维结构 w s b 9 8 ，b g r + 9 9 。因此大多数相似性查找的方法都是先采用某种方法对序列进 行降维( 也称为维约简) ，在此基础上再进行相似性度量的计算。常见的时间序 列降维方法包括离散傅里叶变换( d f t ) 【a f s 9 3 1 、离散小波变换( d w t ) 【c f 9 9 ， z h s 0 4 】以及逐段线性描述( p i e c e w i s el i n e a rp r e s e n t a t i o n ，p l r ) 【k c h 0 1 等。 ( b ) 即便使用了降维方法对时间序列进行降维，得到的仍然可能是一个多 维结构，为了有效地对这些多维结构进行查找，需要使用相关的空间索引结构以 第一章绪论 提高查找速度，常见的空间索引结构包括r t r e e g u t 8 4 、r + t r e e b k s + 9 0 、 m t r e e c p z 9 7 、a - t r e e s y u + 0 0 等。 ( c ) 对于时间序列数据，如何判断它们之间是否相似是一个重要的问题， 常用的相似性度量包括厶范式( 当p = 2 时即为欧氏距离) 【a f s 9 3 ，c f 9 9 和动态 时间弯曲距离d t w b c 9 4 等。 ( 3 ) 聚类分析 聚类分析的目的是把整个目标数据分成多个不同的类( d u s t e r ) ，使得每个 类中的数据尽可能相似，而不同类中的数据具有明显的差别。聚类分析的典型应 用包括空间数据处理、银行信用卡客户分析等。 常见的聚类算法主要包括划分方法和层次方法。基于划分的聚类随机选定k 个对象为初始类中心，计算每个对象到类中心的距离，并将其分配到距离最近的 类中，然后重新计算新的类中心，如此反复直到对象不再发生变化。典型的划分 聚类算法包括p a m 算法 r , r 9 0 和c _ a r a n s 算法 n h 9 4 等。 层次聚类方法将数据对象组织成一棵树，根据层次构造是自顶向下还是自底 向上，该方法可以分成分裂和凝聚两种。分裂法将所有对象看成属于同一类，逐 步向下分裂成更多更小的类，直到每个对象都自成一类或满足某个结束条件为 止。凝聚法则将每个对象都看成独立的类，由下向上合并数据对象，直到满足某 一结束条件或所有对象已经合并到一个类中。典型的层次聚类算法包括b i r c h 算法 z r l 9 6 、c u r e 算法 g r s 9 8 和c h a m e l e o n 算法 k h k 9 9 等。 其他的聚类方法还包括基于密度的方法 e k s + 9 6 ，a b k + 9 9 、基于网格的方 法 w y m 9 7 1 和基于密度与网格的混合方法 a g g + 9 8 等。 时间序列数据的聚类分析近年来也得到了广泛的研究。f a f s 9 3 1 使用离散傅 里叶变换( d f t ) 将原始时间序列转换为少数几个离散傅里叶系数，从而对序列 进行降维，在此基础上使用欧氏距离进行序列的聚类研究。与此类似，【s s 9 9 】 和g a l 0 0 分别研究了基于离散小波变换( d w t ) 和主成分分析( p c a ) 的时间 序列维降维及聚类，k p 9 8 贝t j 使用逐段线性分割( 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 ， p l s ) 的方法，将时间序列分段转换为带权重的五元向量，在此基础上进行聚类。 f s m y 9 7 ，l b 0 0 研究了基于隐式马尔可夫模型( h i d d e nm a k o vm o d e l ，h m m ) 的时间序列聚类，由于这些方法在聚类过程中均使用k - m e a i i s 算法，在迭代的 过程中将每个时间序列都明确地划分到某一个h m m 中，这样当实际序列并不是 完全明确可分时，算法的准确性就受到影响。【a s k + 0 3 改进了【s m y 9 7 ，l b 0 0 】的 这一缺陷，结合h m m 和期望最大( e m ) 方法，使得迭代的过程中每个序列以 一定的概率属于多个h m m ，而将类的划分留到最后，从而提高了聚类的准确性。 针对时间序列中经常存在异常数据的情况，f b j z 0 3 提出将原始序列根据中 4 第一章绪论 位数转化为二元时间序列，在此基础上进行聚类，从而减少异常数据的影响。对 多个模型和距离度量的试验表明，当序列中存在异常数据时，该方法能够有效地 提高聚类的准确性。 ( 4 ) 异常检测 异常检测是数据挖掘中的一个重要方面，用来发现在数据集中显著不同于其 它大多数数据的对象。异常检测主要用于信用卡欺诈检测、电子商务中犯罪活动 的发现以及气象预报等领域。 根据 h a w 8 0 的定义，异常是指在数据集中明显与众不同的数据，使人怀疑 这些数据是由不同的机制产生的，而非随机偏差。异常检测问题最先在统计学领 域里得到研究 b l 9 4 ，这些方法通常将数据用某个假定的统计分布进行建模，然 后根据假定的模型和数据点的实际分布来确定异常。由于大多数情况下无法准确 地确定实际数据的分布形式，并且现实数据往往并不一定符合某些理想的数学分 布，因此统计异常检测方法具有相当大的局限性 h k 0 1 1 。在数据挖掘领域常用 的异常检测算法包括基于深度的方法 r r 9 6 、基于距离的方法 k n 9 8 , r r s 0 0 以 及基于密度的方法 b k n + 0 0 i 等。 在时间序列挖掘领域， a a r 9 6 1 提出了序列异常( s e q u e n t i a le x c e p t i o n ) 的 概念，即当扫描数据序列时，如果某个数据点明显不同于其前面的序列，这样的 点就被认为是异常数据。由于序列异常在概念上存在一定的缺陷，因此算法容易 遗漏真正的异常数据。 j k m 9 9 1 使用直方图( h i s t o g r a m ) 方法来发现异常数据， 如果将某个数据从序列中移去，单独用一个桶存放，能够减少整体直方图的误差， 则该数据被认为是异常。y h c + 0 4 提出了一种两阶段支持向量回归( s u p p o r t v e c t o rr e g r e s s i o n ，s v r ) 的训练算法，用于检测序列中的异常，以避免异常数 据对预测精度产生影响。 对异常检测研究研究算法大致可以分为五类：基于分布的方法 h a w 8 0 ， b l 9 4 ；基于深度的方法 j k n 9 8 ，r r 9 6 ；基于聚类的方法 j t s 0 1 ，y s z 0 2 ，h s d 0 3 ； 基于距离的方法 k n 9 8 ，r r s 0 0 和基于密度的方法 b k n + 0 0 ，j t h 0 1 ，p k g + 0 3 1 。 基于分布和基于深度的方法主要来源于统计学领域。基于分布的方法假设数据集 的分布己知，根据分布对数据集中的每个对象进行“不一致”测试，如果该对象 与分布不符合，那么就认为是异常。实际上，实际数据集的分布通常是未知的， 往往也很难通过估计得到；基于深度的方法只适合于二维或三维数据，对于四维 以上的数据集就显得效率低下；基于聚类的方法间接或者直接利用已有的聚类算 法，但是聚类算法对于检测异常来说显得不是那么高效，因为它一般不对异常检 测作特别优化，而且这类算法通常没有一个形式化的易于被用户接受的异常定 义。k n o r r 等 k n 9 8 第一次提出了基于距离的方法，他们把至少存在p 个对象与 第一章绪论 之距离大于某个距离阈值d 的对象定义为d b ( p ，异常。随后，r a m a s w a m y 等 人 r r s 0 0 将距离的概念推广到矿近邻距离，所有对象按照胪近邻距离从大到 小排序，将妒近邻距离最大的前h 个对象视为异常。然而正如b r e u n i g 等人 b k n + 0 0 所指出的，基于距离的方法在处理内部密度差异明显的数据集时遇到 了麻烦：或者将密度稀疏的区域都判断为异常，或者无法发现某些异常。他们认 为异常不应该只是一个简单的二值属性，提出了基于密度的异常检测算法，定义 了对象的矽距离领域，根据对象的局部领域密度计算它的局部异常因子( l o c a l o u t l i e rf a c t o r , l o f ) ，用l o f 来描述一个对象的异常程度。l o f 值越高，对象 是异常的可能性就越大。通常需要指定一个异常阈值，所有l o f 值大于该异常 阈值的对象都被视为异常。为了避免指定异常阈值参数，【j k h 0 1 】将所有对象按 照l o f 值从大到小排序，将前行个对象视为异常。对于时间序列，它的一个重 要特点是具有时间属性，序列值之间存在严格的顺序，是一种有序的数据。 根据按照异常的表现形式不同，时间序列的异常通常可以分为以下三种： ( a ) 序列异常：序列异常是指在时间序列数据集中与其它时间序列显著不 同的、来源于不同产生机制的时间序列。 ( b ) 点异常：点异常是指在一条时间序列上与其它序列点存在显著差异的、 具有异常特征的序列点。 ( c ) 模式异常：模式异常是在一条时间序列上与其它模式存在显著差异的、 具有异常行为的模式。 ( 5 ) 分割 时间序列的分割是指对长度为n 的时间序列q ，将其分为k 段( 缸嘲) ，对 各段分别使用某种模型进行描述并记为q ，使得q 与q 非常接近 k k 0 2 。图 1 - 1 给出了使用线性模型对时间序列进行逐段描述的例子 k k 0 2 。 图1 - 1 使用线性模型逐段描述时间序列 第一章绪论 对时间序列进行分割与逐段描述的主要原因包括： ( a ) 时间序列往往跨越较长的时间段，某些时间序列在理论上甚至具有无 限长度，在这期间数据的许多特征都可能发生变化，对这样的数据用一个单一的 模型来描述是不合适的； ( b ) 时间序列在演化的过程中，由于受到各种因素的影响，往往具有复杂 的局部特征，在图形上则表现为局部曲折不平。使用一些简单的模型( 如常用的 线性模型等) 对数据进行逐段描述，丢弃一些细节的变化信息，对于某些挖掘任 务来说更合适。 最常用的时间序列分割方法是使用线性模型对序列进行分割与逐段描述，称 为逐段线性描述，【k c h 0 1 1 对这类分割方法进行了详细的介绍。此外，p s 0 1 提 出了一种基于隐马尔可夫的联机时间序列分割，w w 0 4 则研究了基于概率密度 函数的时间序列分割。 根据分段误差控制的方法不同，一般可以将算法分为以下三种： ( a ) 滑动窗1 1 ( s l i d i n gw i n d o w ) ：从时间序列的第一个点开始一个新的分段， 持续向后增长直到该分段与时间序列的拟合误差超出了某个指定阈值，结束该分 段，然后以下一个序列点作为新分段的开始，不断重复上述过程直到时间序列末 端 k j m 9 5 ，v w