一种基于信息熵和DTW的多维时间序列相似性度量算法
乔美英;刘宇翔;陶慧
【摘 要】正则化降低准确率提出一种基于信息熵和动态时间规整(DTW)的多维时间序列相似性度量的方法.首先,基于马氏距离(mahalanobis distance)的DTW,不仅考虑了多维时间序列的各个变量间的相互关系,而且对于长度不同的时间序列,通过动态规整可以进行准确地对齐.其次,利用信息熵理论,通过最小化损失函数,对马氏距离矩阵进行学习,来获得全局最优的马氏矩阵.为了验证所提算法的效果,选用UCI数据集中的5个数据集,采用最近邻分类算法对其进行分类实验.实验结果表明:该算法相比于其他算法,具有较高的分类准确率,且时间消耗较少.
【期刊名称】《中山大学学报（自然科学版）》
【年(卷),期】2019(058)002
【总页数】8页(P1-8)
【关键词】多维时间序列;相似性;动态时间规整;马氏距离;信息熵
【作 者】乔美英;刘宇翔;陶慧
【作者单位】河南理工大学电气学院,河南焦作454000;煤炭安全生产河南省协同创新中心,河南焦作454000;河南理工大学电气学院,河南焦作454000;河南理工大学电气学院,河南焦作454000
【正文语种】中 文
【中图分类】TP391
时间序列是按照时间顺序获得的一系列的观测值，描述了时间序列数据随时间变化的动态特性[1-2]。随着卫星定位、通信技术、跟踪检测、传感器技术的发展，时间序列数据与日俱增，其涵盖人类行为、社交网络、物流交通、核能化工、天文气象等诸多领域，因此对时间序列数据的分析利用变得越来越重要。为了从这些海量数据中挖掘有效信息，研究人员开发了时间序列数据方面的很多应用技术，诸如：系统的状态预测[3]、医学[4]、故障检测[5]、行为识别[6]等。这些技术的应用均依赖于对时间序列数据样本相似性的度量，只有准确地表达并量化样本轨迹之间相似程度，才能度量同类样本数据之间的相似性与不同类样本数据之间
的差异性，使各类数据挖掘算法的应用顺利实现。因此，相似性度量是时间序列数据挖掘应用中的重中之重。
目前，有很多方法能够对多维时间序列进行相似性度量，包括欧氏距离度量，动态时间规整(DTW，dynamic time warping)度量[7]，短时间序列度量[8]，KL距离度量[9]，二维奇异值分解[10]和基于概率的距离度量[11]等。其中，欧氏距离和短时间序列度量要求时间序列具有相同的相位，对于测量非一致的多维时间序列并不适用。DTW通过对时间轴进行规整，有效地解决了时间序列在时间轴上的伸缩与偏移，但传统的动态时间规整算法只能对单维时间序列进行测量，文献[12]将其扩展为多维动态时间规整算法。KL距离度量和基于概率的距离度量适合测量线性弯曲的多维时间序列之间的相似性，当出现的两个非线性弯曲的多维时间序列的概率分布差异较大时，该两种方法将不准确。奇异值分解法将多维时间序列的列与列、行与行的协方差矩阵分解，计算出特征值并将其作为特征，从而把度量时间序列的相似性转为度量特征的相似性。此外，对多维时间序列的相似性分析还可以采用度量学习的方法，其利用给定的训练样本集学习，得到一个能有效反映数据样本间距离的度量矩阵[13]。如今，多数度量学习算法往往是基于马氏距离。由于马氏距离不仅能排除变量间的相关性干扰，而且不受量纲的影响，所以广泛应用于分类等数据处理[14-15]。文献[16]将大间距最近邻(large
margin nearest neighbor，LMNN)算法与DTW算法结合，用LMNN算法在特定的损失函数下优化马氏矩阵，取得了较好的度量效果。文献[17]提出一种基于LogDet dicergence 的度量学习算法，它通过三元约束来学习马氏矩阵，用于度量多维时间序列的相似性，该方法度量结果虽然比较准确，但时间复杂度较高、耗时较多。文献[18]提出一种将支持向量机(SVM)与DTW相结合的模型，该模型中DTW 的局部距离使用的是欧氏距离，对每个变量赋予相同的权重，忽略了各个变量间的相关性，所以不能进行准确的相似性度量。本文提出一种基于信息熵和DTW的多维时间序列相似性度量算法，简称IEML-MD DTW (information entropy metric learning-mahalanobis distance DTW)算法。首先，通过动态时间规整对多维时间序列进行相似性度量，再用MDDTW消除时间序列中变量间的相关性干扰，最后使用信息熵理论通过最小化损失函数，学习得到优化后的马氏距离矩阵。研究结果表明，该算法优于其他的算法。
1 动态时间规整(DTW)
动态时间规整(DTW)的基本思想是通过时间序列数值上的相似性来对时间轴进行规整，然后寻这两个时间序列的最优对应关系。因此，这两个时间序列的相似关系就可以被很容易的
测量出来。设有两个单维时间序列X和Y，分别为 X={x1,x2,x3,,xn}和Y={y1,y2,y3,,ym}。其中，n和m分别为X和Y的长度。构造一个n×m的矩阵网格，矩阵元素(i,j)表示xi和yj两点的距离dl(i,j)=(xi-yj)2，称其为局部距离。最优规整路径W可以表示为：
(1)
其中，wx(k)表示时间序列xi的索引，wy(k)表示时间序列yj的索引，p为规整路径W的长度，且p∈[max(m,n),m+n]，(wx(k),wy(k))′表明时间序列X中的第wx(k)个元素与时间序列Y中第wy(k)个元素是一一对应的。
只取使得下式(2)规整代价最小的路径：
(2)
利用最佳的规整路径W，可以将两个时间序列xi和yj扩展为两个新的时间序列和表示为：
(3)
因此，时间序列xi和yj的规整距离可用两个扩展的时间序列和的欧氏距离来表示，如式(4)。
(4)
定义一个累加距离r，其可用式(5)表示。累加距离为当前格点距离d(i,j)与可到达该点的最小邻近元素的累加距离之和。
r(i,j)=d(i,j)+
min{r(i-1,j),r(i,j-1),r(i-1,j-1)}
(5)
从(1,1)点开始匹配两个序列S和T，每到一个点，之前所有的点计算的距离都会累加。要到达点(i,j)，只能从(i-1,j)、(i,j-1)或(i-1,j-1)出发。r(i,j)即为从(1,1)到(i,j)的最小累加距离。最优的弯曲路径如图1所示。
图1 两个时间序列的最佳弯曲路径Fig.1 The best warping path of two time series
2 基于马氏距离的DTW
马氏距离(Mahalanobis diatance)是由印度统计学家马哈拉诺比斯提出的，是一种有效的计算两个样本的相似度的方法。其通过优化特定的损失函数来得到一个对称的半正定参数矩阵，该对称的半正定参数矩阵即为马氏矩阵，马氏距离正是通过马氏矩阵来表示各个变量之间的相关性。假设有两个具有d个属性变量的样本和则xi和xj之间的马氏距离的平方可以通过一个对称的半正定的矩阵来表示：
DM(xi,xj)=(xi-xj)TM(xi-xj)
(6)
对称的半正定矩阵M为马氏矩阵。当M=I，马氏距离就转变为欧氏距离。将马氏距离进行分解为M=ATA,则(6)中的马氏距离可以转为：
DM(xi,xj)=
(xi-xj)TATA(xi-xj)=
(Axi-Axj)T(Axi-Axj)
(7)
可以看出，马氏距离的计算就是利用矩阵A通过线性变换，将原始的特征空间映射到一个具有更好度量的新的特征空间，再计算在新空间中的两个样本之间的欧氏距离。因此，马氏距离可以有效地度量两个向量的距离。然而，如何学习到一个较优的马氏矩阵，将是马氏距离计算的关键。传统的动态时间规整算法只能处理单维时间序列的规整问题。在很多应用中，单维时间序列只能提供序列的部分信息，不能准确地反映样本的多个属性的变化情况。因此，需要将传统的DTW算法进行扩展，以满足处理多维时间序列的要求。
给定两个多维时间序列X和Y，
(8)
其中，d是多维时间序列的维数，即属性变量的个数，m和n分别表示时间序列X和Y的长度。定义Xi=(x1i,x2i,,xdi)T表示X的第i列，为在第i时刻时各个变量的值；Yj=(y1j,y2j,,ydj)T表示Y的第j列，为在第j时刻时各个变量的值。于是，用马氏距离来计算DTW中的局部距离，即：
dM(Xi,Yj)=(Xi-Yj)TM(Xi-Yj)
(9)
其中，1≤i≤m,1≤j≤n，M是一个对称的半正定矩阵，即为马氏矩阵。
与单维时间序列的DTW类似，多维时间序列X和Y之间的距离和最优的规整路径可以由下式(10)来计算：
(10)
原始多维时间序列X和Y，则可以用两个经过变换后的多维时间序列和来表示：
(11)
因此，可以得到DTW中局部距离的另一种表示：
(12)
该种表示与上式(10)中动态规划方程所得到的解是一致的，但具有更好的扩展性。
3 IEML-MDDTW
多维时间序列基于马氏距离的DTW表示，不仅解决了传统DTW只能度量单维时间序列相似性的缺点，而且在局部距离计算中，引入马氏距离，可以更加准确地反映样本的各个属性变量之间的关系。然而，如何寻到一个合适的马氏度量矩阵，使得各个变量之间有更好的度量关系，是度量时间序列的相似性中重要的一步。

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