Multivariate Time Series Density Clustering Algorithm Using Shapelet Space

doi:10.3778/j.issn.1673-9418.2211099

Abstract

Abstract: Multivariate time series clustering has become an important research topic in the task of time series analysis. Compared with univariate time series, the research of multivariate time series is more complex and difficult. Although many clustering algorithms for multivariate time series have been proposed, these algorithms still have difficulties in solving the accuracy and interpretation at the same time. Firstly, most of the current work does not consider the length redundancy and variable correlation of multivariable time series, resulting in large errors in the final similarity matrix. Secondly, the data are commonly used in the clustering process with the division paradigm, when the numerical space presents a complex distribution, this idea does not perform well, and it does not have the explanatory power of each variable and space. To address the above problems, this paper proposes a multivariate time series adaptive weight density clustering algorithm using Shapelet (high information-rich continuous subsequence) space (MDCS). This algorithm firstly performs a Shapelet search for each variable, and obtains its own Shapelet space through an adaptive strategy. Then, it weights the numerical distribution generated by each variable to obtain a similarity matrix that is more consistent with the characteristics of data distribution. Finally, the data are finally allocated using the shared nearest neighbor density peak clustering algorithm with improved density calculation and secondary allocation. Experimental results on several real datasets demonstrate that MDCS has better clustering results compared with current state-of-the-art clustering algorithms, with an average increase of 0.344 and 0.09 in the normalized mutual information and Rand index, balancing performance and interpretability.

Key words: multivariate time series, subseries, Shapelet space, density peak clustering, data mining

摘要： 多变量时间序列聚类问题已经成为时间序列分析任务中重要的研究课题，相较于单变量时间序列，多变量时间序列的研究复杂性更高，难度更大。尽管当前已经提出了许多针对多变量时间序列的聚类算法，但是这些算法在精度和解释性方面仍旧不足。其一，当前大部分工作并未考虑多变量时间序列的长度冗余性和变量相关性等问题，导致最终得到的相似性矩阵具有较大误差；其二，数据在聚类过程中普遍采用划分范式，当数值空间呈现复杂分布时该思想表现不佳，并且不具备对各个变量及空间的解释力。针对上述问题，提出了一种面向Shapelet（富有高信息量的连续子序列）空间的多变量时间序列自适应权重密度聚类算法（MDCS）。算法首先对各个变量进行Shapelet搜索，通过自适应策略获取到各自的Shapelet空间，接着对各个变量产生的数值分布进行组合加权，得到了更符合数据分布特征的相似度矩阵，最后利用改进密度计算和二次分配的共享最近邻密度峰值聚类算法对数据进行最终分配。在真实数据集上的实验结果证明，与目前先进的聚类算法相比，MDCS拥有更好的聚类结果，在标准化互信息和兰德系数指标上平均提高了0.344与0.09，兼顾了性能与可解释性。

关键词: 多变量时间序列, 子序列, Shapelet空间, 密度峰值聚类, 数据挖掘

SHENG Jinchao, DU Mingjing, SUN Jiarui, LI Yurui. Multivariate Time Series Density Clustering Algorithm Using Shapelet Space[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(2): 387-402.

盛锦超, 杜明晶, 孙嘉睿, 李宇蕊. 面向Shapelet空间的多变量时间序列密度聚类算法[J]. 计算机科学与探索, 2024, 18(2): 387-402.

References

[1] BAELDE M, BIERNACKI C, GREFF R. Real-time monophonic and polyphonic audio classification from power spectra[J]. Pattern Recognition, 2019, 92: 82-92.
[2] XU R, WUNSCH D. Survey of clustering algorithms[J]. IEEE Transactions on Neural Networks, 2005, 16(3): 645-678.
[3] ASAD M, JIANG H, YANG J, et al. Multi-stream 3D latent feature clustering for abnormality detection in videos[J]. Applied Intelligence, 2022, 52(1): 1126-1143.
[4] SHARIF A, LI J P, SALEEM M A, et al. A dynamic clustering technique based on deep reinforcement learning for Internet of vehicles[J]. Journal of Intelligent Manufacturing, 2021, 32(3): 757-768.
[5] AGHABOZORGI S, SHIRKHORSHIDI A S, WAH T Y. Time-series clustering—a decade review[J]. Information Systems, 2015, 53: 16-38.
[6] LI H. Multivariate time series clustering based on common principal component analysis[J]. Neurocomputing, 2019, 349: 239-247.
[7] HE H, TAN Y. Unsupervised classification of multivariate time series using VPCA and fuzzy clustering with spatial weighted matrix distance[J]. IEEE Transactions on Cybernetics, 2018, 50(3): 1096-1105.
[8] LI H, LIU Z. Multivariate time series clustering based on complex network[J]. Pattern Recognition, 2021, 115: 107919.
[9] LI H, DU T. Multivariate time-series clustering based on component relationship networks[J]. Expert Systems with Applications, 2021, 173: 114649.
[10] 李海林, 王成, 邓晓懿. 基于分量属性近邻传播的多元时间序列数据聚类方法[J]. 控制与决策, 2018, 33(4): 649-656.
LI H L, WANG C, DENG X Y. Multivariate time series clustering based on affinity propagation of component attributes[J]. Control and Decision, 2018, 33(4): 649-656.
[11] OZER M, SAPIENZA A, ABELIUK A, et al. Discovering patterns of online popularity from time series[J]. Expert Systems with Applications, 2020, 151: 113337.
[12] LI H, WEI M. Fuzzy clustering based on feature weights for multivariate time series[J]. Knowledge-Based Systems, 2020, 197: 105907.
[13] HE G, JIANG W, PENG R, et al. Soft subspace based ensemble clustering for multivariate time series data[J]. IEEE Transactions on Neural Networks and Learning Systems, 2023, 34(10): 7761-7774.
[14] MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, Dec 27, 1965-Jan 7, 1966. California: University of California Press, 1967: 281-297.
[15] RODRIGUEZ A，LAIO A. Clustering by fast search and find of density peaks[J]. Science, 2014, 344(6191): 1492-1496.
[16] 吕伟杰, 方一帆, 程泽. 基于模糊C均值聚类和样本加权卷积神经网络的日前光伏出力预测研究[J]. 电网技术, 2022, 46(1): 8-14.
LV W J, FANG Y F, CHENG Z. Prediction of day-ahead photovoltaic output based on FCM-WS-CNN[J]. Power System Technology, 2022, 46(1): 8-14.
[17] TONG W, WANG Y, ZHONG J, et al. A new weight based density peaks clustering algorithm for numerical and categorical data[C]//Proceedings of the 13th International Conference on Computational Intelligence and Security, Hong Kong, China, Dec 15-18, 2017: 169-172.
[18] FRANCESCHI J Y, DIEULEVEUT A, JAGGI M. Unsupervised scalable representation learning for multivariate time series[C]//Proceedings of the 2019 Annual Conference on Neural Information Processing Systems, Vancouver, Dec 8-14, 2019. Cambridge: MIT Press, 2019: 4652-4663.
[19] IENCO D, INTERDONATO R. Deep multivariate time series embedding clustering via attentive-gated autoencoder[C]//Proceedings of the 24th Pacific-Asia Conference on Knowledge Discovery and Data Mining, Singapore, May 11-14, 2020. Cham: Springer, 2020: 318-329.
[20] ZAKARIA J, MUEEN A, KEOGH E. Clustering time series using unsupervised-shapelets[C]//Proceedings of the 12th International Conference on Data Mining, Brussels, Dec 10-13, 2012: 785-794.
[21] LIU R, WANG H, YU X. Shared-nearest-neighbor-based clustering by fast search and find of density peaks[J]. Information Sciences, 2018, 450: 200-226.
[22] 余思琴, 闫秋艳, 闫欣鸣. 基于最佳U-shapelets的时间序列聚类算法[J]. 计算机应用, 2017, 37(8): 2349-2356.
YU S Q, YAN Q Y, YAN X M. Clustering algorithm of time series with optimal U-shapelets[J]. Journal of Computer Applications, 2017, 37(8): 2349-2356.
[23] YE L, KEOGH E. Time series shapelets: a new primitive for data mining[C]//Proceedings of the 15th International Conference on Knowledge Discovery and Data Mining, Paris, Jun 28-Jul 1, 2009. New York: ACM, 2009: 947-956.
[24] ULANOVA L, BEGUM N, KEOGH E. Scalable clustering of time series with u-shapelets[C]//Proceedings of the 2015 SIAM International Conference on Data Mining, Vancouver, Apr 30-May 2, 2015. Philadelphia: SIAM, 2015: 900-908.
[25] ZHANG Q, WU J, ZHANG P, et al. Salient subsequence learning for time series clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018, 41(9): 2193-2207.
[26] ZHANG N, SUN S. Multiview unsupervised shapelet learning for multivariate time series clustering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023, 45(4): 4981-4996.
[27] 陈磊, 吴润秀, 李沛武, 等. 加权K近邻和多簇合并的密度峰值聚类算法[J]. 计算机科学与探索, 2022, 16(9): 2163-2176.
CHEN L, WU R X, LI P W, et al. Weighted K-nearest neighbors and multi-cluster merge density peaks clustering algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(9): 2163-2176.
[28] DU M, WANG R, JI R, et al. ROBP a robust border-peeling clustering using Cauchy kernel[J]. Information Sciences, 2021, 571: 375-400.
[29] 曹俊茸, 张德生, 肖燕婷. 结合密度比和系统演化的密度峰值聚类算法[J]. 计算机工程与应用, 2022, 58(21): 75-82.
CAO J R, ZHANG D S, XIAO Y T. Density peak clustering algorithm combining density-ratio and system evolution[J]. Computer Engineering and Applications, 2022, 58(21): 75-82.