0 引言

时间序列分类已成为数据挖掘领域最重要的研究方向之一。时间序列是由多个特定时间上的数据点组合而成的高维向量。由于时间序列的高维性,传统的时间序列分类方法存在运算时间过长以及算法效率低下等缺点。因此在对时间序列进行数据挖掘前,对原始数据进行相应的降维处理变得尤为重要。目前,已经提出许多用于时间序列预处理的降维算法,如离散傅里叶变换(discrete fourier transformation,DFT)^[1]、离散小波变换(discrete wavelet transformation,DWT)^[2-3]、分段累计近似(piecewise aggregate approximation,PAA)^[4-5]、符号累计近似(symbolic aggregate approximation,SAX)^[5-6]、奇异值分解(singular value decomposition,SVD)^[7]、分段矢量量化(piecewise vector quantized approximation,PVQA)^[8-9]等。对于降维后的时间序列,通常采取最近邻分类器进行分类。

PVQA对于时间序列有较好的降维效果^[8-9],本文采用PVQA作为时间序列进行降维。PVQA对时间序列降维分为两步:先把时间序列分割成等长的时间子序列,并根据这些时间子序列生成相应的码本;然后使用码词替代给定的训练时间子序,并重构时间序列,达到降维的目的。若要对未知时间序列进行处理,则用同样的方法重构该时间序列,然后采用最近邻策略,计算未知重构样例与训练重构样例的最小欧氏距离,从而判断未知样例的类别。在PVQA的重构过程中也采用了欧氏距离作为相似性度量。由于欧氏距离受模式特征量纲的影响^[10],不一定是最好的相似性度量选择。其他常见的相似性度量还有余弦相似度(cosine similarity,CS)^[11]、马氏距离(Mahalanobis distance,MD)^[12]等。

由于马氏距离^[12-14]不受量纲影响,并且能够消除码词间相关性,因此本文采用马氏距离处理分段矢量量化时间序列的重构和分类问题。首先,在训练时采用分段矢量量化近似方法获得码本,然后以马氏距离为相似性度量对时间序列进行分段重构。对重构后的时间序列,同样以马氏距离为相似性度量进行判别。

1 矢量量化

矢量量化^{[9, 15]}是将若干标量数据组合在一起,并在矢量空间中整体量化的一种基于分组编码的有损压缩方法,常用于图像、语音信号压缩^[16]。 假设有训练样本集X=｛(x₁,v₁),…(x_i,v_i),…,(x_n,v_n)｝ ,其中x_i∈R^m 为某个时间序列,v_i∈｛1,2,…,S｝ 为时间序列x_i 的类别,m 和n 分别为训练样例的长度以及个数,S 为时间序列的类别数。假设产生一个大小为K 的码本C=｛c₁,c₂,…,c_K｝ ,其中c_i∈R^l 是码本中的码词,l 为每个时间子序列的长度,l=m/W,W 是分段数。

定义一个码区集Q=｛Q₁,Q₂,…,Q_K｝ ,其中 ${{Q}_{i}}\subseteq {{R}^{m}}$ 为一个码区且${{Q}_{i}}\cap {{Q}_{j}}=\phi ,i\ne j\text{ }$。作一个从码区集到码本的映射g:Q→C 。如果x_i∈Q_k,则g(x_i)=c_k 。

矢量量化就是在给定样本集X 以及码本大小为K 的前提下,通过最小化平均失真度来求解所需要的码本C 以及码区集Q ,也就是说要求解下面的优化问题:

$minf\left( X,K \right)=\frac{1}{mn}\sum\limits_{i=1}^{n}{\|{{x}_{i}}-g\left( {{x}_{i}} \right){{\|}^{2}}},$

式中g(x_i)为离时间序列x_i最相似的码词c_k。最终求解得到的码本C以及码区集Q必须满足最近邻条件以及质心条件^{[8, 17]}。

2 基于马氏距离的分段矢量量化

为了提高分段矢量量化时间序列分类的性能,提出了基于马氏距离的分段矢量量化分类算法,其框架如图 1所示,共包含了3个主要步骤:(1)在时间子序列上应用PVQA产生码本;(2)对于产生的码本,引入马氏距离的重构未知样例以及训练时间序列;(3)根据马氏距离计算重构误差,并确定未知样例的类别。

2.1 马氏距离

马氏距离是由印度统计学家Mahalanobis于1936年引入的一种新的统计距离。马氏距离具有平移不变性、旋转不变性以及仿射不变性等3个性质^[18]。马氏距离由于独立于测量尺度之外,不受量纲的影响,从而消除了变量属性间的相关性干扰。

一般情况下,对于服从同一分布且协方差矩阵为P的两个随机向量x=[x₁,x₂,…,x_M]^T,y=[y₁,y₂,…,y_M]^T,其马氏距离

${{d}_{M}}\left( x,y \right)=\sqrt{\|x-y\|_{M}^{2}}\text{ }=\sqrt{\left( x-y \right)P{{\left( x-y \right)}^{T}}}。$

(1)

2.2 码本生成

对于给定时间序列集合X=｛(x₁,v₁),…(x_i,v_i),…,(x_n,v_n)｝ ,其中x_i∈R^m ,v_i∈｛1,2,…,S｝ 描述了该时间序列的类别信息。根据文献^{[8, 19]},可以将一个较长的时间序列分割成多份等长的时间子序列。这样,对于某一个训练时间序列x_i ,可以分割成W 个时间子序列x_i¹,x_i²,…,x_i^W ,原本大小为n×m 的1个时间序列集X 可以分割成大小为n×W×l 的时间子序列集x′ 。直接在x′ 中使用分段矢量量化,生成大小为K×l 的码本C=｛c₁,c₂,…,c_K｝ ,即码本中码词个数为K ,码词长度与时间子序列长度一致为l 。

2.3 基于马氏距离的重构

一旦生成码本,可以重构任意给定的时间序列。对于给定的某一时间序列x,同样可以将其分为长度为l的W段时间子序列,即x¹,x²,…,x^W。然后用K个码词替代这W个时间子序列。对于时间子序列x^j,以马氏距离为相似性度量,在码本中选择与该子序列最相似的码词来替代。若

${{p}_{j}}=\underset{k=1,2,\ldots ,K}{\mathop{arg\text{ }min}}\,\text{ }{{d}_{M}}\left( {{x}^{j}},{{c}_{k}} \right),$

则c_pj与x^j最为相似。此时,式(1)中的矩阵P 为码本的协方差矩阵。

若想获得重构的时间序列,不妨令${{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x}}^{j}}={{c}_{{{p}_{j}}}}$ ,则有$\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x}=({{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x}}^{1}};{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x}}^{2}};\cdots ;{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x}}^{W)}}$ ,其中$\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x}$为x 的重构。为了减少运算量且增加运算速度,只用W 个字符组合代表长度为m 的原时间序列,即令x的重构为$\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x}$=[p₁,…,p_W]_T 。这样就实现了时间序列的维数约简。对时间序列集X ,按照上述方法重构,可以得到重构的训练时间序列集$\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{X}=\{\left( {{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x}}}_{1}},{{v}_{1}} \right),\cdots ,({{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x}}_{i}},{{v}_{i}}),\cdots ,\left( {{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x}}}_{n}},{{v}_{n}} \right)\}$。

2.4 基于马氏距离的分类

在得到训练重构样例以及未知重构样例后,按照最近邻的思想,在训练重构样本集中找到与未知重构样本最相似的样本,然后根据该样本的类别判别未知样本的类别。

由于距离计算是在码词之间进行的,可以先计算出各码词间的马氏距离。即对于码词c_i和c_j ,其马氏距离

${{d}_{M}}\left( {{c}_{i}},{{c}_{j}} \right)=\sqrt{\left( {{c}_{i}}-{{c}_{j}} \right)C{{\left( {{c}_{i}}-{{c}_{j}} \right)}^{T}}},$

其中C是码本的协方差矩阵。

得到各码词间的马氏距离后,可以形成一个码词距离矩阵

$A=\left[ \begin{matrix} {{a}_{11}} & {{a}_{12}} & \cdots & {{a}_{1k}} \\ {{a}_{21}} & {{a}_{22}} & \cdots & {{a}_{2k}} \\ \vdots & \vdots & \ddots & \vdots \\ \text{ }{{a}_{k1}} & {{a}_{k2}} & \cdots & {{a}_{kk}} \\ \end{matrix} \right]\text{ },$

其中:a_ij为码词c_i和c_j间的马氏距离,即a_ij=d_M(c_i,c_j),其中a_ii=0。

若给定任意2个重构样本$\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x}={{\left[ {{p}_{1}},\ldots ,{{p}_{W}} \right]}^{T}}$和$\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{y}={{\left[ {{q}_{1}},\ldots ,{{q}_{W}} \right]}^{T}}$ ,则其马氏距离

${{d}_{M}}\left( \overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x},\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{y} \right)=\sum\limits_{i=1}^{W}{{{d}_{M(}}{{c}_{pi}},{{c}_{qi}})}=\sum\limits_{i=1}^{W}{{{a}_{piqi}}}。$

实际上,这个计算过程只需要在码词距离矩阵A 中找到对应的项即可。

若${\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x}}$ 是一未知类别的时间序列的重构,则在重构的训练时间序列集$\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{X}=\{\left( {{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x}}}_{1}},{{v}_{1}} \right),\cdots ,({{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x}}}_{i}},{{v}_{i}}),\cdots ,({{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x}}}_{n}},{{v}_{n}})\}$ 中找其最近邻,则该最近邻对应的类别记为${\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x}}$的类别。即,若

$J=\underset{i=1,2,\ldots ,n}{\mathop{arg\text{ }min}}\,\text{ }{{d}_{M}}\left( x,{{x}_{i}} \right),$

则${{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x}}}_{_{J}}}$是${\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x}}$在马氏距离意义下的最近邻,且$\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{v}={{v}_{J}}$,其中${\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{v}}$是${\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\frown}$}}{x}}$的类别估计。

3 仿真试验

由于PVQA比基于PCA的欧氏距离以及基于SAX的分段累计在许多实际和仿真数据中都有更好的分类效果^[8],此处只关注PVQA作为降维手段,后续的重构采用不同的度量的情况。将采用欧氏距离重构的PVQA记作PVQA-E,本文框架下的记作PVQA-M。将采用欧氏距离的最近邻分类器记作NN-E,采用马氏距离的记作NN-M。在NN-M中,矩阵P 取训练样本的协方差矩阵。而降维后采用最近邻分类器的传统方法记为PVQA-NN-E,本文的方法记为PVQA-NN-M。本文试验中所有用到的时间序列数据集均来自文献^[20]。

3.1 Control数据集

在Control数据集中,有300个训练时间序列以及300个测试时间序列,每个时间序列的长度为60,共有6类时间序列。这里主要比较PVQA-M和PVQA-E在时间序列重构以及时间序列分类上的性能。

3.1.1 码本生成

取K=16 ,W=10 ,在码本生成过程中,采用PVQA对300个训练时间序列进行分割,产生300个长度为6的时间子序列,并对这些时间子序列进行矢量量化操作,得到大小为16的码本,如图 2所示。

3.1.2 重构和分类

在生成码本后,对于任意给定的时间序列x ,可以通过欧氏距离或者马氏距离进行重构。先采用PVQA-E或者PVQA-M对300个训练样本重构后,再对测试样本进行重构。图 3给出了一个测试样本的重构曲线。由图 3可以看到,这两种方法的重构曲线有大约半数的重叠。此外在0～10区间和40～50区间,PVQA-M比PVQA-E更接近真实的曲线。为了描述方便,令该选定的测试时间序列为x 。

然后分别用NN-E和NN-M对PVQA-E和PVQA-M的重构进行处理(即PVQA-NN-E和PVQA-NN-M)。这两种方法求得的最近邻时间序列不同,令PVQA-NN-E和PVQA-NN-M找到的最近邻分别为x′ 和x″。表 1给出了测试时间序列x 和其不同方法找到的近邻x′ 和x″ 之间的距离。实际上PVQA-NN-M找到的最近邻x″ 和x 是同一类的,但是x 和x″ 之间的欧氏距离非常大,这样就会引起误判。

图 4给出了这2个训练时间序列的重构曲线。很显然,图 4(b)和图 3的原始时间序列更为相似。

3.1.3 分类结果

在不同码本和不同分段数设置下,比较PVQA-NN-M和PVQA-NN-E的性能。令K∈｛4,8,16,32,64｝ ,W∈｛6,10,15｝ 。性能衡量用分类错误率CER来定义:

$CER=\frac{{{n}_{w}}}{{{n}_{t}}}$

式中:n_w为分类错误的测试样例个数;n_t 为总的测试样例个数。

图 5展示了两种方法分类效果的对比。由图 5可以看出,在分段数相同的情况下,均随着K的增加,2种方法的分类错误率降低。这是由于当码本大小增加时,提取的代表性特征矢量数量增加,分类错误率自然相应减小。对于本文提出的方法,最小的分类错误率出现在W=6 且K=32 时,错误率为0.33％,而对于经典的PVQA-NN-E方法,最小的分类错误率出现在W=6 且K=64 时,错误率为2.00％。若不降维,直接采用NN-E方法,错误率为12.00％。降维后的性能有了很大的提高。而用NN-M方法,错误率为2.00％,和PVQA-NN-E的性能是一样的。

3.2 50Words数据集

该数据集中共有50类时间序列,包含了450个训练时间序列以及455个测试时间序列,各时间序列的长度为270。将其分割成W∈｛6,18｝ 个时间子序列,令K∈｛4,8,16,32,64｝ 。图 6中描述的是MPVQA以及PVQA在该数据集上的分类错误率对比。在分段数为6时,PVQA-NN-M的错误率明显比PVQA-NN-E要低。在W=18时,PVQA-NN-M除了在K=4的情况下性能劣于PVQA-NN-E以外,其他码本数情况下均占优势。

表 2列举出这两种方法的最小分类错误率。此外,还给出了不降维近邻方法的结果。由表 2可知,马氏距离的近邻方法优于欧氏距离,且降维方法的性能优于不降维方法。总之,在此数据集上,本文提出的方法具有较大的优势。

3.3 Two Patterns数据集

该数据集中共有4类时间序列,包含了1000个训练时间序列以及4000个测试时间序列,各时间序列的长度为128。令子序列的W∈｛4,16,32｝ 和K∈｛4,8,16,32｝ 。图 7中对比了PVQA-NN-E以及PVQA-NN-M在该数据集上的分类错误率。同样,在多数情况下,PVQA-NN-M的错误率较PVQA-NN-E更低。

表 3列举了Two Patterns数据集中分别采取不同算法时的最小分类错误率。可以看到PVQA-NN-M具有最好的性能。

3.4 Swedishleaf数据集

该数据集中共有15类时间序列,包含了500个训练时间序列以及625个测试时间序列,各时间序列的长度为128。令W∈｛16,32｝ 和K∈｛4,8,16,32,64｝ 。图 8是PVQA-NN-E和PVQA-NN-M在该数据集上的分类错误率对比。表 4列举了该数据集中分别采取不同算法时的最小分类错误率。和其他数据集类似,多数情况下,PVQA-NN-M具有很好的性能,最好错误率是在W=32 、K=32 时取得,为20.80％。

4 结语

由于传统方法在重构时间序列以及计算重构误差时,使用了欧氏距离,会忽略时间序列间的相关性干扰,从而可能导致精度降低。本文引入了马氏距离来处理分段矢量量化时间序列的重构和分类问题,提出了基于马氏距离的分段矢量量化时间序列分类算法。由于马氏距离不受量纲的影响,从而在保证准确度的同时,消除时间序列间的相关性干扰。在4个数据集上的试验结果证明,本文的方法确实在时间序列分类问题上有很好的表现。

在计算马氏距离时,直接采用了码本的协方差矩阵,在度量学习中,可以用学习的方法获得该矩阵。下一步,将采用度量学习的方式来学习该矩阵,希望能进一步提高时间序列分类的性能。