V ol.15, No.1 ©2004 Journal of Software  软 件 学 报 1000-9825/2004/15(01)0000                                                                时序数据上的数据挖掘
∗ 黄书剑1+
1(南京大学 计算机科学与技术系 江苏 南京 210093)
Data Mining on Time-series Data
HUANG Shu-Jian 1+
1(Department of Computer Science and technology, Nanjing University, Nanjing 210093, China)
+ Corresponding author: Phn +86-**-****-****, Fax +86-**-****-****, E-mail: ****, ****
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
摘  要: 近年来数据挖掘得到了蓬勃的发展。由于越来越多的数据都与时间有着密切的关系，时序数据的挖掘作为数据挖掘的一个分支，正在受到越来越高的重视。本文概述了时序数据上的数据挖掘这个领域内的主要研究方向和课题，包括数据预处理、数据表示、分割、相似度度量、分类、聚类、异常检测、规则识别等。并对部分课题的主要解决方案进行了一些介绍。
关键词: 数据挖掘；时序数据挖掘
中图法分类号: ****  文献标识码: A
1  引言
近几十年来，计算机运算存储能力不断提高，数据产生和采集的速度也越来越快，因而数据量越来越大；而与此同时，人们面对巨量数据，能够直接获得的信息量却越来越有限。单纯的人力已经很难胜任对这样巨量的数据进行分析并提取出相关信息的任务。为了解决这种数据与信息之间的矛盾，数据挖掘应运而生。所谓数据挖掘，即从巨量数据中获取有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程[1]。数据挖掘的目的就在于出巨量数据中的潜在规律，以对未来的分析和决策提供支持，其在分析处理中的优势以
∗ Supported by the **** Foundation of China under Grant No.****, **** (基金中文完整名称); the **** Foundation of China
under 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  数据预处理
数据预处理泛指对得到的原始数据进行一定的加工处理，使之能够为其他数据挖掘方法所用的过程。和其他类型的数据挖掘一样，时序数据在进行处理前往往要先进行一些数据预处理，例如去除噪音，
填补缺失数值等。去除噪音可以在数域或频域上采用一定的阈值过滤来完成，而缺失数值则通常可以采用插值的方法进行估计和填补。这些操作的目的就在于保证数据的可靠性和完整性，在进行进一步分析时，不会因为一些明显不合理的噪音而影响整体结果，也不会因为存在数值确实而影响一些学习方法的正常执行。adaptive
作者名等：题目  3
数据预处理要涉及的另一个可能的任务就是重新采样(Re-sampling)。一些研究工作中，并不把时序数据中的时间信息作为主要的研究对象，而是仅要求这些数据按照时间序排列，甚至有的时候要求按照等时间间隔排列，这就涉及到在原数据基础上进行重新采样的问题。
3.2  时序数据表示
对时序数据采取有别于原来实值序列的表示方法的原因是：希望能新的表示形式能更好、更简洁的表达出原有数据的主要性质。
有些情况下，研究者会采取特征(feature)的形式来描述时序数据，这就牵涉到特征提取(Feature Extraction)的问题，同时，对于特征数量较为庞大的时候，往往还会通过一些方法来进行维数约简，来提高特征表达能力，并减少特征数量。常用的方法有奇异值分解(Singular Value Decomposition SV
D)、离散傅立叶变换(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 Representation
Non-Data-adaptive Representation是指用和数据独立的转换方法和系数选择，把时序数据转换到一个不同的空间之中表示的方法[8]。这一工作在很大程度上是为了对数据的进行进一步的降维，在本节开头中提到的几种降维方法如DFT、DWT、PAA等都是基于相应的non-data-adaptive representation的。
此外，文献[11][12]中还使用了一种称为的随机投影(Random projection)的方法进行了时序数据的表示。
3.2.3  Data-adaptive Representation
Data-adaptive的方法依赖于一个时间序列或者多个时间序列的整体的时序数据进行系数的选择。在3.2.2中的提到的几种方法中有一些(如DFT)只需在选取系数时取局部或全局的最大项，而不是某一个固定的项(如第一项)，就可以将结果看作Data-adaptive的表示形式。相应的PAA等方法也有对应的Data-adaptive的形式，此外还有许多不同的方法如基于奇异值分解的方法，Symbolic Aggregate Approximation(SAX)方法，Piecewise Linear Approximation(PLA)方法等，都有各自的特点和优势。
总的来说依赖于数据的表示方法在一定程度上保留了数据中比较显著的部分特征为后续分析所用，直觉上可以对整个系统的性能有较大帮助，因而受到了较为广泛的关注。
3.2.4  Data-dictated Representation
Data-dictated实际上可以看作是数据离散化的过程。在这种表示形式中，数据的表示粒度和表示结果的大小是自动决定的。数据离散化的方法很多，文献[13][14]中描述了一种基于两维规则网格的方法，将数据按照规则网格划分的bins存放，最后用bins来代替具体的数值实现离散化。文献[15][16]则分别是采用中间值和平均值作为阈值进行clipping的方法。
3.3  时序数据分割
时序数据的分割大体上有三种类型：滑动窗口、自顶向下、自底向上。目前流行的各种方法虽然名称各异，实现也各不相同，但基本上都可以包含在这三类中[17]。
滑动窗口模型指分割以循环的方式进行，每次处理一个没有被最新分割包含的数据，分割不断的增长知道超出某个界限而停止。滑动窗口模型的效果通常跟数据集合本身有很大的关系，而且滑动窗口的大小选择也是一个比较难确定的问题。自顶向下的模型中，数据不断的按照某种规则被划分，直到满足一定的停止条
4 Journal of Software软件学报  2004,15(1)
件。在自底向上模型中，将最底层的数据作为原始分割，然后不断的合并小的分割直到满足一定的停止条件为止。光从时间性能上比较通常自底向下的方法要好于自顶向下的方法[8]。Himberg等人在实践中采用了一种贪婪算法来改进其他方法产生的分割，也取得了不错的效果[18]。
以上所提到的三种方法都需要人为的提供参数或者停止条件等信息，而这些信息往往都是难以用经验描述的。因此，一些基于统计的方法也逐渐开始发展，一些方法通过比较k个分类和k-1个分类的好坏来自动的确定分类的个数，也有一些通过建立某个符合数据的随机过程模型的方法来完成分割过程。对此本文不作进一步阐述。
3.4  相似度度量
相似度和距离是相对的两个概念，是用来衡量两个(通常是两个，也有可能是多个)数据或实例之间关系的标准。在一定意义上，相似度和距离的表示能力是等价的，他们分别适用于一定的环境，也可以通过一定的方法互相转换。相似度度量问题是数据挖掘中的一个重要问题，是整个数据挖掘过程中的许多其他工作(比如聚类问题等)的基础，相似度度量的好坏对这些问题的解决有着非常大的影响。
以数值时间序列(numeric time-series)为例，相似度的度量可以分为如下几类：基于形状的(Shape-based)相似度、基于特征的(Feature-based)相似度、基于模型的(Model-based)相似度、基于数据压缩的(Compression-based)相似度[8]。
3.4.1  基于形状的相似度
欧式距离(Euclidean distance)是对于数值的时间序列而言最简单却应用最广泛的基于形状的距离。此外Manhattan的p=1和Maximum的p=∞时的Lp范式也是常用的距离度量。但是，直接使用这种度量也有一些共同的缺点，这些距离在对数据进行缩放或转换时容易受到影响，而且距离受噪声、特殊值以及数据是否归一化的影响也较大。因此人们开始寻适当的转换使得这些Lp距离能够在以上这些变化发生时保持不变，对于不同的应用来说，到一个有意义的转换方式也是一个很重要的课题[8]。
跟Lp距离相关的有另外两个距离定义：Correlation和Cosine distance。Correlation的定义是基于衡量线性相关性的Pearson correlation系数，要求时间序列都是独立的，而且所有的时间点是符合同一个概率分布的独立样本。Cosine distance则将不同的时间序列描述为多维空间中的向量，并用他们之间的夹角来表示距离。
对于大量的长度不一的时序数据，基于形状的相似度度量效果往往不好，这时，就得考虑基于特征或者基于模型的相似度。
3.4.2  基于特征的相似度
抽取特征并比较特征集合的相似度计算方法和具体的应用领域有很大的关系。对于一些具有某些重要特征的时序数据，选取合适的特征来表示可以收到很好的效果。除了人工抽取比较重要的特征以外，也可以像上文3.2.3节中提到一样，取DFT或者DWT后得到的最大的系数作为特征，用来表示整个数据。文献[19]中提到了一种通过对时间点加上偏向最近时间的权重，从而自动选取独立于数据的系数作为特征的方法。从整体来说，目前，基于特征的相似度度量还是一个有很强的领域相关性，需要较多人为干预的过程。
3.4.3  基于模型的相似度
与基于特征的相似度相比，基于模型的相似度有一个很大的优势，那就是基于模型来计算相似度可以将预先得到的关于数据产生的知识结合进来。通常计算相似度时，对每一个时间序列建模，并用对某个序列所建模型生成另一序列的概率值来衡量这两个序列间的相似度。常用的模型有上文提到过的HMM，AMRA等，近年来对这些模型本身及使用方法的研究和改进也是一个重要的研究课题。
基于模型的方法往往需要较长的时间序列来完成较好的参数估计，对于较短的、采样不规则的时间序列，文献[20][21]提供了一种将形状和模型相结合的方法。文献[22]则描述了一种将形状和特征相结合的相似度度量方法。这些混合模型的方法在某些应用中会收到意想不到的效果。
3.4.4  基于压缩的相似度
基于压缩的时序数据相似度来自于生物信息学和计算理论研究的一些结果，是一个较新的想法[8]。
作者名等：题目  5
Compression-Based Dissimilarity Measure (CDM)的基本思想认为对相似数据的连接和压缩，应该得到比在相差较大的数据上做同样操作更高的压缩比率。Kolmogorov复杂度是指生成所得数据的最短程序长度。基于条件Kolmogorov 复杂度，Keogh等人定义了CDM，并说明了其在聚类、分类、异常检测等工作上的优越性能[23]。
3.4.5  符号时序数据(symbolic time-series)的相似度
对于符号时序数据，可以直接通过对符号序列的比较来计算两个时间序列的距离，被称为Proximity-based method。较典型的例子是计算编辑距离(edit distance)的方法，定义两个时间序列的距离为将其中一个转换为另一个所需要的最少转换数。
此外对符号时序数据也可以使用上文所提到的基于特征、基于模型或者基于压缩的方法，只是根据方法类型不同需要在符号数据和数值数据之间做一些转换。
3.5  分类问题
分类就是根据某个训练好的模型给数据选择某种已知类型标记的过程。按照处理的对象不同，时间序列的分类问题有两种，一种是对整个时间序列的分类问题，由一组时间序列训练一个分类器来标注新的时间序列，其中每个序列只有单独的一个标记。另一种分类问题是对时间序列中的时间点进行分类，训练集合中每一个时间序列的每一个时间点都一个标记，训练成的分类器会对新到的序列数据中的每一个时间点进行分类[8]。
3.5.1  时间序列的分类问题
常见的时间序列的分类问题大都由提取时间序列特征加上某个机器学习的分类算法组成。特征提取的
方法可以参见上文3.2时序数据的表示一节，常用的分类算法则范围较为广泛，由经典的C4.5决策树算法到近几年较为流行的支持向量机(Support Vector Machine SVM)的方法都可以应用到该问题中。
以往大部分的分类方法都将特征的选择提取与统计学习的方法分开处理，近年来，将时序结构与学习算法更紧密结合起来的想法也渐渐被人们关注，文献[24]中就提到了一种采取上述思想的决策树算法。此外，文献[25]中提出，对一个完整的时间序列可能比抽取出来的特征更具有价值，由这种思想出发，采用整个序列作为独立节点进行训练的k近邻分类器在一些数据集上也取得了不错的效果。
3.5.2  时间点的分类问题
对于时间点的分类问题往往采用基于滑动窗口的特征选择方法，将每个时间点及周围相邻时间点的特征用向量进行表示，然后再采用一些分类方法进行分类。常见的分类模型有：隐马尔可夫模型，条件随机场模型，最大熵马尔可夫模型等。Cotofrei和Stoffel提出了一种基于一阶逻辑的分类模型，将时间序列用等频直方图来离散化，再通过差分或分割获得每个时间点的特征向量用以进行分类器训练。训练时，通过滑动窗口来保持数据的时间顺序[26]。
3.6  聚类问题
聚类的目的是为了发现数据集合内部的某种联系。聚类过程一般以某种距离或相似度度量为基础，结
果中每个类的内部应该尽可能类似，而类与类之间应该保证尽量大的差别。和分类问题一样，聚类问题也可以按照操作的对象进行分类：以一组时间序列集合进行聚类，可以称为全序列聚类(whole series clustering)；对某一个时间序列的若干分割即子序列进行聚类，称为子序列聚类(sub-series clustering)；对某一个时间序列中的若干时间点进行聚类，称为时间点聚类(time point clustering)[8]。
全序列聚类问题的情况和分类问题很像，主要分为距离表示和聚类算法选择两个方面。欧式距离和DTW 距离是常用的距离表示，更多的距离问题参见3.4节。常用的聚类算法有k均值，k中值等。如何更合适的定义距离，更有效的利用时序数据表示中的信息，使得聚类更能反映数据的本质情况是这一方向研究的重点问题之一。文献[23]中就是一种利用基于压缩的距离表示进行聚类的例子。
子序列聚类由于是在同一个时间序列的内部进行聚类，往往会采用滑动窗口的方法，因而窗口的大小以及窗口之间间隔的大小选择问题，对这种聚类的结果有着非常大的影响。
时间点聚类的过程跟时间序列的分割比较相近，所不同的是，聚类是按照内部联系将一个时间序列内的

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。