（计算机应用技术专业论文）多时间序列上挖掘框架的研究.pdf

中 毒 一j 南 at h e s i si nc o m p u t e r a p p l i c a t i o nt e c h n o l o g y r e s e a r c ho nt h ef r a m e w o r ko fm i n i n go nm u l t i p l et i m e s e r i e s b y w e iz h i y o n g s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rj i a n gx u e y i n g n o r t h e a s t e r nu n i v e r s i t y j u n e 2 0 0 9 l j 独创性声明 本人声明所呈交的学位论文是本人在导师指导下完成的论文中取得的 研究成果，除了加以标注和致谢的地方外，不包含其他人已经发表或撰写 过的研究成果，也不包含本人为获得其他学位或证书而使用过的材料与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并 表示诚挚的谢意 学位论文作者签名：鳓苏勇 日 期：卯7 年_ 7 月1 日 学位论文版权使用授权书 本学位论文作者和指导老师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅本人同意东北大学可以将学位论文的全部或 部分内容编入有关数据库进行检索、交流 ( 如作者和导师同意网上交流，请在下方签名：否则视为不同意) 学位论文作者签名：素锄 签字日期：聊- 7 、7 办勇 导师橼荡菩菱 签字日期：勿移27 ，o | 1 f i 东北大学硕士学位论文 多时间序列上 摘要 时间序列是一组按时间顺序排列的数据集合，它广泛存在于商业、交通、工业等各 个行业，对时间序列数据进行分析，可以揭示事物运动、变化和发展的内在规律，对于 人们正确认识事物并据此作出科学的决策具有重要的现实意义。 本文的具体研究背景为热轧控制。在轧制过程中很多异常情况大多由多个原因引 起，原因之间存在着相互关联的关系。针对此，本文提出了一个多时间序列上的挖掘框 架。框架首先采用模式表示的方法将数据进行压缩，在压缩后的数据上进行异常检测。 然后在检测到的异常模式基础上进行挖掘，从中发现一些对企业决策有决定性或者指导 性的信息。 框架中模式表示部分，通过借鉴数字图像研究领域中边缘算子的基本思想，将边缘 算子与时间序列的特点结合起来，得到了时间序列的一种分段线性表示。框架中异常检 测部分，在t o d 异常模式发现算法的基础上加入了滑动窗口的思想，以进行局部异常 的检测。在序列模式挖掘中，本框架采用一种基于p r e f i x s p a n 序列模式挖掘的改进算法 ( p s d 算法) ，通过删除非频繁项以及判断投影序列数与最小支持数的关系，减少不必 要的存储空间，提高查询速度。本框架的多时间序列上的挖掘，采用了非同步多时间 序列中频繁模式的发现算法。针对上述算法的实验证明了各个算法的可行性和有效性。 实验证明，本框架较好地完成了钢轧制过程中的异常模式发现，以及多种因素间相 互影响关系的挖掘，可以为企业提高钢产品质量，控制钢生产数量起到指导作用。 关键词：时间序列；数据挖掘；异常模式；异常检测；关联规则 i i t 东北大学硕士学位论文 r e s e a r c ho nt h ef r t i m es e r i e si sas e to f t i m e s e r i e sd a t as e t , w h i c he x i s t si naw i d er a n g eo f c o m m e r c i a l ， t r a n s p o r t ，i n d u s t r ya n do t h e ri n d u s t r i e s a n a l y s i so ft i m es e r i e sd a t ac a nr e v e a lt h ei n t e m a l r u l e so ft h i n g si nm o v e m e n t ， c h a n g ea n dd e v e l o p m e n t ， a n dh a v ei m p o r t a n tp r a c t i c a l s i g n i f i c a n c ef o r t h ep e o p l et ou n d e r s t a n dt h i n g sc o r r e c t l ya n dm a k eas c i e n t i f i cd e c i s i o n i nt h i sp a p e r ，t h es p e c i f i cr e s e a r c hb a c k g r o u n di sc o n t r o lf o rh o t r o l l e d i nt h er o l l i n g p r o c e s s ，m a n ya n o m a l i e sa r ec a u s e db yan u m b e ro fr e a s o n s ， a n dt h e r ei se x i s t e n c eo ft h e r e l a t i o n s h i pb e t w e e nt h er e a s o n s f o rt h i s ，t h ep a p e rp r e s e n t e dam u l t i p l et i m es e r i e s f r a m e w o r ko fa b n o r m a lp a r e r nm i n i n g f i r s to fa l l ，t h ef r a m e w o r ku s e sm e t h o do fp a t t e m r e p r e s e n t a t i o nt oc o m p r e s st h ed a t a ， a n dm a k ea b n o r m i t yd e t e c t i o nf o rt h ec o m p r e s s e dd a t a a n dt h e nm i n i n go nt h eb a s i so fa b n o r m a lp a a e m ，i no r d e rt of o u n ds o m ed e c i s i v ea n d g u i d i n gi n f o r m a t i o n sf o rt h ed e c i s i o n - m a k i n go fc o m p a n i e s p a t t e r nr e p r e s e n t a t i o no ft h ef a m e w o r k ，t h r o u g ht h eb a s i ci d e ao ft h ee d g eo p e r a t o ri n t h ef i e l do fd i g i t a li m a g e ， c o m b i n a t i n gt h ee d g eo p e r a t o ra n dt h ec h a r a c t e r i s t i c so ft i m e s e r i e s ，t h e r ei st i m e s e r i e sp i e c e w i s el i n e a rr e p r e s e n t a t i o n a n o m a l yd e t e c t i o no ft h e f r a m e w o r k ，a d d i n gt h ei d e ao fas l i d i n gw i n d o wb a s e do nt o da n o m a l yp a t t e md i s c o v e r y a l g o r i t h m ，f o rd e t e c t i o no fl o c a la n o m a l y i nt h em i n i n gs e q u e n t i a lp a t t e r n s ，t h ef r a m e w o r k u s e sa ni m p r o v e da l g o r i t h m ，w h i c hi sb a s e do np r e f i x s p a n b yr e m o v i n gt h en o n - f r e q u e n t i t e m s e t sa n dd e t e r m i n i n gt h er e l a t i o n s h i pb e t w e e np r o je c t i o ns e q u e n c en u m b e ra n dt h e n u m b e ro fm i n i m u ms u p p o r t ，t or e d u c eu n n e c e s s a r ys t o r a g es p a c ea n di m p r o v et h eq u e r y s p e e d m i n i n go fm u l t i p l et i m es e r i e so ft h ef r a m e w o r ku s e df r e q u e n tp a t t e md i s c o v e r y a l g o r i t h mi nn o n s y n c h r o n o u sm u l t i - t i m es e r i e s e x p e r i m e n t sf o r t h ea b o v e m e n t i o n e d a l g o r i t h md e m o n s t r a t e dt h ef e a s i b i l i t ya n de f f e c t i v e n e s so fe v e r ya l g o r i t h m s e x p e r i m e n t ss h o wt h a tt h i sf r a m e w o r kh a sb e e nc o m p l e t e dw e l li na b n o r m a lp a t t e m s d e t e c t i o no ft h ep r o c e s so fs t e e l r o l l i n g ， 弱w e l la st h em i n i n go ft h ei n t e r r e l a t i o n s h i p b e t w e e nv a r i o u sf a c t o r s t h ef r a m e w o r kc a np l a yag o o dr o l ef o ri m p r o v i n gt h eq u a l i t yo f s t e e lp r o d u c t sf o rt h ee n t e r p r i s ea n dc o n t r o l l i n gt h eq u a n t i t yo fs t e e lp r o d u c t i o n k e yw o r d s ：t i m es e r i e s ；d a t am i n i n g ；a b n o r m a lp a t t e r ；a n o m a l yd e t e c t i o n ；a s s o c i a t i o nr u l e s i i i t - 东北大学硕士学位论文 目录 目录 独创性声明i 摘要i i a b s t r a c t i i i 第1 章绪论1 1 1 论文研究的背景l 1 2 相关技术的研究现状2 1 2 1 模式表示的研究现状2 1 2 2 异常检测的研究现状4 1 2 3 序列模式挖掘的研究现状5 1 2 4 关联规则分析的研究现状6 1 3 论文研究内容及意义8 1 4 论文组织结构9 第2 章多时间序列上挖掘的框架1 l 2 1 热轧控制的领域背景1 l 2 1 1 质量数据库服务器一1 1 2 1 2 质量诊断过程一1 2 2 2 框架的提出1 2 2 2 1 框架的意义1 3 2 2 2 框架的基本内容1 3 2 3 框架实现目标l5 2 3 1 异常模式发现1 5 2 3 2 异常模式挖掘一16 2 4 ，j 、结1 6 第3 章框架中时间序列的模式表示1 7 3 1 模式表示方法的研究18 3 1 1 频域表示19 3 1 2 奇异值分解2 1 3 1 3 符号化表示2 l 3 1 4 分段线性表示2 2 3 2 本框架采用的模式表示方法2 4 3 2 1 边缘算子2 4 i v 东北大学硕士学位论文目 录 3 2 2 时间序列的t e o 表示2 5 3 2 3 算法分析2 7 3 3 小结。2 8 第4 章框架中时间序列的异常检测2 9 4 1 异常检测方法的研究2 9 4 2 时间序列的模式异常定义3 2 ， 4 3 本框架采用的异常检测算法3 4 4 4 j 、结3 5 第5 章框架中时间序列的挖掘3 6 5 1 序列模式挖掘3 6 5 1 1 相关算法研究与比较。3 6 5 1 2 本框架采用算法3 8 5 2 多时间序列上的模式挖掘4 0 5 2 1 a p d o r i 算法一4 0 5 2 2 本框架采用算法。4 2 5 3 小结。4 5 第6 章框架实现及结果分析4 6 6 1 框架实现背景4 6 6 1 1 实验的硬件条件4 6 6 1 2 数据准备4 6 6 1 3 数据预处理4 7 6 2 框架的实现4 8 6 3 结果评价4 8 6 3 1 模式表示结果及分析4 8 6 3 2 异常检测结果分析4 9 6 3 3 序列模式挖掘结果分析5 1 6 3 4 多时间序列上的挖掘结果及分析5 2 6 4 小结5 2 第7 章结束语5 3 ， 7 1 工作总结5 3 7 2 未来研究方向5 4 参考文献5 6 致谢6 1 攻硕期间参加的项目6 2 一v 东北大学硕士学位论文第1 章绪论 第1 章绪论 本章阐述了全文研究工作的背景和意义，对时间序列的模式表示、异常检测和模式 挖掘等相关问题的现状进行了研究。同时，简要介绍了全文的研究内容、相关成果以及 组织结构。 1 1 论文研究的背景 一些大型企业和组织不断深入信息化建设，因此收集了大量的数据，并利用数据仓 库( d a t aw a r e h o u s i n g ) 技术、联机分析处理技术以及数据挖掘技术为决策者提供了定 量化的决策依据。数据仓库系统已经成为企业和组织生产经营决策不可或缺的辅助工 具。数据仓库经过多年的发展，其技术也日趋成熟，己在商务活动中发挥重要的作用。 在这些保存的历史数据中，绝大部分都是根据时间顺序对历史事件的记录，称之为 时态数据( t e m p o r a lc l a m ) 。根据记录数据类型的不同，时态数据主要包括三种类型：时间 序列，事务序列和事件序列。 所谓时间序列( t i m e s e r i e s ) 【1 】就是按照时间先后顺序排列的各个观测记录的有序集 合，其中观察记录是数值类型的。对时间序列数据进行分析，可以揭示事物运动、变化 和发展的内在规律，对于人们正确认识事物并据此作出科学的决策具有重要的现实意 义。 时间序列在商业、经济以及科学观测等各个社会领域中都广泛存在，比如金融证券 市场中每天的股票价格；商业零售行业中，某项商品的周期销售额；气象预报研究中， 某一地区的气温与气压读数；以及在生物医学中，某一症状病人在每个时刻的心跳变化 等等；钢厂每天的精轧出口温度数据、每天的卷曲温度数据、以及每天的宽度与厚度数 据等都是时间序列。 传统的时间序列分析是作为概率统计学科的一个课题来研究的，经过几十年的发 展，己经奠定了比较完善的理论基础，在实际应用中也发挥了重要的作用。传统的时间 序列分析着重研究具有随机性的动态数据，研究方法着重于全局模型的构造。常用的方 法有自回归滑动平均( a r m a ) 模型等。 基于关联规则分析的方法是一种近年来发展起来的新方法。对于时间序列的分析往 往涉及到多个变量。从广义上讲，关联分析是数据挖掘的本质。既然数据挖掘的目的是 发现数据背后的潜在知识，那么这种知识一定是反映不同对象之间的关联。它集中在数 东北大学硕士学位论文第1 章绪论 据库中对象之间关联及其程度的刻画。关联知识反映一个事件和其它事件之间的依赖或 关联。数据库中的数据一般都存在着关联关系，也就是说，两个或多个变量的取值之间 存在某种规律性。数据库中的数据关联是现实世界中事物联系的表现。数据库作为一种 结构化的数据组织形式，利用其依附的数据模型刻画了数据间的关联。但是，数据之间 的关联是复杂的、有时是隐含的。关联分析的目的就是要找出数据库中隐藏的关联信息。 多变量时间序列的关联规则挖掘问题，可以分为以下两类： ( 1 ) 多时间序列的事务内序列模式挖掘； ( 2 ) 多时间序列的跨事务序列模式挖掘。 在进行事务内序列模式挖掘时，现在普遍流行使用序列模式挖掘。序列模式挖掘 ( s e q u e n t i a lp a t t e r n sm i i l i n g ) 2 】是a g r a w a lr a k e s h 等人首先提出的一种重要的数据挖掘方 法，有着广泛的应用，如顾客购物习惯、w e b 访问模式、科学实验过程分析、自然灾害 预测、疾病治疗、药物检验以及d n a 分析等。序列模式挖掘的基本算法及早期算法都 是基于关联规则挖掘的a p d o d 性质的，即频繁模式的非空子模式都必须是频繁的。 a p r i o r i a l l ，a p d o n s o m e ，d y n a m i c s o m e ，g s p 以及s p a d e 等一系列算法都是基于a p f i o d 算法提出来的；此后，基于数据投影( d a t ap r o j e c t i o n ) 的算法由于它的高效率而广为流行， 如f r e e s p a n 和p r e f i x s p a n ；s p a d e 是一种基于格的算法，而m e m i s p 是基于内存索引 的方法；s p i r i t 使用正则表达式综合了挖掘中的各种约束( c o n s t r a i n t s ) 条件。 在进行跨事务序列模式挖掘时，经常希望能够发现不同时间序列间可能存在的关联 关系，这种关联关系一般表现为不同序列中频繁地同时或依次出现的变化模式。发现这 种多时间序列中的频繁结构模式对于人们认识内在的相互影响并据此作出合理的决策 具有重要的参考价值。 1 2 相关技术的研究现状 本节分别对模式表示、异常检测、序列模式挖掘以及关联规则分析几个部分进行了 现状的研究。 1 2 1 模式表示的研究现状 时间序列数据挖掘的对象通常是海量的时间序列数据，其短期波动频繁、大量噪声 干扰以及非稳态的特点使得直接采用原始时间序列进行相似性查询、时间序列分类和聚 类、时序模式挖掘等工作不但效率低下，甚至会影响时间序列数据挖掘的准确性和可靠 性。因此，许多研究者提出了时间序列的模式表示方法，从更高层次上对时间序列重新 2 -z - 东北大学硕士学位论文第1 章绪论 进行描述，在时间序列的模式表示上进行数据挖掘。时间序列模式表示的基本思想是从 时间序列中提取特征，将时间序列变换到特征空间，采用特征空间的特征模式来表示原 始时间序列。时间序列的模式表示有两个优点：首先是压缩了时间序列数据，能够提高数 据挖掘工作的效率；其次时间序列的模式表示在一定程度上保留了时间序列的主要特 征，去除了一些次要细节，更能反应时间序列的变化情况，有利于数据挖掘的进行。 时间序列的模式表示方法主要可以分类四种类型：频域表示法、奇异值表示法、符号 表示法以及分段线性表示法。 频域表示的基本思想将时间序列看作是一个离散信号，采用离散傅立叶变换 ( d i s c r e t ef o u r i e rt r a n s f o r i l l ，d f n 或者离散小波变换( d i s c r e t ew a v e l e tt r a n s f o r l i l ，d w t ) 将时间序列从时间域映射到频率域空间，用频谱来表示原始时间序列【3 一钉。对于大部分 信号来说，能量主要集中在几个主要的频率上，因此可以用很少的几个频率来近似表示 原始时间序列，达到数据压缩的目的，而且能够较好地保持时间序列的主要形态。 奇异值分解( s i n g u l a rv a l u ed e c o m p o s i t i o n ，s v d ) 是一种常见的降维方法，已经成功 用于图像和文本的索引【5 卅。时间序列的s v d 表示方法【7 】与其它的模式表示方法不同， 它是对整个时间序列数据库的整体表示，是对整个时间序列数据库的特征提取和变换。 作为线性变换，s v d 方法在数据重构上误差最小，这使得s v d 在一些情况下能够取得 很好的性能。但是，s v d 表示方法的时间复杂度为o ( m n 2 ) ，其中m 是指时间序列数据 库的大小，n 是指时间序列的平均长度。当插入或者删除一条时间序列时，整个时间序 列数据库的s v d 表示都必须重新计算，时间代价很高。 符号化表示就是通过一些离散化方法将时间序列的实数值或者一段时间内的时间 序列波形映射到有限的符号表上，将时间序列表示为有限符号的有序集合，即字符串。 符号化表示的优点在于可以利用许多字符串研究领域的成果，缺点在于如何选择合适的 离散化算法，解释符号的意义，以及定义符号之间的相似性度量。a g r a w a l 等人将时间 序列的波形符号化，引入多种符号算子【3 1 ；p a r k 等人直接将时间序列的值采用等宽离散 化方法和最大墒方法符号化【9 】；w hh u a n g 等人将时间序列相邻点的变化率符号化 【1 0 】； 蒋嵘等提出了基于云模型的符号化方法【l l 】。 时间序列的分段线性表示( p i e c e w i s el i n e a rr e p r e s e n t a t i o n ，p l r ) 是指采用首尾相邻 的一系列线段来近似表示时间序列。利用线段来近似表示时间序列的思想最早可追溯到 p a v l i d i s t l 2 1 ，他们指出分段线性表示有数据压缩和过滤的作用，而且具有时间多解析的 特点。时间序列p l r 表示中线段的数目决定了对原始时间序列的近似粒度。线段越多， 线段平均长度就越短，反应了时间序列的短期波动情况：线段越小，线段平均长度就越 3 东北大学硕士学位论文第1 章绪论 长，反应了时间序列的中长期趋势。 时间序列的p l r 表示简单直观，而且具有许多优点，得到众多研究者的重视，是 一种很有希望的模式表示方法【1 3 1 9 】。 与时间序列的分段线性表示思想类似的还有分段多项式表示，采用多项式函数而不 是线段来近似表示一段时间范围内的时间序列。当多项式的阶为l 时，则退化为时间序 列的分段线性表示。 1 2 2 异常检测的研究现状 近几年，时间序列的异常研究渐渐兴起，成为时间序列数据挖掘的一个新热点。对 于时间序列，并不关心单个序列点的异常，而是关心时间序列在一段时间内的异常变化 情况。 目前，时间序列的异常还没有一个公认的定义，许多研究者都提出了不同的异常定 义，与时间序列异常相关的术语包括“新颖性( n o v e l t y ) t 2 0 。2 3 】、不规则 ( a n o m a l y ) 2 4 。2 5 1 、 “奇异 ( s u r p r i s e ) 2 睨7 1 、“偏离 ( d e v i a n t ) 2 8 1 和“异常( o u t l i e r ) 2 9 】等。 d i p a n k e r 提出采用人工免疫系统的负选择( n e g a t i v e s e l e c t i o n ) 机制来检测时间序列的 新颖模式。负选择机制可以辨别自我( s e l f ) 和异己( n o n s e l f ) ，其中s e l f 表示正常的数据模 式，用于训练检测器( d e t e c t o r ) 模型，n o n s e l f 表示根据检测器模型超出某个方差闽值的 数据模式，被定义为时间序列的新颖性。 m a 等人采用支持向量回归模型来对历史事件序列进行训练，当新来的时间序列数 据偏离该模型时，认为是一个新颖事件( n o v e l t ye v e n t ) 。 j a g a d i s h 等人将时间序列上的异常描述为偏离( d e v i a n t ) 点，偏离点是时间序列上那 些与相邻点具有显著差异的序列点，采用时间序列的最优直方图表示方法来检测时间序 列的偏离。 s h a h a b i 提出了改进的t s a t r e e 算法，实现了模式的相似性查询和奇异模式 ( s u r p r i s i n gp a t t e r n ) 的发现，他们把奇异模式定义为时间序列上的突然变化，通过小波系 数的局部极大值来发现。但是，他们对异常模式的定义是建立在小波系数的基础上，因 此不够准确和全面，有些奇异模式无法发现。 k e o g h 等人【3 0 】提出t a r z a n 算法，将那些出现概率与期望发生概率不符的模式定义为 奇异模式，采用隐马尔科夫模型来计算模式的期望发生概率。 k e n j i 采用a r 模型对历史时间序列数据进行训练，根据a r 模型对新来的序列点与 模型的偏离程度进行打分，分高的认为是时间序列的异常。 4 东北大学硕士学位论文 第1 章绪论 1 2 3 序列模式挖掘的研究现状 序列模式挖掘( s e q u e n t i a lp a a e mm i n i n g ) 是数据挖掘中非常重要的一个研究领域，最 早是由r a k e s ha g r a w a l 和r a m a k r i s h n a ns r i k a n t 在针对超市中购物篮数据的分析提出来 的。序列模式挖掘是要找出序列数据库中所有超过最小支持度阈值的序列模式。它有着 广泛的应用领域：商业组织利用序列模式挖掘去研究客户购买行为模式特征、计算生物学 中序列模式挖掘用来分析不同氨基酸突变模式、用户w e b 访问模式预测以及d n a 序列 分析和谱分析。序列模式挖掘与关联规则挖掘在许多方面相似，但它更关心数据之间顺 序的关联性。 大多数早期序列模式挖掘算法都是基于a g r a w a l 提出的关联规则挖掘算法a p r i o r i ， 它的特性是频繁模式的任何子模式都是频繁的。基于这个启发，研究者提出一系列类 a p r i o r i 算法，如a p r i o r i a l l l 3 1 1 、a p r i o r i s o m e 、d y n a m i c s o m e 。这些算法的主要缺点是遍 历数据库次数太多，而且产生了太多的候选序列，因此效率并不高。 s r i k a n t 等人提出了g s p ( g e n e r a l i z e ds e q u e m i a lp a m ) 方法【3 2 1 。该方法也是基于 a p r i o r i 的。在g s p 中候选序列的数目大大减少了，而且在挖掘过程中引入了时间约束 和概念分层来生成更多知识，因此g s p 相对于a p r i o r i a l l 有着较好的性能。 z a k i 提出了s p a d e 方法【3 3 1 。该方法同样是基于a 研o r i 的。s p a d e 算法是利用格 技术和简单的连接方法来挖掘频繁序列模式的一种高效算法。它仅需扫描三次数据库即 可挖掘出所有的频繁序列；同时利用格技术将挖掘搜索空间分解为若干个较小的搜索空 间，每个小的搜索空间可以存储在内存中。实验表明，s p a d e 方法性能要优于a p r i o r i a l l 和g s p 。 基于a p r i o r i 特性的算法都存在以下问题：1 ) 如果序列数据库的规模比较大，则有 可能产生大量的候选序列模式；2 ) 需要对序列数据库进行循环扫描；3 ) 对于序列模式 的长度比较长的情况，算法很难处理。这是由a p r i o r i 特性带来的，不可避免。 随后学者们又提出了一系列基于数据投影的算法。这些算法主要使用数据库投影方 法来使下一次遍历的数据库变得更小，不需要产生候选序列，只要根据它们的前缀递归 地将后缀投影到投影数据库中，然后对投影数据库进行挖掘来得到频繁序列模式。 韩家炜在2 0 0 0 年提出的f r e e s p a n 算法【3 4 1 ，它将频繁序列和频繁模式的挖掘统一起 来，把挖掘工作限制在投影数据库中，还能限制序列分片的增长。它能有效地发现完整 的序列模式，同时大大减少产生候选序列所需的开销，比基于a 研o r i 的g s p 算法快很 多。 p e i 在2 0 0 1 年提出的p r e f i x s p a n 算法p 5 1 。p r e f i x s p a n 是f r e e s p a n 的改进算法，即通 5 东北大学硕士学位论文第1 章绪论 过前缀投影挖掘序列模式。其基本思想为：序列数据库投影时，并不考虑所有可能出现的 频繁子序列，而只检验前缀序列，然后把相应的后缀序列投影成投影数据库。每个投影 数据库中，只检查局部频繁模式，在整个过程中不需要生成候选序列。 l i n 和l e e 于2 0 0 2 年提出的m e mi s p 算法【3 6 】则是基于内存索引的。m e mi s p 只需 要遍历一次或最多两次数据库，并且它避免生成候选序列和投影数据库。实验结果表明， m e mi s p 比g s p 和p r e f i x s p a n 要高效，而且对于数据库大小和数据序列数目有着良好 的线性可伸缩性。 g a r o f a l a k i s 等人通过利用正则表达式约束方法提出了s p i r i t 算法【3 7 1 。它通过正则 表达式约束来挖掘用户特定序列模式。这种方法避免了挖掘用户不感兴趣的模式的浪 费，同时也避免了挖掘那些潜在的并无用处的模式。 1 2 4 关联规则分析的研究现状 a g r a w a l 等于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规则问题，并 设计了一个基本算法【3 引，其核心是基于频集理论的递推方法，即基于两阶段频集思想的 方法，将关联规则的设计分解为两个子问题： ( 1 ) 发现所有支持度不小于最小支持度的项目集，即频集。这个子问题是最重要的， 开销最大，因此各种算法主要致力于提高发现频集的效率。 ( 2 ) 根据所获得的频繁项集，产生相应的强关联规则。根据定义这些规则必须满足最 小信任度阐值。 算法的基本思想是首先找出所有的频集，这些项集出现的频繁性至少和预定义的最 小支持度一样。然后由频集产生强关联规则，这些规则必须满足最小可信度。 a p r i o r i 算法有两个致命的性能瓶颈：( 1 ) 多次扫描事务数据库。( 2 ) 可能产生庞大的 候选集。因此许多学者提出了不同的优化算法： ( 1 ) 减少候选项集的数量杂凑算法。p a r k 等在1 9 9 5 年提出了一个高效地产生频 集的、基于杂凑( 1 l a s h ) 的算法- d y n a m i ch a s h s i n ga n dp r u n i n g ( d h p ) 算法【3 9 。4 0 1 。通过实 验可以发现寻找频集主要的计算是在生成频繁2 项集上。d h p 利用一个杂凑表在计算 频繁1 项集时先大概计算出2 项集的支持度，从而减少了候选2 项集的数量。d h p 还 采用了数据库修剪技术，通过修剪掉那些不包含频集的事物集以减小下一次循环中数据 库的大小。 ( 2 ) 减少扫描的数据量a p r i o r i t i d 算法【4 l 】。减少用于未来扫描的事务集的大小的 基本原理是：一个事务不包含长度为k 的大项集，则必然不包含长度为k + l 的大项集。从 而就可以将这些事务移去，这样在下一遍的扫描中就可以减少进行扫描的事务集的个 - 6 - 东北大学硕士学位论文第1 章绪论 数。这个就是a p r i o r t i d 算法的基本思想。 ( 3 ) 减少扫描的次数划分算法【4 2 1 。s a v a s e r e 等设计了一个基于划分的算法，这个 算法采用了“分而治之 的方法，先把数据库从逻辑上分成几个互不相交的块，划分的 原则是使得每个分区的数据都能存入内存，并且各个分区的支持度阐值和全局的支持度 阐值相同。划分算法的过程是：首先对每个分区分别计算局部大项集( 如果项集在分区的 支持度不小于支持度阈值，则称为局部大项集) ，再将结果合并得到全局大项集( 如果项 集在整个数据库中的支持度不小于支持度闽值，则称为全局大项集) 。 ( 4 ) 采样( s a m p l i n g ) 。s a m p l i n g 算法【4 3 】是由t o i v e n e n 提出的。基本思想是对给定数据 的一个子集进行挖掘，其核心是随机从数据集d 中采集样本s ，然后搜索s 中的频繁项 集。样本s 的大小以能够在内存中完成频繁项集的挖掘为准，因此整个只需要扫描一遍 数据库，由于搜索的是s 中的频繁项集而不是d 中的，因此可能漏掉一些全局的频繁项 集。这是一种以效率换取准确性的方法，在对于效率要求较高的应用场合极具意义和重 要性。 ( 5 ) 动态项集计数( d y n a m i ci t e m s e tc o u n t i n g ) 。b r i n 等人提出了动态项集计数( d i c ) 算法m 】。该算法在添加一个新的候选集之前，先估计一下是不是它的所有子集都是频繁 的。算法将项目集分成四种不同的状态：确认的频繁集、确认的非频繁集、可疑的频繁集 和可疑的非频繁集。d i c 算法把数据库分成若干个特定大小的区间。首先计算候选1 项目集在第一个区间上的支持度，根据这些支持度产生候选2 项目集，并且2 项目集的 支持度和1 项目集的支持度在剩余的区间上继续计算。算法的停止条件是没有新的候选 集产生和所有候选集都在整个数据库上计算了支持度。d i c 算法通过区间划分减少遍历 数据库的次数，但是它的性能也是和数据分布密切相关的。 ( 6 ) 基于栈变换的算法。惠晓滨等提出了一个基于频繁模式栈变换的高效关联规则算 法f p s t t 4 5 1 ，该算法采用一种频繁模式栈的数据结构来储存所有的频繁模式信息，所有 的栈单元都具有偏序关系，并分成构造算法和变换算法两个子算法，算法效率提高，且 在数据集的记录数较大时有很好的线性性和伸缩性。 ( 7 ) 减少冗余规则的算法。吴伟平等提出了一种无冗余快速关联规则发现算法【4 6 1 ，该 算法基本原理与a p r i o r i 算法相似，但采取了不同的计算候选项集支持度的方法。首先 通过对数据库的一次搜索得到高频1 项集，然后使用一个链表得到其他频繁项集。规则 生成的方法也与a p d o n 算法不同。该算法首先以最大频繁项集中的某一项目为前件生 成规则，再讨论前件中包含该项目的子规则。所以，该算法所需的i o 次数较少且内存 开销适中，消除了简单和严格冗余规则，减少了发现的规则数量，同时提高了规则发现 - 7 - 东北大学硕士学位论文第1 章绪论 的速度。 以上方法都是基于a 研o r i 的频集方法进行了一些优化，但是a 研o r i 方法一些固有 的缺陷还是无法避免：可能产生大量的候选集；生成候选项目时由于模式匹配引起巨 大时空开销；多次扫描数据库导致的f o 瓶颈。 j h a n 等提出了不产生候选频繁项集的方法却p 树频集算法【4 7 1 。采用分而治之的 策略，在经过第一遍扫描之后，把数据库中的频集压缩进一棵频繁模式树( f p t r e e ) ，同 时依然保留其中的关联信息，随后再将f p t r e e 分化成一些条件库，每个库和一个长度 为1 的频集相关，然后再对这些条件库分别进行挖掘。f p t r e e 只需对数据库进行两次 扫描，而且避免了产生大量候选集的问题。实验表明，f p t r e e 对不同长度的规则具有很 好的适应性，同时在效率上较之a p r i o r i 算法有很大提高。 1 3 论文研究内容及意义 热轧控制中传统的异常诊断方法【4 s 】就是通过对热轧过程中产生的精轧出1 ：3 温度、卷 曲温度、宽度、厚度等数据分析，通过计算获取这些数据的各种统计数据，如公差范围、 命中率、相关系数等，并将这些统计数据作为异常的判断准则。此外，还将控制模型作 为指导，根据实际生产情况来改变各项控制参数以实现更加准确地诊断出异常，这些异 常代表着不同方面的影响，如操作原因、设备原因、控制原因等。这种传统的异常检测 算法存在以下两个缺点：必须通过对时间序列的所有正常行为进行学习，建立正确的训练 模型，才能够区分异常，这样，模型训练的好坏直接影响异常检测的效果；模型的好坏 还依赖于领域知识的完备性与准确性。 传统的热轧控制系统中4 9 忽略了异常原因的不确定性和复杂性。实际上，在轧制过 程中很多异常情况大都由多个原因引起，比如精轧出口温度、卷曲温度、宽度、厚度等 都是引起异常的原因，每个原因之间存在着相互关联的关系，它们的这些关联关系大都 由生产流程和控制模型所决定。这些引起异常的原因是相互影响、相互关联的，所以这 是一个复杂的多时间序列上挖掘的问题。 因此，改善热轧控制系统中的异常检测方法以及进行复杂的原因分析可以有效地提 高钢铁质量，降低钢铁生产成本，从而为钢铁企业带来更大收益、为现代化建设提供更 优质的钢材。本文提出了一个多时间序列上的挖掘框架。框架首先采用模式表示的方法 将数据进行压缩，在压缩后的数据上进行异常检测，这样既可以提高异常检测的效率， 也可以提高异常检测的准