（计算机应用技术专业论文）多流时间序列结构模式发现研究.pdf

洁。我还用v c + 十成功设计了一个挖掘器，并对由医院门诊数据流、 气温变化数据流、气压变化数据流组成的多流时间序列进行了挖掘， 证明了t w m a 是可行。 、r 面对数据的海洋，传统的单机串行算法已经不能适应快速、实 时昀知识需求，研究面向多机、并行、分布式的数据挖掘模型越来 越重要本文通过分析当前主要的并行模型、算法，总结出它们面 临的共同问题是：处理机容量的限制和处理枫需要传输大量的数据， 于是，本文在t w m a 的基础上提出了p t w m a ，采用了表对应技术、 以及算法本身不需要反复传输大项集的策略来克服了上述两个问 题。p t w m a 为分布式，并行控掘多流时间序列提供了一种有效的 算法和模型v 0 芙键词：数据挖掘，时间序列，噌行，关联规则，结构模式 、 r e s e a r c h0 nt h es t r u c t u r ep a t t e r n s o ft h e m u l t i p l et i m e s e r i e s a b s t r a c t s p e c i a l i t y ：c o m p u t e ra p p l i c a t i o n s u p e r v i s o r ：c h e n g x i a o p i n g m a j o r ：d a t am i n i n g a u t h o r ：w a n g g a n g ( 9 9 2 0 5 ) w eo r i e n t e dt h ec o m p l e x i t ym u l t i p l es t r e a m st i m es e r i e sd a t ai n m i l i t a r ya f f a i r s ，i n d u s t r yp r o c e s sm o n i t o rs y s t e m ，m e d i c a ld i a g n o s e ， r o b e r tc o n t r o l ，a n d l o g i s t i c a lm a n a g e m e n t ，f i n a n c i a lm a n a g e m e n t s y s t e m i t i s v e r yi m p o r t a n t t o a n a l y s i s ，e s t i m a t e ，o p t i m i z e a n d i n t e g r a t e t h e s ed a t a b yc o m p u t e rt e c h n o l o g y ，f o r e x a m p l e ，i n a g r i c u l t u r e ，i f w ec a nf i n dt h er e l a t i o n s h i pb e t w e e nt e m p e r a t u r ev a r i e t y a i rp r e s s u r ev a r i e t y ，i n s e c tp e s tv a r i e t y ，a n de m b l e m e n to u t p u tv a r i e t y ， s o ，w ec a nf i n dt h ew a yt oe n l a r g et h eo u t p u t t h ec u r r e n tr e s e a r c ho ft i m es e r i e sa r ef o c u so nt h ef i n d i n go ft h e k n o w l e d g eb e t w e e nt h ee v e n t si nt h es i n g l et i m es e r i e s ，f o re x a m p l e t r e n d ，s e q u e n t i a lp a t t e r n s ，f i n d i n g s i m i l i t u d e p a t t e r n s ，a s s o c i a t i o n r u l e s ，f i n d i n gp e r i o d ，e t c w e c a n td i v i d et h e m u l t i p l e s t r e a m st i m e s e r i e si n t o s i n g l e n e s st i m e ss e r i e ss i m p l yi nt h er e s e a r c ho fm u l t i p l e s t r e a m st i m es e r i e s ，w e 1 1d i s s e v e rt h er e l a t i o nb e t w e e nt h ee v e n t so f t h e m u l t i p l es t r e a m s a l t h o u g ht h em s d dc a nf i n dt h ed e p e n d e n c y r e l a t i o n s h i po fm u l t i p l es t r e a m s ，b u ti th a v e n tt h ei n i t i a l i z a t i o no ft h e e v e n t s ，t h ee x p r e s so ft h et i m er e l a t i o n s h i pb e t w e e ne v e n t si s n o t f r a n k ，t h ec o s to ft h ea l g o r i t h mi se x p e n s i v e ( o ( n ) ) ，ic a n tf i n dm u c h m o r ek n o w l e d g ei nm u l t i p l et i m es e r i e s ，i tf i n dt h ed e p e n d e n c y p a t t e r n s o n l yo ft h em u l t i p l et i m es e r i e s ，s ot h e r en e e dan e wm o r ee f f e c t i v e ， f r a n k ，c o m p l e t ea l g o r i t h mt of i n dt h ek n o w l e d g e 。 t h i s p a p e ra n a l y s i st h ed a t am i n i n go ft h es i n g l ea n dm u l t i p l e s t r e a m st i m e s e r i e s ，a n dd r a wac o n c l u s i o nt h a tt h e r e l a t i o n s h i p b e t w e e nt h ee v e n t so ft h e m u l t i p l e s t r e a m st i m e s e r i e sa r et h e 蜥 a s s o c i a t i o np a t t e r n sd e p e n d e n c yp a t t e r n s ，s u d d e np a t t e r n s ，t h i sp a p e r c a l lt h e ma r es t r u c t u r ep a t t e r n s ，t h ee x i s t i n ga l g o r i t h mh a v e n td i s c u s s t h e s e p a t t e r n s ，a l t h o u g h m s d dd i s c u s s e dt h e d e p e n d e n c yp a t t e r n s ， h o w e v e r ，i ti g n o r e d t h ea s s o c i a t i o n p a t t e r n s ，s u d d e np a t t e r n s ，t h i s p a p e rh a v ead e f i n i t i o no f t h ea s s o c i a t i o np a t t e r n s ，s u d d e np a t t e r n sa n d d e p e n d e n c yp a t t e r n s ，a n d h a v ea c o m p l e t e ，b a n ka l g o r i t h m c a l l e d t w m a ( t i m e w i n d o w m o v i n ga n df i l t e r i n ga l g o r i t h m ) ，t h ep e c u l i a r i t y o ft h i sa l g o r i t h mi st h a te v e n t si sl i s t e db yt h et i m ew i n d o w b yt h i sw a y ， t h er e l a t i o n s h i po ft h ee v e n t si sc l e a r t h i sa l g o r i t h mc a nd i s c o v e r yt h e r e l a t i o n s h i po f t h ee v e n t sa n dc a nd i s c o v e rm o r ek n o w l e d g ea n dt h ec o s t i sm o r ec h e a pt h a no t h e ra l g o r i t h m ，t h ea l g o r i t h mi sc o n c i s i o n ，f r a n k ，i t t a k eo n l y ( 0 ( n 3 ) ) t i m e ，i na d d i t i o n ，id e s i g nad a t am i n e rb yu s eo f v c + + a n di ti ss u c c e s s f u lt om i n et h em u l t i p l et i m es e r i e so fm e d i c a l d a t as t r e a m s ，t e m p e r a t u r ed a t as t r e a m sa n da i rp r e s s u r ed a t as t r e a m s t h et r a d i t i o n a ls e r i a l a l g o r i t h mc a n t d ow o r kw e l lf o rt h ed a t a o c e a nq u i c k l ya n dc o r r e c t l y ，i ta l s oi m p o r t a n tt or e s e a r c ht h ep a r a l l e l a l g o r i t h m t h i sp a p e ra n a l y s i s t h em a i n p a r a l l e la l g o r i t h m a n d m o d e l s ，a n df i n dt h e r ea r et w op r o b l e m a ：h o w t ou s et h e c a p a b i l i t yo f t h ep r o c e s s o r sa n dt h ei n f o r m a t i o nn u m b e ro ft h et r a n s m i s s i o nb e t w e e n t h ep r o c e s s o r s t h i sp a p e re x t e n dt h et w m at op t w m ，a n dp t w m a s o l v et h ep r o b l e mb yt h em e t h o do ft a b l ec o r r e s p o n d i n g ，a n dt h ei d e a t h a tt h ea l g o r i t h mn e e dn o tt ot r a n s m i tt h el a r g ei t e ms e t s p t w m ai sa n e f f e c t i v e 、s u c c e s s f u la l g o r i t h ma n dm o d e lt ot h ek n o w l e d g ed i s c o v e r y o ft h em u l t i p l es t r e a m st 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 ，p a r a l l e l ，a s s o c i a t i o nr u l e s ， s t r u c t u r ep a t t e r n s 1 引言 1 1 研究背景 数据挖掘技术作为人工智能的重要应用，越来越受到人们的重 视复杂系统的输入、输出都是多数据流。如何从多流时序中发现 隐藏的结构模式。如何利用计算机技术对按时序获得的若干观测信息 加以自动分析、优化、综合，以得到有用的知识，是一个很重要的 问题。 军事上：如通过对雷达，卫星获取的各种时序数据进行分析， 以便准确地发现、识别目标 医疗诊断：通过分析病人的病历，天气变化，季节，以更好地 诊断、控制、预防疾病 经济管理：通过分析经济系统的各种指标，发现他们之间的关 系，以便于更好地管理。 工业过程控制：通过分析传感器输入流，输出流的信息，发现 它们之间的一些关系，以便进一步精确控制它。 自然灾害预测：通过分析自然灾害发生时各种特征之间的关系， 发现能够预测灾窖发生的线索。 农业生产中：通过发现影响粮食产量的因素如气温、气压、湿度、 虫害、雨水等，从而更好地加以控制，以提高产量，减少病虫害。 1 2 研究的现状 目前，国内外的研究特别是对多流的研究存在的问题主要表现 在： 对多流时序与单流时序的差异、知识的组成与表示、规则的形 成，没有全面分析研究，要么集中于关联规则的研究，要么集中于 序列模式的研究、要么集中于依赖模式的研究，没有能发现更全面、 更丰富，更有用的知识 多流时序的挖掘有其自身的特点，其它的挖掘算法不能用在对 多流时序的挖掘上，期待要新的算法及模型，目前对多流时序知识 发现的研究比较少【4 1 1 1 0 】【1 3 1 1 4 】1 5 】的算法集中于数据库中的关 联规则、序列模式的发现，没有研究多数据流下依赖模式的发现， 1 引言 1 1 研究背景 数据挖掘技术作为人工智能的重要应用，越来越受到人们的重 视复杂系统的输入、输出都是多数据流。如何从多流时序中发现 隐藏的结构模式。如何利用计算机技术对按时序获得的若干观测信息 加以自动分析、优化、综合，以得到有用的知识，是一个很重要的 问题。 军事上：如通过对雷达，卫星获取的各种时序数据进行分析， 以便准确地发现、识别目标 医疗诊断：通过分析病人的病历，天气变化，季节，以更好地 诊断、控制、预防疾病 经济管理：通过分析经济系统的各种指标，发现他们之间的关 系，以便于更好地管理。 工业过程控制：通过分析传感器输入流，输出流的信息，发现 它们之间的一些关系，以便进一步精确控制它。 自然灾害预测：通过分析自然灾害发生时各种特征之间的关系， 发现能够预测灾窖发生的线索。 农业生产中：通过发现影响粮食产量的因素如气温、气压、湿度、 虫害、雨水等，从而更好地加以控制，以提高产量，减少病虫害。 1 2 研究的现状 目前，国内外的研究特别是对多流的研究存在的问题主要表现 在： 对多流时序与单流时序的差异、知识的组成与表示、规则的形 成，没有全面分析研究，要么集中于关联规则的研究，要么集中于 序列模式的研究、要么集中于依赖模式的研究，没有能发现更全面、 更丰富，更有用的知识 多流时序的挖掘有其自身的特点，其它的挖掘算法不能用在对 多流时序的挖掘上，期待要新的算法及模型，目前对多流时序知识 发现的研究比较少【4 1 1 1 0 】【1 3 1 1 4 】1 5 】的算法集中于数据库中的关 联规则、序列模式的发现，没有研究多数据流下依赖模式的发现， 而【8 】的算法解决的是交易数据库中的关联规则的并行发现问题，不 适合多数据流下的依赖模式及突变模式的发现 在研究高效的单机算法的同时，多机并行、分布式的系统结构 对于提高挖掘海量数据的速度和质量起到决定性的作用，研究多机 并行模型、并行算法、成为关键，也必然是大势所趋，而【4 d 0 d 5 】 是单机数据库挖掘算法，【1 3 1 4 】的并行模型由于挖掘是基于交易数 据库，其不适合多流时间序列的数据挖掘，本文提出了新的多流时 间序列并行挖掘模型 马萨诸塞州大学计算机系的t i mo a t e s 对多流时序进行了研究， 提出了m s d d 算法来发现事件间的依赖关系，但是由于采用树结构， 事件之间的时间关系表示不够直观，该算法没有针对有效事件的前 驱事件，后继事件来生成依赖空间，而是以所有发生的事件为基础， 这需要巨大的空闻、时间算法忽略了事件预处理，不能及时剔除 不满足要求的事件，忽略了异常模式的挖掘，使得很多有用的知识 没有能够被发现。 1 3 本文的工作与意义 ( i ) 将单流时序与多流时序相比较，分析了时间序列知识发现 的定义、现状，给出了多流时序中结构模式的定义和表示。 ( 2 ) 分析了当前串、并行算法的优缺点、提出了发现多流时序 结构模式的算法：时间窗口移动筛选算法t w m a ( t i m ew i n d o w m o v i n ga n df i l t e r i n ga l g o r i t h m ) 。 ( 3 ) 提出了发现多流时序结构模式的一种有效的并行算法 p t w m a 与模型。 ( 4 ) 用v c 什语言，以t w m为核心，开发设计了挖掘器，证明t w m 的可行，并对医疗门诊数据进行了挖掘，得到了满意的结果。 ( 5 ) t w m a 为从多流时间序列中发现事件之闻的关系提供了一种有效的解 决方法。 1 4 论文的结构安捧 第二章介绍了数据挖掘的定义、过程，和数据挖掘的模式。 第三章介绍了时间序列的定义，时问序列数据挖掘发现的知 识，分析了当前时间序列知识发现的现状和不足，提出了时问序列 2 而【8 】的算法解决的是交易数据库中的关联规则的并行发现问题，不 适合多数据流下的依赖模式及突变模式的发现 在研究高效的单机算法的同时，多机并行、分布式的系统结构 对于提高挖掘海量数据的速度和质量起到决定性的作用，研究多机 并行模型、并行算法、成为关键，也必然是大势所趋，而【4 d 0 d 5 】 是单机数据库挖掘算法，【1 3 1 4 】的并行模型由于挖掘是基于交易数 据库，其不适合多流时间序列的数据挖掘，本文提出了新的多流时 间序列并行挖掘模型 马萨诸塞州大学计算机系的t i mo a t e s 对多流时序进行了研究， 提出了m s d d 算法来发现事件间的依赖关系，但是由于采用树结构， 事件之间的时间关系表示不够直观，该算法没有针对有效事件的前 驱事件，后继事件来生成依赖空间，而是以所有发生的事件为基础， 这需要巨大的空闻、时间算法忽略了事件预处理，不能及时剔除 不满足要求的事件，忽略了异常模式的挖掘，使得很多有用的知识 没有能够被发现。 1 3 本文的工作与意义 ( i ) 将单流时序与多流时序相比较，分析了时间序列知识发现 的定义、现状，给出了多流时序中结构模式的定义和表示。 ( 2 ) 分析了当前串、并行算法的优缺点、提出了发现多流时序 结构模式的算法：时间窗口移动筛选算法t w m a ( t i m ew i n d o w m o v i n ga n df i l t e r i n ga l g o r i t h m ) 。 ( 3 ) 提出了发现多流时序结构模式的一种有效的并行算法 p t w m a 与模型。 ( 4 ) 用v c 什语言，以t w m为核心，开发设计了挖掘器，证明t w m 的可行，并对医疗门诊数据进行了挖掘，得到了满意的结果。 ( 5 ) t w m a 为从多流时间序列中发现事件之闻的关系提供了一种有效的解 决方法。 1 4 论文的结构安捧 第二章介绍了数据挖掘的定义、过程，和数据挖掘的模式。 第三章介绍了时间序列的定义，时问序列数据挖掘发现的知 识，分析了当前时间序列知识发现的现状和不足，提出了时问序列 2 而【8 】的算法解决的是交易数据库中的关联规则的并行发现问题，不 适合多数据流下的依赖模式及突变模式的发现 在研究高效的单机算法的同时，多机并行、分布式的系统结构 对于提高挖掘海量数据的速度和质量起到决定性的作用，研究多机 并行模型、并行算法、成为关键，也必然是大势所趋，而【4 d 0 d 5 】 是单机数据库挖掘算法，【1 3 1 4 】的并行模型由于挖掘是基于交易数 据库，其不适合多流时间序列的数据挖掘，本文提出了新的多流时 间序列并行挖掘模型 马萨诸塞州大学计算机系的t i mo a t e s 对多流时序进行了研究， 提出了m s d d 算法来发现事件间的依赖关系，但是由于采用树结构， 事件之间的时间关系表示不够直观，该算法没有针对有效事件的前 驱事件，后继事件来生成依赖空间，而是以所有发生的事件为基础， 这需要巨大的空闻、时间算法忽略了事件预处理，不能及时剔除 不满足要求的事件，忽略了异常模式的挖掘，使得很多有用的知识 没有能够被发现。 1 3 本文的工作与意义 ( i ) 将单流时序与多流时序相比较，分析了时间序列知识发现 的定义、现状，给出了多流时序中结构模式的定义和表示。 ( 2 ) 分析了当前串、并行算法的优缺点、提出了发现多流时序 结构模式的算法：时间窗口移动筛选算法t w m a ( t i m ew i n d o w m o v i n ga n df i l t e r i n ga l g o r i t h m ) 。 ( 3 ) 提出了发现多流时序结构模式的一种有效的并行算法 p t w m a 与模型。 ( 4 ) 用v c 什语言，以t w m为核心，开发设计了挖掘器，证明t w m 的可行，并对医疗门诊数据进行了挖掘，得到了满意的结果。 ( 5 ) t w m a 为从多流时间序列中发现事件之闻的关系提供了一种有效的解 决方法。 1 4 论文的结构安捧 第二章介绍了数据挖掘的定义、过程，和数据挖掘的模式。 第三章介绍了时间序列的定义，时问序列数据挖掘发现的知 识，分析了当前时间序列知识发现的现状和不足，提出了时问序列 2 的结构模式 第四章详细分析了当前关联规则、序列模式、依赖模式发现的 主要的串、并行算法的思想和不足，为第五章、第六章介绍t w m a 算法及并行算法作好了准备 第五章阐述了t w m a 的思想，算法描述，以及与m s d d 的运 行时间比较发现t w m a 在执行时间上优予m s d d 。 第六章详细介绍了t w m a 的并行思想、模型、算法，以及与当 前主要模型的比较。 第七章介绍了t w m a 用于门诊数据流序列的数据挖掘的过 程、得到了有效的结果，采用的是广西南宁1 9 9 6 年8 月的气温、气 压、医院发病人数组成的数据 第八章结束语，对本文研究的问题进行了总结，并提出了下一 步懂得研究工作。 最后附录了挖掘器界面、部分核心程序以及主要的参考资料。 2 数据挖掘概述 2 1 数据羹炸但知识贫乏 随着数据库技术的迅速发展以及数据库管理系统的广泛应用， 人们积累的数据越来越多。激增的数据背后隐藏着许多重要的信息， 人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。 目前的数据库系统可以高效地实现数据的录入、查询、统计等功能， 但无法发现数据中存在的关系和规则，无法有效地根据现有的数据 预测未来的发展趋势缺乏挖掘数据背后隐藏的知识的手段，导致 了“数据爆炸但知识贫乏”的现象。 知识发现是在需求驱动下发展起来的一门技术，随着政府部门、 企事业单位、大型金融、商业机构的大量建立，以及电子商务的迅 猛发展，数据积累成倍地急速增长，如何充分地利用这些数据，对 数据进行分析来指导生产工作，提供决策，如何从大量的数据中发 现有用的信息和知识，挖掘出未知的规律，已经成为急需解决的问 题。而目前基于数据库的知识发现的研究已经取得了很多成果，它 面向的对象是数据库基于w e b 的数据挖掘，它面向的对象是访问 w e b 的记录。基于时间序列的数据挖掘，面向的对象是随时间不断 变化的数据。面对不同的对象，。其挖掘算法和模型也是不相同的。 2 2 数据挖掘的定义 它从对象中识别出有效的、新颖的、潜在的有用的以及最终可 理解的知识规律的过程。通常面向的对象有：时间序列、数据库、 w e b 等各种信息集合，挖掘的内容通常是事件之间的关系、形成的 路径或轨迹。 2 3 数据挖掘的过程 数据挖掘可以分为数据准备、数据挖掘及结果的解释评价如图1 所示。 ( 1 ) 数据准备：数据准备包括数据的选取，抽样，数据的预处理 和数据的转换。 ( 2 ) 数据挖掘：根据数据挖掘的任务，确定采用哪种数据挖掘算 2 数据挖掘概述 2 1 数据羹炸但知识贫乏 随着数据库技术的迅速发展以及数据库管理系统的广泛应用， 人们积累的数据越来越多。激增的数据背后隐藏着许多重要的信息， 人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。 目前的数据库系统可以高效地实现数据的录入、查询、统计等功能， 但无法发现数据中存在的关系和规则，无法有效地根据现有的数据 预测未来的发展趋势缺乏挖掘数据背后隐藏的知识的手段，导致 了“数据爆炸但知识贫乏”的现象。 知识发现是在需求驱动下发展起来的一门技术，随着政府部门、 企事业单位、大型金融、商业机构的大量建立，以及电子商务的迅 猛发展，数据积累成倍地急速增长，如何充分地利用这些数据，对 数据进行分析来指导生产工作，提供决策，如何从大量的数据中发 现有用的信息和知识，挖掘出未知的规律，已经成为急需解决的问 题。而目前基于数据库的知识发现的研究已经取得了很多成果，它 面向的对象是数据库基于w e b 的数据挖掘，它面向的对象是访问 w e b 的记录。基于时间序列的数据挖掘，面向的对象是随时间不断 变化的数据。面对不同的对象，。其挖掘算法和模型也是不相同的。 2 2 数据挖掘的定义 它从对象中识别出有效的、新颖的、潜在的有用的以及最终可 理解的知识规律的过程。通常面向的对象有：时间序列、数据库、 w e b 等各种信息集合，挖掘的内容通常是事件之间的关系、形成的 路径或轨迹。 2 3 数据挖掘的过程 数据挖掘可以分为数据准备、数据挖掘及结果的解释评价如图1 所示。 ( 1 ) 数据准备：数据准备包括数据的选取，抽样，数据的预处理 和数据的转换。 ( 2 ) 数据挖掘：根据数据挖掘的任务，确定采用哪种数据挖掘算 法，模型。 ( 3 ) 结果解释和评价；经数据挖掘所发现的结果，表现为模式、 一些关系、表达式可能存在冗余和用户不感兴趣的模式，这需要 将其去除，所发掘出的结果需专家进行解释、判断和评价，才能形 成知识。 矗据库 9目 目 | 目标 t 嚣 圈l 后的置 据 教据挖 掘坫粟 擀 解一 评价 知 2 4 数据挖掘的模式 数据挖掘的模式主要有 ( 1 ) 分类模式 分类模式是一个分类函数( 分类器) ，能够把数据集中的数据项 映射到某个给定的类上。分类模式往往表现为一棵分类树，根据数 据的值从树根开始搜索，沿着数据满足的分支往上走，走到树叶就 能确定类别。 ( 2 ) 回归模式 回归模式的函数定义与分类模式相似，它们的差别在于分类模 式的预测值是离散的，回归模式的预测值是连续的。如给出某种动 物的特征，可以用分类模式判定这种动物是哺乳动物还是鸟类：给 出某个人的教育情况、工作经验，可以用回归模式判定这个人的年 工资在哪个范围内，是在6 0 0 0 元以下，还是在6 0 0 0 元到l 万元之 间，还是在l 万元以上。 ( 3 ) 时间序列模式 时间序列模式根据数据随时问变化的趋势预测将来的值或得出 一些规律这里要考虑到时间的特殊性质，像一些周期性的时间定 义如星期、月、季节、年等，不同的日子如节假日可能造成的影响， 法，模型。 ( 3 ) 结果解释和评价；经数据挖掘所发现的结果，表现为模式、 一些关系、表达式可能存在冗余和用户不感兴趣的模式，这需要 将其去除，所发掘出的结果需专家进行解释、判断和评价，才能形 成知识。 矗据库 9目 目 | 目标 t 嚣 圈l 后的置 据 教据挖 掘坫粟 擀 解一 评价 知 2 4 数据挖掘的模式 数据挖掘的模式主要有 ( 1 ) 分类模式 分类模式是一个分类函数( 分类器) ，能够把数据集中的数据项 映射到某个给定的类上。分类模式往往表现为一棵分类树，根据数 据的值从树根开始搜索，沿着数据满足的分支往上走，走到树叶就 能确定类别。 ( 2 ) 回归模式 回归模式的函数定义与分类模式相似，它们的差别在于分类模 式的预测值是离散的，回归模式的预测值是连续的。如给出某种动 物的特征，可以用分类模式判定这种动物是哺乳动物还是鸟类：给 出某个人的教育情况、工作经验，可以用回归模式判定这个人的年 工资在哪个范围内，是在6 0 0 0 元以下，还是在6 0 0 0 元到l 万元之 间，还是在l 万元以上。 ( 3 ) 时间序列模式 时间序列模式根据数据随时问变化的趋势预测将来的值或得出 一些规律这里要考虑到时间的特殊性质，像一些周期性的时间定 义如星期、月、季节、年等，不同的日子如节假日可能造成的影响， 日期本身的计算方法，还有一些需要特殊考虑的地方如时间前后的 相关性( 过去的事情对将来有多大的影响力) g ，如：在购买彩电的 人们当中，6 0 的人会在3 个月内购买影碟机只有充分考虑时间 因素，利用现有数据随时闻变化的一系列的值，才能更好地预测将 来的值 ( 4 ) 聚类模式 聚类模式把数据划分到不同的组中，组之间的差别尽可能大，组 内的差别尽可能小。与分类模式不同，进行聚类前并不知道将要划 分成几个组和什么样的组，也不知道根据哪一( 几) 个数据项来定义 组。一般来说，业务知识丰富的人应该可以理解这些组的含义，如 果产生的模式无法理解或不可用，则该模式可能是无意义的，需要 回到上阶段重新组织数据 ( 5 ) 关联模式 关联模式是数据项之间的关联规则。关联规则是如下形式的一 种规则：“在无力偿还贷款的人当中，6 0 的人的月收入在3 0 0 0 元 以下。” ( 6 ) 突变模式 通过对异常事件的分析，可以引起人们对特殊情况的加倍注意， 包括如下的几种可能情况： 不满足常规的异常事件。 属性在某时刻发生了显著变化：如气温从2 0 c 突然降到5 ， 通过分析其发生突变的原因与产生的后果，提醒人们注意天气的变 化。 6 3 时阅序列数据挖掘 时间序列的数据挖掘是数据挖掘的一个重要分支，它研究的对象是时间序 列事件的集合 3 1 时序的定义 在a g r a w a l 等人的文章中。时间序列定义为”a no r d e rs e t o fr e a l v a l u e ”它是指一类有序的，复杂的对象的集合，时间序列数据挖 掘主要是通过一系列的方法，从大量的时序数据中发现特定的规律 和有价值的知识如“相似性搜索“。”模式发现“，”趋势预测“等。 时间序列首先要解决的问题是时序数据的形式化表示，目前的方 法有：事件表示和状态表示。本文是基于事件表示。 设s = x ) ；t 表示时间；x 。表示在时间t 上发生的事件，则s 表示 时间序列。图2 所示为单流时序其中事件分为平稳事件和突变事 件。平稳事件指属性之间的变化不是非常显著，而突变事件指事件 属性发生了显著变化。如气温时序中，气温从5 变化到7 ，这一 事件是平稳事件，而气温从5 变化到1 5 ，这一事件就是突变事 件。 事件x 的支持度p 定义为：s 中x 。占s 。时序的长度定义为 时序中事件的个数。 图2 3 2 多流时序的定义 所谓“多流”，指系统中的多个数据流，或信息流如电子商务 中的“资金流”，“商品流”，“信息流”。多流时序就是各单流时序按 照事件发生的时间关系组成的集合，s = s 。，s ：s 。) ，s ；= i 流的事件 x 。) ，多流时序如图3 所示，实际中很多连续的数据流可以通过不同的 值对应不同的事件来离散化，得到离散事件的集合，如图3 为连续 事件的数据流。 7 图3 3 时阅序列数据挖掘 时间序列的数据挖掘是数据挖掘的一个重要分支，它研究的对象是时间序 列事件的集合 3 1 时序的定义 在a g r a w a l 等人的文章中。时间序列定义为”a no r d e rs e t o fr e a l v a l u e ”它是指一类有序的，复杂的对象的集合，时间序列数据挖 掘主要是通过一系列的方法，从大量的时序数据中发现特定的规律 和有价值的知识如“相似性搜索“。”模式发现“，”趋势预测“等。 时间序列首先要解决的问题是时序数据的形式化表示，目前的方 法有：事件表示和状态表示。本文是基于事件表示。 设s = x ) ；t 表示时间；x 。表示在时间t 上发生的事件，则s 表示 时间序列。图2 所示为单流时序其中事件分为平稳事件和突变事 件。平稳事件指属性之间的变化不是非常显著，而突变事件指事件 属性发生了显著变化。如气温时序中，气温从5 变化到7 ，这一 事件是平稳事件，而气温从5 变化到1 5 ，这一事件就是突变事 件。 事件x 的支持度p 定义为：s 中x 。占s 。时序的长度定义为 时序中事件的个数。 图2 3 2 多流时序的定义 所谓“多流”，指系统中的多个数据流，或信息流如电子商务 中的“资金流”，“商品流”，“信息流”。多流时序就是各单流时序按 照事件发生的时间关系组成的集合，s = s 。，s ：s 。) ，s ；= i 流的事件 x 。) ，多流时序如图3 所示，实际中很多连续的数据流可以通过不同的 值对应不同的事件来离散化，得到离散事件的集合，如图3 为连续 事件的数据流。 7 图3 假设可以得到的离散事件的集合是： s i ：d b b a dc d a b c s 2 ：x y y z y x z z x y s 3 ：2 1 32 2 l2 2 3 2 l 定义第i 流的数据来自集合则h = a ，b ，c ，d ) ；p 2 。 x ，y ，z ) ； b = l ，2 ，3 ) ，代表不同事件的集合a 依赖型模式：x ! = l y ，称x 为 前驱时间段对应的事件，简称前驱事件，。y 为后继时间段对应的事 件，简称后继事件。p 表示支持度，可通过计算得到。本文研究依 赖模式，关联模式、突变模式。 定义三元组 ，v 对应事件，j 对应输入流，盯指，发生的相 对时间，如 ， ) ，表明，s l 中的事件b 发生后间隔时问 为l ，数据流2 中的事件y 也回发生。 实际中的股市行情、焊接、机器人的多传感器输入，都是多数据 流的例子。 3 3 时同序列中的知识表示 时间序列中的知识表示包括：趋势、相似模式搜索、序列模式、 结构模式( 关联模式、依赖模式、突变模式) 。 3 3 1 趋势 时问序列事件的出现随着时间的改变而变化，如果这些变化长期 且具有方向性，称该序列具有趋势，发现趋势对于时间序列的数据 挖掘，有很重要的意义，趋势通常有如下几类： ( 1 ) 线性变化趋势 y t = 屁+ ，+ 日，其中只表示事件出现对应的值，表示系数， t ，表示时间，占，表示误差 ( 2 ) 二次曲线交化趋势 y l = p o + p i t + p l t l t ( 3 ) 指数变化变化趋势 y t = 氏烈8 t ( 4 ) 周期或季节性变化 0 假设可以得到的离散事件的集合是： s i ：d b b a dc d a b c s 2 ：x y y z y x z z x y s 3 ：2 1 32 2 l2 2 3 2 l 定义第i 流的数据来自集合则h = a ，b ，c ，d ) ；p 2 。 x ，y ，z ) ； b = l ，2 ，3 ) ，代表不同事件的集合a 依赖型模式：x ! = l y ，称x 为 前驱时间段对应的事件，简称前驱事件，。y 为后继时间段对应的事 件，简称后继事件。p 表示支持度，可通过计算得到。本文研究依 赖模式，关联模式、突变模式。 定义三元组 ，v 对应事件，j 对应输入流，盯指，发生的相 对时间，如 ， ) ，表明，s l 中的事件b 发生后间隔时问 为l ，数据流2 中的事件y 也回发生。 实际中的股市行情、焊接、机器人的多传感器输入，都是多数据 流的例子。 3 3 时同序列中的知识表示 时间序列中的知识表示包括：趋势、相似模式搜索、序列模式、 结构模式( 关联模式、依赖模式、突变模式) 。 3 3 1 趋势 时问序列事件的出现随着时间的改变而变化，如果这些变化长期 且具有方向性，称该序列具有趋势，发现趋势对于时间序列的数据 挖掘，有很重要的意义，趋势通常有如下几类： ( 1 ) 线性变化趋势 y t = 屁+ ，+ 日，其中只表示事件出现对应的值，表示系数， t ，表示时间，占，表示误差 ( 2 ) 二次曲线交化趋势 y l = p o + p i t + p l t l t ( 3 ) 指数变化变化趋势 y t = 氏烈8 t ( 4 ) 周期或季节性变化 0 假设可以得到的离散事件的集合是： s i ：d b b a dc d a b c s 2 ：x y y z y x z z x y s 3 ：2 1 32 2 l2 2 3 2 l 定义第i 流的数据来自集合则h = a ，b ，c ，d ) ；p 2 。 x ，y ，z ) ； b = l ，2 ，3 ) ，代表不同事件的集合a 依赖型模式：x ! = l y ，称x 为 前驱时间段对应的事件，简称前驱事件，。y 为后继时间段对应的事 件，简称后继事件。p 表示支持度，可通过计算得到。本文研究依 赖模式，关联模式、突变模式。 定义三元组 ，v 对应事件，j 对应输入流，盯指，发生的相 对时间，如 ， ) ，表明，s l 中的事件b 发生后间隔时问 为l ，数据流2 中的事件y 也回发生。 实际中的股市行情、焊接、机器人的多传感器输入，都是多数据 流的例子。 3 3 时同序列中的知识表示 时间序列中的知识表示包括：趋势、相似模式搜索、序列模式、 结构模式( 关联模式、依赖模式、突变模式) 。 3 3 1 趋势 时问序列事件的出现随着时间的改变而变化，如果这些变化长期 且具有方向性，称该序列具有趋势，发现趋势对于时间序列的数据 挖掘，有很重要的意义，趋势通常有如下几类： ( 1 ) 线性变化趋势 y t = 屁+ ，+ 日，其中只表示事件出现对应的值，表示系数， t ，表示时间，占，表示误差 ( 2 ) 二次曲线交化趋势 y l = p o + p i t + p l t l t ( 3 ) 指数变化变化趋势 y t = 氏烈8 t ( 4 ) 周期或季节性变化 0 时间序列中的事件随着时间的变化，周期性的出现，如市场营销 额，经常出现每年春节前一个月空前高涨，这是人们的消费习惯决 定的因此，发现时间序列中的周期事件，也有很重要的意义。 对趋势的研究揭示的是数据变化的规律和大致方向，需要把对应 的事件连线，然后进行拟合，适合于线性的数字序列。研究趋势的 方法是用求平均值、差分、回归分析。 3 3 2 相似模式拽索川 它研究的对象是一个或几个时间序列。有代表性的思想是分别把 时间序列分为许多的小序列，然后用小线段去拟合它们，通过比较 小线段的斜率，如果它们的差异在一定的误差范围内，于是认为这 些线段相似。如果时间序列中相似的线段达到一定的数量，则认为 这些时间序列相似，它们就应该存在一些关联，就会引起决策者的 注意。另外一种方法就是将斜率离散化f 3 7 l ，对应到字符串，这样就 实现了线段的符号表示，可以通过相似性搜索，发现序列之间的关 系它研究的对象是不规则的，随机的事件序列，发现的是事件序 列之间的关系。 3 3 3 序列模式的发现 它的目的是发现序列之间的关系如对时间序列 ( a , b ) ，( a , b ，e ) ， ( c ) ，( a , d ，b ) ，( b , d ) ，发现( a , b ) 的支持度为! ，满足要求，于是可以 5 得出，a , b 事件能够同时发生，其支持度为! 。目前代表性的文章是 5 【4 】。 “序列之间”与“事件之间”既有区别，又有联系。前者强调的 是时间序列中的许多子序列，如上述，而后者强调的是时间序列中 的事件，例如参考序列 a , b ，d ，c ，a ，b ，x ，d ，a ，b ，a , b 事件之间的关系是： a 发生后，b 就会发生而如果是序列之间的关系，得到的结果就是 a b 出现的支持度为三，a b 就是有价值的序列。发现“序列”、“事件” l o 之间的关系都很重要 3 3 4 肘间序列中的结构棱式 多流时间序列数据挖掘还要发现序列之间的结构模式，本文将结 构模式定义为：关联模式，依赖模式，突变模式，以区别于趋势， 相似性搜索和序列模式。发现结构模式研究的是事件本身相互之间 9 时间序列中的事件随着