（应用数学专业论文）多变量时间序列的预处理和聚类研究.pdf

摘要 摘要 多变量时间序列是时间序列的一个重要部分，而大部分有关于时间序列数据挖 掘的研究都是面对单变量时间序列。多变量时间序列不仅描述了各个变量的变化规 律，而且还揭示了各变量问的相互依存关系，因此，那些处理单变量时间序列的方 法和技术无法照搬到多变量时间序列的研究中去。本文围绕多变量时间序列的预处 理与聚类这两个主题，进行了研究现状分析，并提出了具有针对性的改进方法。 预处理是多变量时间序列数据挖掘的重要课题，而插值是预处理的一种重要技 术。本文将保形三次样条插值引进时间序列的插值，提出了双重插值模型。此模型 两次使用保形三次h e r m i t e 插值技术对时间序列进行插值，继承了保形三次h e r m i t e 插值的优点，不需要序列上各点的导数信息便可以形成序列轨迹，容易将模型推广 到高维空间，弥补了数据库中数据点太稀疏的缺陷。以移动对象时间序列为例，双 重插值模型取得较好的实验效果，插值精度比分段线性插值、非结点样条插值和保 形三次h e r m i t e 插值更高。 多变量时间序列的变量属性可能是混合属性，即，包括数值属性和分类属性等。 针对混合属性的多变量时间序列，首先基于奇异值分解提出了一种加权矩阵覆盖的 方法，直观地判断对象间的邻居关系：然后以对象间的共同邻居数量作为多变量时 间序列相似性的新度量标准，共同邻居越多越相似；最后提出了改进的层次聚类算 法对多变量时间序列进行聚类，每一层上同时合并满足条件的若干对节点，这样减 少了噪音对聚类过程的干扰，具有较好的鲁棒性：实验结果表明，这种方法在混合 多变量时间序列的数据集上具有良好的效果，此外，在数值多变量时间序列的数据 上，实验效果比基于动态时间弯曲距离t 帅的标准层次聚类算法更好。 多变量时间序列数据预处理是聚类研究的前提，数据插值可以填补空缺值、增 加点密度和平衡序列刻度等，从而提高聚类分析的准确率。在移动对象和机器人仿 真领域的实验结果表明，本研究具有较高的实际应用价值和良好的应用前景。 关键词：多变量时间序列，预处理，保形三次h e r m i t e 插值，双重插值模型，混合 属性 中文文摘 中文文摘 时间序列是一类重要的复杂数据，普遍存在于社会的各个领域，如生物医学、 气象预报、网络入侵检测和移动对象模拟等。如何对这些时间序列数据进行有效的 分析，揭示隐藏在其背后的信息，帮助人们正确认识事物并据此做出科学的决策， 已经引起了数据挖掘领域的广泛关注。时间序列按照变量( 属性) 的数目可分为单 变量时间序列和多变量时间序列，但是目前大部分有关于时间序列数据挖掘的文献 都是面对单变量时间序列，并在这方面形成了一套较为完整的理论体系，而对多变 量时间序列的研究工作还很少。多变量时间序列不仅描述了各个变量的变化规律， 而且还揭示了各变量间相互依存关系的动态规律性，因此，那些处理单变量时间序 列的方法和技术无法照搬到多变量时间序列的研究中去。 多变量时间序列的预处理是时间序列数据挖掘的重要课题，而插值是预处理的 一种重要技术。本文围绕多变量时间序列预处理的插值技术与聚类这两个主题，进 行了研究现状分析，并提出了具有针对性的改进方法，具体内容及贡献概括如下： ( 1 ) 第一章说明本文的研究背景及意义，探讨数据挖掘的一般过程和主要技术， 着重分析了分类预测、聚类分析和关联规则三种方法；介绍本文的主要工作，以及 论文的结构安排。 ( 2 ) 第二章对时间序列的理论体系进行较为全面的概述，描述时间序列的概念， 从统计学和数据挖掘两个角度对时间序列分类，并阐述了时间序列数据挖掘的目的； 介绍时间时间序列数据挖掘的主要课题，简单探讨它们的技术分类和适用范围，总 结了这些方面的研究现状和发展前景。 ( 3 ) 第三章说明了多变量时间序列数据预处理过程中插值的意义，介绍一些常 用的插值技术，且对它们的优缺点进行分析和比较；将保形三次h e r m i t e 插值引入 时间序列的插值，并在此基础上提出了双重插值模型。双重插值模型两次使用保形 三次h e r m i t e 插值技术对时间序列进行插值，继承了保形三次h e r m i t e 插值的优点， 不需要导数信息便可以形成序列轨迹，容易将模型推广到高维空间。以移动对象时 间序列为例，将双重插值模型和其它插值技术( 分段线性插值、非结点样条插值和 保形三次h e r m i t e 插值) 进行比较，实验结果表明双重插值模型的插值精度较高。 ( 4 ) 第四章介绍了数值多变量时间序列的一些相似性度量方法，且对它们的优 i v 中文文摘 缺点进行分析和比较，指出它们各自的适用范围；分别综述了数值多变量时间序列 和混合多变量时间序列聚类的研究现状，指出多变量时间序列聚类研究有待发展的 地方。针对混合属性的多变量时间序列，首先引进混合变量之间的协方差计算公式， 基于协方差矩阵进行奇异值分解，实现了数据的降维；然后采用加权矩阵覆盖的方 法，直观地判断多变量时间序列的邻居关系，并以对象间的共同邻居数量作为多变 量时间序列的新度量标准：对传统的凝聚层次聚类算法进行适当的改进，每一层上 同时合并满足条件的若干对节点，这样减少了噪音对聚类过程的干扰，避免聚类结 果过度集中的现象，具有较好的鲁棒性；实验结果表明，这种方法在混合多变量时 间序列的数据集上具有良好的效果，此外，在数值多变量时间序列的数据上，实验 效果比基于动态时间弯曲距离( d t 哪的标准层次聚类算法更好。 ( 5 ) 第五章全面总结了论文的总体结构与创新点，并提出了一些需要改进的地 方，以及今后值得深入研究的方向。 v a b s t r a c t t h o u g hm u l t i v a r i a t et i m es e r i e si s 距i m p o r t a n tp a r to f t i m es e r i e s ，m o s to fr e s e a r c h s o nt i m es e r i e so n l yp a y e da t t e n t i o nt ou n i v a l i a t et i m es e r i e s m u l t i v a r i a t et i m es e r i e sn o t o n l yd e p i c t st h ec h a n g i n gr u l eo fe a c hv a r i a b l e ，b u ta l s or e v e a l e st h er e l a t i o n s h i pb e t w e e n v a r i a b l e s t h u s ，t h o s em e t h o d sa n dt e c h n i q u e so i lu n i v a r i a t et i m es e r i e sc a n n o tb ea p p l i e d t om u l t i v a r i a t et i m es e r i e s d i r e c t l y t h i sp a p e rf o u c s e s o nt h ep r e p r o c e s s i n ga n d c l u s t e r i n go fm u l t i v a r i a t et i m es e r i e s b a s e do ns o m ea n a l 河so ft h e m ，s o m em o d i f i e d a p p r o a c h e sa l ep r o p o s e d p r e p r o c e s s i n gi s a ni m p o r t a n tt a s ko fm u l t i v a r i a t et i m es e r i e sd a t am i n i n g i n t e r p o l a t i n g i sa ni m p o r t a n tt e c h n i q u eo fp r e p r o c e s s i n g t h i s p a p e r i n t r o d u c e s s h a p e - p r e s e r v i n gp i e c e w i s ec u b i ch e r i m t ei n t e r p o l a t i o ni n t ot h ei n t e r p o l a t i o no ft i m e s e r i e s b a s e do nt h i st e c h n i q u e , ad o u b l ei n t e r p o l a t i o nm o d e li sp r o p o s e d l i k e s h a p e - p r e s e r v i n gp i e c e w i s ec u b i ch e r m i t ei n t e r p o l a t i o n , i td o e s n tn e e da n y i n f o r m a t i o n a b o u td e r i v a t i v e s8 0t h a ti tc a nb ea p p l i e dt oh i g hd i m e n s i o ne a s i l y i na d d i t i o n ，i tc o u l d c o m p e n s a t et h ef l a wo fd a t a b a s ei ft h er e c o r d si ni ta r es p a r s e t a k i n gm o v i n g0 b j e c t s 弱 a ne x a m p l e ，t h ed o u b l ei n t e r p o l a t i o nm o d e lg a i n sb e t t e re x p e r i m e n t a lr e s u l t st h a nl i n e a r i n t e r p o l a t i o n ，n o t - a - k n o ts p l i n ei n t e r p o l a t i o n a n ds h a p e - p r e s e r v i n gp i e c e w i s ec u b i c h e n n i t e i n t e r p o l a t i o n t h ev a r i a b l e so fm u l t i v a r i a t et i m es e r i e s ( m t s ) c a nb eh e t e r o g e n e o u sa t t r i b u t e , w h i c h c o n t a i n sn u m e r i ca n dc a t e g o r i c a la t t r i b u t e s f i r s t l y , i nt e r m so fh e t e r o g e n e o u s m u l t i v a r i a t et i m es e r i e s ，an o v e la p p r o a c ho fw e i g h t e dm a t r i xc o v e r a g ei sp r o p o s e dt o j u d g et h en e i g h b o r h o o db e t w e e nm t s b a s e do ns 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 ) h l t u r n ，an o t i o na b o u tt h en u m b e ro fc o m m o nn e i g h b o r so c i si n t r o d u c e dt om e a s u r e t h es i m i l a r i t i e s t h eg r e a t e rn c ni s ，t h em o r es i m i l a rt h e y 御e a tt h ee n d ，am o d i f i e d h i e r a r c h i c a lc l u s t e r i n ga l g o r i t h mi sp u tf o r w a r dt oc l u s t e rm t s i ne v e r yl e v e lo ft h e a l g o r i t h m ，s o m ep a i r ( s ) o fn o d e sa r em e r g e dt h a ti tr e d u c e st h ei n f l u e n c e so fn o i s e s t h e e x p e r i m e n t a lr e s u l t ss h o wt h a to u ra l g o r i t h mh a sag o o dp e r f o r m a n c eo nh e t e r o g e n e o u s d a t a s e t ，a n dp e r f o r m sb e t t e rt h a nt h es t a n d a r dh i e r a r c h i c a lc l u s t e r i n ga l g o r i t h mb a s e do n d y n a m i ct i m ew r a p p i n g ( d t w ) d i s t a n c em e t r i co nn u m e r i cd a t a s e t s t h ep r e p r o c e s s i n go fm u l t i v a r i a t et i m es e r i e si st h ep r e m i s eo fc l u s t e r i n ga n a l y s i s d a t ai n t e r p o l a t i o nc a r lb eu s e dt of i l lm i s s i n gv a l u e s ，a n di n c r e a s et h ed e n s i t yo fm t s ， a n du n i f yt h es c a l e sb e t w e e nm t s a sar e s u l t ，t h ec l u s t r i n gp u r i t yc o u l db ei m p r o v e d t h e e x p e r i m e n t s0 1 1m o v i n go b j e c t aa n dr o b o ts i m u l a t i o ns h o wt h a tt h i ss t u d yi sv a l u a b l e t op r a c t i c a la p p l i c a t i o na n d h a sag o o dp r a c t i c a lp r o s p e c t k e y w o r d s ：m u l t i v a r i a t et i m es e r i e s ，p r e p r o c e s s i n g ，s h a p e - p r e s e r v i n gp i e c e w i s ec u b i c h e f i m t ei n t e r p o l a t i o n , d o u b l ei n t e r p o l a t i o nm o d e l , h e t e r o g e n e o u sa t t r i b u t e s h i 论文独创性和使用授权声明 福建师范大学硕士学位论文独创性和使用授权声明 本人( 姓名) 皇飞豹学号2 q q 鱼q 鱼2 专业应用数堂所 呈交的学位论文( 论文题目：多变量时间序列的预处理和聚类研究) 是 本人在导师指导下，独立进行的研究工作及取得的研究成果。尽我所知， 除论文中己特别标明引用和致谢的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的研究成果。对本论文的研究工作做出贡献的 个人或集体，均已在论文中作了明确说明并表示谢意，由此产生的一切 法律结果均由本人承担。 本人完全了解福建师范大学有关保留、使用学位论文的规定，即： 福建师范大学有权保留学位论文( 含纸质版和电子版) ，并允许论文被 查阅和借阅；本人授权福建师范大学可以将本学位论文的全部或部分内 容采用影印、缩印或扫描等复制手段保存和汇编本学位论文，并按国家 有关规定，向有关部门或机构( 如国家图书馆、中国科学技术信息研究 所等) 送交学位论文( 含纸质版和电子版) 。 ( 保密的学位论文在解密后亦遵守本声明) 学位论文作者签名：枷匀 签字日期 护7 年彳月妇 指剐獬：却钥乇 签字日期：跏阳月f 3 日 第一章绪论 1 1 研究背景及意义 第一章绪论 近几十年来，随着计算机网络和数据存储技术的迅速发展，人们利用信息技术 产生和搜集数据的能力大幅度提高，数以千万计的数据库被用于经济管理、政府办 公、科学实验和工业生产等方面。随着数据量的激增，数据泛滥和知识贫乏无可避 免地成了一对矛盾。传统的数据管理系统和数据检索机制已经远远无法满足人们对 知识的渴求，我们急需一些新的工具和技术，能够高效地发现隐藏在数据背后的信 息，能够智能化且自动地把这些数据转化为有用的知识，从而解决“信息爆炸”所带 来的问题数据丰富、信息贫乏【。在这样的背景下，数据挖掘( d a t am i n i n g ) 和 知识发现( k n o w l e d g ed i s c o v e r y ) 技术应运而生并得到了蓬勃发展，越来越显示出其 强大的生命力和广阔的前景，各项技术的发展也激发了数据挖掘的开发、应用和研 究的兴趣。数据挖掘和知识发现可以说是信息技术发展的一个必然趋势，它们使数 据处理技术进入了一个更高的阶段。 时间序列是一类重要的复杂数据，普遍存在于社会的各个领域，如生物医学、 气象预报、网络入侵检测和移动对象模拟等。一般来说，时间序列泛指那些与时间 有关的数据集合，按照其出现时间的先后顺序进行排列。时间序列数据挖掘( t i m e s e r i e sd a t am i n i n g , t s d m ) 是数据挖掘的主要内容，是近年来相当热门的研究领域， 许多学者都相继投入该方面的研究。对于时间序列的研究，如时间序列分割、相似 性度量、异常检测和聚类分析等，目前主要针对单变量时间序列，并在这方面形成 了一套较为完整的理论体系。多变量时间序列是时间序列的一个重要部分，而关于 这方面的研究却仍然处在萌芽状态。相对于单变量时间序列，多变量时间序列有许 多独特的性质，因此原有的那些方法无法直接照搬到多变量时间序列的研究中。 多变量时间序列包含两个或两个以上的变量( 属性) ，变量间相互影响。时间 序列数据库需要存储大量的数据，尤其是多变量时间序列，如果序列历时较长，那 么将占用数据库很大的存储空间。在大多数情况下，我们只是基于一定的采样刻度 记录时间序列各个点的测量值，根据数据库的存储能力确定采样刻度的大小。许多 采样刻度貌似细小，但是相对于实际情况却有点偏大，如汽车的移动轨迹，每3 0 福建师范大学卓飞豹硕士学位论文 秒记录一次汽车地理位置的信息，包括经度坐标和纬度坐标等，于是形成了一个多 变量时间序列，然而相对实际情况，汽车时隔3 0 秒会移动几十米的距离，这样使得 序列上点的间隔太稀疏，导致数据信息丢失，甚至影响数据挖掘的准确度。为克服 数据库存储空间和数据挖掘准确度之间的矛盾，我们需要对多变量时间序列进行预 处理，采用插值的办法增加多变量时间序列的点，为多变量时间序列的其它数据挖 掘工作打下基础。 现实生活中存在着许多多变量时间序列，它们某些变量的测量值无法用数值表 示，而是采用符号进行标记，这些的符号和数值共存的多变量时间序列，既混合多 变量时间序列，是时间序列数据挖掘工作的难点。混合多变量时间序列的聚类是一 个复杂的过程，首先是不同属性的变量难以确定孰轻孰重的关系，也就导致了序列 间的相似性难以度量。我们在研究多变量时间序列聚类前，着手研究了多变量时间 序列的相似性度量。相似性度量是聚类的基础，到目前为止，关于多变量时间序列 的度量的研究集中于数值时间序列，因此需要在前人的基础上进行开拓创新，并将 其应用到多变量时间序列的聚类研究中。 1 2 数据挖掘的过程与方法 数据挖掘就是从大量数据中获取有趣的或者有价值信息的过程，它汇集了统计 学、机器学习、数据库和人工智能等学科的知识，是- j , - j 新兴的交叉学科。这些学 科都致力于数据分析的某些方面，而数据挖掘是将它们有机结合。 1 2 1 数据挖掘的一般过程 数据挖掘不是一个简单的线性过程，包括很多的反馈回路在内，其中某几个步 骤可以重复进行，也可以在整个流程中进行循环，以保证挖掘的知识准确可靠。 u s a m af a y y a d 等人定义了一个数据挖掘处理模型【2 】，其中包括数据准备、数据选择、 数据预处理、数据缩减、数据挖掘目标确定、挖掘算法确定、数据挖掘、模式解释 及知识评价九个处理步骤： ( 1 ) 数据准备 了解应用的范围，预先准备数据挖掘相关领域的背景知识，明确用户的需求， 生成目标数据集。 第一章绪论 ( 2 ) 数据选择 根据用户的要求从数据库中提取与数据挖掘相关的数据；数据数据挖掘将主要 从这些数据中进行知识挖掘。 ( 3 ) 数据预处理 主要是对上一阶段选择的数据进行再加工，去除噪声和奇异值，检查数据的完 整性，对丢失的数据进行插值和预测等。 ( 4 ) 数据缩减 数据变换和压缩，根据知识发现的任务目标，查找有用的特性来表示数据，对 数据进行降维压缩或投影转换等，在不影响大局的前提下，有效地减少变量的数目。 ( 5 ) 数据挖掘目标确定 根据用户的要求，了解最终用户的目标。一般来说，目标可以是关联规则的发 现，数据分类，回归，聚类，数据汇总，概念描述，相关分析建模或者异常检测等 等。 ( 6 ) 挖掘算法确定 选取合适的算法，如机器学习、统计分析和支持向量机等，确定合适的模型和 参数，查找感兴趣的模式，使得数据挖掘算法与整个数据挖掘的评判标准相一致。 ( 7 ) 数据挖掘 利用选定的数据挖掘算法从数据中提取出用户感兴趣的知识。 ( 8 ) 模式解释 对发现的模式进行解释。在此过程中，为了剔除冗余无关的知识，可能会返回 到前面的某些处理步骤，使得最终得出的知识更有效，再将这些知识转换成用户容 易理解的形式。 ( 9 ) 知识评价 选择评价指标和定义评价体系，尽量直观地表示挖掘结果，比如采用图表方式 表示实验结果：筛选数据挖掘结果中有用的部分，对发现的知识进行一致性检验。 1 2 2 数据挖掘的主要技术 ( 1 ) 分类和预测 分类是描述和区分数据类别的模型，以便能够使用模型预测对象的类标号。预 福建师范大学卓飞豹硕士学位论文 测是利用历史数据记录来推导数据的模型，从而估计未来的可能结果。分类和回归 都可以用于预测，分类是预测类标号，返回离散值，而回归是预测空缺的或未知的 值，返回连续值。分类需要在训练样本集上构造分类器，构造方法有贝叶斯方法、 决策树方法、神经网络方法和遗传算法等等。 贝叶斯分类方法：是统计学分类方法，预测类成员关系的可能性，如，样本属 于某个类的概率。贝叶斯分类的基础是贝叶斯定理【3 1 。设x 是数据元组，日为某种 假设，e ( x ) 、p ( h ) 分别为x 和日的先验概率；p ( x 1 日) 为在条件日下，x 的后 验概率；p ( h i x ) 为在条件x 下，日的后验概率。那么贝叶斯定理是： p ( hx ) ：p ( x ih ) p ( h ) ( 1 1 ) p 【爿) 最常用的贝叶斯分类方法有两种，一种是朴素贝叶斯分类，另一种是贝叶斯信 念网络。 决策树方法【4 】：类似于流程图的结构，其中每个内部节点表示在一个属性上的 测试，每个分支代表一个测试输出，而每个树叶节点存放一个类标号。决策树的构 造是一种自上而下，分而治之的归纳过程，分为建树阶段和剪枝阶段。 建树阶段：首先选取样本的每个属性都作为根节点，把该属性的所有可能值 作为子节点，这样整个训练集就被分成与属性对应的几个子集，然后采用广度优先 策略对每个子树进一步划分，直到划分不再有意义时，决策树停止生长。 剪枝阶段：利用剩余数据检验决策树，如果决策树不能正确描述所研究的问 题，就要对其进行必要的调整，包括剪枝和增加节点，直到决策树的每个分枝都正 确为止。决策树在内部节点进行属性值的比较，在叶节点得到结论，从根节点到叶 节点的每一条路径都对应着一条规则，这样整棵决策树就对应着一组析取表达式规 则。 具体的决策树算法有i d 3 算法和c 4 5 算法【5 1 。 ( 2 ) 聚类分析 聚类( c l u s t e r i n g ) 是把一组对象按照相似性归为若干类，聚类形成的每一个组称 为类( c l u s t e r ) 。在多维数据空间中，数据点通常不会均匀分布。数据聚类方法可以 找出稀疏和稠密的位置，进而发现数据集的整个分布模式。聚类分析算法可以分为： 划分聚类方法、层次聚类方法、基于密度的聚类方法、基于网格的聚类方法和基于 第一章绪论 模型的聚类方法。 划分聚类算法( p a r t i t i o n i n gc l u s t e r i n gm e t h o d ) 把数据集划分成七个不相交的簇， 基本思路是：首先从数据集中选取k 个对象作为簇的原型，然后根据就近原则，将 其它对象分配给这些原型所在的簇。划分过程中必须满足两点要求：一是每个簇至 少包含一个对象，二是每个对象只能属于一个簇。为了达到全局最优，基于划分的 聚类需要穷举所有可能的划分，常见的有k - m e m s 和k - m e x i o i d 方法。 层次聚类算法c r l i 髓a r c h i c a lc l u s t e r i n gm e t h o d ) ：对给定数据集创建层次分解的 树，所有对象组成一棵树。根据层次分解的形式，可分为分裂法和凝聚法。分裂层 次聚类法：自顶向下分解，开始将整个数据集视为一个簇，每次迭代，簇分裂为更 小的簇，直到每个簇中只有一个对象，或者满足其它终止条件；凝聚层次聚类法： 自底向上分解，开始将每个对象视为单独的节点，然后逐层合并相近的节点，直到 所有的对象被并为一个节点，或者满足其它终止条件。层次聚类方法的可伸缩性比 较差，一旦完成一个步骤，就不能撤销。因此如果中间某个步骤出错，问题将一直 被遗留到最后。层次聚类方法有c u r e 算法 4 1 、b i r c h 算法【7 】和r o c k 算法( 8 j 等。 ( 3 ) 关联规则 关联规则挖掘是用于发现交易数据库中不同商品( 项) 之间的联系。典型的关 联规则形式是购物篮分析，用于发现交易数据库中不同商品之间的联系，通过这些 规则找出顾客购买行为模式，如购买了某一商品对购买其它商品的影响【3 1 。关联规 则一般是用支持度( s u p p o r t ) 和置信度( c o n f i d e n c e ) 来评价的。设卢 也，厶 是项的 集合，亦称项集。设任务相关的数据d 是数据库事务的集合，其中每个事务r 是项 的集合，使得z ，。每一个事务有一个标识符，称作t d 。设彳是一个项集，事 务r 包含彳当且仅当彳互t 。关联规则是形如a j b 在事务集d 中成立，具有支持 度s u p p o r t ，其中s u p p o r t 是d 中事务包含彳ub 的百分比，即使概率p ( a l j 曰) 。规 则aj b 在事务集d 中具有置信度c o n f i d e n c c e ，其中c o n f i d e n c c e 是d 中包含事务 彳的同时也包含曰的概率，即条件概率p ( bi 彳) 。其一般表示方式是： s u p p o r t ( a 男) = p ( a u b )( 1 2 ) c o n f i d e n c e ( aj 曰) = p ( bl 彳)( 1 3 ) 挖掘关联规则问题就是产生支持度和可信度分别大于用户给定最小支持度 福建师范大学卓飞豹硕士学位论文 ( m i ns u p ) 和最小置信度( m i nc o n f ) 的规则，也称为强规则。包含k 个项的项集称为 缸项集；项集出现的频率是包含项集的事物数，又称为项集的频率或计数。如果项 集，的相对支持度大于预定义的最小支持度阈值，则称，是频繁项集。 一般来说，关联规则的挖掘可以看作两步的过程： 识别所有的频繁项目集，即其支持度不低于最低支持度的项目集； 从频繁集中构造其信任度不低于最低信任度的规则。 关联规则最著名的算法是a g r a w a l 和s r i k a n t 提出的a p r i o r i 算法【9 】。a p r i o r i 算 法使用一种逐层搜索的迭代方法，将缸项集用于探索( 斛1 ) 项集。首先，通过扫描 数据库，累积每个项的计数，并收集满足最小支持度的项，找出频繁1 项集的集合。 该集合记作l l ；然后，三l 用于寻找频繁2 项集的集合三2 ，上2 用于查找三3 ，如此下 去，直到不能找到频繁k 项集【3 】。但是每次找厶都需要扫描整个数据库，时间效率 ，较低。 1 3 多变量时间序列的研究现状 时间序列按照变量( 属性) 的数目分为单变量时间序列( u 小撕a t et i m es e r i e s ， u t s ) 和多变量时间序列( m u l t i v a r i a t et i m es e r i e s ，m t s ) 。设有时间序列以d ，俨l ， ，聊；户l ，d ，其中t 代表时间序号，_ ，代表变量序号。当m 等于1 时，x a t ) y g 单 变量时间序列；若大于1 ，则为多变量时间序列。 关于时间序列的研究，目前主要针对单变量时间序列，并在这方面形成了一套 较为完整的理论体系，而对多变量时间序列的研究却很少。多变量时间序列有着多 维的性质，变量之间存在着紧密的联系，那些处理单变量时间序列的方法和技术无 法照搬到多变量时间序列的研究中去。根据综合收集到的关于多变量时间序列数据 挖掘的文献资料，目前这方面的研究成果主要分为以下几个方面： ( 1 ) 异常检测 异常检测是在数据库中找出明显偏离其它数据，不满足数据的一般模式或行为， 或与其它数据不一致的数据【2 1 ，多变量时间序列的异常检测就是找出数据集中偏离 寻常数据的时间点或者时间段，包括异常点、异常模式、异常子序列或异常全序列。 翁小清和沈钧毅提出一种基于局部稀疏系数的异常样本的识别算法【1 0 】，a h m e d 等基 于核函数( k e r n e l - b a s e d ) 在线查询多变量时间序列的异常事件【l l 】，o a t e s 等基于凝 第一章绪论 聚层次聚类算法查找异常的序列原型【1 2 1 。 ( 2 ) 趋势分析和预测 多变量时间序列往往隐藏着复杂的数据模型，基于这些模型可以对整个序列进 行趋势分析，以及预测未来的数值。杨一文和刘贵忠采用神经网络预测股票数据【1 3 】， l i u 等使用贝叶斯和决策树双分类器结合的方法预测时间序列【1 4 】。 ( 3 ) 相似性度量或查询 相似性度量包含相似度和距离两个相对的概念，是用来衡量两个( 通常是两个， 也有可能是多个) 数据或实例之间关系的标准。y a n g 等提出了一种扩展的f r o b e n i u s 范数度量多变量时间序列 1 5 】，g u a n 等提出一种称为交叉相关系数( c r o s s c o r r e l a t i o n m a t r i x ) 矩阵的度量方法【1 6 】。 ( 4 ) 聚类分析 多变量时间序列聚类算法是寻找具有相似特征的序列，包括子序列聚类和全序 列聚类。o w s l e y 等采用隐马尔科夫模型( h i d d e n - m a r k o vm o d e l s ，h m m s ) 聚集多变量 时间序列【1 7 1 ，y a n g 和z h o u 针对混合属性的数据流，提出了一种h c l u s t r e a m 的聚类 算法【1 8 】，h u a n g 等采用自组织映射和扩展的朴素贝叶斯方法对混合时间序列进行模 式识别【1 9 1 。 多变量时间序列数据库中的数据从现实中提取出来，存在着各种各样的无法避 免的缺陷，因此需要对数据集进行相应的预处理。常用的预处理技术有数据清洗、 数据合成、数据变换和数据插值等，数据插值一般用于填补空缺值、增大序列密度， 因此研究多变量时间序列的数据插值对数据挖掘的其它工作( 如预测和聚类) 有着 重要的意义。 以上的研究领域大都处理数值多变量时间序列( n u m e r i cm u l t i v a r i a t et i m e s e r i e s ) ，而对混合多变量时间序列( h e t e r o g e n e o u sm u l t i v a r i a t et i m es e r i e s ) 研究甚少， 或者只能处理混合多变量时间序列的某些方面。因此，需要深入挖掘混合多变量时 间序列的特性，寻找切实可行的方法处理实际面临的问题。 1 4 本文的主要工作 目前大部分有关于时间序列数据挖掘的文献都是面对单变量时间序列，对多变 量时间序列的研究工作还很少。多变量时间序列有着多维的性质，变量之间存在着 福建师范大学卓飞豹硕士学位论文 紧密的联系，那些处理单变量时间序列的方法和技术无法照搬到多变量时间序列的 研究中去。为了能够有效地处理多变量时间序列的预处理和聚类问题，本文着重从 以下两个方面进行了改进工作： ( 1 ) 多变量时间序列的插值研究 将保形三次h e r m i t e 插值引入时间序列的预处理，并在此基础上提出了适合时 间序列的双重插值模型，两次采用保形三次h e r m i t e 插值对原有时间序列进行插值， 填补空缺值或者增加时间序列的记录点。 ( 2 ) 多变量时间序列的相似性度量及其聚类研究 研究混合多变量时间序列为主，序列间的长度不一，提出了一种直观判别序列 对象间邻居关系的方法，将对象间的共同邻居数量作为新的相似性度量，尽可能减 少人为因素的影响；提出一种改进的层次聚类算法，在每一层同时合并若干对节点， 减少噪音对聚类过程的干扰作用，具有较好的鲁棒性。 1 5 论文组织结构 本文采用理论研究研究与实证分析相结合的方法，利用数据挖掘技术、计算数 学和时间序列分析方法的相关理论，对多变量时间序列的插值和聚类提出了富有新 意的解决办法，通过对国内外研究现状的了解和综合分析，力求从他人的研究成果 中得到启发、发现不足，从而得出有独特见解的方法和模型。本文共分为5 章，全 文结构及具体内容如下： ( 1 ) 绪论 说明本文的研究背景及意义，探讨数据挖掘的一般过程和主要技术，着重分析 了分类预测、聚类分析和关联规则三种方法；介绍多变量时间序列的研究现状，本 文的主要工作，以及论文的结构安排。 ( 2 ) 时间序列数据挖掘 对时间序列的理论体系进行较为全面的概述，给出时间序列的概念和分类，并 阐述了时间序列数据挖掘的目的；介绍时间时间序列数据挖掘的主要课题，简单探 讨它们的技术分类和适用范围，总结了这些方面的研究现状和发展前景。 ( 3 ) 多变量时间序列的数据预处理 阐述数据预处理过程中数据插值的意义，介绍了时间序列插值的研究进展，对 第一章绪论 于结合现代插值技术和时间序列本身的特点，提出了一种双重插值的时间序列插值 模型，并将该模型应用于移动对象时间序列的插值。 ( 4 ) 多变量时间序列的聚类算法 介绍了目前多变量时间序列研究文献中的一些相似性度量标准，分析它们对于 各种多变量时间序列相似性的度量效果；介绍多变量时间序列一些主要的聚类算法， 针对这些相似性度量和聚类算法存在的缺陷，提出了一种加权矩阵覆盖( w e i g h t e d m a t r i xc o v e r a g eb a s e da p p r o a c h ，w m c a ) 的聚类算法。 ( 5 ) 总结与展望 全面总结论文的总体结构与创新点，并提出了一些需要改进的地方，以及今后 值得深入研究的方向。 第二章时间序列数据挖掘 第二章时间序列数据挖掘 时间序列是一类重要的复杂数据，普遍存在于社会的各个领域，如生物医学、 气象预报、网络入侵检测和移动对象模拟等。如何对这些时间序列数据进行有效的 分析，揭示隐藏在其背后的有用信息，帮助人们正确认识事物并据此做出科学的决 策，已经引起了数据挖掘领域的广泛关注。本章首先介绍了时间序列的概念及其不 同前提条件下的分类，然后列出了时间序列数据挖掘的主要课题。 2 1 时间序列数据挖掘概述 2 1 1 时间序列数据的概念 时间序列数据是指由随着时间变化的序列值或事件，往往用数字或符号表示。 时间序列数据一般都以时间为基准呈序列状排列，测量这些值或事件的时间间隔可 以是等间距的或者不等间距的，因此时间序列数据也可以看作一种特殊的序列数据。 2 1 2 时间序列的分类 时间序列根据所研究的依据不同，可以有不同的分类。 ( 1 ) 按序列变量的数目，有单变量时间序列( u n i v a r i a t et i m es e r i e s ，u t s ) 和多变 量时间序歹u ( m u l t i v a r i a t et i m es e r i e s ，m t s ) 。若变量个数为1 ，则称为单变量时间序 列，比如股票价格是单一的数列，则为单变量时间序列；如果序列的变量数目大于 1 ，则称为多变量时间序列，比如汽车移动的时间序列包含横坐标、纵坐标等变量， 则为多变量时间序列。多变量时间序列不仅描述了各个变量的变化规律，而且还揭 示了各变量间相互依存关系的动态规律性。本文研究多变量时间序列为主，且序列 的持续时间( 长度) 可以互不相同。 ( 2 ) 按序列变量的属性分类，分为数值时间序列( n u m e r i ct i m es e r i e s ) 、符号时 间序列( s y m b o l i ct i m es e r i e s ) 和混合时间序列( h e t e r o g e n e o u st i m es e r i e s ) 。若时间序 列的所有变量为数值属性，则称为数值时间序列；若变量全部是分类属性，则称为 符号时间序列；若同时存在数值和分类属性，则称为混合时间序列。 福建师范大学卓飞豹硕士学位论文 ( 3 ) 按时间序列的连续性，分为离散时间序列和连续时间序列【2 0 1 。如果序列的 属性值所对应的时间参数为间断点，则称该序列为离散时间序列；若对应的时间参 数为连续函数，则称该序列为连续时间序列。在实际应用领域，时间序列一般采用 问断点表示，因此大部分文献都是面向离散时间序列。 ( 4 ) 按序列的统计特性分为平稳时间序列和非平稳时间序列【2 0 】。如果一个时间 序列的概率分布与时间无关，则称该序列为严格平稳时间序列，也称狭义时间序列： 如果序列的一、二阶矩存在，而且在任意时刻满足：均值为常数，协方差为时 间间隔t 的函数，则称为宽平稳( 广义) 时间序列；如果均值或协方差与时间无关， 则称为非平稳时间序列。 2 1 3 时间序列数据挖掘的目的 时间序列数据是随着时间连续变化的数据，因而其反映的大都是某个观察过程 在一定时期内的状态或表现。时间序列数据挖掘的目的就是从时间序列中检测出用 户感兴趣的模式，这些模式可以帮助人们更好地认识时间序列中蕴含的规律，加深 人们对系统或者现象的理解【2 l l 。 2 2 时间序列数据挖掘的主要任务 时间序列数据挖掘的任务，涉及从处理初始时序数据开始，到采用各种方法分 析数据，直至得到信息的整个过程。本部分以下内容将介绍时序数据挖掘中的如下 几个主要任务：数据预处理( p r e p r o c e s s i n g ) 、时间序列数据表示( t i m e s e r i e s r e p r e s e n t a t i o n ) 、分割( s e g m e n t a t i o n ) 、相似度度量( s i m i l 耐t ym e a s u r e m e n t ) 、异常检 i 9 1 l j ( a n o m a l yd e t e c t i o n ) 、聚类( c l u s t e 血曲和分类( c l a s s i f i c a t i o n ) 等。 2 2 1 时间序列的数据预处理 数据挖掘过程中，原始数据库中的数据从现实中提取出来，存在着各种各样的 无法避免的缺陷。现实世界中存在着大量的时间序列数据，而且各种数据性质各异， 不能一概而论，因此时间序列数据的预处理研究是数据挖掘研究中的一个重要方面， 也是一个极具挑战性和应用前景的研究领域，预处理方法的选择对最终数据挖掘的 第二章时间序列数据挖据 结果有着很大的影响。数据预处理泛指对得到的原始数据进行一定的加工处理，使 之能够为其它数据挖掘方法所用的过程【2 2 l 。时间序列数据挖掘常用的预处理技术有 数据清洗、数据合成、数据变换和数据插值等。 数据清洗：通过分箱( b i n n i n g ) 技术、聚类和回归等技术可以识别异常点以平 滑数据、消除噪音，以及处理不一致数据。 数据合成：主要是指将数据从多个数据源抽出融合在一起。这些数据源可能 包括多种数据库、数据立方和平面文件。 数据变换：使变化后的数据更适于进行数据挖掘。常用的技术有平滑、聚集、 概括化、正规化和特征组建等，其中正规化是比较常用的方法，有零均值正规化、 最大最小正规化。 数据插值：主要对现实存在而没有被实际记录的点进行估计，在某些情况下， 如序列数据值缺失、数据点太稀疏，以及序列之间采样刻度不一致等，可采用数