Hallac, David, et al. “Toeplitz Inverse Covariance-Based Clustering of Multivariate Time Series Data.” KDD. (2017).

本文是2017年KDD最佳论文，解决了高维时间信号的自动分割聚类问题，并给出了基于python的源码（戳这里下载）。

核心思想

在实际问题中有大量随时间变化的高维信号。
- 驾驶汽车：油门，刹车，地理位置，空调，门窗…
- 支付软件：用户的登陆，转入，提现，消费…

在没有标定的情况下，想发掘这些数据中隐藏的信息，即将信号划分为若干可能的状态，并标记每条信号的各段。
- 驾驶汽车：起步，上坡，超车，拥堵…
- 支付软件：用户发薪，过节，打新股…

这就需要同时对数据进行两种操作：
- 将各条数据进行分割
- 将分割结果各个聚类

传统聚类方法考察信号各维度的绝对值，以确定信号间的相似度；
本文算法考察信号各维度之间的相关性，以确定信号间的相似度。

建模

信号段

设有时间长度为T的原始信号

实际应用中，会有来自多个用户的多段原始信号。这里可以直接将它们连缀成一个向量。如果需要考虑绝对时刻，则可以将时间戳也作为一维信号增补上去。

其中每一时刻的信号xi为n维向量。

为了便于考察信号相关性，以每一时刻为基准，向前截取宽度为w的一段：

信号段Xi为nw维向量。

类别信息

预期将所有信号段划分为K类，属于第j类的信号段序号集合记为Pj,j=1,2...K。

举例：有信号段ABAAC，n=5, K=3。P1=[0,2,3],P2=[1],P3=[4]

认为每一类信号段服从0均值高斯分布，其协方差逆矩阵为Θj,j=1,2...K。这是一个nw×nw的矩阵。

Θi由w×w个子矩阵组成，每个子矩阵的尺寸为n×n。位置pq的子矩阵描述时刻p和时刻q之间，n个维度之间的协方差逆矩阵。

这里假设信号是非时变的，不同时刻信号之间的关系只和相对时间差有关；交换pq，其协方差逆阵互为转置。

换句话说，Θj是个分块Toeplitz矩阵：

每条斜线上的子矩阵相同；对角对称斜线的子矩阵互为转置。

求解

我们需要轮流求解两个问题
- 给定Θj，求解信号段分类方法Pj
- 给定Pj，求解各类逆协方差阵Θj

信号段分类Pj

给定Θj，把信号段Xi归入j类的代价可以负对数似然表示：

另外考虑信号的连续性：相连信号段不同类时施加惩罚β。

两个代价构成经典的流水线调度问题，可以使用BP算法求解。

其核心思路是：在给第i个信号段分类时，只需考虑第i-1信号段分为各类时的代价即可。

逆协方差阵Θj

给定一类中所有信号段集合Pj，通过最小化其负对数似然总和，可以求解Θj。
各类可以并行计算，故书写时省去下标j。

求和号内第一项和j无关，||表示集合内元素计数：

求和号内第二项可以写成迹的形式：

其中S是由Pj中所有信号段计算得到的当前协方差阵。1

另外添加一个正则项：

其中λ为权重矩阵，⊙表示矩阵对位相乘。

根据前述，要求Θ是分块Toeplitz矩阵。

把问题稍作变换为如下形式，可以用ADMM2算法快速求解：

实验

正确率

使用模拟数据：信号维度n=5，窗口宽度w=5。聚类数量K从2到4不等。每个实验包含100K个样本。
试验中直接固定K为真值。使用所有聚类的F1 score均值作为聚类质量评估。

可以看到，本文的TICC算法（第一行）有十分明显的优势。

TICC算法（蓝方块）聚类所需的样本数也较少。

可扩展性

使用n=50的高维样本，聚类数量K=5，窗口宽度w=3。下图示出，当信号长度增加时，聚类时间的增长基本为线性。

真实案例

给出了汽车行驶案例，大家体会一下。

传感器n=7

• 刹车状态
• 前向加速度
• 侧向加速度
• 方向盘角度
• 速度
• 发动机转速
• 油门状态

每一组观测时长1小时，每隔0.1秒采样一次。共有36000组观测。

使用的窗口w=10时长1秒。

使用BIC方法3发现的最佳聚类数量为K=5。人工观察，它们对应于如下状态：