自适应时间平滑的演化谱聚类

Adaptive Time-Smoothed Evolutionary Spectral Clustering

传统的聚类算法一般只适用于静态数据的处理,而真实世界的数据往往数据量大且变化多,静态的聚类算法不能为动态数据提供其演化规律的分析学习。演化数据的聚类,一方面要正确反映每一时刻数据的合理簇划分,另一方面又要使动态的聚类结果在演化过程中尽可能平滑。本文提出了一种自适应时间平滑的演化聚类框架,该模型考虑到当前时刻数据与历史时刻数据的未知关联,通过限定时间回溯的范围,自适应地寻找与当前快照最相关的历史快照,并通过有机融合基于Itakura-Saito距离的静态相似度和基于时间序列的动态相似度,计算各个时间片快照上的相似度矩阵。本文进一步提出了两种自适应时间平滑的演化谱聚类算法,从不同的角度定义时间代价,得到不同的演化聚类结果。在真实数据集上的实验表明这两种算法能够有效地利用历史数据,在聚类结果上准确性更高,时间平滑性也更好。

Traditional clustering algorithms are generally only suitable for static data processing,while the real world data are often large and changeable,so static clustering algorithms cannot provide the analysis and learning of evolution rules for dynamic data.On one hand,the clustering of evolutionary data needs to reflect the reasonable cluster partition of data at each snapshot;on the other hand,it needs to make sure the dynamic clustering results are as smooth as possible.This paper proposes an adaptive time-smoothed evolutionary clustering framework,which takes into account of the unknown relationship between the current data and the historical data.By imposing a time window for backtracking,it adaptively finds the most relevant historical snapshot to the current snapshot.Meanwhile,it fuses the static similarity based on the Itakura-Saito distance and the dynamic similarity based on the time series to compute,so as so compute the similarity matrix on each snapshot.Under this framework,this paper further proposes two adaptive time-smoothed evolutionary spectral clustering algorithms,which define the time cost from different aspects,and obtain different evolutionary clustering results.Experiments on real datasets show that the two proposed algorithms can effectively utilize historical data,and achieve better clustering performance as well as better temporal smoothness.