（计算机软件与理论专业论文）相似时序检索技术研究.pdf

中国科学技术大学博士论文 摘要 相似时序检索技术在数据挖掘、天气预报、股票走势的分析和预测等方面有 着广阔的应用前景。常见的相似时序检索技术包括：时域法、频域法、段化法和 波形描述法等。扩展时序数据的距离，是种对原始距离的扩展，前人提出的扩 展相似时序的检索技术有进一步改进的空间。本文试图解决扩展相似时序检索的 若干问题：1 解决时序各窗1 3 数据增量式d f t ( d i s c r e t ef o u r i e r t r a n s f o r m ) 的问题， 从而提高相似时序检索技术预处理的效率；2 给出新的基于频域的相似时序检索 算法，该算法能够给出扩展距离满足相似条件的时序，而且由于其在降维后的频 域空间上计算，效率较高，综合代价较低；3 给出一种快速的离散属性序列检索 算法；4 结合相似时序检索技术与c b r ( c a s e - b a s e dr e a s o n i n g ) 技术，构建一种有 效的时序数据预测系统。 在相似时序检索技术中，进行维度简约和在降维之后的空间上进行相似时序 的搜索是常见的处理办法。在多维空间上进行扩展相似时序的搜索，需要对长时 序的各个窗1 3 进行维度简约，例如d f t ，常规技术比较耗时，有没有更简单更 快速的算法? 例如：增量式的d f t ；另外对于加权时序数据的维度简约，是否 也存在着增量式的变换技术? 是本文的一个出发点。前人给出的搜索扩展相似时 序的技术，通用性不好，效率有待提高。是否存在更简单形式的相似序列的搜索 算法，最好是降维空间上的解析形式，是本文的另外一个出发点。对于离散属性 序列，有没有快速的相似检索算法。如何将相似时序检索技术和基于范例的推理 的技术结合起来，一方面验证相似时序检索技术的有效性，另外一方面，给出一 种新的时序数据的预测技术，是本文提出的基于范例推理的预测技术的出发点。 本文在综述时序数据挖掘、相似时序检索技术以及基于范例推理技术的相关 工作的基础上，按照下面的结构展开： 时序数据的伸缩和漂移不变距离是对原始时序距离的一个扩展，该扩展定义 能够保持时序数据在线性变换之后的相似性，能够克服传感器不同零点和增益带 来的相似性变化的问题。本文给出并且证明了一种在频域上快速计算时序数据扩 展距离的解析算法，该算法能够利用时序数据的少量( 2 - - 5 ) d f t 参数计算时 序的扩展距离，即有在降维后的频域空间上计算时序距离的快速性的特点，又能 中国科学技术大学博士论文 够适应扩展距离的定义。实验表明该算法简单快速，综合代价较低。 给定一个待查序列，在长时序中寻找出与它相似的若干子序列是相似时序检 索的常见任务。对长序列的每一个子序列窗口进行d f t ，将其映射到频域从而 进行维度简约，是预处理中不可缺少的一个步骤。本文给出并证明了一个增量式 的d f t 算法，该算法能够增量式地计算出各个子序列窗口的d f t 参数，从而能 够大大提高预处理的效率。该算法还可以迸一步扩展，能够为线性加权时序数据 进行增量d f t 计算。实验结果表明，这种算法比常规处理办法效率提高很多。 本文还给出了一种计算离散序列距离的快速算法，该算法的一个主要思想是 通过对离散属性值进行人工赋值，将其变换到数值空间，从而可以利用d f t 、 小波等维度简约技术，结合多维索引技术能够大大提高相似离散属性序列检索的 效率。 最后本文结合相似时序检索技术和基于范例推理的技术，进行相似气象数据 的检索和适航气象类型的预测。该技术的主要思想是：利用相似时序检索技术从 历史气象数据库中检索出和当前气象数据类似的若干个气象序列，利用c b r 技 术进行适航气象类型的预测。实验表明，该技术预测精度令人满意。 本文的创新之处在于： 1 ) 提出了一种新的时序数据和加权时序数据的增量d f t 算法。对一个长 时序中各个子序列窗口进行d f t ，是进行相似子序列搜索的不可缺少的 预处理步骤，本文给出并且证明了时序数据和线性加权时序数据的增量 d f t 算法，实验表明该算法能够大大提高d f t 的效率，使得原来的时 间复杂度为o ( n x m ) 的工作，变成了o ( n x f c ) ； 2 ) 给出并且证明了在频域上计算时序扩展距离的解析算法。实验表明该算 法能够提高相似时序的检索效率，既有代价较小的优点，又能够解决时 序数据在y 轴上的漂移和伸缩后仍然保留相似性的问题，实验结果表 明，该算法简洁快速，综合代价较小： 3 1 给出了一个快速检索相似离散属性序列的算法。该算法通过为每一个离 散属性值进行人工赋值，将其映射到数值空间，从而利用d f t 或 d w t ( d i s e r e t e w a v e l e tt r a n s f o r m ) 术进行维度简约，并可以结合多维索引 技术，能够大大提高相似离散属性序列的检索效率。 中国科学技术大学博士论文v “ a b s t r a c t t h et e c h n o l o g yo fs e a r c h i n gs i m i l a rs e q u e n c ei s w i d e l y u s e di nd a t a m i n i n g ，w e a t h e rf o r e c a s t i n ga n d s t o c kt r e n dp r e d i c a t i o n t h ef r e q u e n t l yu s e d m e t h o d sa r e ：t i m ed o m a i nm e t h o d ，f r e q u e n c yd o m a i nm e t h o d ，s e g m e n t a t i o n m e t h o da n dw a v e d e s c r i p t i o nm e t h o d t h i sd i s s e r t a t i o nt r i e st os o l v eas e r i e s o f p r o b l e m s i n s e a r c h i n g s i m i l a r s e q u e n c e ：1 s o l v e s t h e p r o b l e m o f i n c r e m e n t a ld f t ( d i s c r e t ef o u r i e rt r a n s f o r m ) o fs u bs e q u e n c e si na l o n g s e q u e n c e ，a n ds oi m p r o v e st h ee f f i c i e n c yo fp r e p r o c e s s ；2 g i v e san e w f r e q u e n c yb a s e da l g o r i t h mo fs e a r c h i n gs i m i l a rs e q u e n c e t h i sa l g o r i t h mi s v e r ye f f e c t i v eb e c a u s e i tc a l c u l a t e st h ee x t e n dd i s t a n c eo nr e d u c e df r e q u e n c y d o m a i n t h es y n t h e s i z ec o s to ft h ea l g o r i t h mi sv e r yl o w 3g i v et h e t e c h n o l o g y o f s e a r c h i n g s i m i l a rd i s c r e t ea t t r i b u t e s e q u e n c e w i t h h i g he f f i c i e n c y ；4 c o n s t r u c t sa ne f f e c t i v ed a t as e r i e s f o r e c a s t i n gs y s t e mb yc o m b i n i n g t h e t e c h n o l o g yo fs e a r c h i n gs i m i l a rs e q u e n c e a n dc b r ( c a s e b a s e dr e a s o n i n g ) i ns e a r c h i n gs i m i l a rs e q u e n c e d i m e n s i o nr e d u c i n ga n ds e a r c h i n gs i m i l a r s e q u e n c e si n t h er e d u c e ds p a c ea r eo f t e nu s e dt e c h n o l o g y i ns e a r c h i n g e x t e n ds i m i l a rs e q u e n c ei nm u l t i d i m e n s i o ns p a c e ，i ti sn e e d e dt od f tt h e e a c hw i n d o w so fl o n gs e q u e n c e t h i si sat i m ec o n s u m i n gw o r k i st h e r ea n y f a s t e ra n ds i m p l e ra l g o r i t h m ? f o re x a m p l e ：i n c r e m e n t a ld f tt e c h n o l o g y i n a d d i t i o n ，i st h e r ea n yi n c r e m e n t a ld f tt e c h n o l o g yo fl i n e a rw e i g h t e dd a t a s e q u e n c e ? t h i si s as t a r to ft h i sd i s s e r t a t i o n e x t e n d e dd i s t a n c eb e t w e e n d a t as e q u e n c ei se x t e n do fo r i g i n a ld i s t a n c et h ep r e v i o u st e c h n o l o g yo f s e a r c h i n ge x t e n d e ds i m i l a rs e q u e n c e a r ei nl o w e f f i c i e n c ya n d n o t v e r yg e n e r a l i st h e r ea n ys i m p l ea l g o r i t h mo ff i n d i n gt h er e s o l u t i o ni nr e d u c e ds p a c e ? t h i s i sa n o t h e rs t a r to ft h i sd i s s e r t a t i o n h o wt oc o n s t r u c tan e w p r e d i c t i o ns y s t e m b yc o m b i n gt h et e c h n o l o g yo fs e a r c h i n gs i m i l a rs e q u e n c ea n dc a s e b a s e d r e a s o n i n g ，t h i si st h e s t a r to ft h ec b rb a s e dp r e d i c t i o nt e c h n o l o g yp r e s e n t e d b yt h i sd i s s e r t a t i o n a f t e rs u m m a r i z i n gt h ew o r ko fd a t am i n i n g ，s e a r c h i n gs i m i l a rs e q u e n c e 中国科学技术大学博士论文v i i i a n dc a s e b a s e d r e a s o n i n g ，t h i sd i s s e r t a t i o n i sw r i t t e ni nt h e f o l l o w i n g s t r u c t u r e ： t h ee x t e n dd i s t a n c eb e t w e e nd a t as e q u e n c ei se m e n d e df r o mo r i g i n a l d i s t a n c ew h i c hi sn o tc h a n g eb ys c a l i n ga n ds h i f t i n g t h i sd e f i n i t i o nc a nh o l d t h e s i m i l a r i t yb e t w e e ns e q u e n c e sa f t e rl i n e a rt r a n s f o r m a t i o na n dc a ns o l v et h e p r o b l e mo fd i f f e r e n ts e n s o r sw i t hd i f f e r e n tm a g n i f i c a t i o n sa n dz e r o s t h i s d i s s er t a t i o ng i v e sa n d p r o v e saf a s tr e s o l u t i o na l g o r i t h mw h i c hc a l c u l a t i n gt h e d i s t a n c eo nt h er e d u c e df r e q u e n c yd o m a i n a n dt h i sa l g o r i t h mc a l c u l a t e st h e d i s t a n c e u s i n go n l y af e w ( 2 - 5 ) d f tp a r a m e t e r s s ot h ea l g o r i t h mi sf a s t b e c a u s ei ti sc a l c u l a t e do nf r e q u e n c yd o m a i na n dt h ea l g o r i t h mi sa d a p t i v et o t h ee x t e n dd i s t a n c eo fs e q u e n c e t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h i s a l g o r i t h mi sf a s ta n ds i m p l e ，w i t hl o ws y n t h e s i z ec o s t g i v i n gas u b s e q u e n c e s e a r c h i n gt h em o s t s i m i l a rs u b s e q u e n c ei nal o n g s e q u e n c ei sa no r d i n a r yt a s ki nt i m es e r i e ss i m i l a r i t ya n a l y s i s d o i n gd f t o n e a c hw i n d o w so fal o n gs e q u e n c e m a p p i n gt h e mt of r e q u e n c yd o m a i na n d r e d u c i n g t h ed i m e n s i o na r e n e c e s s a r ys t e p s i n p r e p r o c e s s i n g t h i s d i s s e r t a t i o ng i v e sa n dp r o v e sa ni n c r e m e n t a ld f ta l g o r i t h mo nt i m es e r i e s ， a n dt h i s a l g o r i t h mc a nc a l c u l a t et h ed f tp a r a m e t e r si n c r e m e n t a l l y ，a n ds o i m p r o v e st h ee f f i c i e n c y a n dt h i sa l g o r i t h mc a nb ee m e n d e dt oc a l c u l a t et h e p a r a m e t e r so fl i n e a rw e i g h t e ds e q u e n c e t h i sd i s s e r t a t i o na l s og i v e saf a s ta l g o r i t h mt h a tc a nc a l c u l a t et h ed i s t a n c e b e t w e e nd i s c r e t ea t t r i b u t e s s e q u e n c e s t h e m a i ni d e ai s ：f i r s ta r t i f i c i a i e v a l u a t i n gt h e d i s c r e t e a t t r i b u t e s ，m a p p i n gt h e mt o n u m e r i c a ls p a c e ，t h e n u s i n g t h ed i m e n s i o n r e d u c i n gt e c h n o l o g y l i k e d f t , d v 、几a n du s i n g m u l t i d i m e n s i o n a l i n d e x ，a t l a s t s e a r c h i n g t h es i m i l a r s e q u e n c e i nt h e m u l t i d i m e n s i o n a li n d e x t h i st e c h n o l o g yi sv e r ye f f e c t i v e a tt h ee n do ft h i sd i s s e r t a t i o n ，g i v e sat e c h n o l o g yo fs e a r c h i n gs i m i l a r s e q u e n c e i n h i s t o r y r e c o r d sa n d f o r e c a s t i n g t h e f l y w e a t h e rt y p e s ，b y c o m b i n i n gt h e s i m i l a rs e r i e ss e a r c h i n ga n dc b r t e c h n o l o g yt h e m a i ni d e ai s ： s e a r c h i n g t h em o s ts i m i l a rs e q u e n c ei nw e a t h e rh i s t o r yd a t a b a s e s ，f o r e c a s t i n g 中国科学技术大学博士论文i x t h ef l yw e a t h e r t y p eu s i n gc b rt e c h n o l o g y t h ee x p e r i m e n tr e s u l t ss h o wt h a t t h ef o r e c a s t i n gp r e c i s i o ni ss a t i s f a c t o r y t h ei n n o v a t ep o i n t so ft h i sd i s s e r t a t i o na r e ： 1 g i v e sa ( ii n c r e m e n t a l a t g o r i t h m t h a tc a nc a l c u l a t et h ed f t p a r a m e t e r so fs e q u e n c ea n dl i n e a rw e i g h t e ds e q u e n c e d o i n gd f t o ne a c hw i n d o w so fa l o n gs e q u e n c e i sa n e c e s s a r ys t e p i n s e a r c h i n gs i m i l a rs e q u e n c e t h i sd i s s e r t a t i o ng i v e sa n dp r o v e st h e i n c r e m e n t a l a l g o r i t h m t h a tc a nc a l c u l a t et h ed f tp a r a m e t e r so f s e q u e n c e a n dl i n e a r w e i g h t e ds e q u e n c e t h et i m ec o m p l e x i t y b e c o m e s o ( n f c ) f r o mo ( n m f c ) ： 2 g i v e sa n dp r o v e sar e s o l u t i o n a l g o r i t h m t h a tc a nc a l c u l a t et h e e x t e n d e dd i s t a n c eb e t w e e ns e q u e n c e s t h i sa l g o r i t h m i s v e r y e f f e c t i v eb e c a u s ei tc a l c u l a t e st h ed i s t a n c eo nt h er e d u c e d f r e q u e n c yd o m a i n ，a n di t i sa l s oa d a p t i v et ot h ee x t e n d e dd i s t a n c e d e f i n i t i o nt h a tc a nh o l dt h es i m i l a r i t yo fs e q u e n c e sa f t e rs c a l i n ga n d s h i f t i n go n y a x i s 3 g i v e saf a s td i s t a n c e c a l c u l a t i n g a l g o r i t h m o nd i s c r e t ea t t r i b u t e s e r i e s t h em a i ni d e ai s ：f i r s t a r t i f i c i a l e v a l u a t i n g t h ed i s c r e t e a t t r i b u t e s ，m a p p i n g t h e mt on u m e r i c a ls p a c e ，t h e nu s i n gt h e d i m e n s i o nr e d u c i n gt e c h n o l o g yl i k ed f t , d w t , a n di n d e x i n gt h e m o nm u l t i d i m e n s i o n a li n d e xl i k er + t r e e a tl a s ts e a r c h i n gt h es i m i l a r s e q u e n c ei n t h em u l t i d i m e n s i o n a li n d e x t h i st e c h n o l o g yi sv e r y e f f e c t i v ei ns e a r c h i n gs i m i l a rd i s c r e t ea t t r i b u t e ss e r i e s 中国科学技术大学博士论文 第一章绪论 1 1 数据挖掘 1 1 1 数据挖掘技术起因 计算机和信息技术的发展，为人类社会带来了巨大的影响和变化，将人类社 会从工业化时代推进到了信息化时代，人类社会也从中受益匪浅。由于信息系统 的大规模采用和运行，i n t e r n e t 的大规模普及，各行各业的信息量呈爆炸性地增 长，据统计，1 9 9 3 年全球信息的存储容量约为2 0 0 0 t b ，但是到了2 0 0 0 年就增 加到了3 0 0 万t b ，面对这个极度膨胀的信息容量，人类正面临着“信息爆炸” 或“数据过剩”的压力。 然而，人类的各项活动都是基于人类的知识，根据这些学习到的知识进行决 策和判断，从而采取正确的行动，数据本身是人们利用各种工具和手段观察外部 世界所得到的原始材料，它本身没有太多意义 f a y 9 6 。从数据到知识，需要人们 进行进一步的深加工、分析和处理才能够变成人类所需要的知识。 由于人类的信息处理速度、容量等生物因素的限制，使得人类直接处理这些 海量数据变成了一件不可能的事情。从而形成了现在这种“数据丰富但知识贫乏” 的现象 h a n 0 1 1 。如何对这些数据量巨大的数据进行自动地分析、处理，从而得到 人类可以直接利用的知识，进行决策和判断，是目前信息化过程中所面临的一个 重要的问题。就好像从一座矿山的矿石当中，挖掘出有价值的金块一样，数据挖 掘由此而来 f a y 9 6 s i m 9 6 】。 1 1 2 数据挖掘的定义 数据挖掘( d a t am i n i n g ：简称d m ) 简单地讲就是从大量数据中抽取或挖掘 出知识。和很多人工智能技术一样，数据挖掘目前还没有一个被普遍接受的定义。 数据挖掘又称之为数据库中的知识发现( 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 ) ，它是一个从大量数据中挖掘出未知的、有价值的模式和规律等知 识的复杂过程。数据挖掘的过程描述如下图所示 f a y 9 6 1 ： 第1 章绪论 2 数据库l 一一上一主一 图1 1 知识挖掘全过程 由图1 1 可见，整个数据库中的知识发现的过程是由若干个步骤组成的，而 数据挖掘仅是其中的一个主要的步骤。整个知识挖掘的主要步骤有 f a y 9 6 ： 口数据清洗( d a t ac l e a r i n g ) ：主要作用是清除数据噪声，以及与挖掘主题 明显无关的数据： 口数据集成( d a t ai n t e g r a t i o n ) 将来自多数据源的相关数据集成到一起： 口数据转换( d a t at r a n s f o r m a t i o n ) ：将数据转换为易于进行数据挖掘的存储 形式； 口数据挖掘( d a t a m i n i n g ) ：是知识挖掘的个主要步骤，利用智能方法挖 掘数据的模式和规律等知识； 口 模式评估( p a t t e me v a l u a t i o n ) ：根据一定的评估标准从挖掘出的结果中 筛选出有意义的模式知识； 口 知识表示( k n o w l e d g ep r e s e n t a t i o n ) ：利用可视化和知识表示技术，向用 户展示挖掘出的相关知识。 尽管数据挖掘仅仅是整个知识挖掘过程的一个重要步骤，但由于目前工业 界、媒体、数据研究领域中，“数据挖掘”一词已经被广泛地采用和接受，因此 在以下内容中，使用数据挖掘来表示知识发现的全过程。 中国科学技术大学博士论文 3 1 1 3 数据挖掘的功能和主要方法 数据挖掘的功能是用于从指定的数据中挖掘或寻找出有价值的模式和规律。 数据挖掘任务一般地可以分成2 类：描述与预测 h a l l o l 】，描述性的挖掘任务刻划 数据库中数据的一般特性，预测性的挖掘任务是从当前数据中进行推断，从而进 行预测。 数据挖掘功能从发现模式的类型，以及采用的主要方法可以分成以下几种 h a n 0 1 ： 1 概念描述：定性和对比 一个概念常常是对一个包含大量数据的数据集合总体情况的概述。对于含有 大量数据的数据集合进行概述性的总结，并获得简明的、准确的描述，这种描述 就称之为概念描述。获得概念性描述的方法主要有2 种： a 利用更广义的属性，对所分析的数据进行概要总结，其中被分析的数据 被称之为目标数据集： b 对两类所分析的数据特点进行对比，并且对对比结果给出概要性总结， 而其中两类分析的数据集分别被称之为目标数据集和对比数据集。 数据概要总结就是利用数据描述属性中更广义的内容对其进行归纳描述。其 中被分析的数据，常常可以通过简单的数据库查询表来获取。数据概要总结常常 都用更广义的关系表和特征描述规则来加以输出表示。 概念描述的方法主要分成以下几种： 数据立方体：在多维数据模型中，数据被看成数据立方体的形式。 这个模型是数据仓库和o l a p 工具的基础模型。数据立方体允许以 多维形式对数据进行建模和观察，由维和事实定义。 面向属性的归纳：使用关系数据库查询收集与任务相关的数据，然 后通过考察任务相关数据中的每一个属性的不同值的个数，进行概 化。概化可以通过属性删除或属性概化来进行。 2 关联分析 关联分析就是从给定的数据集中发现频繁出现的项集模式知识 a g r 9 3 】( 又称 之为关联规则) ，关联分析广泛应用于市场营销、事务分析等领域。 第1 章绪论4 通常关联规则具有：x j y 的形式，即：a 1 a 2 a 。j b i a b 2 b n 。其中 a i ，b j 均为“属性一值”的形式。关联规则x j y 表示“数据库中满足条件x 的 记录也一定满足y 的条件”。 例如：一个数据挖掘系统可以从一个商场的销售( 交易事务处理) 记录数据 中，挖掘出如下的关联规则： a g e ( x ，”2 0 2 9 ”) i n c o m i n g ( x ，”2 0 k 一3 0 k ) j ( x ，”m p 3 ”) s u p p o r t = 2 ，c o n f i d e n c e 2 6 0 】 上述关联规则表示，该商场有2 的顾客年龄在2 0 岁到2 9 岁，且年收入在 2 万到3 万之间，这群顾客中有6 0 的人购买了m p 3 ，或者说这群顾客购买m p 3 的概率为6 0 。 关联规则挖掘首先由a g r a w a l 等在 a g r 9 3 1 6 0 提出，a p r i o r i 算法由a g r a w a l 等在 a g r 9 4 提出，这一算法的一个变形可见m a n n i l a 等 m a n 9 4 ；使用散列表提 高关联规则挖掘效率由p a r k 等研究提出 p a r 9 5 ；事务压缩技术见a g r a w a l 等 a g r 9 4 ，h a r t 等 h a n 9 5 ，p a r k p a r 9 5 ；划分技术由s a v a s e r e 等提出 s a v 9 5 ；选 样方法见t o i v o n e n t o i 9 6 ；动态项集计数由b r i n 等给 b r i 9 7 】。 关联规则挖掘有许多扩充，包括序列模式挖掘( a g r a w a l 等 a g r 9 5 】) ，e p i s o d e s 规则挖掘( m a n n i l a 等 m a n 9 7 ) ；挖掘空间关联规则( k o p e r s k i 等 k o p 9 5 ) ，挖 掘有环的关联规则( o z d e n 等 o z d 9 8 】) ，挖掘否定的关联规则( s a v a s e r e 等 【s a y 9 8 】) ：挖掘事务间关联规则( l u 等 l u 9 8 】) ，日历购物篮分析( r a m a s w a m y 等 r a m 9 8 1 ) ：最大模式的挖掘在b a y a r d o b a y 9 8 中介绍：频繁闭合项集的挖掘由 p a s q u i e r 等提出 p a s 9 9 ，而p e i 等给出了一个有效的挖掘算法【p e i o o 】；频繁项集 的深度优先产生由a g r a w a l 等提 a g r 0 0 ；挖掘频繁模式而不产生候选集的方 法由h a n 等提出 h a n 0 0 】。 3 分类与预测 分类就是找出一组能够描述数据集合典型特征的模型或函数，以便能够分类 标识出未知数据的归属或类别，即将未知事例映射到某种离散类别之一。分类模 型或函数可以通过分类挖掘算法从一组训练样本数据中学习获得。 分类挖掘所获得的分类模型可以采用多种形式加以描述输出，其中主要的表 示方法有：分类规则( i f t h e n ) 、决策树，数学公式和神经元网络。决策树是 中国科学技术大学博士论文 一个具有层次结构的树，决策树可以很容易地转换成分类规则。 分类通常用于预测未知数据实例的归属类别( 有限属性值) ，如一个银行客 户的信用等级属于a 级，b 级或c 级。但是在一些情况下，需要预测某数值属 性的值( 连续属性) ，这样的分类被称之为预测。尽管预测即包括了有限离散属 性值的预钡4 ，但一般还是使用预测来表示对连续数值的预测，而使用分类来表示 对有限离散值的预测。 4 聚类分析 聚类分析与分类预测方法的一个明显的不同之处在于，后者所学习获取分类 预测模型所使用的数据是已知类别的归属，属于有教师监督的学习方法，而聚类 分析所处理的数据是无类别归属，类别归属标志在聚类分析处理的数据集中是不 存在的。原因很简单，它们原来就不存在，因此聚类分析属于无教师监督的学习 方法。 聚类分析中，首先需要根据“各个聚集内部数据对象之间的相似度最大化和 各聚集对象之间相似度最小化”的基本聚类原则，以及度量数据对象之间相似度 的计算公式，将聚类分析的数据对象划分为若干组。因此，一个组中数据对象间 的相似度要比不同组数据对象间的相似度要大。每一个聚类分析所获得的组就可 以视为是一个同类别归属的数据对象集合，更进一步从这些同类别数据集，又可 以通过分类学习获得相应的分类预测模型。此外通过反复不断地对所获得聚类组 进行聚类分析，还可以获得初始数据集合的一个层次结构模型。 5 异类分析 一个数据库中的数据一般不可能都符合分类预测和聚类分析所获取的模型。 那些不符合大多数数据对象所构成规律的数据对象就被称为异类。以前许多数据 挖掘方法都在正式进行数据挖掘之前就将这些异类数据作为噪声或意外而将其 排除在数据挖掘的分析处理范围之外。但是在一些场合，如商业欺诈行为的检测， 小概率发生的事件往往比经常发生的事件更有挖掘价值。对于异类数据的分析处 理通常就称为异类挖掘。 数据中的异类可以利用数理统计的方法来获得，即利用已知数据所获得的概 率统计分布模型，或利用相似度计算出所获得的相似数据对象分布，分析确认异 第1 苹绪论 6 类数据。而偏差检测就是从数据已有或期望值中找出某些关键测度显著的变化。 6 演化分析 数据演化分析即对随着时间变化的数据对象的变化规律和趋势进行建模描 述。这一个建模手段包括：概念描述、对比概念描述、关联分析、分类分析、时 间相关数据分析。包括时序数据分析、序列或周期模式匹配、以及基于相似性的 数据分析等。 1 1 4 时序数据挖掘技术 时间序列是一种常见的数据形式。在金融、工业、气象、医学、交通乃至计 算机网络等十分广泛的领域，有大量的数据都是以时间序列的形式存在的。目前， 在数据挖掘领域内，对时间序列的关注也越来越多。时间序列中的数据挖掘已经 成为该领域中的一个热点问题。 对于时间序列的研究已经开展了很久，在利用时间序列数据来建立线性模型 并进行预测等方面，已经有了相当成熟的研究 安8 3 】 陈8 8 。但是，数据挖掘领 域的时间序列的研究问题，则更多的是从现代信息学的角度来考虑的，比如时间 序列的查询、编码、分类等等，这些问题与经典的时间序列研究的问题有着显著 的差别，从而也导致了对新方法与新技术的要求。 下面，我们将就时间序列中的数据挖掘的一些不同的问题进行说明。 一、相似序列的查询问题 相似的时间序列查询是时间序列中的数据挖掘方面的一个具有基础性作用 的问题。很多进一步的分析与挖掘都是建立在查询的基础上，而在数据挖掘领域 较早对时间序列进行的研究中，也是集中在时间序列的查询上。现在这个问题仍 然是领域中研究的一个主要问题。 本问题的另外一个重点，就是如何来定义“相似”。针对不通领域的实际问 题，相似的定义往往有着很大的区别。因此，提出不同的相似的定义，以及在这 种定义下如何完成查询任务，仍然将是研究的主要方向之一。 时间序列的全匹配问题 相似序列查询方面的基础性工作由a g r a w a l 等 a g r 9 3 + 1 给出。所采用的相 似性度量是e u c l i d e a n 距离，而具体考虑的问题则是时间序列的全匹配( w h o l e 中国科学技术大学博士论文7 m a t c h i n g ) i h 日 ，即2 个等长的时间序列在首尾对齐时的相似性查询问题。具体而 言，即给定查询序列y ，以及e u c l i d e a n 距离阈值e ，要求从时间序列数据库中 找出所有与y 之间的e u c l i d e a n 距离不大于的序列。 文中给出的方法，关键点有2 个：1 个是p a r s e v a l 恒等式，另外一个是r + t r e e 数据结构。 假设x 为一时间序列，而x 为其离散f o u r i e r 参数，那么，p a r s e v a l 恒等式 指出，信号在时域的能量与在频域上的能量是相等的，即： e ( x ) = e ( x ) n 1 n 1 e ( x ) = ) i 2 e ( x ) = i j ( 圳2 l = 0l = 0 n 为序列长度。根据这个式子，则进一步有： d ( x ，y ) = 4 e ( x y ) = 4 e ( x 一】，) = d ( x ，y ) 即2 个信号在时域上的e u c l i d e a n 距离与在频域上的e u c l i d e a n 距离是一样 的。 因此，我们可以将时域的利用e u c l i d e a n 距离度量来定义的序列相似度转化为 频域中的离散f o u r i e r 序列之间的e u c l i d e a n 距离来解决。而这一转化带来的好处， 是根据以下的事实：信号的能量一般主要集中其低频区域，即代表低频分量的最 初几个离散f o u r i e r 系数一般远远高于其它频段的f o u r i e r 系数，而且是数量级上 差别。于是我们可以利用以下的式子来计算出频域距离： d 2 ( ) ：窆阶) 一y ( 圳2z 篁i x ( f ) 一y ( 叫2 = 西( w ) t = 0 j 1 0 其中f c 是我们选取的低频f o u r i e r 系数。 由于：西( x ，y ) d ( x ，y ) ，西( x ，y ) 兰s 并不能说明x 与y 相似，但是如果： 5 ( x ，y ) s ，则x 和y 一定不相似。我们可以利用这一点，来对数据库中的时间 序列进行初步的筛选，将一定不相似的序列预先排除，而未能排除的序列再根据 实际的距离定义计算出准确的距离，并判断是否与待查的序列相似。 任何实数序列的第一个f o u r i e r 系数都为实数，而其它的系数都为复数。因 此这一个筛选的步骤，实际上就变成了2 个维数为( 2 + f c 一1 ) 的点之间的距离计算问 第1章绪论8 题。当维数不是太高时，我们可以预先将数据库中的时间序列的这些( 2 + f c 1 ) 维点 计算好，并采用合适的空间索引结构来存储这些点，从而构成数据库的一个索引， 加速筛选的运行速度。 一股适合于进行这样的工作的空间索引有k - d t r e e b e n 7 5 、b - t r e e b a y 7 2 、 与r t r e e 、r 十一t r e e 、r * - t r e e g u t 8 4 等。在 a g r 9 3 + 1 e ? 采用的是r + t r e e 。这一结 构是将维空间分割为若干个( 2 + f c 一1 ) 维的矩形，使得这些矩形能够包括所有( 2 * f o 1 1 维点，并形成个层次结构。通过这个索引，我们可以方便而迅速地完成筛选工 作。一个2 维的r + t r e e 索引的例子见下图1 2 ： ( a ) 树的较高层的空间划分( b )