不等长时间序列滑窗STS距离聚类算法  

Non-Equal Time Series Clustering Algorithm with Sliding Window STS Distance

作　　者：刘琴[1] 王恺乐 饶卫雄[1] 

机构地区：[1]同济大学软件学院,上海201804

出　　处：《计算机科学与探索》2015年第11期1301-1313,共13页Journal of Frontiers of Computer Science and Technology

基　　金：国家自然科学基金No.61103006~~

摘　　要：时间序列的聚类算法是分析预测互联网搜索对象搜索指数和社交网络话题热度随时间变化趋势的重要过程,但目前时间序列聚类算法的研究存在两点不足:首先国内外的时间序列聚类的研究都采用等长划分的时间序列,这往往会丢失许多重要特征点,对数据挖掘结果产生一定的负面影响;其次直接使用时间序列观测值不能准确地度量时间序列的形状相似度。因此,通过标准分数z_score预处理消除了时间序列观测值数量级差异的影响,并设计了基于滑窗的不等长时间序列STS(short time series)距离和类k-means聚类算法的中心曲线计算方法,最终提出了基于滑窗不等长时间序列STS距离的聚类算法,从而解决了不等长时间序列聚类问题。采集互联网上的真实数据集作为测试样本,并进行了大量实验。实验结果表明,基于滑窗不等长时间序列STS距离的聚类算法不仅消除了时间序列观测值数量级差异的影响,解决了不等长时间序列聚类问题,并且比现有算法取得了更优的聚类效果。Time series clustering is an important algorithm widely used by many applications,such as the analysis and forecast of topics on social media and search words on search engine.However,existing time series clustering algorithms suffer from two shortcomings.Firstly,time series clustering algorithms mostly work only for isometric time series with equal length,leading to the loss of many important features and negative impact of clustering results.Secondly,time series similarity metrics are not able to compare the shape similarity of time series.To address the problems,this paper proposes a novel computation framework to cluster time series data with non-equal length.At first,this paper uses z_score standardization to normalize the observed values of time series data.Next,based on sliding window,this paper extends STS（short time series） distance and designs a new distance measure for time series with non-equal time length.After that,this paper adapts the classic k-means algorithm to develop a new clustering algorithm.The extensive experimental results,by two real datasets that are collected from search engines and public data,successfully verify that the proposed time series clustering algorithm can handle non-equal time series data and outperform the state of arts in terms of clustering accuracy and quality.

关 键 词：聚类 时间序列 K-MEANS算法 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]