1.1数据挖掘的概述

随着数据库技术、信息技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据量急剧增长。面对如此大规模的海量数据，人们可以利用它们处理繁琐的日常事务，但同时又给人们带来了很多的不便。如：信息量过大难以消化问题、信息安全问题、信息存储问题等。所以人们开始考虑这些大量数据的背后必然隐藏着许多有价值的知识，因此人们希望对这些数据进行更高层次的决策分析与研究，以便更好地利用这些数据，以达到实时作出决策的目的。当前的数据库管理系统的数据存取、查询、描述统计等技术已日益成熟，但始终无法发现隐含在数据中的有价值的信息，缺乏从数据中挖掘出有趣知识的手段和技术，导致了数据丰富而知识贫乏难以获取的现象。数据挖掘(DM，DataMining)出现于20世纪80年代后期，到了90年代有了突飞猛进的发展，并有望在新千年继续繁荣。数据挖掘是一个新兴的、飞速发展的领域。随着人们对数据挖掘技术的深入研究，数据挖掘技术必将在更加广泛的领域得到应用与发展。数据挖掘作为一种有效的知识发现手段，可以从大量的无序数据中发现知识，提取规则，用以帮助人们做出实时决策。

1.1.1 数据挖掘的定义

数据挖掘(Data Mining，DM) 是从存储在数据库、数据仓库或其他信息库中的大量数据中挖掘有趣知识的过程，这些知识是隐含的、事先未知的、潜在的有用信息。从技术角度看，数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程；从商业角度看，数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决策的关键性数据。数据挖掘是一个多学科领域，从多个学科汲取营养。它从一个新的角度把数据库技术、人工智能、机器学习、神经网络、统计学、模式识别、知识库系统、知识获取等领域结合起来，从更深层次挖掘存在于数据内部新颖、有效、具有潜在效用的乃至最终可理解的模式。数据挖掘还有另一个常用的术语——数据库中的知识发现(KDD)。

1.1.2 数据挖掘的对象

数据挖掘技术从兴起到发展的十几年间，主要面对的挖掘对象都是以结构化数据为主的关系数据库和数据仓库。但随着数据库技术和Internet技术的迅速发展，大量的复杂类型的数据不断涌现，恰恰正是在这些数据里隐含了更具价值的知识和信息。因此，数据挖掘对象的进一步发展就是针对复杂类型数据的挖掘。复杂类型数据的挖掘主要包括:空间数据挖掘、多媒体数据挖掘，时序数据挖掘，文本数据挖掘，Web数据挖掘，流数据挖掘。

(1)空间数据挖掘

空间数据挖掘(spatial data mining)，是指对空间数据库中非显式存在的知识空间关系或其它有意义的模式等的提取。

(2)多媒体数据挖掘

多媒体数据挖掘(multimedia data mining)，主要是指对多媒体数据库中多媒体数据的相似性搜索，多维分析，分类和预测分析，以及多媒体数据的关联挖掘。

(3)时序数据挖掘

时序数据挖掘(time-series data mining)，主要指对时序数据库中时序数据的趋势分析，相似性搜索，与时间有关数据的序列模式挖掘和周期模式挖掘。

(4)文本数据挖掘

文本数据挖掘(text data mining)，当数据挖掘的对象完全由文本这种数据类型组成时，这个挖掘过程就称为文本数据挖掘。

(5)Web数据挖掘

web数据挖掘(Web mining)，是将数据挖掘技术应用于web，以实现对Web存取模式、Web结构和规则，以及动态的Web内容的查找。一般将Web挖掘分为三类:web内容挖掘(Web content mining)，Web结构挖掘(web strueture mining)和Web使用记录的挖掘(Web usage mining)。值得一提的是XML技术的出现，不仅为互联网上的电子数据交换提供了一个标准，而且XML技术从数据的角度提供了一个更好地表示数据内容以及数据所代表的意义的手段。因此，基于XML技术进行数据挖掘为数据挖掘的研究提供了新的契机。对于Web数据挖掘的研究也逐渐与XML结合起来。

(6)流数据挖掘

流数据挖掘(streamingdatamining)，在数据挖掘和数据分析研究领域中，出现了一个新的研究方向，即流数据的挖掘与分析。流数据是指那些数据量非常巨大的，无法全部存放在存储介质上进行分析和计算的数据。其特点是数据持续到达，且速度快、多变化、规模宏大;其研究核心是设计高效的单遍数据集扫描算法，在一个远小于数据规模的内存空间里不断更新一个代表数据集的结构，使得在任何时候都能根据这个结构迅速获得近似查询结果。

1.1.3 数据挖掘的主要步骤

数据挖掘的主要步骤如下:

(l)问题定义

数据挖掘是为了在大量数据中发现有用的令人感兴趣的信息，因此发现何种知识就成为整个过程中第一个也是最重要的阶段。在问题定义的过程中，一方面明确实际工作对数据挖掘的要求，另一方面通过对各种学习算法的对比来确定可用的学习算法。

(2)数据准备

数据准备又可分为三个子步骤:数据选取、数据预处理和数据变换。

数据选取的目的是确定发现任务的操作对象，是根据用户的需要从原始数据库中抽取一组数据;数据预处理一般包括消除噪声、推导缺失值、消除冗余数据、完成数据类型的转换等;数据变换的主要目的是消减数据的维数，即从初始特征中找出真正有用的特征，以减少数据挖掘时要考虑的特征或变量个数。

(3)数据挖掘

它是数据挖掘算法的执行阶段，也是技术难点所在。首先根据对问题的定义明确挖掘的任务或者目的，如分类、聚类、关联规则发现或序列模式发现等。确定了挖掘任务后，就要决定使用什么样的算法，选取相应

(4)结果解释和评估

数据挖掘的结果有些是有实际意义的，而有些是没有实际意义或没有价值的，或是与实际情况相违背的，这就需要对结果进行评估。评估可以根据用户多年的经验，也可以直接用实际数据来验证模型的准确性，进而调整挖掘模型，不断重复数据挖掘和模型构建过程。

(5)分析决策

数据挖掘的最终目的是辅助决策，决策者可以根据数据挖掘的结果，结合实际情况，调整竞争策略等。

数据挖掘是一个多步骤的处理过程，步骤之间相互影响，反复调整，形成一种螺旋式上升过程。只有这样才有可能达到预期的效果。

1.1.4 数据挖掘的方法及应用

数据挖掘的分析方法主要有关联分析、聚类分析、分类分析、预测分析、序列分析、偏差分析等。

(1)关联分析

关联分析是寻找数据库中值的相关性，即寻找在同一个事件中出现的不同数据项的相关性，比如一次购买活动中所买不同商品的相关性。关联规则可以记为A B，A成为前提，B成为后续，反映A中的项目出现时，B中的项目也跟着出现的规律。关联分析属于数据挖掘研究领域一个比较成熟的分支，人们提出了多种关联规则的挖掘算法，如Apriori、STEM、AIS、DHP等算法。

(2)序列分析

与关联分析相似，序列分析的目的也是为了挖掘数据项之间的联系，但序列分析的侧重点在于分析数据项之间在发生时间上的前后关系。序列规则也可记为A、B，表示A发生以后将会发生B。序列模式分析描述问题的过程是：在给定的事件序列数据库中，每个序列都是按照事件发生时间排列的一组交易集，将挖掘序列函数作用在这个事件序列数据库上，然后返回该数据库中出现的高频序列。

序列规则的研究基本与关联规则同步，各种算法也基本上是对各种关联规则挖掘算法的修改。

(3)分类分析

分类要解决的问题是为一个事件或对象归类。在使用上，既可以用此模型分析已有的数据，也可以用它来预测未来的数据。例如，用分类来预测哪些客户最可能对直接邮件推销做出回应。

分类分析是通过分析己知分类信息的历史数据总结出预测模型。这里用于建立模型的数据称为训练集，通常是已经掌握的历史数据。训练集也可以是通过实际的实验得到的数据。

(4)聚类分析

聚类是把整个数据库分成不同的群组(cluster)。它的目的是要使群与群之间的差别很明显，而同一个群之间的数据则尽量相似。与分类不同，在开始聚类之前我们并不知道要把数据分成几组，也不知道怎么分(依照哪几个变量)。因此在聚类之后要有一个对业务很熟悉的人来解决这样分群的意义。在很多情况下，一次聚集得到的分群对于特定的业务来说可能并不好，这时需要删除或增加变量以影响分群的方式，经过几次反复之后才能最终得到一个理想的结果。神经元网络和K—均值是比较常用的聚类方法。

1.2时间序列数据挖掘的进展

传统的时间序列分析已是一个发展得相当成熟的学科，有着一整套分析理论和分析工具，是目前时间序列分析的主要方法。传统时间序列分析的研究目的在于：

(1)预测时间序列的未来发展情况。

(2)分析特定的数据集合，建立数学模型，进行模式结构分析和实证研究。

传统时间序列分析最基本的理论基础是40年代分别由Norbor Wiener和Andrei Kolmogomor提出的。20世纪70年代，G.P.Box和G.M.Jenkins发表专著《时间序列分析：预测和控制》，对平稳时间序列数据提出了自回归滑动平均模型(ARMA)，以及一整套的建模、估计、检验和控制方法，使时间序列分析得以广泛运用于各种工程领域。

目前，面向工程应用的时间序列分析主要存在两种不同的分析方法和发展路线。一种是频域法，强调谱密度和时间序列谱分析，主要是时间序列做非参数描述，较多地应用与工程物理学科，在经济学领域也有一定的应用。另一种方法是时域法，主要采用相关函数的方法处理随机过程，如用ARMA参数模型拟合观测序列并进行相关分析，更复杂的是用传递函数模型和多元ARMA模型来拟合观测值。其中，最常用也是最重要的依赖模型是ARMA模型，它是AR和MA模型的混合。

然而，大部分时间序列分析方法都是假定存在一类数据序列和可用于该类数据的某种数据结构，然后以此为基础进行推广。通常需要假定序列是平稳的或可以通过某些基本方法使之平稳化。例如，当采用ARMA模型来拟合一个非平稳时间序列时，一般先通过差分法或适当的变换使非平稳序列转化为平稳序列，然后再估计模型的结构参数。用这种参数化方法将时间序列拟合为某种特定的结构，只用到很少的参数，从而使参数的有效估计成为可能。当然，用非参数的谱分析的方法也能使用较少的观测值进行分析，但是时域参数化方法提出了一种更加实用的方法，即从一个序列的历史数据出发，直接进行分析，找出其数据特征，并构造出其模型，再利用模型对该序列的未来进行预测。

在利用传统的统计模型对实际序列进行拟合时经常会遇到两类处理的问题。一个问题是所观测的时间序列往往很少注重，只能获得这些序列在某一段时间内的一次实现。这样在构造一个时间序列 。( 为随机变量)的统计模型时，只能得到 的一次观察。这与通常的基于统计模型的分析方法所要求的并不一致。另一个问题上，对于许多现实世界的时间序列来说，其系统结构本身经常是随时间变化的，因而也不满足通常的统计分析方法中关于模型结构不变的假定。

上述问题促使人们开始从其他方面寻求一些方法来补充传统时间序列分析方法中不足，其中，基于局部模型的分析方法在很多场合被证明是有效的，这促进了一系列关于时间序列局部分析方法的研究。时间序列中静态模式的挖掘研究就是这类研究的一个重要组成部分。

自进入上世纪90年代以来时间序列的数据挖掘技术有了快速发展。由最初相似性的分析到目前的人工智能的多学科交叉研究，时间序列的数据挖掘技术已经有了多个研究方向，主要包括相似性的研究和模式挖掘的研究等，分述如下。

(1)相似性搜索

时间序列数据的相似性搜索问题最早由IBM公司的Agrawal等人于1993年提出，该问题描述为“给定某个时间序列，要求从一个大型时间序列数据库中找出与之最相似的序列”[1]。这与找出符合查询的精确数据的通常的数据库查询是不同的。由于实际需要的驱动，使得在时间序列的数据挖掘研究中，相似性搜索是一个重要的研究内容。在相似性搜索的基础上又发展出了时间序列的聚类、分类、以及关联规则的抽取等等数据挖掘技术。

相似性搜索首先要解决的问题是相似性的定义。相似性就是指测定两个给定的时间序列是否为具有相似的行为曲线。但困难地方是时间序列往往是来自于实际，这使得相似性的测量要求并不是完全严密的，而且时间序列数据库来自于各个领域，测量标准也不尽相同。而相似性度量模型则是依据所定义的相似性进行数学抽象而成。在相似性定义方面，有比较简单粗糙的，如Agrawal等人提出的一种相似性，它是根据直观意义上时间序列数据的上升、下降的趋势定义的，通过这种相似性可以比较粗糙地从数据库中发现具有相似形状的时间序列。后来Agrawal等又提出一种 -相似性度量模型，这种相似性可以容忍时间序列中噪声的存在而引起的局部不匹配，并对时间轴上的偏移以及幅值的缩放不敏感。有的相似性定义则比较复杂，例如GautamDas等提出的一种称为F-相似的相似性模型：设F是一个函数集，对于两个待比较的时间序列而言，如果它们满足一定长度要求的子序列，且存在F中的一个函数f使得其中的某个子序列可以近似的映射到另一个子序列，则称两个时间序列具有F-相似。这种相似性对异常点(outhers)、基线以及比例因子不敏感。

相似性的测量方法包括欧几里德距离测量方法、C-S.Li等提出的相关性测量和动态时间弯曲法DTW等。其中欧几里德距离测量方法是一个基本的、简单的测量方法，多数研究也都是基于欧几里德距离的。为了提高相似计算的效率同时又不会丢失原有的信息，人们又提出对时间序列进行重新描述，经过多年的努力，先后出现了许多面向相似性搜索的时间序列近似表示方法。

本文将在文章的第四部分对时间序列的相似性搜索挖掘做进一步的介绍。

(2)模式挖掘

模式挖掘主要包括时态模式挖掘和趋势预测。时态模式挖掘的一个主要技术是关联规则的挖掘。

①时态模式挖掘

在时态模式挖掘方面，M.chen等人[2]，提出了一种具有比较好的包容性的时态模式挖掘的定义，其定义如下:

定义1.l(时态模式):一个时态模式是一个二元组

。其中Patt是一个一般意义上的模式，可以是趋势、偏差、分类规则和关联规则等，TimeExp就是一个时间表达式，它表示Patt在(TimeExp)中的每个时间区间内成立。

RiehardJ.povinelli对时间序列中的事件(Event)的出现加以模式发现和预测。他对相空间(phase spaces)采用时间延迟法(time-delayed embedding)进行重新构建，然后在相空间上定义了一种事件标志函数，寻找那些对于预测未来事件有用的点进行聚类形成时态模式，用这些时态模式进行事件的预测。GautamDaS[3]则通过在时间序列中挖掘局部模式(local pattern)，从中抽取关联规则。他首先用一个时间窗口在时间序列上滑动形成子序列，然后通过相似性测量对子序列聚类，然后采用规则生成方法发现序列中模式的行为和时间的关系。

②趋势预测

趋势预测采用的技术主要是分类规则的挖掘技术，即Last.M[4]提出的首先对时间序列进行预处理，然后从中抽取关键的预测属性(predicting attributes)，这些属性对时间序列的发展趋势影响较大，将其组成属性集，这些预测属性表征了时间序列的某种特性，这种特性与时间没有关系，因此可以采用普通的静态的数据挖掘工具对时间序列进行行为趋势的分类预测。

1.3本文工作

在分析了国内外时间序列挖掘研究现状的基础上，本文分别详细讨论了时间序列的分段线性划分和时间序列的相似性度量两方面问题。时间序列数据的挖掘在近十几年已经成了数据挖掘中的一个热点。本文在时间序列分段划分上的创新工作是提出了一种新的基于关键点的时间序列分段划分方法。引入了“双阈值”概念来进行关键点的选取，实验表明：该方法能够在剔除噪音干扰的同时，精确定位单调序列中的突变转折点。接下来在分段划分选取高效关键点的基础上，本文在时间序列相似性度量上提出了一种基于关键值的动态时间弯曲距离的相似性度量方法。该方法在时间序列线性拟合的基础上，只保留序列中的关键点来用于弯曲距离矩阵计算，实验结果表明：这种方法在准确性上明显优于欧氏距离，与经典的动态时间弯曲距离相似，检索速度却有了极大的提高。

时间序列数据挖掘是一个有广泛发展前景和重大意义的科研课题，其中的任何一个分支都值得深入的探讨和研究，本文在此方面的研究仅是九牛一毛，但作者希望它能起到抛砖引玉的作用，以引起后来或者其他学者的兴趣，并希望对他们开拓思维有一定的贡献。本文的组织结构如下：

第一章：论述了数据挖掘的定义和分类，介绍了时间序列数据挖掘的进展，并简要介绍了本文主要的研究内容和研究成果。

第二章：介绍了时间序列挖掘的有关研究历史及现状，并简要介绍了时间序列的模式表示与相似性度量的研究进展。

第三章：主要介绍了时间序列的三种线性拟合方法：极值点拟合法、特征点拟合法和局部极值点法，讨论了它们各自的优缺点。提出了时间序列的双阈值关键点线性拟合表示方法，并与极值点拟合法和特征点拟合法两种线性拟合表示方法进行了比较。其中关键点的选取算法是本文的一个创新点。

第四章：介绍了欧几里德距离和动态时间弯曲距离两种常用的相似性度量方法，指出他们各自的优缺点。对分段极值DTW算法进行了改进，提出了基于关键点动态时间弯曲距离的相似性度量算法，从准确率和计算速度两方面与经典动态弯曲距离和分段极值DTW距离进行了比较。

第五章：对全文进行了总结，提出了下一步需要研究的工作，并对该发展方向进行了展望。