基于OLPP符号表示的时间序列分类算法

武天鸿 翁小清

(河北经贸大学信息技术学院 河北 石家庄 050061)

0 引 言

时间序列通常是指按时间顺序排列而成的一组数据，任何有序的实值型数据都可以当作时间序列处理[1]。时间序列分类根据训练集中对象所构建的分类模型，判别被分类对象所属的类别[2]。时间序列分类已经被广泛应用于生活的各个方面，如模式识别、工业控制、金融和交通等，但时间序列数据维度高，分类难度大。

时间序列符号表示是一种重要的时间序列分析方法，是指将连续的实值型数据表示成低维离散的符号序列数据。时间序列符号表示方法不仅简单高效，对噪声具有鲁棒性，还可以利用来自文本处理、信息检索和生物信息学等领域的算法，对于提高时间序列分类算法的性能和效率具有重要意义。SAX(Symbolic Aggregate approXimation)[3-4]是一种经典的时间序列符号表示方法，该方法能较好地体现时间序列的整体趋势且简单高效。但SAX只适用于服从高斯分布的时序数据，且仅用分段的均值并不能很好地描述时间序列的局部特征，完全不同的时间序列可能会得到相似的符号表示，SAX的MINDIST距离度量的紧性较差，容易产生误报。目前，大部分基于符号表示的时间序列分类研究主要集中在SAX性能的改进上，符号化时只考虑了单个时间序列样本的数据，没有考虑数据集样本间的近邻关系对分类的影响，且降维过程中没有利用类标签的信息，是无监督的表示方法。

本文提出一种基于正交局部保持映射[5]符号表示的时间序列分类方法OLPP_SC(OLPP Symbolic Classification)。该方法使用OLPP 将原始高维的时间序列数据映射到低维空间，在降维的同时很好地保留数据在原始空间的局部近邻结构；利用信息增益在降维后的数据上寻找最佳符号区间划分点，采用多重系数分箱技术[6]将维数约简后数据离散表示成符号序列，最后根据最近邻法对符号表示的时间序列进行分类。OLPP_SC清晰地考虑了样本间近邻关系和类标签信息对符号化分类的影响，具有自适应的符号区间分段点，且仅需要较少的维数和字母个数就能达到不错的分类效果，对于解决时间序列分类中的维数灾难问题具有重要意义，在计算资源和存储资源较少的设备中具有适用性。

1 相关研究

1.1 正交局部保持映射

正交局部保持映射是由局部保留投影(Locality Preserving Projection,LPP)[7]衍生的一种线性维数约减方法。LPP可得到一个简单的线性变换，这个线性变换能够最优地将时间序列数据在高维空间的局部几何结构信息保留到低维空间。LPP的变换向量是非正交的，数据重构困难，而OLPP的变换向量是正交的，具有比LPP更强的局部保留能力。非线性降维方法如局部线性嵌入[8](Locally Linear Embedding,LLE)、等距映射[9](Isometric Mapping,IsoMap)以及拉普拉斯特征映射(Laplacian Eigenmaps,LE)[10]等，只能用于给定的数据集，缺乏将新数据或对象映射到低维空间的泛化能力，不适合解决分类问题。由于OLPP对测试样本的适用性，相较于非线性降维方法，OLPP更适用于分类问题。OLPP降维算法可应用于人脸识别[11]和文本索引[12]等方面。OLPP的实现[5]可简述如下：

OLPP方法寻找一个变换矩阵G，该变换矩阵能够将已知高维空间训练数据集X=[x1,x2,…,xk]∈Rm映射到低维空间数据集Y=[y1,y2,…,yk]∈Rd,(d≪m)，即yi=GTxi。通过对如式(1)所示的最小值问题进行优化求解转换矩阵G，约束条件为gTXDXg=1，其中g为转换向量。

(1)

可以采用两种模式构造邻近图：KNN模式和Supervised模式。KNN模式是指采用欧氏距离计算数据点间的距离，选取最近的k个点作为近邻构造近邻图，是无监督的方法；Supervised模式是指根据类标签将属于同一类的数据点相连，是有监督的方法。定义相似矩阵(或权重矩阵)S，Sij评估数据集的局部近邻结构，其数学定义如下：

(2)

式中：t为常数。

令变换矩阵G中的变换向量为{g1,g2,…,gk}，定义G(k-1)=[g1,g2,…,gk-1],B(k-1)=[G(k-1)]T(XDXT)-1G(k-1)，可通过如下方式迭代计算正交变换基向量：g1等于与(XDXT)-1XLXT的最小特征值对应的特征向量；gk等于与式(3)的最小特征值对应的特征向量。

M(k)={I-(XDXT)-1G(k-1)[B(k-1)]-1[G(k-1)]T}

(XDXT)-1XLXT

(3)

xi→yi=GTxi

(4)

式中：yi是d维向量；G是m×d变换矩阵。

降维后的两个数据点在低维空间的欧氏距离可以表示为：

Dolpp(yi,yj)=‖yi-yj‖=

‖xi-xj‖

(5)

G为正交矩阵,GGT=I也是单位矩阵，原始数据集的空间结构能够被很好地保留。

1.2 信息增益

信息增益(Information Gain)[6]表示得知特征X的信息而使得类Y的信息的不确定性减少的程度。对于分类系统而言，假设Y={(s1,y1),(s2,y2),…,(sN,yN)}是由N个值与类标签对组成的列表，pyi是标签yi在Y中出现的频率，则多分类的熵定义为：

(6)

若以sp为符号区间分割点，则sp的熵如下：

(7)

式中：YL={(si,yi)|si≤sp,(si,yi)∈Y};YR={(si,yi)|si>sp,(si,yi)∈Y}。分割点sp的信息增益为：

inf_gain=Ent(Y)-Ent(Y,sp)

(8)

本文提出的时间序列符号表示方法，利用信息增益寻找符号区间的最佳划分点，使每个分区中的大多数值对应于同一个类，可以用同一个字母表示。这种有监督的符号表示方法能够充分利用类别的标签信息，有效提高训练模型的分类能力。

1.3 相关研究评述

基于符号表示的时间序列分类方法，根据时间序列数据转化成符号序列的不同方式大致可以划分为4类：基于趋势分析，基于聚类或进化计算，基于文本，基于频率域。

针对SAX存在的缺陷，学者们提出的改进方法大致可归结为从局部趋势特征描述、距离度量、符号区间划分和序列分段4个方面，不同程度地提高算法分类性能，但是也不可避免地带来一些新的问题，如参数选择困难、计算复杂度高和维数约简性能较差等。

Lkhagva等[13]提出使用每个分段的最小值、最大值和均值表示的 ESAX(Extended SAX)，字符串长度是SAX的三倍，且较SAX分类效果不显著。将每个分段的线性回归量化为字母表中一个符号的表示方法1d-SAX[14]在分段有噪声时拟合误差较大。首先将时间序列转换成比值序列，再根据比值序列分段的趋势特征进行符号表示的方法[15-17]，在一定程度上保留原始时间序列的整体趋势变化信息，但是对于变化特征不明显的时间序列具有一定的局限。虽然符号与数值混合的表示方法[18-21]能够显著提高分类准确率，但是不能应用来自信息检索、文本处理和生物信息学等领域算法，应用领域受到限制。

为了减少SAX离散化过程中的信息丢失，Yin等[22]根据全局关键点将长时间序列分成若干个分段，依据各分段的趋势特征对时间序列符号化，Fuad等[23]对距离查找表进行改进提出UMD，这两种方法在下界距离紧性和分类性能方面都好于SAX。Bai等[24]提出的rSAX通过小距离调整分段点使得彼此接近的点以更高的概率映射到相同符号。Sharabiani等[25]先使用SAX将时间序列转化为符号序列，在符号序列上使用Bayesian规则和概率链规则建立模型BCM，然后用BCM对待测符号序列进行分类，然而，BCM的分类准确率与原始时间序列使用欧氏距离的1NN分类的准确率差别不显著。基于聚类和进化计算的符号表示方法[26-31]，不管数据集是否具有Gaussian分布性质都具有较好的适应性，扩展了SAX方法的适用范围，但这类方法对于合适的聚类半径、种群数量和进化代数等参数的选择是非常困难的，且所需存储空间大、计算复杂度高。

将时间序列表示成符号序列后可利用自然语言处理的方法进行分类，如：Boer等[32]使用Edit距离对符号序列进行分类，分类性能好于Lin等[33]提出的BOP(Bag-Of-Patterns)模型；Senin等[34]提出将SAX与向量空间模型相结合的SAX-VSM模型。BOP和SAX-VSM可兼顾时间序列数据的局部特性和整体特性，对偏移量和噪声具有鲁棒性，分类准确度高，但是，这类方法通常在训练阶段的时间复杂度比较高，需要存储空间也较大。

目前基于频率域的符号表示分类方法的相关研究较少，主要是Schafer等[6]提出的SFA(Symbolic Fourier Approximation)以及以SFA为基础的改进算法[35-37]。SFA首先对时间序列进行离散傅里叶变换，利用信息增益寻找前n个傅里叶系数的符号区间划分点，并使用等宽离散方法对每一维系数进行符号表示。基于频率域的符号表示方法能够有效解决分类任务中的维数灾难问题，而且能够在一定程度上反映时间序列的整体变化趋势。

武天鸿等[38]提出一种有监督的时间序列符号化分类算法LDA_SC(LDA Symbolic Classification)，该算法考虑了样本类别的标签信息对符号化分类的影响，分类效果好于已有方法。

大多数已有方法对原始时间序列进行符号表示时，仅考虑了单个时间序列样本的局部形态特征或整体趋势，没有考虑样本之间的近邻关系对符号化分类性能的影响。在分类问题中，清晰的样本间近邻关系能够提高算法的分类性能，有监督的符号表示方法具有更好的分类效果。

2 算法设计

2.1 符号近似表示

本文提出基于正交局部保持映射的符号表示方法SOLPPA (Symbolic OLPP Approximation)，该方法使用OLPP将时间序列的长度由n降到w(w≪n)，采用数据自适应的MCB方法，对维数约减后数据使用大小为a(2≤a≤20)的字母表进行符号表示。使用SOLPPA将时间序列T近似表示成符号序列的过程如图1所示。

图1 SOLPPA符号近似表示过程

MCB是指根据每组数据的自身特点确定不同的离散间隔，各组数据之间离散间隔的分布是不同的，比如对时间序列的每一维数据可以采用等深或等宽的方式离散化，但是各个维度的数据的离散间隔分布不同。在SOLPPA算法中，使用信息增益确定降维后数据每一维的a-1个最佳分段点，即对应a个符号的离散区间，落入任意区间的时间序列数据用相应的符号表示。由于每维数据分段点的位置是不同的，长度为w的时间序列就有w组不同的分段间隔。这种方法能够将离散化过程中的信息损失降到最小，在一定程度上提高分类准确性。

2.2 距离度量

考虑两条具有相同长度n的时间序列Q和C，它们之间的欧氏距离可表示为：

(9)

式中：qi和ci表示时间序列Q和C在时间点i的值。

(10)

(11)

2.3 算法步骤

本文提出的基于OLPP符号表示的时间序列分类算法主要包括三个步骤：(1) 使用OLPP将训练集和测试集从高维空间映射到低维空间；(2) 在降维后训练集的每一维上寻找符号区间分割点，根据分割点将降维后训练样本表示成符号序列；(3) 利用训练集的分割点，将低维空间的测试样本表示成符号序列并分类。基于OLPP符号表示的分类算法如下：

OLPP_SC(TRAIN,TEST,w,a,PCAratio,k，t)

输入：训练集TRAIN，测试集TEST，OLPP降维数w，字母个数a，PCA率PCA_ratio，近邻个数k和参数t。

输出：分类准确率accuracy。

Step1将TRAIN投影到PCA子空间，可通过PCA_ratio调整对原始数据降噪和消除矩阵奇异性的程度，PCA的转换矩阵用WPCA表示。

Step2构建邻接图P：在KNN模式中，若xi是xj的k近邻或xj是xi的k近邻，将xi与xj用一条边相连,默认t=1；在Supervised模式中，将属于同类别的两个样本用一条边相连，通过调节t值控制各边权重，此时k不起作用。

Step3根据式(2)计算相似矩阵S及拉普拉斯矩阵G，L=D-S。

Step4根据式(3)，计算由正交基向量组成的转换矩阵Gk={g1,g2,…,gk}。

Step5根据式(4)计算嵌入结果，yi=WTxi，其中W=WPCAGk。

Step6取出低维空间中训练集的某一维数据，根据式(6)-式(8)寻找信息增益最大的分段点sp1。

Step7分别在sp1前后两段数据中找出分段点sp2和sp3，重复执行，直至找出(a-1)个分段点，将该维数据划分成a个区间，分别用a个不同字母表示。

Step8将每个样本在该维的数据，根据其所在区间，转换为相应的字母。

Step9重复执行Step 6-Step 8，直到训练集每一维数据都映射成字母，每个样本也就表示成了符号序列。

Step10使用Step 5中的变换矩阵W，将TEST样本映射到低维空间，使用TRAIN的分段点将低维空间的测试样本表示成符号序列。

Step11使用最近邻分类器，根据距离函数DIST对表示成符号序列的测试样本进行分类。

OLPP_SC根据OLPP构造邻接图的两种方法分为OLPP_SC的KNN模式和Supervised模式。OLPP_SC主要分为数据降维和符号表示两个阶段，Step 1是使用PCA对m个长度为n的样本组成的训练集进行预处理，其时间复杂度为O(m×n2)，Step 2搜索具有相同类标号的样本构建邻接图，时间复杂度为O(n×m2)，Step 3-Step 5为计算正交基向量，若将n维降到d维，时间复杂度为O(d×m×n)；Step 6-Step 9为符号表示阶段，用大小为a的字母表，将降维后的样本表示成符号序列的时间复杂度为O((a-1)×m×d)，Step 10对表示成符号序列的测试样本进行分类，时间复杂度为O(m2)，所以算法总的时间复杂度为O((m×n2)+(n×m2)+(d×m×n)+((a-1)×m×d)+m2)。

3 实 验

本节对OLPP_SC在20个来自UCR[39]档案库的单变量时间序列数据集上的分类性能进行评估，评估标准是分类准确率。

3.1 数据集描述

20个时间序列数据集主要来自工业控制、人脸识别、医疗监测等领域，表1描述了这些数据集的主要特征。

表1 数据集描述

3.2 性能比较

将OLPP_SC方法的分类性能与SAX、ESAX、BCM、SAX_SM、LDA_SC五种方法进行比较，评估标准为分类准确率。为了实验对照，将字母个数限制在2～10之间。表2中分别给出了使用SAX、ESAX、BCM和LDA_SC四种方法在测试集上的分类准确率及相应参数，其中：w是符号序列的长度(即低维空间的维数);a是字母表的大小;PCA_ratio是LDA_SC算法中的PCA比率。

表2 SAX、ESAX、BCM和LDA_SC的分类准确率比较

表3给出了使用SAX_SM和OLPP_SC的两种模式在测试集上的分类准确率和相应的参数设置，其中：PCA_ratio是OLPP_SC算法中的PCA比率，k是近邻个数;t是相似矩阵中的计算权重系数的常数。

表3 SAX_SM和OLPP_SC的两种模式的分类准确率

续表3

分析表2和表3中实验结果可知，OLPP_SC算法的两种模式在20个数据集上分类的平均准确率高于另外五种方法的平均准确率，且OLPP_SC仅需要较少的维数就能够达到较好的分类效果；OLPP_SC的Supervised模式的平均分类准确率大于KNN模式的平均分类准确率，Supervised模式分类性能比KNN模式的分类性能更好。

采用Wilcoxon符号秩检验对实验结果进行进一步评价。从表4可以看出，OLPP_SC的KNN模式与SAX、ESAX、BCM、SAX_SM的Wilcoxon符号秩检验的概率p值都小于0.05，说明OLPP_SC_KNN的分类性能显著地好于这四种分类方法。OLPP_SC_KNN的平均分类准确率高于LDA_SC，但分类效果与LDA_SC差别不显著；OLPP_SC的Supervised模式同时考虑了样本间近邻关系和类别的标签信息，OLPP_SC_Supervised与另外五种算法的Wilcoxon符号秩检验的概率p值都小于0.05， 说明OLPP_SC_Supervised的分类效果显著好于其他算法，样本间的近邻关系对符号化分类效果具有重要影响。

表4 Wilcoxon符号秩检验

3.3 参数对分类性能的影响

本文提出的OLPP_SC算法的KNN模式有4个参数，即嵌入维数w、字母表大小a、PCA_ratio和近邻个数k，Supervised模式有4个参数，即嵌入维数w、字母表大小a、PCA_ratio和参数t。

图2给出了OLPP_SC的KNN模式在Synthetic_control数据集上，当嵌入维数为20，k=9，PCA_ratio=0.99时，准确率随字母表大小a的变化情况。图3给出了OLPP_SC的Supervised模式在Synthetic_control数据集上，当嵌入维数为22，t=8，PCA_ratio=1时，准确率随字母表大小a的变化情况。分析图2和图3可以得出，字母个数小于3时，accuracy相对较低，字母个数在4～6之间分类准确率较高，随着字母个数继续增加，准确率趋于平稳。字母表的大小对OLPP_SC的分类性能具有较大影响，OLPP_SC仅需要较小的字母表就能取得不错的分类效果，不需要太多的资源存储距离查找表，分类计算复杂性也较低。

图2 KNN模式准确率随a的变化(Snthetic_control数据集)

图3 Supervised模式准确率随a的变化(Snthetic_control数据集)

图4给出了OLPP_SC的KNN模式在Facefour数据集上，使用大小为8的字母表，k=7，当PCA_ratio=0.99时，准确率随嵌入维数w的变化情况。图5给出了OLPP_SC的Supervised模式在Synthetic_control数据集上，使用大小为8的字母表，t=8，当PCA_ratio=0.99时，准确率随嵌入维数w的变化情况。分析图4和图5可知，当嵌入维数w比较小时，分类准确率比较低，随着嵌入维数w逐步增加，准确率快速升高并趋于稳定。这说明嵌入维数对OLPP_SC具有较大影响，OLPP_SC不需要很高的嵌入维数就可以获得很好的分类效果，良好的维数约简性能对于解决时间序列分类中的维数灾难问题具有重要意义，且对计算资源和存储资源较少的设备具有适用性。

图4 KNN模式准确率随w的变化(Facefour数据集)

图5 Supervised模式准确率随w的变化(Synthetic_control数据集)

图6给出了OLPP_SC的KNN模式在Synthetic_control数据集上，当字母个数为8，嵌入维数为25，k=7时，准确率随PCA_ratio变化的情况。图7展示了OLPP_SC的Supervised模式在Synthetic_control数据集上，当字母个数为8，降维数为22，t=8时，准确率随PCA_ratio变化的情况。分析图6和图7可知，准确率在一定区域内波动，PCA_ratio对OLPP_SC算法性能影响较小。PCA_ratio的主要作用是消除噪声和矩阵奇异性，如果PCA_ratio太小会造成信息损失过多，一般PCA_ratio的取值为80%～100%。

图6 KNN模式准确率随PCA_ratio变化(Synthetic_control数据集)

图8和图9分别给出OLPP_SC的KNN模式在gun-point数据集和Oliveoil数据集上，使用大小为6的字母表，嵌入维数为20，当PCA_ratio=0.99时，准确率随近邻个数k的变化情况。可以看出，近邻个数k对分类性能影响较大，通常选取较小的k值就能达到较好的分类效果，k值取得越小，表示的线性结构越明显，但是若邻域过小，无法保证距离较远的数据间有足够的联系，算法不稳定；如果k值较大则会无法较好地逼近局部线性结构，且计算量较大，准确率较低。

图8 KNN模式准确率随k的变化(gun-point数据集)

图9 KNN模式准确率随k的变化(Oliveoil数据集)

权重的设置与空间结构的保留情况有很大关系，调节OLPP邻接图各边上的权重大小可通过改变t值实现，当t取无穷大时，权重逼近于1，此时可看作是LPP相似矩阵的推广，t的取值与局部保留规模有关。图10 给出OLPP_SC的Supervised模式在Trace数据集上，当字母个数为9，嵌入维数为35，PCA_ratio=0.99时，准确率随t的变化情况。图11是OLPP_SC的Supervised模式在Synthetic_control数据集上，当字母个数为8，嵌入维数为22，PCA_ratio=0.99时，准确率随t的变化情况。分析图10和图11可得出，参数t对算法具有较大影响，t的值选取过大或过小都会使算法的分类准确率降低，恰当地选取t值能够使OLPP_SC得到较好的分类效果。

图10 Supervised模式准确率随参数t的变化(Trace数据集)

图11 Supervised模式准确率随参数t的变化(Synthetic_control数据集)

4 结 语

本文提出的基于OLPP符号表示的时间序列分类方法，在降维去噪的同时清晰地保留了样本间的近邻关系，使用信息增益寻找分段点能够减少离散过程中的信息丢失，且有效利用样本的类别信息。在20个时间序列数据集上的实验结果表明，OLPP_SC好于已有的基于符号表示的时间序列分类方法，清晰的样本间近邻关系能够提高算法的分类性能，有监督的符号表示方法具有更好的分类效果。本文提出的OLPP_SC方法在目前使用全局统一的邻域参数，对于如何根据样本分布寻找自适应的参数有待讨论，如何将该算法与向量空间模型结合以及如何将OLPP_SC应用于多变量时间序列的分类，还需要进步一研究。