| 摘要: |
| 时间序列分类问题是时间序列数据挖掘中的一项重要任务, 近些年受到了越来越广泛的关注. 该问题的一个重要组成部分就是时间序列间的相似性度量. 在众多相似性度量算法中, 动态时间规整是一种非常有效的算法, 目前已经被广泛应用到视频、音频、手写体识别以及生物信息处理等众多领域. 动态时间规整本质上是一种在边界及时间一致性约束下的点对点的匹配算法, 能够获得两条序列间的全局最优匹配. 但该算法存在一个明显的不足, 即不一定能实现序列间的局部合理匹配. 具体的讲, 就是具有完全不同局部结构信息的时间点有可能被动态时间规整算法错误匹配. 为了解决这个问题, 提出了一种改进的基于局部梯度和二进制模式的动态时间规整算法LGBDTW (local gradient and binary pattern based dynamic time warping), 通过考虑时间序列点的局部结构信息来强化传统动态时间规整算法. 所提算法虽然实质上是一种动态时间规整算法, 但它通过考虑序列点的局部梯度和二进制模式值来进行相似性加权度量, 有效避免了具有相异局部结构的点匹配. 为了进行全面比较, 将所提出的算法应用到了最近邻分类算法的相似性度量中, 并在多个UCR时间序列数据集上进行了测试. 实验结果表明, 所提出的方法能有效提高时间序列分类的准确率. 此外, 实例分析验证了所提出算法的可解释性. |
| 关键词: 动态时间规整 时间序列相似性 数据挖掘 时间序列分类 |
| DOI：10.13328/j.cnki.jos.006208 |
| 分类号:TP301 |
| 基金项目:中央高校基本科研业务费专项(2019YJS041); 国家自然科学基金(61672086, 61702030, 61771058); 北京市自然科学基金(4182052) |
|
| Time Series Classification Algorithm Based on Local Gradient and Binary Pattern |
|
HAO Shi-Lei1,2, WANG Zhi-Hai1,2, LIU Hai-Yang1,2
|
|
1.School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China;2.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 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 |
