Page 241 - 《软件学报》2020年第10期

张伟 等:一种时间序列鉴别性特征字典构建算法 3217

目前,获得的时间序列通常具有如下两个特点:时间序列数据集的规模很大,同时,每条时间序列数据的维度都
很高.
时间序列分类(time series classification,简称 TSC)技术的研究涉及到许多方面的技术问题,这些问题可能
包括时间序列特征的发现或生成以及如何存储或压缩时间序列等.Esling 等人对时间序列的研究领域给出了详
[4]
[5]
细介绍 .Bagnall 等人对各种时间序列分类算法进行了详细分析 .一般 TSC 算法可大致分为两类:基于完整时
[6]
间序列的方法和基于局部特征的方法 .前者基于全局相似性进行分类预测,主要研究相似性的不同度量方式
和使用方法 [7−11] ;而后者基于时间序列的局部特征进行分类预测,通常利用不同的特征生成和转换技术来发现
局部特征,然后基于建立的特征集合直接构建分类模型或对时间序列数据进行转换 [12−15] .然而,目前多数的 TSC
算法无法以足够的精度和速度充分处理大规模的数据.一些精度较高的分类算法,例如,基于局部鉴别性特征
4 [16]
2
Shapelet 的转换算法的时间复杂度为 O(N ×n ) ,其中,N 为时间序列数据集中的实例数,n 为时间序列的长度.
基于时间序列转换的集成分类算法(the collective of transformation-based ensembles,简称 COTE) [17] 的分类精度
显著地优于常见的时间序列分类算法,但该算法中包含多个时间复杂度非常高的基分类器.
为了提高 TSC 算法的分类效率,时间序列的快速转换表示方法成为当前的一个研究热点.本文对基于特征
包(bag-of-pattern,简称 BOP)的分类模型进行研究,这类模型具有分类精度高和运行速度快的特点.BOP 模型将
时间序列分成一系列子结构,并将这些子结构作为离散化特征构建特征字典,最后将基于特征频数的向量作为
模型训练和分类的基础.最早的特征包模型(bag-of-patterns using symbolic aggregate approximation,简称 BOP-
SAX) [18] 使用固定长度的滑动窗口和符号聚合近似技术(SAX)将每个窗口中的子序列转换成离散化特征,然后
使用基于频数向量的欧几里德距离作为相似性度量方式,最后通过 1NN 分类器进行分类预测.Senin 等人利用
SAX 技术和向量空间模型构建了一种新的时间序列分类模型(symbolic aggregate approximation and vector
space model,简称 SAX-VSM) [19] ,该模型基于词频-逆向文档频率(term frequency-inverse document frequency,简
称 tf-idf)对符号化特征进行加权,同时使用余弦距离代替欧式距离进行相似性度量;此外,它只为每个类构建一
个特征向量,而不是每个样本一个向量,这极大地缩短了模型的运行时间.Neuyen 等人 [14] 对基于 SAX 的转换方
法的可变长度的单词进行了研究,并将序列学习算法用于转换后的时间序列分类问题.SAX 技术本质上仍然是
在时域空间对时间序列进行处理,然而,实际中的一些问题在时域空间进行处理时会比较困难,而在频域空间更
容易取得好的处理效果.例如,通常可在频域空间将代表噪声的频率成分去除来实现降噪.此外,频域中包含一
些时域难以发现的鉴别性信息.
离散傅里叶变换(discrete Fourier transform,简称 DFT) [20,21] 可将时域空间的时间序列转换为一组频域空间
的不同频率的正弦波.因此,基于离散傅里叶变换的时间序列符号化表示方法受到各国研究人员的重视.Schafer
等人 [22] 提出用符号傅里叶近似(symbolic Fourier approximation,简称 SFA)来代替 SAX 对时间序列进行离散化
表示.接着,Schafer 又提出了一种基于 SFA 的特征包算法(bag-of-SFA-symbol,简称 BOSS) [23] ,但该算法对时间序
列离散化过程中只简单挑选前 l 个傅里叶值,未考虑傅里叶值的鉴别性.为此,Schafer 等人进一步提出一种用于
时间序列的单词抽取方法(word extraction for time series classification,简称 WEASEL) [24] ,该方法用鉴别性较强
的 top-l 个傅里叶值代替前 l 个傅里叶值对时间序列进行符号化,但是该方法存在一个明显的缺陷,其将所有长
度子序列转化得到的单词设为定长,即,所有子序列经离散傅里叶变换后保留的傅里叶值的个数相同.然而,实
际中不同周期的时间序列子序列所含有的鉴别性频域信息量可能不同,单一的固定长度会导致损失大量鉴别
性信息或包含冗余信息.为此,针对目前基于 SFA 的时间序列离散化表示方法存在的问题,本文首先提出一种用
于时间序列分类的基于 SFA 的可变长度单词抽取算法(variable-length word extraction algorithm,简称 VLWEA).
该算法为每个窗口长度学习性能最优的单词长度.图 1 展示了本文提出的变长单词抽取算法相对于定长单词
抽取算法所具有的优势.图中,w 表示滑动窗口长度,l w 表示长度为 w 的滑动窗口中提取的单词长度,c 1 和 c 2 表示
类别.
图 1(b)中给出了长度为 6 和 8 的滑动窗口获得的 4 个子序列经过 SFA 转换得来的完整字符序列.图 1(a)
所示为用定长单词抽取算法得到的特征(假定共同单词长度为 4),其中,“6aabc”表示一个长度为 6 的滑动窗口子