基于持续同调的倾斜时间序列分类算法

doi:10.19678/j.issn.1000-3428.0068354

摘要/Abstract

摘要： 针对现有时间序列分类算法对高维拓扑信息以及时序顺序信息提取能力不足等问题,提出一种基于持续同调的倾斜时间序列分类算法。该算法结合时序数据方差,将原始单变量时序数据嵌入二维点云,同时展现出周期内和周期间的时序变化;在滑动窗口划分的子区间上进行时间倾斜,将点云分解为不同结构,从而使算法适应更多的时序数据,有效捕捉时序顺序信息;利用持续同调技术在点云上构建Vietoris-Rips(VR)复形流,从不同尺度分析各个维度下孔洞数量的变化,从而提取到更全面的时序数据的拓扑结构特征,并通过计算持久性图像得到点云中的拓扑特征。在此基础上,以持久性中心表示向量作为输入,使用随机森林模型对点云进行分类。在9个UCR时间序列数据集上进行对比实验,结果显示,该算法在其中8个数据集上取得了最高的准确率,相较于其他6种传统时间序列分类算法分类准确率提高了0.5~24个百分点,F1值提高了0.9~23.9个百分点,表明该算法在时间序列数据分类方面具有较高的精度和良好的鲁棒性。

关键词: 时间序列, 时间序列分类, 时间倾斜, 持续同调, 持久性图

Abstract: To address the limitations of traditional time series classification algorithms to extract high-dimensional topological information and temporal sequence information, this paper proposes a skewed time series classification algorithm based on persistent homology for extracting high-dimensional topological and temporal sequential information. The algorithm combines the variance of temporal data to embed univariate time series data into a two-dimensional point cloud, displaying temporal changes within and between cycles. It performs a time skew on the subintervals divided by the sliding window and decomposes the point cloud into different structures through time skew. Thus, the algorithm can adapt to more temporal data and effectively capture temporal order information. It uses persistent homology technology to construct Vietoris-Rips(VR) complex flows on point clouds, analyzes the changes in number of holes in various dimensions at different scales to extract more comprehensive topological structural features of the temporal data, and obtains topological features in point clouds by calculating persistence diagram. It uses persistent center representation vectors as input and classifies point clouds using a random forest model. The results of comparative experiments performed on nine UCR time series datasets show that the algorithm achieves the highest accuracy on eight of these datasets. Compared to six traditional time series classification algorithms, the algorithm achieves classification accuracy improvement and increase in F1 value by 0.5-24 percentage points and 0.9-23.9 percentage points, respectively. This indicates its higher accuracy and good robustness in time series data classification.

Key words: time series, time series classification, time skew, persistent homology, persistence diagram

中图分类号:

TP18

严银凯, 彭宁宁, 易丽莎. 基于持续同调的倾斜时间序列分类算法[J]. 计算机工程, 2024, 50(6): 110-123.

YAN Yinkai, PENG Ningning, YI Lisha. Skewed Time Series Classification Algorithm Based on Persistent Homology[J]. Computer Engineering, 2024, 50(6): 110-123.

https://www.ecice06.com/CN/Y2024/V50/I6/110

参考文献

[1] SPECHT O, SPECHT M, STATECZNY A, et al. Concept of an innovative system for dimensioning and predicting changes in the coastal zone topography using UAVs and USVs (4DBatMap system)[J]. Electronics, 2023, 12(19):4112.
[2] SUN M X, JI Z X, JIAO X, et al. Mapping grassland based on bio-climate probability and intra-annual time-series abundance data of vegetation habitats[J]. Remote Sensing, 2023, 15(19):4723.
[3] YANG X D, CHEN M H, REN Y L, et al. Multivariate joint order recurrence networks for characterization of multi-lead ECG time series from healthy and pathological heartbeat dynamics[J]. Chaos, 2023, 33(10):103120.
[4] KHOSRAVI M, GHAZANI M M. Novel insights into the modeling financial time-series through machine learning methods:evidence from the cryptocurrency market[J]. Expert Systems with Applications, 2023, 234:121012.
[5] 李显.天文数据稀有时间序列分类研究[D].太原:太原理工大学, 2022. LI X. Research on rare time series classification of astronomical data[D]. Taiyuan:Taiyuan University of Technology, 2022.(in Chinese)
[6] ZHAO H Y, JIN J, LIU Y, et al. Detection of X-ray bursts in astronomical time series:the burst of GRO J1744-28 as an example[J]. The Astrophysical Journal, 2023, 942(2):89.
[7] 康璐璐,范兴容,王茜竹,等.基于特征组分层与半监督学习的鼠标轨迹识别[J].计算机工程, 2021, 47(4):277-284. KANG L L, FAN X R, WANG Q Z, et al. Mouse trajectory recognition based on feature group hierarchy and semi-supervised learning[J]. Computer Engineering, 2021, 47(4):277-284.(in Chinese)
[8] 孙昂,陈宁,何俐,等.基于小样本功能磁共振数据的偏头痛时序特征分类研究[J].生物医学工程学杂志, 2023, 40(1):110-117. SUN A, CHEN N, HE L, et al. Research on migraine time-series features classification based on small-sample functional magnetic resonance imaging data[J]. Journal of Biomedical Engineering, 2023, 40(1):110-117.(in Chinese)
[9] YAN Y, SHEN X Z. Research on speech emotion recognition based on AA-CBGRU network[J]. Electronics, 2022, 11(9):1409.
[10] BAGNALL A, LINES J, BOSTROM A, et al. The great time series classification bake off:a review and experimental evaluation of recent algorithmic advances[J]. Data Mining and Knowledge Discovery, 2017, 31(3):606-660.
[11] CHEN L, NG R. On the marriage of Lp-norms and edit distance[C]//Proceedings of the 30th International Conference on Very Large Data Bases. Toronto, Canada:EVLD Press, 2004:792-803.
[12] CHEN L, ÖZSU M T, ORIA V. Robust and fast similarity search for moving object trajectories[C]//Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. New York, USA:ACM Press, 2005:491-502.
[13] MARTEAU P F. Time warp edit distance with stiffness adjustment for time series matching[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(2):306-318.
[14] STEFAN A, ATHITSOS V, DAS G. The move-split-merge metric for time series[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(6):1425-1438.
[15] SCHÄFER P. The BOSS is concerned with time series classification in the presence of noise[J]. Data Mining and Knowledge Discovery, 2015, 29(6):1505-1530.
[16] SCHÄFER P, LESER U. Fast and accurate time series classification with WEASEL[C]//Proceedings of the 2017 ACM Conference on Information and Knowledge Management. New York, USA:ACM Press, 2017:637-646.
[17] MORRILL J, FERMANIAN A, KIDGER P, et al. A generalised signature method for multivariate time series feature extraction[EB/OL].[2023-08-10]. https://arxiv.org/abs/2006.00873.
[18] CABELLO N, NAGHIZADE E, QI J Z, et al. Fast and accurate time series classification through supervised interval search[C]//Proceedings of the IEEE International Conference on Data Mining. Washington D. C., USA:IEEE Press, 2020:948-953.
[19] FLYNN M, LARGE J, BAGNALL T. The contract Random Interval Spectral Ensemble (c-RISE):the effect of contracting a classifier on accuracy[C]//Proceedings of International Conference on Hybrid Artificial Intelligence Systems. Berlin, Germany:Springer, 2019:381-392.
[20] MIDDLEHURST M, LARGE J, FLYNN M, et al. HIVE-COTE 2.0:a new meta ensemble for time series classification[J]. Machine Learning, 2021, 110(11/12):3211-3243.
[21] SHIFAZ A, PELLETIER C, PETITJEAN F, et al. TS-CHIEF:a scalable and accurate forest algorithm for time series classification[J]. Data Mining and Knowledge Discovery, 2020, 34(3):742-775.
[22] WANG Z G, YAN W Z, OATES T. Time series classification from scratch with deep neural networks:a strong baseline[C]//Proceedings of International Joint Conference on Neural Networks. Washington D. C., USA:IEEE Press, 2017:1578-1585.
[23] WU H X, HU T G, LIU Y, et al. TimesNet:temporal 2d-variation modeling for general time series analysis[EB/OL].[2023-08-10]. https://arxiv.org/abs/2210.02186.
[24] 赵欣瑶.基于拓扑结构的全球股市联动与系统性金融风险研究[D].济南:山东财经大学, 2021. ZHAO X Y. Research on global stock market linkage and systematic financial risk based on topological structures[D]. Jinan:Shandong University of Finance and Economics, 2021.(in Chinese)
[25] UMEDA Y. Time series classification via topological data analysis[J]. Information and Media Technologies, 2017, 12:228-239.
[26] KARAN A, KAYGUN A. Time series classification via topological data analysis[J]. Expert Systems with Applications, 2021, 183:115326.
[27] 任亚婧,张宏立.融合TDA的深度自编码网络车辆目标检测[J].信息与控制, 2019, 48(5):627-633. REN Y J, ZHANG H L. Vehicle target detection based on deep self-encoding network with TDA[J]. Information and Control, 2019, 48(5):627-633.(in Chinese)
[28] 海彤.基于拓扑分析的时间序列分类[D].成都:西南财经大学, 2021. HAI T. Time series classification with topological data analysis[D]. Chengdu:Southwestern University of Finance and Economics, 2021.(in Chinese)
[29] 尤承业.基础拓扑学讲义[M].北京:北京大学出版社, 1997. YOU C Y. Lecture notes on basic topology[M]. Beijing:Peking University Press, 1997.(in Chinese)
[30] CARLSSON G, ZOMORODIAN A, COLLINS A, et al. Persistence barcodes for shapes[C]//Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. New York, USA:ACM Press, 2004:124-135.
[31] ADAMS H, EMERSON T, KIRBY M, et al. Persistence images:a stable vector representation of persistent homology[J]. Journal of Machine Learning Research, 2017, 18(8):1-35.
[32] BUBENIK P. Statistical topological data analysis using persistence landscapes[J]. Journal of Machine Learning Research, 2015, 16(1):77-102.
[33] CHEVYREV I, NANDA V, OBERHAUSER H. Persistence paths and signature features in topological data analysis[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020, 42(1):192-202.
[34] ZOMORODIAN A, CARLSSON G. Computing persistent homology[J]. Discrete&Computational Geometry, 2005, 33(2):249-274.
[35] PACKARD N H, CRUTCHFIELD J P, FARMER J D, et al. Geometry from a time series[J]. Physical Review Letters, 1980, 45(9):712-716.
[36] COHEN-STEINER D, EDELSBRUNNER H, HARER J, et al. Persistent homology for kernels, images, and cokernels[C]//Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. New York, USA:ACM Press, 2009:1011-1020.
[37] 詹学燕,彭宁宁,殷杏子.基于持续同调改进的KNN拓扑分类算法[J].武汉理工大学学报, 2023, 45(3):146-155. ZHAN X Y, PENG N N, YIN X Z. An improved KNN topological classification algorithm based on persistent homology[J]. Journal of Wuhan University of Technology, 2023, 45(3):146-155.(in Chinese)
[38] 殷杏子,彭宁宁,詹学燕.基于持续同调的过滤式特征选择算法[J].计算机科学, 2023, 50(6):159-166. YIN X Z, PENG N N, ZHAN X Y. Filtered feature selection algorithm based on persistent homology[J]. Computer Science, 2023, 50(6):159-166.(in Chinese)
[39] BAUER U. Ripser:efficient computation of Vietoris-Rips persistence barcodes[J]. Journal of Applied and Computational Topology, 2021, 5(3):391-423.

选择文件类型/文献管理软件名称

选择包含的内容