基于小波变换的时间序列挖掘研究.doc

天津大学硕士学位论文基于小波变换的时间序列挖掘研究姓名：田政雄申请学位级别：硕士专业：管理科学与工程指导教师：寇纪淞20080501摘要时间序列是按时间顺序排列的，随时间变化且相互关联的数据序列，在金融、科学观测和工程等各个领域都广泛存在。如何有效的管理和利用这些数据，发现这些数据背后隐含的规律和知识，是人们广泛关注，具有重要意义的理论和实际应用课题。数据挖掘的方法主要有统计方法、机器学习方法、神经网络方法和数据库方法。本文主要研究了小波变换应用到时间序列挖掘中的方法，包括小波变换在时间序列属性约简，时间序列相似性匹配，时间序列奇异点检测中的应用，根据小波变换的多分辨性提出了基于小波变换的聚类算法，重点研究了时间序列挖掘中的多层次相似性匹配和多层次频繁模式挖掘问题。主要研究成果如下：小波变换改进传统聚类算法针对传统聚类算法如算法中初始聚类中心是随机选择的，不太合理的问题，提出了基于小波分析的时间序列聚类算法算法，一算出时间序列的分解系数，就在这些系数上运用聚类算法，从第二个层次开始，再渐渐的进行到更高的层次上。时间序列的多尺度相似性模式匹配改进了现有的时间序列多尺度相似匹配算法，现有算法中序列的片段相似标准仅仅考虑了两个片段的倾角而没有考虑长度，本文结合时间序列的相似性度量提出了一种更好更合理的多尺度时间序列相似模式匹配算法。并根据小波变换的多尺度性提出一种更有效，更合理的方法来解决时间轴伸缩问题，进行更长时间的模式匹配。时间序列的多尺度频繁模式挖掘时间序列本身有长期和短期之分，挖掘时间序列的多尺度模式有着重要的现实意义，本文首次提出了多尺度频繁模式挖掘的概念，并根据小波变换的多分辨性，提出了基于小波变换的时间序列多尺度频繁模式挖掘算法，本算法首先对原序列进行小波变换，然后在变换后的序列上挖掘频繁模式，并结合了基于重要点分段方法和互关联后继树方法，能挖掘出不同尺度的频繁模式。关键词：数据挖掘，时间序列，小波变换，频繁模式，互关联后继树（），：，独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得苤盗叁茎或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名：、刁蛔签字隰沙孑年月日学位论文版权使用授权书本学位论文作者完全了解苤奎盘茎有关保留、使用学位论文的规定。特授权苤壅盘茎可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。（保密的学位论文在解密后适用本授权说明）学位论文作者签名：喻侈娣旧侈吲导师签名：签字日期：加，年月日签字日期：涵貅蚀；翻移伊眸旯善第一章绪论研究背景和意义数据挖掘概述第一章绪论随着计算机技术的发展和应用的普及，人类社会已经进入一个信息化时代，信息技术在金融、经济、工农业生产、科学实验和人类生活的各个领域都得到了广泛应用。信息技术的应用产生了大量的各种类型的数据，自世纪年代起，全球信息量每隔十几个月甚至几个月就要增加一倍，呈爆炸式增长。面对浩瀚的数据，人们难以找到合适的方法和工具，发现隐藏在这些数据背后的知识，出现了“数据爆炸，知识贫乏”的现象。数据挖掘正是为了解决这种问题而提出的。数据挖掘（，）【】是从大量的、不完全的、随机的数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息的过程。数据挖掘将人们对数据的应用从低层次的简单查询，提升到从数据中挖掘有用的信息和知识，提高决策水平，其主要任务包括相似性查询、模式挖掘、聚类分析、分类和预测和异常检测等。与数据挖掘有着同样内涵的一个概念是知识发现（，）。一种观点认为数据挖掘是知识发现过程中的二个基本步骤（如图所示）；另一种观点则将数据挖掘视为知识发现的同义词。持前一种观点的人将知识发现分成如下几个步骤【】：（）需求分析。不同领域的用户对数据挖掘有着不同的需求，分析用户的需求是为了确定挖掘的技术路线并使挖掘的最终结果符合用户的期望，为此需要了解原始数据所涉及的应用领域，掌握用户的需求和目标，并制定挖掘计划。（）数据清理。大型数据库或数据仓库中往往包含有大量不完整的、含噪声的和不一致的数据，如果不对这些数据加以处理，就有可能使数据挖掘过程陷入混乱，导致不可靠的输出。数据清理是对原始数据的初步加工，目标是识别原始数据中的孤立点、消除噪声、填充空缺的值，并纠正数据中的不一致。（）数据筛选。参与挖掘任务的数据集的规模对于挖掘过程和结果都有重要的影响。数据太少往往不具有代表性，会影响挖掘结果的正确性；数据太多难免包含一些与挖掘任务不相干的数据，会影响挖掘过程的效率。数据筛选就是将来自多个数据源的数据组合在一起，根据一定的标准从中检索或分析出任务相关的数据，并将筛选出的数据变换成适合挖掘的统一形式。第一章绪论（）数据挖掘。这是知识发现全部过程中的基本步骤，是对海量数据进行加工和分析的过程。从本质来说，数据挖掘的基本任务是从大规模数据集中发现有价值的模式，如关联规则、分类模式、序列模式等等。数据挖掘是一个智能分析过程，所使用的方法和手段涉及机器学习、神经网络、序列模式分析，以及其它一些相关领域的知识。（）知识表示。数据挖掘系统应当能够将所得知识直观、形象地展示给用户，如采用表、饼图、直方图、判定树、曲线等来表示。此外用户常常会发现一般系统将一大堆无用的结果展示出来，只有少数有用的知识却被淹没在其中。因此好的系统应该能够在将挖掘结果提交给用户之前先进行筛选。最后，数据挖掘系统还应当是一个能够与用户交互的系统，允许用户将修正后的参数输入系统，开始新一轮的挖掘。数据源厂需求分一析厂广可一一厂、。，。一数据清理二习一卜、骜羹霞选数据挖掘知识表示、？一”卜卜、。，图处理过程数据挖掘涉及多种学科的相关技术，包括数据库技术、概率与数理统计、机器学习、数据可视化等。其中数据库技术是数据挖掘的基础，因为数据库为数据挖掘提供数据来源，而数据挖掘则为数据库提供智能化的分析手段。与机器学习等其他人工智能技术相比，数据挖掘有其自身的特点：首先，数据挖掘通常要处理大规模的数据集，即数据挖掘的目标是从数据库的海量数据中发现有价值的知识，因此，算法的可扩展性通常是衡量数据挖掘算法的主要指标；第二，数据挖掘系统具有多种不同的挖掘工具，可以从同一海量数据集中发现不同类型的知识。通常用户不知道他们的数据中什么类型的模式是有趣的、有价值的，因此想尽可能搜索多种不同的模式，这就要求数据挖掘系统能够挖掘多种不同类型的模式，以适应不同用户的需求或不同的应用；第三，数据挖掘系统能够发现各种粒度（不同抽象层次）的知识，通过用户与数据挖掘系统之间的交互，由用户输入参数来指导或聚焦有趣模式的搜索。用户的输入参数对于数据挖掘的结果和质量会产生重要的影响，这就要求用户具备一定的数据第一章绪论挖掘知识；第四，数据挖掘通常并不产生精确的结果，而是基于概率的统计规律。这意味着有些被发现的模式并非对数据库中的所有数据都成立，通常每个被发现的模式带有一个“可信性度量。目前，数据挖掘已经引起了学术界和工业界的广泛关注，成为国际上数据库和信息决策领域最前沿、最热门的研究方向之一【】【】。频繁模式挖掘的基本概念频繁模式挖掘最初是作为关联规则挖掘的一个子问题被提出来的，而关联规则挖掘又源于购物篮分析的需要。大型超市通过日常经营积累了大量的销售数据，企业经营者希望通过分析这些数据，得到一些有价值的规则，例如：通过分析发现了这样的关联规则，面包牛奶（），意思是的顾客在购买面包的同时也会购买牛奶。这样的关联规则可以为企业的产品定价、促销以及商场布局等经营决策提供有力支持。设岛，乙）是由个不同的项目（）所组成的集合，每一个项目可以是一种商品或一个网页。不同的项目所组成的集合称为项集，由个项目所组成的集合称为项集。代表一个事务数据库，简称为数据库。中的一条事务是中一组项目的集合，代表顾客的一次购买行为中所购买的商品的集合或用户一次浏览的网页的集合。每个事务有一个标识符，称作。一条事务包含项集当且仅当。项集在中的覆盖（）是由中包含项集的所有事务的组成的集合，即：（，）互（）项集在中的支持度（）是中包含项集的事务数占中事务总数的比例：（、（，）寺二（）因为的值是一定的，为了方便有时也用（，）表示支持度。满足最小支持度阈值氏。的项集被称为频繁项集。最小支持度阈值氏。是由用户指定的一个参数，氏。，代表用户认可的频繁项集的最低出现频率。关联规则是形如的蕴涵式，其中、，并且。关联规则由支持度和可信度进行度量。支持度表示规则出现的频度，可信度表示规则的强度。力（彳，）（，）：（污一，）（）第一章绪论关联规则的可信度（）是中同时包含项集和项集的事务数占包含项集的事务数的比例：（，）：（，）（）一力（，）、给定项集，事务数据库，以及最小支持度和最小可信度曲，关联规则挖掘就是找出中所有满足最小支持度和最小可信度的关联规则：（，）】厂，】一、（，），（，）。）”关联规则挖掘的过程通常分为两个大的阶段：第一阶段找出所有满足最小支持度阈值的频繁项集；第二阶段在频繁项集中找出所有满足最小可信度阈值的关联规则。关联规则挖掘通常要处理规模庞大的数据集，在大数据集中搜索频繁项集需要大量的时间和空间，而在频繁项集中搜索关联规则要简单得多。因此在关联规则挖掘的过程中，第一阶段是解决问题的关键。目前绝大多数关于关联规则挖掘的算法都主要解决第一阶段问题，即如何高效率地挖掘频繁项集的问题。频繁模式挖掘的问题可以看作是一个搜索问题，目标是在数据库空间中以尽可能高的效率搜索频繁模式。由于数据库的规模通常很大，频繁模式挖掘算法需要在一个庞大的空间中进行搜索，因此如何提高算法的效率始终是频繁模式挖掘算法要解决的一个主要问题。频繁模式挖掘的搜索空间并不等同于数据库空间，数据库空间是物理数据空间，而搜索空间是逻辑数据空间。在一些层次挖掘算法中由于要多次扫描数据库，使得算法的搜索空间大于数据库空间，而在一些采用抽样技术和剪枝策略的算法中，算法搜索的数据可能只是数据库中数据的一部分，算法的搜索空间可能会小于数据库空间。频繁模式挖掘算法的搜索空间大小取决于许多因素，主要有：（）数据库记录的数目。以记录为单位的数据库规模是决定搜索空间大小的最主要因素。在已有的频繁模式挖掘算法中，大多数算法可以找出数据库中所有的频繁模式，这要求算法对数据库中的每条记录至少作一次搜索。虽然一些算法采用在数据库中抽样的技术，但这些算法不能保证得到所有的频繁模式。（）数据库包含的项目数。数据库记录的属性即是数据库记录包含的项目。数据库中可能的频繁模式数与数据库记录包含的项目数之间呈指数关系。对于项目集合的关联规则而言，设数据库记录包含的项目数为，则数据库中可能的频繁模式数为”，而对于序列模式而言，可能的频繁模式数目会更多。因此，随着数据库记录包含的项目数的增加，频繁模式挖掘算法的搜索空间可能会以指数方式增长。（）数据库记录和频繁模式的长度。在数据库记录数目一定的前提下，数据库记录和频繁模式的平均长度越长，频繁模式挖掘算法的搜索空间就越大，尤其第一章绪论是对于层次搜索算法（如类算法），算法搜索数据库的次数直接取决于数据库记录的最大长度。（）数据库的类型。尽管没有严格的界定方式，在频繁模式挖掘的实践中，人们仍然将数据库分为两种，即稠密数据库和稀疏数据库。一般认为，在数据库中记录数目一定的前提下，如果数据库包含的项目数较少，且数据库记录和频繁模式的平均长度也较短，则这样的数据库属于稠密数据库，反之，则是稀疏数据库。在稀疏数据库中搜索要比在稠密数据库中搜索困难得多。（）搜索的策略。对于同样的数据库，算法采用的策略方式不同，搜索的空间也有很大差别。采用层次搜索的方式进行搜索通常要产生候选模式集，需要多次搜索数据库，数据库中的一条记录被多次搜索，搜索的相对空间较大，而基于内存的算法通常不产生候选模式集，一般只需要对数据库进行一二次的搜索，搜索的效率较高。频繁模式挖掘根据处理数据集的性质和挖掘结果的不同有不同的分类方式：（）根据处理数据的类型不同，频繁模式挖掘可以分为布尔型频繁模式挖掘和数值型频繁模式挖掘。布尔型频繁模式挖掘处理的数据都是离散的枚举类型数据，数据被限制在一个枚举集合中取值，枚举集合中的元素称为项目，项目被包含于一个模式中，或者不被这个模式包含，因此项目对于模式来说是布尔型数据。例如某商场发现，在顾客的购买模式中，（面包，牛奶）的支持度为，超过了的最小支持度阈值，因此是布尔型频繁模式。现实世界中数据库存储的数据不全是布尔型的数据，绝大多数数据是连续的数值型数据，如工资、年龄、商品价格等。布尔型频繁模式的相关概念通常不能直接应用于数值型频繁模式的挖掘，例如某个大型企业将（年龄，月收）作为一个模式，希望知道该模式在企业员工中的支持度，结果发现该模式的支持度为，因为根本没有员工的月收入正好等于。在挖掘数值型频繁模式时，通常要将数值型数据离散化，从而将数值型频繁模式挖掘的问题转化为布尔型频繁模式挖掘问题。（）根据处理数据是否有序，频繁模式挖掘可以分为项目集合的频繁模式挖掘和时态数据的频繁模式挖掘。项目集合中元素之间是无序的，因此在项目集合的频繁模式挖掘过程中，可以根据需要对项目集合中的元素排序，如按项目的支持度降序排序。时态数据本身是有序的数据，它的数据之间存在着某种顺序，这种顺序关系可以是时间上的先后关系，也可以是与时间无关的某种顺序。在对时态数据进行挖掘时，必须考虑时态数据之间的顺序关系。时态数据是对具有时间关系的一大类数据的统称，可以是各种类型的数据，如数值型数据、枚举型数据、布尔型数据、事务性数据等。数值型时态数据又称为时间序列（），如证券市场上股票价格的历史数据、商业零售行业中某种商品销售额的历史数第一章绪论据，以及天气预报中某地区每天气温气压的历史数据等。枚举型时态数据则通常被称为序列（），如用户浏览某网站时的路径、用户购买商品构成的序列，以及中基因排列构成的序列等。（）根据模式中数据的抽象层次，可以分为单层频繁模式挖掘和多层频繁模式挖掘。在单层的频繁模式挖掘中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的；而在多层的频繁模式挖掘中，对数据的多层性已经进行了充分的考虑。例如：（计算机，打印机）和（计算机，打印机）分别是个不同层次上的频繁模式，前者是对后者的高层次上的抽象，后者则是前者在低层次上的细节表现。从频繁模式挖掘的分类可以看出，进行多层次多尺度模式挖掘是很有意义的，而时间序列本身就有长期和短期的概念，进行时间序列的多尺度分析很有必要，本文首次提出了时间序列多尺度模式挖掘的概念，根据小波分析的多尺度性研究了时间序列的多尺度相似模式匹配问题和多尺度频繁模式挖掘问题。时间序列挖掘中的关键问题时间序列在商业、经济以及科学研究等人们生活的各个领域中普遍存在。例如，金融证券市场中每天的股票价格，商业中某项商品的周期销售额等。时间序列挖掘是数据挖掘技术在时间序列分析中的具体应用。其目的是在时间序列中发现隐藏的知识，分析时间序列变化规律，帮助人们科学地做出决策。例如：（）在证券市场，找出上月与公司股票价格变化模式相似的股票，从中可以分析产生这种变化的原因。（）在金融领域，跟踪信用卡顾客的使用情况，当顾客在某段时期内的信用卡使用情况异常时，能够及时报告，预防信用欺诈。（）在天气预报中，找出在一段时间内频繁出现的温度的变化模式，从中归纳出温度变化的规律等。世纪年代以来，时间序列挖掘的研究和应用发展迅速，成为数据挖掘领域的一个重要分支。时间序列挖掘的任务主要包括【】以下几个方面：（）相似性查询。给定两个时间序列和，定义一个相似性度量标准（，），如果（，），则称和是相似的。相似性查询就是在时间序列数据库中找出与给定的相似的时间序列。例如，找出上月与公司的股票价格变化模式相似的股票等。（）频繁模式挖掘。找出在一段时间内频繁出现的模式。例如，找出上月公司股票频繁出现的变化模式。第一章绪论（）聚类。聚合那些具有相似模式的时间序列，例如，根据上月股价变化模式对股票聚类等。（）分类。根据时间序列的变化模式将其划分到不同的类中。例如，根据上月股价变化模式，将其分为涨、跌、平三类。（）异常检测。找出一个时间序列，其在一时间段内的变化模式同其它序列存在明显的差异。例如，在某一周内所有公司的股票都上涨，而唯有一家公司的股票下降等。从时间序列挖掘的任务可以看出，时间序列查询和频繁模式挖掘不仅是时间序列数据挖掘的一项重要任务，同时也是聚类、分类和异常检测等其它任务的基础，单层次上的时间序列相似性查询和频繁模式挖掘有了大量的研究，而多层次的查询和频繁模式的挖掘同样有着很好的实际意义，这方面的文献还比较少，本文主要对这方面进行了研究并提出了一些思路。国内外研究现状传统的时间序列分析方法传统的时间序列分析建立在概率统计的基础上，研究对象着重于随机性的动态数据，研究方法着重于全局模型的构造。模型法是目前对时间序列进行深层次分析的主要方法，经典的时间序列分析模型主要有、等【】。模型法中的理论模型是在数学理论和假设基础上，通过演绎推理的方法建立起来的。各种模型都有坚实的数学基础，只要假设合理，所得出的结论就是合理的。但如果所提出的假设不合理，模型法将会严重失真。这样，模型的构建就非常重要，如果对系统认识不够和不具备良好的建模技巧，很难构建出一个好的模型。例如很多金融计量模型，常常基于平稳性假设、正态分布假设、线性假设等，但实际上金融时间序列具有信噪比低、非平稳、非正态、非线性的特点。另一方面，模型法反映的是序列的总体的特征，对序列中隐含的一些局部的细节特征很难表现出来。然而，在实际应用中，往往需要对时间序列局部特征进行分析，如发现频繁出现的变化模式，两个时间序列相似性比较等。数据挖掘是基于归纳的方法，从大量的、不完全的、模糊的、随机的数据中，提取隐含在其中的信息和知识的过程，与模型法的主要区别是可以撇开假设，通过数据归纳出结论。数据挖掘建立在大量数据的基础上，依靠更多的是“经验”，这就决定了数据挖掘对数据的质量要求比较高，否则就会产生“垃圾进、垃圾出”的现象。第一章绪论时间序列挖掘并不是对传统的时间序列分析方法的完全否定，而是补充、完善和发展。实际上，数据挖掘的许多方法也都是建立在统计学的基础之上，如贝叶斯、粗糙集和支持向量机等。因此，时间序列挖掘在传统的时间序列分析方法基础上，借助信息技术领域一些新的方法和技术，如机器学习，神经网络，数据库技术等，对大规模的时间序列数据进行分析和处理，提出隐含在其中的知识，为分析决策提供更加有力的技术支持。时间序列频繁模式挖掘在年提出的算法是频繁模式挖掘算法发展过程中的一个里程碑，由于在算法中使用层次搜索策略以及在搜索过程中对候选模式进行剪枝，使得算法在处理大规模数据集的频繁模式挖掘问题时具有较高的效率，算法的基本思想至今仍被一些新提出的高效算法借鉴使用。在算法被提出后，很快出现了一大批使用算法框架的算法，如、等算法，这些算法被统称为类算法。各种类算法从不同的方面改进算法，算法提出了更高效的剪枝策略，算法和算法则致力于减少对内存的占用【】。随着对算法的进一步研究，人们很快发现算法的一些局限性：第一，算法使用基于磁盘的数据库，并且在层次搜索的每次迭代中都要访问磁盘数据库，当数据库的规模很大时，算法需要过多的开销；第二，算法需要生成候选集，而候选集的规模与数据库中包含的项目数里指数关系，影响算法的效率；第三，算法有可能发现过多的频繁模式，使用户无法从中得到有用的信息。解决上述问题的途径主要有两个：一是采用特殊的数据结构将数据库压缩于内存，即以基于内存的数据库取代基于磁盘的数据库，这样可以减少读写磁盘的开销；二是以挖掘部分频繁模式取代挖掘完全频繁模式，如挖掘最大频繁模式、频繁闭项集。为了将数据库压缩于内存，人们提出了多种新颖的数据结构。由提出的算法是一种基于内存的典型算法【】。该算法采用分治策略：在经过了第一次扫描之后，把数据库中的数据压缩进一棵频繁模式树（），随后再将分化成一些条件数据库，然后再对这些条件数据库分别进行挖掘。算法不产生候选模式集，但由于要递归地生成，算法仍然需要较大的内存空间。频繁序列挖掘是频繁模式挖掘的又一个重要研究领域。在提出用于频繁项集挖掘的算法后不久，又提出了用于频繁序列模式挖掘的算法幂。用于频繁序列挖掘的算法一般沿用了频繁项集挖掘算法的基本思想。如后来出现的、和算法沿用了第一章绪论算法的思想，因此这类算法可以被称为是频繁序列挖掘的类算法。然而在对序列进行数据挖掘时，必须考虑序列中数据之间的顺序关系，这使得频繁序列挖掘面临更大的搜索空间。近年来在频繁序列挖掘领域虽然取得了一些进展，但人们更加关注一些具体应用问题的研究，如时间序列分析，分析，访问路径挖掘等。对频繁时间序列挖掘的研究由来己久，但由于该问题的复杂性而进展缓慢。频繁时间序列挖掘过程通常分为两个步骤：即首先将时间序列转化为项目序列，然后再应用频繁序列挖掘的算法进行挖掘。频繁时间序列挖掘的困难在于第一步，把时间序列转化为项目序列一般有两种方法：一是通过滑动窗口分割再聚类的方法【】；二是分段线性化分割。使用第一种方法时，不同的子序列聚类算法往往得到很不相同的结果，使频繁时间序列挖掘结果的意义受到质疑。文献提出的平凡簇概念和基于小波滤波的时间序列模式挖掘算法一算法取得了一定的效果。时间序列本身有长期和短期的概念，时间序列的多尺度分析有着很好的现实意义，文献首次提出一种多尺度的时间序列相似匹配算法，其思想是用小波变换的多分辨性质，在不同的尺度上提取出时间序列的形状特征，然后在形状特征序列中进行多尺度相似模式逼近匹配，从而搜索出相似时间序列或子序列。但算法中序列的片段相似标准仅仅考虑了两个片段的倾角而没有考虑长度，可以提出更好的相似性度量改进算法。根据我们掌握的资料，还没有文献进行时间序列的多尺度频繁模式挖掘，这是一个需要研究的领域。本文的主要工作和结构人可以借助显微镜来观察微小物质，通过调焦获得不同清晰度的观察结果。在高清晰度下，看到物质的细节变化，在低清晰度下，看到物质的轮廓。人还可以借助望远镜观察远处景物，通过调焦也可以调节景物清晰度。小波分析方法是一种时频局部化分析方法，对信号的低频部分具有较高的频率分辨率和较低的时间分辨率，在高频部分具有较高的时间分辨率和较低的频率分辨率，它被誉为数学显微镜。小波分析的基本理论将在第三章给予介绍。小波分析己被成功用于时间序列属性约简，时间序列相似性匹配，时间序列奇异点检测中，但已有的工作都未充分利用小波的多分辨分析等特性。本文主要研究时间序列挖掘中的多层次相似性匹配和多层次频繁模式挖掘问题，在综述了时间序列数据挖掘的基础上，研究了小波变换在时间序列挖掘中的应用，并根据小波变换的多分辨性提出了时间序列多尺度相似性匹配和频繁模式挖掘算法。第一章绪论论文的主要研究问题及相互关系如图所示：图论文的主要研究内容及相互关系各章主要内容安排如下：第一章绪论。概述了数据挖掘和频繁模式挖掘，针对时间序列数据挖掘，指出相似性查询和频繁模式挖掘是解决问题的关键，并指出多尺度相似性查询和多尺度频繁模式挖掘有着很大的现实意义。第二章时间序列数据挖掘概述。对时间序列数据挖掘的各个方面进行了分析，包括时间序列相似性查询，模式挖掘，分类，聚类，多时间序列和多维时间序列的挖掘。第三章小波变换及其在时间序列挖掘中应用。在介绍了小波分析的基本理论的基础上，分析了小波变换在时间序列属性约简，时间序列相似性匹配，时间序列奇异点检测中的应用，针对传统聚类算法如算法中初始聚类中心是随机选择的，不太合理的问题，本文提出了基于小波分析的时间序列聚类算法。第四章基于小波变换的多尺度相似性查询。在时间序列的表示法和动态模式匹配的基础上，提出了时间序列的多尺度匹配算法。第五章基于小波变换的时间序列多尺度频繁模式挖掘。提出了时间序列多尺度频繁模式的概念，研究了小波变换，互关联后继树在频繁模式挖掘的应用，最后提出了基于小波变换的多尺度频繁模式挖掘算法。第二章时间序列数据挖掘概述第二章时间序列数据挖掘概述现实世界存在着大量的时间序列数据，时间序列数据挖掘是近年来学术界关注的一个重要研究课题。本章概述了时序数据挖掘这个领域内的主要研究方向和课题，包括相似性发现技术，模式挖掘，分类，聚类，异常检测，增量挖掘等。时间序列相似性查询定义（时间序列）：时间序列（）】是按时间顺序排列的、具有相等时间间隔的一系列数据的集合，记为：（五，瓦）。其中：薯（，）为时间序列的状态点，表示在，时刻时间序列的值为，为数值型数据；为时间序列的长度。时间序列中的时间是严格递增的。作为时间序列数据相似性发现的基本问题，相似性查询可简单地描述为【】：给定一个序列集合、一个序列、一个距离度量和容错阈值，要找出序列集合（，）鱼）。进一步地，可定义搜索中序列的子序列集合，即不仅比较中的序列，而且比较序列中所有与相似的子序列。如果实际搜索的结果，则为漏报（）；反之，若，则为多报（）。保证无漏报的相似性匹配称为精确的，否则称为近似的。高维度、高特征相关性和大量噪音是时间序列数据的独特结构，这种特征使许多经典算法难以发挥作用，增加了挖掘算法的研究难度。通常认为解决时间序列挖掘问题需要以下几种技术：（）抽象表示数据形态的技术，即时间序列数据表示（）（）时间序列分割（）（）比较两个序列的相似性距离度量。时间序列数据表示面对海量数据，直接去操作一个高维的数据空间是很困难的。一个具有个点的序列可以看成是维空间的点，若直接用（）多维索引结构（如水树）来索引这种维点，则容易导致维度灾难。因此，需要研究合适的数据表示形式，进行维度约简，在高效、方便的表示形式上进行有效的挖掘。衡量维度约简效果的重要标准之一是要满足“无漏报”原则，要求数据表示满足以下条件，即下边界引理：第二章时间序列数据挖掘概述引理（下边界引理）：约简后的距离应不大于原先的距离，（，）（，）。其中：是查询序列；是数据集中的任意序列；是约简空间中的两序列距离；是真实的两序列距离。时间序列数据表示形式可分为基于模型、基于变换和其他方法。搜索方法与数据表示形式密切相关。图对时间序列表示方法进行了总结，几种主要技术，如离散傅立叶变换、小波变换和奇异值分解等是精确的方法。为提高相似匹配效率，也有学者提倡使用近似的方法，可采用有损耗的数据压缩模式，如分段线性方法、序列离散化、字符串匹配方法等。下面简单介绍以上几种方法：。一一“丫，一一；图时间序列表示方法分类（）基于模型的方法基于模型的数据表示假设时序数据是由某个模型生成的。模型被用来与数据拟和，并计算出相应的模型参数，这些参数也会在之后的数据挖掘过程中起到重要的作用。常用的模型有隐马尔科夫模型（）、（）等。（）基于变换的方法基于变换的方法将时间序列从时间域映射到另一个特征空间，用特征空间的映像点表示原始序列，从而实现维度约简，并用多维索引结构存储映像点。另方面，也可以将时间序列转换成离散的字符序列。等人【使用离散傅立叶变换（，）将时间序列从时域空间变换到频域空间。根据定理，在频域空间中，保持原序列的距离，即满足下边界引理。可取频域的前个系数形成一个维点来表示原序列，相似度量就是维点的距离，并建立索引。匹配序列必须等长、系数相同，且仅对全序列匹配有效。为了解决子序列匹配的第二章时间序列数据挖掘概述问题，等人【】提出设定滑动窗，对窗口内的子序列进行后形成维特征点轨迹，并对轨迹按照（）来划分，建立相应索引。这种方法形成基于变换的（）通用框架，其主要步骤是：（）建立距离度量；（）维度约简后适用于；（）产生特征空间的距离度量，证明满足下边界引理。支持树等各种高维索引方法，能够保持欧氏距离不变性，保证了查询的完备性。离散傅立叶变换的时间复杂性是（）。但是，平滑了原始序列中局部极大值和局部极小值，导致了许多重要信息的丢失；此外，还对时间序列的平稳性具有比较高要求，对非平稳序列并不适用。离散小波变换（，）作为一种较新的线性变换技术，利用变换后生成的少数小波参数近似模拟原始信号。其小波参数具有时间频率特性，可以保持比还要多的信息，满足多分辨率的表示需求。文献【】首次提出用代替对时间序列进行约简，并证明了，、波变换保持距离且满足下边界引理，但未考虑小波的多尺度性。还可以使用全特征小波变换方式将一般小波变换应用于时间序列，实验显示，许多小波的性能优于和波，且一般小波变换表示也满足下边界引理，但还有待数学证明。同类似，支持各种树等高维索引，具有欧氏距离不变性，保证了查询的完备性，而且支持非欧式距离。但其主要缺陷是信号长度必须是的整数次方，无法处理任意长度的序列，而且不支持带有权重的距离度量。分段常数逼近方法【婚】【】将序列分成等长的个段，各段的平均值就构成该序列的维特征向量。这种方法的优点是易于理解和实现、转换速度快、无漏报、线性建立索引开销、存在更灵活的距离度量等。对这种维特征向量可建立的多形式距离度量和综合索引机制，还可加入偏移变换、幅度时间伸缩【引。（）方法【】使用更灵活的距离度量，如加权距离、，并支持比索引项更短的查询，这种能力是，和所没有的。在表示方法的基础上，矛提出一种（）方法，用符号化表示各子段均值的变化区间；文献对方法进行了扩展，在的基础上，增加每段的极大值和极小值，提出了表示法，应用到金融等领域。（）方法【是方法的改进，其序列分段是变长的、可索引的，对波动较大区间划分多个短区段，对平稳区间划分少量长区段，优化表示性能。为了高效、高质量地拟合分段，算法首先利用小波变换，然后还原为变长分段。和都能处理范数，的性能比和提升了个数量级。第二章时间序列数据挖掘概述以上变换方法都是遵循框架进行的。，和都是利用多个基本函数的线性组合来表示序列的。利用正弦和余弦函数，利用小波基函数，利用特征波函数（）。和利用一系列箱型（）基函数来表示序列，其中的箱型基是定长的，而的箱型基是变长的。从可使用的距离度量、性能和效果的综合评价来看，这些方法虽然各有长处，但多数情况下，是较优的。这些方法的共同不足是：当要求匹配的子序列长度超过滑动窗口时，算法性能明显下降；需要平衡维度约简与准确表示序列的矛盾；大多数算法不能处理小于滑动窗口的子序列匹配问题。用字符串表示时间序列的方法已有多种：（）聚类变换方法【】，先由滑动窗口获得子序列集合，再对子序列聚类，并指定相应类符号表示，序列就由这些类符号构成，主要问题在于窗口宽度的选取没有一个明确的标准，很难确定一个合理的窗口宽度使得所有时问序列片段都具有相对独立的变化模式。此外，这种方法不经过任何特征提取与转换直接对时间序列数据进行聚类，计算数据量大且聚类效果不理想。文献利用线性化分段表示法所独有的形态分割与表达能力实现了时间序列的分段与表示，再利用神经网络模糊聚类算法实现了时间序列的在线聚类，实现了对金融领域时间序列数据的符号化转换；（）分段划分方法，将两点之间具有相同比率的连续点划分成段，并指定某个符号表示；（）聚合近似，方法【先将序列变换为表示，然后符号化为字符串，实现了维度约简且满足下边界引理，这是其独特的优点，大量文献使用了这种表示方法【引。由于字符串匹配和索引方面的研究工作已经比较成熟，符号表示法可以利用现有的研究成果，设计查询算法。其缺点是离散化符号的定义、相似性度量比较困难，同时其表示方法比较粗糙，难以反映时间序列变化的细节。不过一些学者还是认为字符串表示方法有很好的前景。时间序列数据分割从时间序列数据抽取模式的一般方法是，先将原始时间序列分割，并将所得的子序列转换为某种高级的数据表示，如符号序列或者某个特征空间中的点，然后在此符号序列或者特征空间中进行聚类（或分类），生成模式或模式集合。其中关键问题之一是如何分割时间序列数据。时序数据的分割大体有三种类型：滑动窗口、自顶向下、自底向上。滑动窗口模型指分割以循环的方式进行，每次处理一个没有被最新分割包含的数据，分割不断的增长直到超出某个界限而停止。滑动窗口模型的效果通常跟数据集合本身有很大的关系，而且滑动窗口的大小选择也是一个难确定的问题。自顶向下的模型中，数据不断的按照某种规则被划分，直到满足一定的停止条件。在自底向第二章时间序列数据挖掘概述上模型中，将最底层的数据作为原始分割，然后不断的合并小的分割直到满足一定的停止条件为止。光从时间性能上比较通常自底向下的方法要好于自顶向下的方法。文献在累积残差法基础上进行了改进，使用双误差标准。滑动窗口的主要问题是它不能向前看，不能考虑全局，而自顶向下、自底向上的方法不是在线的，需要扫描整个数据。这在现实中是不可取的，时间序列流以千兆每秒的速度到来，文献整合了滑动窗口的在线和自底向上的效率优势，提出了算法（），主要通过一个缓冲器（）来实现在线分割。在时间序列数据挖掘研究中，常采用分段直线表示（，）方法分割时间序列。因为法比较符合人们的直观经验，而且通常索引结构维数低计算速度较快，所以被较多人采用。等人【提出将一个时间序列经过固定宽度窗口分割，得到等长的时间序列片段构成的分段序列，以各段采样点振幅的平均值来代替各段振幅，既能够压缩时间维，又能够用欧氏公式计算各分段的相似距离。文献在时间序列上依次取相邻点，拟合成线段，在允许累积的误差范围内将其合并成更长的直线段，以标识符号序列代替各直线段，形成字符串集，用比较字符串相似的方法查找相似子序列。这种方法的出发点是时间序列最基本的变化形态，解决了文献中如何确定合理的分隔窗口宽度的问题，但是时间序列数据内在的整体特征被忽略了，而且没有保留各分段在时间序列中的位置信息，挖掘效果受影响。为此，文献提出一种检索时间序列分段关键点的算法，以关键点为边界分段，使用形态距离测度和快速剪除的算法，高效简便地检索出相似子模式。文献提出了