基于局部梯度和二进制模式的时间序列分类算法-郝石磊，王志海，刘海洋.pdf

上善若水

147

16页

0次

2022-05-19

免费下载



基于局部梯度和二进制模式的时间序列分类算法

郝石磊

1,2

,王志海

1,2

,刘海洋

1,2

(北京交通大学计算机与信息技术学院,北京100044)

(交通数据分析与挖掘北京市重点实验室(北京交通大学),北京100044)

通信作者:刘海洋,E-mail:haiyangliu@bjtu.edu.cn

摘　要:时间序列分类问题是时间序列数据挖掘中的一项重要任务,近些年受到了越来越广泛的关注.该问题的一

个重要组成部分就是时间序列间的相似性度量.在众多相似性度量算法中,动态时间规整是一种非常有效的算法,

目前已经被广泛应用到视频、音频、手写体识别以及生物信息处理等众多领域.动态时间规整本质上是一种在边

界及时间一致性约束下的点对点的匹配算法,能够获得两条序列间的全局最优匹配.但该算法存在一个明显的不

足,即不一定能实现序列间的局部合理匹配.具体的讲,就是具有完全不同局部结构信息的时间点有可能被动态时

间规整算法错误匹配.为了解决这个问题,提出了一种改进的基于局部梯度和二进制模式的动态时间规整算法

LGBDTW(localgradientandbinarypatternbaseddynamictimewarping),通过考虑时间序列点的局部结构信息来强

化传统动态时间规整算法.所提算法虽然实质上是一种动态时间规整算法,但它通过考虑序列点的局部梯度和二

进制模式值来进行相似性加权度量,有效避免了具有相异局部结构的点匹配.为了进行全面比较,将所提出的算法

应用到了最近邻分类算法的相似性度量中,并在多个UCR时间序列数据集上进行了测试.实验结果表明,所提出

的方法能有效提高时间序列分类的准确率.此外,实例分析验证了所提出算法的可解释性.

关键词:动态时间规整;时间序列相似性;数据挖掘;时间序列分类

中图法分类号:TP301

中文引用格式:郝石磊,王志海,刘海洋.基于局部梯度和二进制模式的时间序列分类算法.软件学报,2022,33(5):1817–1832.

http://www.jos.org.cn/1000-9825/6208.htm

英文引用格式:HaoSL,WangZH,LiuHY.TimeSeriesClassificationAlgorithmBasedonLocalGradientandBinaryPattern.Ruan

JianXueBao/JournalofSoftware,2022,33(5):1817–1832(inChinese).http://www.jos.org.cn/1000-9825/6208.htm

Time Series Classification Algorithm Based on Local Gradient and Binary Pattern

HAOShi-Lei

1,2

,WANGZhi-Hai

1,2

,LIUHai-Yang

1,2

(SchoolofComputerandInformationTechnology,BeijingJiaotongUniversity,Beijing100044,China)

(BeijingKeyLabofTrafficDataAnalysisandMining(BeijingJiaotongUniversity),Beijing100044,China)

Abstract:Time series classification is an important task in time series data mining and has attracted significant attention in recent years.

An important part of this problem is the similarity measurement between time series. Among many similarity measurement algorithms,

dynamic time warping (DTW) is very effective, which has been widely used in many fields such as video, audio, handwriting recognition,

and biological information processing. DTW is essentially a point-to-point matching algorithm under the boundary and time consistency

constraints, which is able to provide the global optimal matching between two sequences. However, there is an obvious deficiency in this

algorithm, that is, it does not necessarily achieve reasonable local matching between sequences. Specifically, the time points with

completely different local structure information may be incorrectly matched by DTW algorithm. In order to solve this problem, an

improved DTW algorithm based on local gradient and binary pattern (LGBDTW) is proposed. Although the proposed algorithm is

essentially a dynamic time warping algorithm, it takes into account the local gradient and binary pattern values of sequence points to carry

out similarity weighted measurement, effectively avoiding points matching with different local structures. In order to make a



*

基金项目:中央高校基本科研业务费专项(2019YJS041);国家自然科学基金(61672086,61702030,61771058);北京市自然科学基金

(4182052)

收稿时间:2020-04-12;修改时间:2020-08-27;采用时间:2020-11-18



软件学报ISSN1000-9825,CODENRUXUEW E-mail:jos@iscas.ac.cn

Journal of Software,2022,33(5):1817−1832[doi:10.13328/j.cnki.jos.006208] http://www.jos.org.cn

comprehensive comparison, the algorithm is adopted as the similarity measurement of the nearest neighbor classification algorithm, and

tests it on multiple UCR time series datasets. Experimental results show that the proposed method can effectively improve the accuracy of

timeseriesclassification.Inaddition,someexamplesareprovidedtoverifytheinterpretabilityoftheproposedalgorithm.

Key words:dynamictimewarping(DTW);timeseriessimilarity;datamining;timeseriesclassification



时间序列数据广泛存在于现实世界的各个领域,目前对时间序列的分析已经成为股票价格、天气数据、生物

医学测量、航空航天等许多领域研究的重要课题

[1,2]

.时间序列数据类型为实值型,数据维度高且数据量通常较大.

此外,时间序列分类问题中的序列属性是有序的,这使其明显区别于传统的分类问题.实质上,序列中的属性排序

是否按照时间进行是无关紧要的,重要的是序列中可能存在依赖于顺序的辨别性特征

[3]

.因此,时间序列分类问题

的研究对于数据挖掘领域的发展具有重要意义.

在时间序列分类问题中,最近邻算法(onenearestneighbor,1NN)是目前最为流行的分类算法之一,该算法较

为简单,且分类效果显著.最近邻算法的核心部分就是相似性度量,而动态时间规整(dynamictimewarping,DTW)

就是一种非常有效的相似性度量算法,该算法能够通过局部的非线性规整找到序列间的最佳匹配路径.DTW是

由Berndt等人

[4]

提出并将其应用到了时间序列的模式发现,后来又被广泛用于人体活动识别

[5]

,孤立词识别

[6]

,文

字图像匹配

[7]

,人体运动动画

[8]

,生物信息处理

[9]

以及时间序列分类

[3]

等多个领域中.

基于DTW的1NN算法是众多时间序列分类算法中最有效的算法之一,很难被其他算法超越

[3]

.DTW本质上

是一种点对点的对齐算法,它通过允许一个序列到另一个序列的非线性映射提高了匹配点对之间的时间一致性.

从DTW提取匹配分量之后,通常是基于两点之间的欧几里得距离来进行点匹配.然而,这种使用基于点数值的欧

几里得距离的相似性度量方法是不可靠的,甚至会导致匹配错误,即产生局部结构并不相似的点的对齐(如图1(a)

所示).很明显,虽然DTW实现了全局最优匹配,但它没有兼顾序列的局部结构信息.这也反映了为什么DTW相

似性度量之下的最近邻分类器的可解释性会弱于基于shapelet的分类器

[10,11]

.总的来说,DTW的确能够捕捉到时

间序列的全局最优匹配,但是它没有考虑到序列的局部结构信息,这样的对齐结果是缺乏语义的.



(a) DTW

(b) LGBDTW

图1　DTW与LGBDTW对齐效果比较



为了解决这个问题,本文提出了一种基于局部梯度和局部二进制模式(localbinarypattern,LBP)的动态时间

规整算法LGBDTW.该算法不只是考虑了时间序列点的局部梯度信息,同时还兼顾点的局部二进制模式信息,它通

过将点对的这两种局部结构信息以一定的权重进行融合强化了DTW.通过实例测试,所提算法获得了更加准确并具

有较好可解释性的对齐.图1(b)是一个基于LGBDTW对齐的实例,很明显时间序列间的局部形状信息被成功匹配.

本文所提出方法的灵感来自于计算机视觉领域的方向梯度直方图(histogramoforientedgridients,HOG)

[12]

,图

像特征描述子LBP

[13]

,以及一维时间序列局部特征描述子HOG-1D

[11]

.众所周知,现实世界大多数数据可能含有噪

声,时间序列数据也是如此,其获取甚至分类过程很容易受到噪声的影响.因此,本文首先使用滤波技术来缓解噪

声对数据的影响,然后提出了一种基于局部二进制模式的时间序列局部特征描述子LBPT(localbinarypatternof

timeseries),之后又在此基础上提出了融合HOG-1D和LBPT两种特征描述子的加权动态时间规整算法(LGBDTW),

并成功将其应用到了时间序列分类任务.

本文的主要贡献如下:(1)提出了一种新的基于局部二进制模式的时间序列局部特征描述子LBPT来更加准

确的反映序列的局部结构信息.(2)提出了一种基于HOG-1D特征描述子和LBPT特征描述子的加权动态时间规

1818 软件学报2022年第33卷第5期

of 16

免费下载

软件学报计算机技术

关注

评论