Toeplitz Inverse Covariance-based Clustering （TICC）方法

文章原名：Toeplitz Inverse Covariance-Based Clustering of
Multivariate Time Series Data
网址：Toeplitz Inverse Covariance-Based Clustering of
Multivariate Time Series Data
github:https://github.com/davidhallac/TICC

背景

有多种场景下可能会采集到高维度的时间信息，而我们想从中获取一些模式信息，并对这些模式进行聚类。简单的例子：汽车在行驶时会有加速，减速，左转弯，右转弯，红灯停等多种状态，这些状态可能交替出现，而多个传感器采集的是不同的信息，形成了一个高维时间信息，TICC就是要从这些高维信息中抽取出相同状态的时间段，并将其划分为一类。

要解决的问题

多维时间序列分类难，既不同于传统时间序列分割，因为多个时间序列片段可能属于同一列；也不同于子序列聚类问题，因为不能当多独立的序列去聚类，相邻的点更倾向于分为同一类。本文关注各维度的相关性，可解释性更强。

方法

不止着眼于某一时刻，而是着眼于某一跨度为w的时间段，如果有n维数据，将这些时间段连起来形成新的变量
X t = [ x t − w + 1 , . . . x t ] X_t=[x_{t-w+1},...x_t] Xt​=[xt−w+1​,...xt​]
通过处理他的高斯逆协方差矩阵 Θ i ∈ R n w × n w \varTheta _i ∈ R^{nw×nw} Θi​∈Rnw×nw和分类标记 P i , i = 1 , 2 , 3... k ) P_i,i=1,2,3...k) Pi​,i=1,2,3...k)之间的关系来进行聚类，这里用到了EM方法。
其中 Θ \varTheta Θ是一个分块的Toeplitz矩阵。
总体优化函数为：

看不懂。。。
作者说这是一个高度非凸问题，很难求得最优值，往往通过EM方法可以取得较好结果

步骤

EM包括两步

• E步：已知 Θ \varTheta Θ的聚类结构参数，求解具体分类结果 P P P;
• M步：已知具体分类结果 P P P，分析 Θ \varTheta Θ的聚类结构参数

E步

给 x i x_i xi​指定具体分类，通过求解：

β \beta β是用来衡量偏不偏向把相邻的时间段 X i X_i Xi​划分到一个类的参数， β \beta β越大则更偏向，这从公式中很好理解。
具体的求解方法为BP算法：

M步

给定分类 P P P，来求解 Θ \varTheta Θ,实际是求解Toeplitz图回归

作者的方法交替方向乘子法（ADDM）方法进行了求解。