1.文章介绍

• 论文出处：IEEE TRANSACTIONS ON CYBERNETICS 2021
  （SCI 1区，CCF-B）

• 论文链接

• 暂无代码

• 【摘要】：时间序列聚类是根据时间序列的相似性或特征对其进行分组的过程。以往的方法通常将时间序列的特定距离测量和标准聚类方法结合起来。然而，这些方法并没有考虑每个时间序列的不同子序列的相似性，而这种相似性可以用来更好地比较数据集的时间序列对象。在本文中，我们提出了一种由两个聚类阶段组成的新型时间序列聚类技术。第一步，对每个时间序列应用最小二乘多项式分割程序，该程序基于增长窗口技术，可返回不同长度的片段。然后，根据近似线段模型的系数和一组统计特征，将所有线段投影到同一维空间。映射完成后，第一个分层聚类阶段将应用于所有映射的片段，返回每个时间序列的片段组。在定义另一个特定的映射过程后，这些聚类用于在同一维空间中表示所有时间序列。在第二个也是最后一个聚类阶段，对所有时间序列对象进行分组。我们考虑内部聚类质量，自动调整算法的主要参数，即分割的误差阈值。在 UCR 时间序列分类档案中的 84 个数据集上获得的结果已经过比较。

2.问题背景

• 以前的方法并没有考虑每个时间序列的不同子序列的相似性，然而这可以用来更好地比较数据集的时间序列对象

3.拟解决的问题

• 将每个时间序列的子序列的差异引入聚类算法中

4.主要贡献

• 使用了一种新的时间序列特征提取来减少这些时间序列的大小，同时又不丢失太多信息。

5.提出的方法

5.1算法伪代码

5.2两阶段统计分段聚类时间序列方法

5.2.1第一阶段

时间序列分割

• 定义：给定一个长度为$N_i$的给定时间序列，分割由 t = { t s } s = 1 m t = \{t_s\}_{s=1}^m t={ts​}s=1m​个切点定义的$m$段。这样，分段$S$的集合= { s 1 , s 2 ， … ， s m } \{s_1, s_2，…， s_m\} {s1​,s2​，…，sm​}，其中 s 1 = { y 1 ， … ， y t 1 } s_1 = \{y_1，…， y_{t_1}\} s1​={y1​，…，yt1​​}， s 2 = { y t 1 ， … ， y t 2 } s_2 = \{y_{t_1}，…， y_{t_2}\} s2​={yt1​​，…，yt2​​}，…， s m = { y t m − 1 ， … , y N i } s_m = \{y_{t_{m-1}}，…, y_{N_i}\} sm​={ytm−1​​，…,yNi​​}

• 本文中采用的是SwiftSeg，该算法迭代地将时间序列中的点引入一个不断增长的窗口中，同时更新相应的分段的最小二乘多项式近似及其误差。窗口不断增长，直到超过error阈值，引入一个切点($t_s$)，分割结束。这个过程一直重复，直到到达时间序列的末尾。

• 错误函数SEP(standard error of prediction)：
  
  
  式中，$y_i$ 为第 $i$ 时刻的时间序列值，$\widehat{y_i}$ 为其对应的最小二乘多项式近似。这个误差函数的优点是它不考虑每个段的值的规模。

片段映射

• 每个片段被映射到一个数组中，包括段的最小二乘近似的多项式系数和一组统计特征，故每个线段被映射到I维空间，其中I为映射线段的长度

• 统计特征

1. 方差：
   

2. 偏态
   

3. 自回归系数
   

• 每个段被映射到一个 $l$ 维数组 ($l=c+f$)，用作片段表示，其中 $c$ 是多项式的次数，$f$ 是统计特征的数量，$f=3$

其中$p_s$是近似于片段$s$的多项式近似的参数

片段聚类

• 使用agglomerative的层次聚类，相似性度量采用的是Ward距离，聚类类别数设置2，

5.2.2第二阶段

时间序列映射

• 对于每个时间序列 ${\mathbf{Y}}_i$, 提取相应的质心，其中 i ∈ { 1 , … , T } i \in \{1, \dots, T\} i∈{1,…,T}， j ∈ { 1 , … , k } j \in \{1, \dots, k\} j∈{1,…,k}，其中 $k$ 为簇的个数，$T$ 为时间序列的个数。对于每个 cluster，提取以下信息：

1. 质心$\widehat{c_{ij}}$

2. 方差较大的片段的映射$X_{C_{ij}}$

3. 映射结果为：
   

4. 映射的时间序列的长度为$(w\times k)+v$，其中$k$为集群的数量，$v$为时间序列的额外信息的数量，这里设置为2。

时间序列聚类

• 采用agglomerative的层次聚类

5.3参数设置

• TS3C算法的参数只涉及分割过程的错误阈值SEPmax

• 错误阈值SEPmax的设置可以通过以下两种方式进行设置

1. 选择SEPmax能够获得最佳的CH指数

2. 选择能获得最多内部测量数的最佳值的SEPmax，即多数表决

6.实验

6.1模型设置

• 数据集：
  
  

• 评价指标：

1. RI
2. 执行时间

6.2实验结果

• Group1数据集上的实验结果
  

• Group2数据集上的实验结果
  

• Group3数据集上的实验结果
  

• 每个数据组的平均排名
  

• 假设检验
  

• 由于Friedman检验没有发现组2和组3的RI有显著的统计学差异，使用Holm检验，通过比较第i和第j个算法，计算以下统计量：
  
  其中 $J$ 表示算法的数量，$T$ 表示数据集的数量，$R_i$ 是第 $i$ 种方法的排名，$R_j$ 是第 $j$ 种方法的排名。

• 显著性检验
  

7.结论

• 本文使用了以下方法：

1. 最小二乘多项式分割过程，使用增长窗口法

2. 提取每个时间序列片段的特征(多项式趋势系数、方差、偏度和自相关系数)

3. 使用分层聚类对这些特征进行聚类

4. 每个聚类的质心、方差较大的时间序列片段、均方误差的差值和段数的表示

5. 利用时间序列簇的信息对时间序列进行映射

6. 最后的聚类阶段使用映射的数据集作为输入,内部性能度量用于调整唯一的参数值。

8.个人观点

1. 对原始时间序列的分割方式为SwiftSeg，即迭代地将时间序列中的点引入一个不断增长的窗口中，同时更新相应的分段的最小二乘多项式近似及其误差。窗口不断增长，直到超过error阈值，引入一个切点(ts)，分割结束

2. 对原始时间序列进行分割后，计算每个时间序列片段的统计特征，如方差、偏度、自回归系数，将这些统计特征用于层次聚类