V ol.15, No.1 ©2004 Journal of Software 软 件 学 报 1000-9825/2004/15(01)0000 时序数据上的数据挖掘∗ 黄书剑1+1(南京大学 计算机科学与技术系 江苏 南京 210093)Data Mining on Time-series DataHUANG Shu-Jian 1+1(Department of Computer Science and technology, Nanjing University, Nanjing 210093, China)+ Corresponding author: Phn +86-**-****-****, Fax +86-**-****-****, E-mail: ****, http://****Abstract : Data mining has been developing rapidly in the recent years. Since time related data occurs frequently in various areas, there has been “an explosion” of interest in mining time-series data, which is a popular branch of data mining. In this paper we present an overview of the major research areas and tasks in mining time-series data, such as preprocessing, representation, segmentation, similarity, classification, clustering, anomaly detection, rule discovery, etc. Some solutions of several tasks are also included in this paper.Key words : data mining; time-series摘 要: 近年来数据挖掘得到了蓬勃的发展。
由于越来越多的数据都与时间有着密切的关系，时序数据的挖掘作为数据挖掘的一个分支，正在受到越来越高的重视。
本文概述了时序数据上的数据挖掘这个领域内的主要研究方向和课题，包括数据预处理、数据表示、分割、相似度度量、分类、聚类、异常检测、规则识别等。
并对部分课题的主要解决方案进行了一些介绍。
关键词: 数据挖掘;时序数据挖掘中图法分类号: **** 文献标识码: A1 引言近几十年来，计算机运算存储能力不断提高，数据产生和采集的速度也越来越快，因而数据量越来越大；而与此同时，人们面对巨量数据，能够直接获得的信息量却越来越有限。
单纯的人力已经很难胜任对这样巨量的数据进行分析并提取出相关信息的任务。
为了解决这种数据与信息之间的矛盾，数据挖掘应运而生。
所谓数据挖掘，即从巨量数据中获取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程[1]。
数据挖掘的目的就在于找出巨量数据中的潜在规律，以对未来的分析和决策提供支持，其在分析处理中的优势以∗ Supported by the **** Foundation of China under Grant No.****, **** (基金中文完整名称); the **** Foundation of Chinaunder Grant No.****, **** (基金中文完整名称)作者简介: 黄书剑(1984),男,江苏盐城人,硕士生,主要研究领域为自然语言处理.2 Journal of Software软件学报 2004,15(1)及结论的正确性、有效性已经被越来越多的实践所证明。
数据挖掘可以处理各种各样形式的数据，包括关系数据库、数据仓库、事务数据库中的数据，面向对象数据库、对象关系数据库以及空间数据库、时序数据库、文本数据库和多媒体数据库等面向应用的专用数据库中的数据，以及普通文本，互联网中的数据在内的各种数据都可以作为数据挖掘的对象[2]。
本文着重讨论与时序数据的数据挖掘相关的一些内容。
简单的说，时序数据就是和时间相关的数据。
在数据挖掘的实际应用中，很多的数据都是与时间相关的，比如股票市场的交易数据，传感器网络收集到的状态数据，商店的消费统计数据，电话通信量统计数据等等。
这些数据中往往都蕴含着一些跟时间相关的现象甚至规律。
研究这些数据对分析问题的现状(如分析股票交易情况、发现异常交易，总结顾客消费规律等)，以及预测问题将来的发展(如销售决策，传感器分布调整等)，都有很大的帮助[3][4][5]。
时序数据的数据挖掘就是对这些与时间相关的数据进行分析并从中获取相关的信息的过程[4][6]。
本文的后续部分组织如下：第二部分是对时序数据挖掘的目的和过程的进一步介绍；第三部分主要介绍了时序数据挖掘中的主要研究方向和课题，并对部分课题的解决方案及算法进行了一些介绍；第四部分是对时序数据挖掘的一个简单讨论；第五部分是本文的总结。
2 时序数据挖掘概述2.1 时序数据挖掘的概念时序数据广义上是指所有与时间相关，或者说含有时间信息的数据。
但在具体的应用中，时序数据往往是指用数字或符号表示的时间序列[6]，但有的时候特指由连续的实值数据元素组成的序列[4]。
当然连续的实值数据元素在实际处理时可以通过一定的离散化手段，转换成离散的值数据再进行处理。
在大部分情况下，时序数据一般都以时间为基准呈序列状排列，因而，对时序数据的挖掘也可以看作一种比较特殊的序列数据挖掘(Sequence Data Mining)。
2.2 时序数据挖掘的目的时序数据是随着时间连续变化的数据，因而其反映的大都是某个待观察过程在一定时期内的状态或表现。
其研究的目的主要是以下两个方面：其一是学习待观察过程过去的行为特征，比如顾客的消费习惯等；其二是预测未来该过程的可能状态或表现，比如顾客是否会在短时间内进行大规模购物等。
这两个目的直接带来了时序数据挖掘中的一个重要的问题：查找相似的行为模式(Rule Discovery)。
另一个相关的问题就是异常活动检测(Outlier Detection or Anomaly Detection)。
关于这两个问题的详细阐述请参见第三部分。
3 时序数据挖掘中的主要课题时序数据挖掘中的课题，涉及从处理初始数据开始，到通过各种方法分析数据，直至得到所需要的信息的整个过程。
本部分以下内容将介绍时序数据挖掘中的如下几个主要任务：数据预处理(Preprocessing)，时序数据表示(Time-series Representation)，分割(Segmentation)，相似度度量(Similarity)，分类(Classification)，聚类(Clustering)，异常检测(Anomaly detection)，规则识别(Rule Discovery)等。
其他一些时序数据挖掘中的任务，如文献[6][7][8]中提到的：子序列匹配(subsequence matching)，内容查询(retrieval by content)等，限于篇幅，本文不作介绍。
3.1 数据预处理数据预处理泛指对得到的原始数据进行一定的加工处理，使之能够为其他数据挖掘方法所用的过程。
和其他类型的数据挖掘一样，时序数据在进行处理前往往要先进行一些数据预处理，例如去除噪音，填补缺失数值等。
去除噪音可以在数域或频域上采用一定的阈值过滤来完成，而缺失数值则通常可以采用插值的方法进行估计和填补。
这些操作的目的就在于保证数据的可靠性和完整性，在进行进一步分析时，不会因为一些明显不合理的噪音而影响整体结果，也不会因为存在数值确实而影响一些学习方法的正常执行。
作者名等:题目 3数据预处理要涉及的另一个可能的任务就是重新采样(Re-sampling)。
一些研究工作中，并不把时序数据中的时间信息作为主要的研究对象，而是仅要求这些数据按照时间序排列，甚至有的时候要求按照等时间间隔排列，这就涉及到在原数据基础上进行重新采样的问题。
3.2 时序数据表示对时序数据采取有别于原来实值序列的表示方法的原因是：希望能新的表示形式能更好、更简洁的表达出原有数据的主要性质。
有些情况下，研究者会采取特征(feature)的形式来描述时序数据，这就牵涉到特征提取(Feature Extraction)的问题，同时，对于特征数量较为庞大的时候，往往还会通过一些方法来进行维数约简，来提高特征表达能力，并减少特征数量。
常用的方法有奇异值分解(Singular Value Decomposition SVD)、离散傅立叶变换(Discrete Fourier Transform DFT)、离散小波变换(Discrete Wavelet Transform DWT)。
Keogh等人提出了一种称为Piece-wise Aggregate Approximation(PAA)的方法，是一种基于对时序数据进行等距离分割，并在分割内求均值的降维方法，取得了一定的效果[8]。
常见的时序数据表示分为如下几类：Model-Based Representation、Non-Data-adaptive Representation、Data-adaptive Representation以及Data-dictated Representation.3.2.1 Model-Based Representation基于模型的数据表示假设时序数据是由某个模型生成的。
模型被用来与数据拟和，并计算出相应的模型参数，这些参数也会在之后的数据挖掘过程中起到重要的作用。
常用的模型有隐马尔科夫模型(Hidden Markov Model HMM)[9][10]、ARMA(Auto Regressive Moving Average)等。
3.2.2 Non-Data-adaptive RepresentationNon-Data-adaptive Representation是指用和数据独立的转换方法和系数选择，把时序数据转换到一个不同的空间之中表示的方法[8]。
这一工作在很大程度上是为了对数据的进行进一步的降维，在本节开头中提到的几种降维方法如DFT、DWT、PAA等都是基于相应的non-data-adaptive representation的。
此外，文献[11][12]中还使用了一种称为的随机投影(Random projection)的方法进行了时序数据的表示。