时空序列数据挖掘中若干关键技术研究.pdf

中图分类号 u d c 学校代码! q 5 3 三 密级公珏 硕士学位论文 时空序列数据挖掘中若干关键技术研究 t h er e s e a r c ho fs e v e r a lk e y t e c h n o l o g i e so ns p a t i a l t i m es e r i e sd a t am i n i n 9 1l m eb e na t am i n i n g 作者姓名： 学科专业： 研究方向： 学院( 系、所) ： 指导教师： 论文答辩日期眵多1 2 杨文涛 地图学与地理信息系统 时空数据挖掘 地球科学与信息物理学院 邓敏教授 答辩委员会主席肄鱼簦 中南大学 2 0 13 年5 月 原创性声明 i iii i i i ii i i i i i ih i ii l u lmh i y 2 4 2 3 0 0 9 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：招童蕴日期：业年月鱼日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 作者签名：盘壶邀导师签名：兰堡丝日期：蛰超年月丝日 中南大学硕士学位论文摘要 时空j 宇歹恻瑚蝴中若干关踺 支= 糊院 摘要：时空序列数据挖掘作为时空数据挖掘的一个重要分支，是专门 针对时空数据中时空序列类型的数据进行研究。时空序列数据不仅描 述了地理对象或现象存在的空间特征，而且有效地记录了地理对象或 现象随时间的演变状态，因此对其研究具有重要的意义。本文回顾了 国内外相关研究成果，结合现有的空间数据挖掘与时间序列数据挖掘 理论体系，提出了对时空序列数据进行挖掘，探讨了时空序列数据挖 掘的主要内容与技术手段，就时空序列数据挖掘的技术中存在的特定 问题，提出了相应的解决策略。本文主要工作包括： ( 1 ) 在时空序列聚类分析研究方向，针对“时序相似，空间邻 接”的聚类要求，提出了种子点扩散的时空序列聚类算法，首先选取 与空间近邻时间序列相似性最高的对象作为种子，对种子进行标记并 且将标记扩散到其空间近邻，然后选取下一个种子点，进行标记、扩 散操作，直到所有的时空序列依附的实体都被标记，该方法计算简单、 效率高并且无需进行参数的设定，避免了参数选取的主观性。 ( 2 ) 在时空序列关联规则研究方向，针对“后件已知，前件未 知”的关联条件，提出了一种约束条件下事件关联规则算法，首先在 后件目标事件已知的条件下，通过一个有效时间窗口来顾及前件事件 间及前件事件与后件目标事件在时间上的滞后因素，然后在计算前件 事件集中，只考虑对后件目标事件有效时间窗口中的候选前件事件 集，而不需要对整个事件序列中的频繁事件集进行搜索，避免对整个 事件序列中的频繁集计算，从而降低了算法的复杂度。 ( 3 ) 在时空序列预测建模研究方向，针对g m ( 1 ，1 ) 能够对“小 样本，贫信息”进行建模预测，而缺乏对空间自相关性的考虑，提出 了s t g m ( 1 ，1 ) 建模方法，此方法是结合空间自相关特性与灰色理论 预测模型，空间自相关性是对空间对象或现象在空间上的依赖性描 述，因而s t g m ( 1 ，1 ) 能够处理具有小样本的时空序列数据。 最后，总结了本文的研究成果，并展望了时空序列数据挖掘进一 步需要研究的工作。 关键词：数据挖掘；时空序列；聚类分析；关联分析；灰色模型 中南大学硕士学位论文 t h er e s e a r c ho fs e v e r a lk e y t e c h n o l o g i e so ns p a t i a l ” s e r kd a t am i n i n 9 1l m es e n e sd a t am i n i n g a b s t r a c t ：s p a t i a lt i m es e r i e sd a t am i n i n g ，a sa l li m p o r t a n tb r a n c ho f s p a t i a l t e m p o r a ld a t am i n i n gt e c h n i q u e s ，i ss p e c i f i c a l l yf o rt h es t u d yo f s p a t i a l - t e m p o r a ld a t ai nt e m p o r a ls e q u e n c ec a t e g o r i e s n o to n l yc a ni t d e s c r i b et h es p a t i a lc h a r a c t e r i s t i c so fg e o g r a p h i co b je c t so rp h e n o m e n a ， b u ta l s oc a ne f f e c t i v e l yr e c o r dt h et i m ee v o l u t i o no f t h o s e c o n s e q u e n t l y , t h er e s e a r c hi nt h i sf i e l di sm o r em e a n i n g f u l a f t e rr e v i e w i n gr e l e v a n t r e s e a r c hp r o g r e s sa n dp o i n t i n go u tt h ee x i s t i n gp r o b l e m sa n dd e f i c i e n c i e s ， t h i sp a p e rs y s t e m a t i c a l l ys t u d i e st h em e a s u r e m e n to fs p a t i a lt i m es e r i e s d a t am i n i n gi nt h e o r i e sa n dm e t h o d s t os o l v et h es p e c i f i cp r o b l e m st h a t e x i s ti nt h ed a t am i n i n gt e c h n o l o g y , s o m ec o r r e s p o n d i n gs t r a t e g i e sa r e g i v e n m a i nw o r k sa r es u m m a r i z e da sf o l l o w s ： ( 1 ) i nt h ea n a l y s i so ft h es p a t i a ls e q u e n c ec l u s t e r i n g t h i sp a p e r p r o p o s e dt h es e e dp o i n tc o u n t e de x p a n s i o nc l u s t e r i n ga l g o r i t h mt om a t c h t h ec l u s t e r i n gr e q u i r e m e n t so ft i m i n gs i m i l a ra n ds p a c ea d j a c e n t f i r s t l y , t h ea l g o r i t h ms e l e c t e da n o b j e c tw h i c hh a v et h eh i g h e s ts e q u e n c e s i m i l a r i t ya m o n gs p a c en e i g h b o r sa ss e e d ，m a r k e di ta n de x p a n d e dt ot h e n e a r s i d e t h e nc h o s et h en e x ts e e dp o i n t ，r e p e a tt h ea b o v e o p e r m i o n ，u n t i l a l lt h ee n t i t i e sw h i c ht h o s es p a t i a la n dt e m p o r a ls e q u e n c ed e p e n d e dh a v e c o m p l e t e dt h em a r k t h em e t h o di sm o r es i m p l e ，e f f i c i e n c ya n dw i t h o u t t h ec l a s sp a r a m e t e rs e t t i n g ，t h u sa v o i dt h es u b j e c t i v i t yo ft h ep a r a m e t e r s e l e c t i o n ( 2 ) i nt h es p a t i a l t e m p o r a ls e q u e n c ea s s o c i a t i o nr u l e s t h i sp a p e r p r o p o s e da na l g o r i t h mo fc o n s t r a i n t st om e e tt h er u l eo ft h el a t t e ri s k n o w n ，p r e c e d i n ge v e n t su n k n o w nc o n d i t i o n s av a l i dt i m ew i n d o ww a s f i r s t l ys e tt oa c c o u n tt h et i m el a gf a c t o rb o t he x i s tb e t w e e nt h ef r o n tt a r g e t i n c i d e n t sa sw e l la st h ep r e c e d i n ga n d1 a t t e rt a r g e te v e n t su n d e rt h e c o n d i t i o n so ft h er e a ra r ek n o w n a n dt h e nc o n c e n t r a t e di nt h ec a l c u l a t i o n o ft h ef i r s te v e n t ，c o n s i d e r i n go n l yt h ec a n d i d a t eo ft h ep r e c e d i n ge v e n t s t h a ta m o n gt h el a t t e re v e n t s e f f e c t i v et i m ew i n d o w w i t h o u tt h en e e dt o s e a r c ht h ee n t i r es e q u e n c eo fe v e n t si nt h e f r e q u e n te v e n ts e t ，t h i s a l g o r i t h ma v o i d t h ec a l c u l a t i o no ft h o s e f r e q u e n t s e ti nt h ee n t i r e s e q u e n c e ，t h e r e b ye f f e c t i v er e d u c i n gt h ec o m p l e x i t yo fi t ( 3 ) f o rt h es p a t i a l t i m es e r i e s p r e d i c t i o nm o d e l i n g ，t h i sp a p e r i i p r o p o s e dt h es t g m ( 1 ，1 ) m e t h o dt os o l v et h e d e f e c t i o no fg m ( 1 ，1 ) m o d e lf o ri tc a nm o d e la n df o r e c a s tt h es m a l ls i z ea n dp o o ri n f o r m a t i o n s a m p l e ，b u tl a c k i n g c o n s i d e r a t i o no ft h es p a t i a la u t o c o r r e l a t i o n t h e s t g m ( 1 ，1 ) m e t h o dh a sc o m b i n e ds p a t i a la u t o c o r r e l a t i o nc h a r a c t e r i s t i c s w i t hg r e yp r e d i c t i o nm o d e l b e c a u s es p a t i a la u t o c o r r e l a t i o nw a sa b l et o d e s c r i b et h es p a c e d e p e n d e n c yi ns p a t i a lo b j e c t so rp h e n o m e n a t h u s ， t h i sm e t h o dw a su s e f u l t oh a n d l et h es m a l ls a m p l ep o i n t s i nt h e s p a t i a l t e m p o r a ls e q u e n c ed a t a f i n a l l v ，t h i sp a p e rs u m m a r i z e sm a i nf i n d i n g s ，a n dh i g h l i g h t sf u r t h e r r e s e a r c hd i r e c t i o n si nt h en e a rf u t u r e k e yw o r d s ：d a t am i n i n g ；s p a t i a lt i m es e r i e s ；c l u s t e ra n a l y s i s ；c o r r e l a t i o n a n a l y s i s ；g r e ym o d e l i i i 中南大学硕士学位论文目录 目录 l 绪论1 1 1 引言1 1 2 研究背景与意义l 1 3 数据挖掘概论2 1 3 1 数据挖掘的过程3 1 3 2 数据挖掘的主要方法4 1 4 时空序列数据挖掘的研究进展及评述5 1 4 1 时间序列挖掘技术研究简介5 1 4 2 空间数据挖掘技术研究简介6 1 4 3 时空序列数据技术研究内容与研究现状8 1 5 本文的主要研究内容。1 2 2 时空序列数据的表达、相似性度量及基本性质1 4 2 1 引言1 4 2 2 时空序列数据的表达。1 4 2 2 1 基于离散化的表达1 4 2 2 2 基于时间域的表达1 5 2 2 3 基于频率域的表达1 5 2 3 时空序列的相似性度量15 2 3 1 空间相似性度量方法1 6 2 3 2 时间序列相似性度量方法17 2 4 时空序列数据的基本性质18 2 4 1 时空自相关性1 8 2 4 2 时空异质性2 0 2 5 本章小结2 1 3 时空序列聚类分析算法研究2 2 3 1 引言。2 2 3 2 基于种子扩散的时空序列聚类方法2 2 3 2 1 研究现状2 2 3 2 2 相关定义2 3 3 2 3 基于种子扩散的时空序列聚类算法2 4 3 3 实验分析一2 5 3 4 本章小结2 7 4 时空序列关联规则算法研究2 8 4 1 引言2 8 4 2 一种约束条件下时空事件关联规则算法2 8 4 2 1 时空事件关联规则构建2 8 中南大学硕士学位论文目录 4 2 2 一种约束条件下时空事件关联规则算法3 0 4 3 实验分析31 4 4 本章小结3 5 5 时空序列预测模型研究3 6 5 1 引言。3 6 5 2 时空灰色预测模型构建。3 6 5 2 1 灰色预测模型g m ( 1 ，1 ) 3 6 5 2 2 空间自相关模型3 8 5 2 3 时空灰色预测模型s t g m ( 1 ，1 ) 。3 9 5 3 实验分析3 9 5 4 本章小结4 2 6 总结与展望4 3 6 1 引言4 3 6 2 主要内容总结与创新4 3 6 3 研究展望4 4 参考文献4 5 致谢4 9 攻读硕士学位期间的科研情况5 0 v 中南大学硕士学位论文第一章绪论 1 绪论 1 1 引言 时空序列数据挖掘作为时空数据挖掘的一个重要分支，是专门针对时空数据 中时空序列类型的数据进行研究。时空数据中的时空序列数据具有明显的时间特 征，是对时空对象或现象的完整描述，时空序列数据挖掘是数据挖掘理论体系中 空间数据挖掘与时域数据挖掘的结合，然而传统的空间数据挖掘重点是以空间实 体或现象的空间特征为导向的，对时域特性缺乏重视，时空耦合性的忽视注定了 其在处理、分析时空序列数据时存在的局限性；另一方面，时间序列数据挖掘侧 重于属性随时间的变化特性，空间数据具有空间异质性、空间自相关、空间多尺 度特性等，致使照搬时间序列数据挖掘方法硬套于时空序列数据分析无法保证科 学分析的严谨性；此外，现有的研究较多集中时空序列数据建模与预测分析，对 时空序列数据挖掘缺乏系统的研究，因而对时空序列数据挖掘的研究必将成为一 个重要趋势。 本章首先介绍时空序列数据挖掘的研究背景与研究意义，然后对数据挖掘技 术进行简要的回顾，重点分析时空序列数据挖掘的内容与主要技术手段，同时对 其研究现状进行了的阐述，最后指出了本文的研究工作以及研究架构。 1 2 研究背景与意义 伴随空间信息技术的高速发展，尤其是对地观测技术的不断进步，地理信息 对国家制定发展战略与规划具有重大意义，为此我国将在2 0 1 3 年到2 0 1 5 年开展 第一次全国地理国情普查。地理国情主要是反映国家地表自然和人文地理要素的 空间分布、特征及其相互关系，传统仅依靠地理信息的静态数据进行分析已无法 满足管理决策部门的实际应用需要，必须对我国地表自然和人文地理要素进行持 续动态的数据获取与分析，为对我国科学管理与持续发展提供持续、客观、综合 的地理国情监测数据。地理国情普查是一项重大的国情国力调查，开展全国地理 国情普查，系统掌握权威、客观、准确的地理国情信息，是制定和实施国家发展 战略与规划、优化国土空间开发格局和各类资源配置的重要依据，是推进生态环 境保护、建设资源节约型和环境友好型社会的重要支撑【1 3 】。 地理国情主要包括感知信息、统计信息与分析信息。感知信息与统计信息是 地理国情的基础内容，通过对数据进行可视化处理与统计分析获取，而分析信息 是地理国情监测中深层次的内容，分析信息是在对不同时间段的地理数据进行动 态监测基础上，对其内涵进行分析，揭示对象的客观变化规律，预测其发展变化 趋势。在分析信息的获取过程中，多时态、多源、多尺度下的海量地理国情数据 需要进行动态的、高效的、智能的分析，传统的静态的空间数据分析无法适应这 中南大学硕士学位论文第一章绪论 种动态的、高效的、智能的分析需求，导致地理国情监测在分析信息的获取技术 层面面临巨大的挑战。 在大数据时代，急需要新的工具与技术手段，能够对大空间数据进行处理， 高效的、智能的将数据转化为知识，从而解决所谓的“数据海量，知识贫乏 的 科学问题。在此背景下，数据挖掘技术应运而生并呈现出蓬勃的发展趋势。数据 挖掘技术是从大量的数据中获取隐含的、未知的、有潜在使用价值信息的过程。 数据挖掘时作为一个新的交叉技术，继承了数据库技术、模式识别、人工智能、 统计学、机器学习、专家学习等技术，在各领域受到了广泛的应用。空间数据挖 掘则是数据挖掘的一个崭新的分支，是指从空间数据库中获取用户感兴趣的、未 知的、潜在有用的信息，主要对地理空间数据进行分析。 传统的空间数据挖掘大多只考虑地理实体的空间特征与专题属性特征，却忽 略了时间特征，持续动态地理国情监测的地理空间实体或现象，不仅拥有空间特 征，还具有显著的时间动态变化特征，在许多应用领域中，如气象监测、环境监 测、区域经济研究等，研究的地理空间实体或现象都是随时间发生变化的，使得 在建立应用模型中，描述与研究空间对象或现象的时间特征，才能揭示对象或现 象的客观变化规律，强调空间数据的时间动态变化特征，对获取地理国情监测中 的分析信息具有重大意义。 时空数据中的时空序列数据具有明显的时间特征，是对时空对象的完整描 述，是地理国情监测获取的最主要的数据类型，现有的研究较多集中时空序列数 据建模与预测分析，但是对时空序列数据挖掘缺乏系统的研究，为此针对时空序 列数据，本文提出从时空序列数据中发现知识。 时空序列数据挖掘是数据挖掘系统中空间数据挖掘与时域数据挖掘的结合。 一方面，传统的空间数据挖掘重点是以空间特征为导向的，对时域特性缺乏重视， 时空耦合性的忽视注定了其在处理、分析时空序列数据时存在的局限性；另一方 面，时间序列数据挖掘侧重于属性随时间的变化，空间数据具有空间异质性、空 间自相关、空间多尺度特性等，致使照搬时间序列数据挖掘方法硬套于时空实体 的分析无法保证科学分析的严谨性，时空序列数据挖掘综合了空间数据的空间特 征与专题属性随时间的演变特征，因而时空序列数据挖掘的研究必将成为一个重 要趋势。 1 3 数据挖掘概论 数据挖掘技术也称为“从数据库中进行知识发现( 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 s ，k d d ) p 99 从海量的数据中获取隐含的、未知的、有潜在使用价值信息 的过程。最早是在1 9 8 9 年国际人工智能的学术会议上提出k d d ，数据挖掘是作 中南大学硕士学位论文 第一章绪论 为一个新的交叉技术，综合了数据库技术、模式识别、人工智能、统计学、机器 学习、专家学习等方法。自1 9 8 9 年始，k d d 国际研讨会由美国人工智能协会主 办每年召开一次，重点对数据挖掘的系统应用和知识服务领域进行研究探讨。 1 9 9 3 年，i e e e 的k n o w l e d g ea n d d a t ae n g i n e e r i n g 会议出版的知识发现相关的论 文，对知识发现系统与数理统计、人工智能、机器学习、专家系统等相互之间的 联系与区别做了全面的论述，代表了当前知识发现研究的最新理论动态。1 9 9 7 年，第一本介绍知识发现理论与应用研究的期刊( ( d a t am i n i n ga n dk n o w l e d g e d i s c o v e r y ) ) 创刊。2 0 0 0 年，韩家炜教授出版了介绍数据挖掘技术的第一本著作 ：数据挖掘：概念与技术【4 5 】。 1 3 1 数据挖掘的过程 针对不同的领域和不同的应用场合，所采取的数据挖掘技术是不同的，因此 其挖掘过程也是不尽相同的。一般而言数据挖掘主要有以下步骤： ( 1 ) 理解数据和数据的来源 随着社会的发展，人类获取数据的能力越来越强，能获取的数据类型也越来 越多，人们正处于一个被数据淹没的时代。因此在进行数据挖掘之前，有必要确 认数据的来源和数据的可靠性等，同时还应了解数据的背景知识等，根据经验或 者先验知识对数据的形成初步的理解。 ( 2 ) 获取相关知识和技术 根据第一步对数据及数据源形成的理解，获取数据的实际含义，对相应领域 的知识有初步的了解，并且对需要运用那些数据挖掘技术和方法有一定的认识。 能够发现其中的一些比较的浅显的规律和规则等，为数据挖掘工作做好前期准备 工作。 ( 3 ) 整合和检查数据 由于数据的多样性和多元性，在进行数据挖掘之前有必要把所有的数据对象 整合起来，检查数据的可靠性，对其中存在疑问的地方应该通过多种途径核实， 直至数据确认可行，然后对数据进行清洗、转换、标准化等。 ( 4 ) 去除错误或不一致的数据 对于多源数据，有可能存在不同数据源之间的冲突，这是就要通过其他途径 确认正确的数据，如果无法确认，则需要对其进行剔除。对于数据集中存在明显 错误的数据则应直接剔除。 ( 5 ) 建立模型和假设 根据数据的基本特征以及数据挖掘的目的，选择合适的数据挖掘方法，并且 检验数据集是否符合这些模型的应用条件，如果符合则可以用这些方法建模。对 于复杂的建模问题，可以先对其提出适当的假设，模型建立以后再对其进行验证。 中南大学硕士学位论文第一章绪论 ( 6 ) 实际数据挖掘工作 运用建立好的模型，对数据集进行分类、估计、预测等工作，得到相应的数 据挖掘的结果。 ( 7 ) 测试和验证挖掘结果 对于上一步产生的数据挖掘的结果，需要通过相应的途径对其进行测试和验 证，如果得到的结果不合理，则需要重新选择其他的数据挖掘方法，重复上面的 建模工作，直至建立的模型能产生合适的结果。 ( 8 ) 解释和应用 对于合理的数据挖掘结果，还需要将与背景知识建立连接，能用相应的专业 知识对挖掘结果做出合理的解释，最后得到的结果才能称为知识，才能为实际的 决策工作提供指导。 1 3 2 数据挖掘的主要方法 数据挖掘是一个复杂的过程，涉及多个不同的知识领域，交叉性和综合性比 较强。需要综合各方面的技术方法才能挖掘出有用的知识，为决策者提供帮助。 一般来说，数据挖掘的主要方法有统计学方法、关联规则挖掘、决策树方法、神 经网络方法、多层次数据汇总归纳、覆盖正例和排斥反例方法、可视化技术、粗 集方法、遗传算法、证据理论等。 ( 1 ) 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，a n n ) 人工神经网络是对人的大脑的活动机理进行模拟以实现大脑的某些方面的 功能，是由大量神经元通过极其丰富和完善的连接而构成的自适应的非线性动态 系统【6 】。由于人工神经网络不需要较多的先验知识、并行计算速度较快，因而人 工神经网络近来受到广泛的关注与普遍的应用。 ( 2 ) 粗糙集( r o u g hs e t ) 粗糙集理论是研究不确定性与不精确知识的工具之一，最早由波兰科学家 z p a w l a k 于1 9 8 2 年提出【7 1 。粗糙集的基本思想是依据给定问题的先验知识，对 问题论域进行划分，然后对划分后的元素确定其对应决策集合的属于程度，一般 分三大类：属于该决策集合、不可能属于该决策集合以及可能属于该决策集合， 相应的分别采用三个近似集合正域、负域以及边界来表示属于程度。粗糙集由决 策表来对输入空间与输出空间的映射关系进行表示，通过剔除属性中冗余的部 分，以实现简化空间表达的维数，突出不同属性表达知识的重要程度。 ( 3 ) 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 遗传算法是基于进化理论，在进化过程中通过选择、交叉与变异方式逐渐产 生问题最优的解，最早由美国j o h nh h o l l a n d 于1 9 7 5 年提出【8 1 。遗传算法的基本 思想是将求解问题的解采用染色体编码，然后在初始的群体寻找适用能力强的个 中南大学硕士学位论文第一章绪论 体进行交叉与变异，依次进行一代一代的进化，最终的最优个体经过解码后即为 问题的最优解。遗传算法的能够并行的计算以及有效地对全局信息进行利用，对 解空间进行多点搜索，可以有效的避免搜索收敛于局部解。 ( 4 ) 决策树 决策树是有由一系列的规则对数据进行分类的过程【9 】。决策树的过程是自顶 向下，选择分类属性，依据对训练数据属性值进行判断，将数据分为到不同的类 中，类作为决策结点，最后会遇到一个叶子结点。决策树在各分析领域得到了广 泛应用，决策树算法可以处理不同类别属性的数据，计算量较小且产生的规则比 较容易理解，建立的模型过程很直观。 ( 5 ) 统计学 统计学主要利用概率论建立数学模型，对收集的观察数据进行量化分析，以 达到推测所测对象的本质，甚至对对象进行预测的- - f - 综合性学科【1 0 1 。统计学中 最主要的分析内容有相关分析、回归分析、判别分析、聚类分析、主成分分析与 因子分析等。 1 4 时空序列数据挖掘的研究进展及评述 1 4 1 时间序列挖掘技术研究简介 时间序列挖掘技术起步于上个世纪9 0 年代，最初主要进行时间序列的相似 性分析研究 1 1 - 1 3 】。相似性主要指判断给定的时间序列是否具有相似的行为f h j 线， 相似性研究是时间序列数据最基本的问题，在此基础上发展对时间序列进行一系 列的挖掘技术，如：子序列匹配、聚类分析、分类分析、关联规则分析、预测分 析等。在相似性研究的同时出现了对时间序列的降维研究、时间序列的分隔研究。 ( 1 ) 时间序列分割 时间序列分割是将给定长度的时间序列s 分割为k 组片段，然后对各片段 采用某种模型进行表达为s ，使得s 与s 具有较高的相似性。对时间序列进行 分割主要用于对时间序列进行降维表达，提高时间序列索引、分类分析、聚类分 析等效率。 ( 2 ) 时间序列相似性查找 时间序列相似性查找是对定长度的时间序列s ，在时间序列数据库中搜索与 其等长且最为相似的时间序列集合。相似性查找是时间序列一个最为基础研究内 容，是时间序列分类、聚类等研究的基础性工作。 ( 3 ) 时间序列聚类分析 时间序列聚类分析是将给定的时间序列数据集分成不同的簇，使得相同类中 的时间序列尽可能相似，而不同类中的时间序列具有显著的差异。与传统的聚类 中南大学硕士学位论文 第一章绪论 相比，时间序列聚类考虑数据的动态变化特征，其主要研究内容包括：时间序列 相似性度量方法、时间序列聚类算法、时间序列聚类结果的有效性评价。 ( 4 ) 时间序列分类分析 时间序列分类分析是依据已知的分类标准将给定的时间序列数据集归为不 同的类中。类似于时间序列的聚类分析，其主要研究内容包括：时间序列相似性 度量方法、时间序列的分类模型、时间序列分类结果的有效性评价。 ( 5 ) 时间序列异常探测 时间序列的异常探测是在给定的时间序列数据集中发现显著不同于其它大 多数数据的时间序列对象。时间序列依据异常存在的时间段，即同一时间序列点 异常、同一时间序列上的片段异常以及整个时间序列异常，可以分为三种模式类 别：点异常模式、片段异常模式、序列异常模式。 ( 6 ) 时间序列关联规则分析 时间序列关联规则分析是获取与时间有关的关联规则，时间序列关联规则将 时间序列划分为不同的模式，也就是具有相似性的片段序列，在模式序列中，挖 掘出形如a = b ( 1 a g = t , s ，c 矧的蕴含式，即事件么或模式彳发生后丁的时间内 事件b 或模式b 也发生，一般来说，我们称彳为关联的前件，b 为关联的后件， l a g = t 表示事件关联的时间关系，s 表示关联规则的置信度，c 表示关联规则 的支持度。 ( 7 ) 时间序列预测分析 时间序列预测通过对时间序列随时间变化的趋势与规律的分析研究，推测出 未来时间的数据趋势或数据值。时间序列预测分析是所有时间序列分析中最热门 的研究方法，在许多应用领域都有广泛的应用。 1 4 2 空间数据挖掘技术研究简介 空间数据挖掘【5 】是数据挖掘的一种重要分支，最早由我国学者李德仁在1 9 9 4 年加拿大举行的g i s 国际学术上提出的。空间数据挖掘是指从空间数据库中获取 用户感兴趣的、未知的、潜在有用的信息，主要对地理空间数据进行分析。 ( 1 ) 空间聚类分析 空间聚类分析是指采用指定的度量方法，将空间中一组具有某种相似性的空 间实体聚合成若干个不同的簇，使得同一个簇里面的实体尽可能相似，不同簇之 间的实体尽可能相异【7 ，m 3 1 。空间聚类主要研究内容集中于以下三个方面： 第一，空间聚类趋势分析。对空间数据的可聚性进行判别，只有在数据满足 聚集分布条件下进行的聚类分析才有意义的。 第二，空间聚类算法设计。目前，国内外已提出了众多算法，但是无法采用 一种算法来解决所有的问题，因而有必要针对不同的数据特征选择选取与设计合 中南大学硕士学位论文第一章绪论 适算法。传统的空间聚类主要是对空间点实体进行分析，常用的聚类方法大致可 以划分为：基于划分的聚类方法，基于层次的聚类方法，基于密度的聚类方法， 基于格网的距离方法，基于图论的聚类方法，基于模型的聚类方法等。 第三，空间聚类的有效性评价。针对同一个空间数据集，空间聚类算法的差 异或相同的算法选取参数的差异都可能导致聚类结果的不同，那么空间聚类有效 性评价的目的就是为了评价不同聚类算法以及同一算法不同参数的性能，即如何 获取最优的聚类结果。 ( 2 ) 空间关联分析 空间关联规则是在空间数据库中挖掘出形如t 暑a 最a l a 只专q 1aq 2 人工人q 埘( c ，s ) 其中，只和q ，中至少存在一个空间谓词，c 与s 分别表示关联规则的可信度 与支持度 2 4 , 2 5 】。其中，空间谓词主要是对空间关系的描述，即对象间存在的拓扑 关系、方位关系以及度量关系。空间关联规则主要研究方向为多层关联规则挖掘、 同位关联规则挖掘等。 ( 3 ) 空间分类分析 空间分类分析就是利用空间对象的非空间属性相似性以及空间对象间的邻 接关系从空间数据库中到处与已知空间特征相关的分类模式。空间分类与空间聚 类的区别在于分析前有无先验信息，空间分类分析事先知道类别数量与各类的特 征，而空间聚类分析前可以不需要先验信息。 空间分类方法主要有e s t e r 等在i d 3 算法的基础，提出了一种结合邻域图进 行分类方法【5 7 】，以及k o p e r s k i 等提出的空间数据的两步决策分类方法【5 8 1 。 ( 4 ) 空间异常探测 空间异常探测是通过一定的方法发现空间对象集中偏离于一般对象分布模 式的异常对剩2 6 1 。空间异常探测在传统的异常探测的基础上考虑空间中的对象与 其邻域空间对象的明显不同。 传统的异常探测的方法主要分类为四大类：基于深度分析方法、基于距离分 析方法、基于密度分析方法、基于分布的分析方法，空间异常探测的方法大致分 为两类：基于图的孤立点、基于多维属性空间的孤立点。 ( 5 ) 空间预测分析 空间预测分析是根据空间对象的变化规律，空间对象之间的相关关系，以及 空间对象的先验知识，对空间对象的发展趋势作出预n t 2 7 - 2 9 。空间预测的核心是 对空间数据数据进行建模分析，目前对空间数据中的时空序列数据进已有大量的 研究，对时空序列数据建模与预测大致可以分为两类，基于时序的预测方法，如 空间移动平均自回归模型( s t a r m a ) 、时空神经网络( s t a n n ) 、时空支持向量 中南大学硕士学位论文 第一章绪论 机( s t s v m ) 等；基于因果预测方法，如地理加权回归( g w r ) 等。 1 4 3 时空序列数据技术研究内容与研究现状 按照牛顿“绝对”空间与时间的观点，空间的存在是永恒的并且无关于空间 里物质的存在，时间的存在也是绝对的且无关于物体的存在以及物理现象的发 生。时间与空间虽然毫无关联的存在，然而，当我们对实体或现象进行观察与研 究时，时间与空间是存在联系的，我们无法想象物体存在于空间而不占据一段时 间，或者物体存在一段时间却并不占据一定的空间。因而，空间与时间是物体存 在的基本特征，物体状态依附于空间与时间，另一方面，时间是一维的，那么依 据此观点，空间中的实体与现象的状态可以视为时间的函数，空间实体在任意一 个时间点都具有唯一的状态，时空序列数据可以认为是描述空间中对象的状态随 时间变化，故时空序列数据能够完整的对空间中的实体与现象进行描述。 时空序列数据是对地理空间对象或现象随时间变化的专题属性记录，广义的 时空序列可以认为是对地理实体或现象的专题属性与空间属性随时间变化的记 录，那么据此状态的变化可分为以下三大类：仅空间属性的变化，仅专题属性的 变化和空间位置与专题属性的变化。本文提出的时空序列数据挖掘重点研究对象 为专题属性随时间变化的时空对象或现象，对空间对象位置信息随时间变化的研 究方向为移动对象建模与分析，不在本文的研究的范围之内。 1 4 3 1 时空序列数据概念 时空序列是时间序列在空间上的扩展，指在空间上有相关关系的多个时间序 列的集合 2 7 - 3 0 】。 时空序列数据是具有空间信息的时间序列数据集。时空序列数据是记录地理 空间实体或现象专题属性随时间的变化状态，因而相比于传统的时间序列数据 集，时空序列数据具有空间特征。 如果时间序列定义为 s = v ( t 1 ) ，v ( t 2 ) ，v ( t 3 ) ，v ( t n ) ) ， 例如：长沙市2 0 1 3 年3 月2 6 至4 月5 日空气中p m 2 5 日监测数据： s = 7 1 ，9 5 ，8 3 ，n u l l ，n u l l ，1 4 3 ，1 8 8 ，1 3 7 ，1 3 5 ，7 1 ，8 8 1 ( 单位微克) 。 那么时空序列可以表示为： s t = l o c a t i o n l ，s 1 ) ， l o c a t i o n 2 ，s 2 ， l o c a t i o n 2 ，s 3 ) ， l o c a t i o n n ， s n ) ) 。 例如：长沙市2 0 1 3 年3 月2 6 至4 月5 日各站点空气中p m 2 5 日监测数据： s t = 长沙市经开区环保局监测点， 5 6 ，7 9 ，7 3 ，5 9 ，1 4 2 ，1 0 4 ，1 2 9 ，1 1 1 ，1 5 2 ，7 5 ， 3 8 ，9 ) ) 湖南师范大学监测点， 4 4 ，7 4 ，4 7 ，6 5 ，1 4 4 ，1 2 8 ，1 6 0 ，2 5 2 ，n u l l ，5 8 ，2 5 ， 中南大学硕士学位论文第一章绪论 1 7 ) ) 天心区环保局监测点， 8 0 ，5 8 ，5 5 ，1 0 9 ，1 1 9 ，1 1 0 ，2 4 0 ，1 4 9 ，1 3 5 ，2 3 ，1 6 ) 湖南中医药大学监测点， 6 4 ，5 6 ，6 6 ，1 1 8 ，9 5 ，1 2 1 ，1 5 3 ，1 3 9 ，8 1 ，1 9 ，1 3 ) ) 1 4 3 2 时空序列数据挖掘的主要技术 时空序列数据挖掘是空间数据挖掘的一个重要分支，是面向空间数据中时空 序列数据，因而继承了空间数据挖掘的主要技术手段，此外，时空序列数据又可 以视为时间序列数据在空间上的扩