Journal of Frontiers of Computer Science and Technology ›› 2024, Vol. 18 ›› Issue (2): 387-402.DOI: 10.3778/j.issn.1673-9418.2211099

• Theory·Algorithm • Previous Articles     Next Articles

Multivariate Time Series Density Clustering Algorithm Using Shapelet Space

SHENG Jinchao, DU Mingjing, SUN Jiarui, LI Yurui   

  1. School of Computer Science and Technology, Jiangsu Normal University, Xuzhou, Jiangsu 221100, China
  • Online:2024-02-01 Published:2024-02-01

面向Shapelet空间的多变量时间序列密度聚类算法

盛锦超,杜明晶,孙嘉睿,李宇蕊   

  1. 江苏师范大学 计算机科学与技术学院,江苏 徐州 221100

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空间, 密度峰值聚类, 数据挖掘