1.文章介绍

• 论文出处：EDBT 2021（CCF-B）

• 论文链接

• 代码地址

• 【摘要】：时间序列聚类问题在现实生活中有多种应用，尤其是在数据科学和数据分析管道中。现有的时间序列聚类算法只能根据原始数据计算时间序列的相似性，或者使用固定的特征集，因此对于特征丰富的真实世界时间序列来说效果不佳。在本文中，我们开发了一种基于特征的半监督聚类框架，解决了变长和异构时间序列的上述问题。具体来说，我们依赖于时间序列的图编码，这种编码是通过考虑大量重要的提取特征而获得的。然后，我们采用社区检测，并利用共现矩阵将所有最佳聚类结果组合在一起。我们进行的大量实验评估表明，我们的方法具有可扩展性和鲁棒性，而且在现实世界的医疗保健数据和 UCR 基准数据上都优于最先进的聚类算法。

2.问题背景

• 现有的时间序列聚类算法一般基于原始数据计算时间序列的相似性或使用一组固定的特征，而这对特征丰富的现实世界时间序列无效

3.拟解决的问题

• 根据输入的数据集自动选择最合适的统计特征，从而用于聚类

4.主要贡献

• 提出了一种利用从时间序列中提取的最有鉴别力的特征的新型半监督聚类方法，将相似的时间序列视为社区，并将不同的社区编码为共现矩阵，从而获得时间序列的统一相似度值

• 对给定数据集的所有特征同等对待，即通过计算选择合适的统计特征

• 与Seeded KMeans 和K-Shape相比，方法高质量且扩展性更高

5.提出的方法

5.1模型pipeline

5.2特征抽取和选择

• 根据时间序列的标签，使用Benjamini-Yekutieli程序识别各个特征的相关性，从而获得每个特征的p值。

• 再从p值列表中选取20个特征，这些特征是通过PFA（PCA的变体）计算而来的

• 示例，获得的特征如下：
  

5.3图渲染和社区检测

定义：假设有一个特征$F_i$和一组时间序列 { T S 1 , . . . , T S n } \{TS_1,...,TS_n\} {TS1​,...,TSn​}，将$T{S}_i$成为图G中顶点集V的一个节点，让E成为图G的边集，每条边$e_i$连接G中的两个结点
如图所示：

使用一个启发式的百分比$x$表示要保持的最小距离的比例,例如选择50%，则距离大于28的边被剪去，小于等于28的边被保留，通常设置阈值为80%

应用社区检测 (CD) 算法来搜索形成社区的密集连接的顶点组，如图所示：

5.4共现矩阵的构建

• 假设有M条时间序列和L个特征，再L个图上应用CD算法，可以获得以下聚类结果：
  

• 共现矩阵单元$x_{ij}$对应于时间序列$T{S}_i$和$T{S}_j$之间的相似度，相似度计算公式如下：
  
  即时间序列$T{S}_i$和$T{S}_j$一起出现的次数除以$T{S}_i$出现的次数

• CD算法的应用及其对无权重共现矩阵的处理可能会导致社区碎片化的问题，即会形成大量的社区，而这些社区只包含几个时间序列，也就是聚类问题中常常遇到的退化解问题。

• 加权函数定义如下：
  
  其中C是用户事先定义的聚类数量，$O_i$是通过CD算法提取的社区数量

示例：

1. 原始数据：
   
2. 通过PFA算法获得三个特征：
   
3. 然后利用CD算法对每个特征进行聚类，获得的结果如下：
   
4. 利用权重函数W获得加权共线矩阵：
   
5. 最终结果如下：
   

5.5对共现矩阵进行聚类

• 将共现矩阵中的每行数据看作一个向量，使用欧氏距离进行计算，计算结果如下：
  

• 最后使用K-Medoid算法进行聚类

6.实验

6.1模型设置

• 数据集：肾小球过滤率（GFR）数据集的两个变体Kidney3Yr和Kidney5Yr，UCR数据集

• 评价指标：AMI

• 对比方法：无监督的KShape和半监督的SeededKMeans

6.2实验结果

• UCR数据集上的AMI指标对比
  

• 肾脏案例研究
  

• 扩展性研究
  

6.3消融实验

• 将距离度量换成DTW
  

• 使用随机选择的特征
  

• 将pipeline中的3，4，5步替换成K-means，即使用PFA算法选择和提取特征后直接使用K-Means算法
  

7.结论

• 本方法利用了从数据本身提取的特征，而不是为所有数据集采用一组预定义的特征

• 本方法可以通过无监督方法进行改进，而不是当前的半监督方法

• 可以根据处理后的特征动态选择图创建的阈值进行改进

• 社区检测（CD）算法的权重可以与特征的相关度相结合

8.个人观点

• 论文仅仅对比了两种算法，因为他的方法是半监督的，相关的论文代码太少，于是作者对比了一个无监督方法和一个半监督方法。我们是否也可以使用半监督方法与无监督方法进行对比

• 本文的算法流程并不复杂，主要步骤就在于怎样获得共现矩阵

• 文中使用到了tsfresh，它是用于从时间序列中自动提取特征的python包。

9.Reference

• Benjamini-Yekutieli程序

• tsfresh