Clustering Multivariate Time Series Data Based on Shape Extraction with Compactness Constraint

doi:10.3778/j.issn.1673-9418.2212038

Abstract

Abstract: Aiming at the naturalness and structural complexity of multivariate time series (MTS) data as well as the inability of existing algorithms to accurately identify clusters of high-dimensional time series data, the shape extraction multivariate time series clustering algorithm C-Shape under compactness constraints is proposed. Firstly, C-Shape performs largest triangle three buckets processing on the complex MTS to achieve the purpose of using fewer data while keeping the original shape unchanged. The raw data and the processed data are then selected to calculate the compactness between them to ensure the reduced spatial dimensionality is reasonable. Next, new cluster centers are obtained by using shape extraction while effectively preserving the shape integrity of the data, and the final cluster is formed by iteration. C-Shape can avoid the difficulty of grasping the low dimensional spatial dimensionality of the traditional down-sampling algorithm by fully taking into account the similarity between the shapes of the processed data and raw data. To validate its performance, C-Shape is tested with two classical and seven excellent time series clustering algorithms presented in recent years on the eight normal and four imbalanced MTS datasets with dimensions ranging from tens to thousands, respectively. Experimental results demonstrate all C-Shape clustering capabilities outperform those of the nine baseline algorithms, with an average improvement of 16.33% in Rand index and an average improvement of 69.71% in time performance. Thus C-Shape is an accurate and efficient multivariate time series clustering algorithm.

Key words: multivariate time series clustering, down-sampling, similarity measurement, shape extraction, time series compactness

摘要： 针对多元时序数据（MTS）的自然性和结构复杂性以及现有算法无法准确识别高维时序数据簇的问题，提出了紧凑性约束下的形状提取多元时间序列聚类算法C-Shape。该算法首先对繁杂的多元时序数据进行最大三角形三段降采样处理，达到使用较少数据而保持原有时序形状不变的目的。然后计算原始时序数据和处理后的时序数据之间的时间序列紧凑性，来评估所定的低维空间维度是否合理。接着在有效保证数据形状完整的基础上使用形状特征提取以确定新的簇中心，最后迭代形成最终簇。C-Shape充分考虑到处理后的数据与原数据形状之间的相似性，解决了传统降采样算法难以确定低维空间维度的难题。为验证算法性能，C-Shape与两个经典算法和七个近年提出的优秀时序聚类算法分别在八个常规和四个不平衡且维数从数十到数千不等的多元时序数据集上进行比较。实验结果显示，C-Shape聚类能力均优于九种对比算法，RI平均提高了16.33%，时间性能平均提高了69.71%。因此，C-Shape是一种精确且高效的多元时间序列聚类算法。

关键词: 多元时间序列聚类, 降采样, 相似度度量, 形状提取, 时间序列紧凑性

ZHANG Chi, CHEN Mei, ZHANG Jinhong. Clustering Multivariate Time Series Data Based on Shape Extraction with Compactness Constraint[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(5): 1243-1258.

张弛, 陈梅, 张锦宏. 紧凑性约束下的形状提取多元时序聚类[J]. 计算机科学与探索, 2024, 18(5): 1243-1258.

References

[1] 钱罗雄, 陈梅, 张弛, 等. 平滑非负低秩图表示聚类算法[J]. 计算机科学与探索, 2024, 18(3): 659-673.
QIAN L X, CHEN M, ZHANG C, et al. Smooth non-negative low-rank graph representation for clustering[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(3): 659-673.
[2] AGHABOZORIGI S, SHIRKHORSHIDI A S, WAH T Y. Time-series clustering—a decade review[J]. Information Systems, 2015, 53: 16-38.
[3] CHEN M, CHEN Y S, ZHU H Y, et al. Analysis of pollutants transport in heavy air pollution processes using a new complex-network based model[J]. Atmospheric Environment, 2023, 292: 119395.
[4] 万静, 吴凡, 何云斌, 等. 新的降维标准下的高维数据聚类算法[J]. 计算机科学与探索, 2020, 14(1): 96-107.
WAN J, WU F, HE Y B, et al. Clustering algorithm for high-dimensional data under new dimensionality reduction criteria[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(1): 96-107.
[5] GEORGE A B, NIU Y B, AVIYENTE S, et al. A practical introduction to EEG time-frequency principal components analysis (TF-PCA)[J]. Developmental Cognitive Neuroscience, 2022, 55: 101114.
[6] LIU J W, KANG H, TAO W D, et al. A spatial distribution-principal component analysis (SD-PCA) model to assess pollution of heavy metals in soil[J]. Science of the Total Environment, 2023, 859: 160112.
[7] LI H L. Multivariate time series clustering based on common principal component analysis[J]. Neurocomputing, 2019, 349: 239-247.
[8] LAURENS V D M, HINTON G. Visualizing data using t-SNE[J]. Journal of Machine Learning Research, 2008, 9: 2579-2605.
[9] MCINNES L, HEALY J. UMAP: uniform manifold approximation and projection for dimension reduction[J]. Journal of Open Source Software, 2018, 3(29): 861.
[10] STEINARSSON S. Down-sampling time series for visual representation[D]. Iceland: Reykjavik University, 2013.
[11] SAKOE H, CHIBA S. A dynamic programming approach to continuous speech recognition[C]//Proceedings of the 7th International Congress on Acoustics, Budapest, Jan 1, 1971: 65-69.
[12] FOLGADO D, BARANDAS M, MATUAS R, et al. Time alignment measurement for time series[J]. Pattern Recognition, 2018, 81: 268-279.
[13] WANG X, YU F, PEDRYCZ W, et al. Clustering of interval-valued time series of unequal length based on improved dynamic time warping[J]. Expert Systems with Applications, 2019, 125: 293-304.
[14] HONG J Y, PARK S H, BAEK J G. SSDTW: shape segment dynamic time warping[J]. Expert Systems with Applications, 2020, 150(3): 113291.
[15] LI H L. Time works well: dynamic time warping based on time weighting for time series data mining[J]. Information Sciences, 2021, 547: 592-608.
[16] PAPARRIZOS J, GRAVANO L. k-Shape: efficient and accurate clustering of time series[J]. SIGMOD Record, 2016,45(1): 69-76.
[17] FELIPE L G, GUSTAVO R F, HENRIQUE F D A, et al. Principal component analysis: a natural approach to data exploration[J]. ACM Computing Surveys, 2021, 54(4): 1-34.
[18] DUFERA A G, LIU T T, XU J. Regression models of Pearson correlation coefficient[J/OL]. Statistical Theory and Related Fields [2022-09-24]. https://doi.org/10.1080/24754269. 2023.2164970.
[19] MACQUEEN J. Some methods for classification and analysis of multivariate observations[C]//Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, Jun 21-Jul 18, 1965. Berkeley: University of California Press, 1967: 281-297.
[20] KAUFMAN L, ROUSSEEUW P J . Finding groups in data: an introduction to cluster analysis[M]. New York: John Wiley & Sons, Inc., 1990.
[21] GUIJIO R D, AM D R, PA G, et al. Time series clustering based on the characterization of segment typologies[J]. IEEE Transactions on Cybernetics, 2021, 51(11): 5409-5422.
[22] LUCZAK M. Hierarchical clustering of time series data with parametric derivative dynamic time warping[J]. Expert Systems with Applications, 2016, 62: 116-130.
[23] YANG J, LESKOVEC J. Patterns of temporal variation in online media[C]//Proceedings of the 4th International Conference on Web Search and Web Data Mining, Hong Kong, China, Feb 9-12, 2011. New York: ACM, 2011: 177-186.
[24] YANG X, DENG C, ZHENG F, et al. Deep spectral clustering using dual autoencoder network[C]//Proceedings of the 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition. Piscataway: IEEE, 2019: 4066-4075.
[25] MADIRAJU N S, SADAT S M, FISHER D, et al. Deep temporal clustering: fully unsupervised learning of time-domain features[J]. arXiv:1802.01059, 2018.
[26] DEYU B, XIAO W, CHUAN S, et al. Structural deep clustering network[C]//Proceedings of the Web Conference 2020, Taipei, China, Apr 20-24, 2020. New York: ACM, 2020: 1400-1410.
[27] 李海林, 贾瑞颖, 谭观音. 基于K-Shape的时间序列模糊分类方法[J]. 电子科技大学学报, 2021, 50(6): 899-906.
LI H L, JIA R Y, TAN G Y. Fuzzy classification for time series data based on K-Shape[J]. Journal of University of Electronic Science and Technology of China, 2021, 50(6): 899-906.
[28] GARCIA V, SANCHEZ J S, MOLLINEDA R A. On the effectiveness of preprocessing methods when dealing with different levels of class imbalance[J]. Knowledge-Based Systems, 2012, 25(1): 13-21.
[29] KEOGH E，CHAKRABARI K，PAZZANI M, et al. Dimensionality reduction for fast similarity search in large time series databases[J]. Knowledge and Information Systems, 2001, 3: 263-286.
[30] 张锦宏, 陈梅, 张弛. 自适应阈值约束的密度簇主干聚类算法[J]. 计算机科学与探索, 2023, 17(12): 2880-2895.
ZHANG J H, CHEN M, ZHANG C. Density backbone clustering algorithm based on adaptive threshold[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(12): 2880-2895.