点击上方蓝字关注我们
Time-Series Clustering Based on the Characterization of Segment Typologies
作者：
David Guijo-Rubio , Antonio Manuel Durán-Rosal, Pedro Antonio Gutiérrez , et al.
期刊：
IEEE Transactions on Cybernetics
论文链接：
https://ieeexplore.ieee.org/document/8960542
简介
提出了一种新的两阶段时间序列聚类算法：
第一阶段对每条时间序列：先使用swiftseg方法【基于最小二乘方法的多项式拟合】，将时间序列分割成不同长度的子序列；再对子序列进行特征提取【多项式拟合参数、方差、偏度、自相关系数】，统一子序列的投影长度；最后，根据子序列的投影序列，使用层次聚类算法进行子序列聚类；
第二阶段对数据集中的全部时间序列聚类：利用子序列的类别信息表征时间序列，将所有时间序列投影到同一个维度的空集中，再使用层次聚类算法对全部时间序列进行聚类。
重要参数：子序列分割时的误差阈值，通过聚类结果的内部评价指标 来动态调整该参数。
数据实验：选取84个UCR数据集，并与三种最先进的方法进行了比较，表明该方法的性能非常有前途，尤其是在较大的数据集上。
研究动机
时间序列聚类通常分为：
1）基于形状的聚类，通过尽可能地匹配不同时间序列的形状【一般是多项式拟合】，之后必须使用适用于时间序列的距离度量，最后采用传统的聚类算法。
2）基于特征的聚类，将时间序列转换为一组统计特征【例如，均值、方差、斜率等】，其中该向量的长度小于原始时间序列。将每个时间序列转换为相同长度的特征向量，计算标准距离度量，再采用经典聚类算法。
3）基于模型的聚类，将原始时间序列转换为一组模型参数【多为概率分布模型】，然后进行模型距离测量，并采用经典聚类算法。
但是，经典的方法往往采用【特定的距离测算】与【经典聚类算法】结合的方法，容易忽视时间序列间模式的差异。对于时间序列中特定模式的提取，可选择通过分割时间序列中不同模式的子序列来实现。并且可以通过提取子序列的特征，来简化表征高维时间序列，在尽可能保存聚类准确性的同时，降低计算复杂度。
论文贡献
提出一种新的时间序列特征提取方法，通过分割时间序列得到不同长度的子序列，利用子序列的特征进行原始时间序列的表征，有效降低原始时间序列的维度；
提出一个新的两阶段时间序列聚类模型（TS3C），更适用于高维时间序列聚类，且计算成本低于其他方法（如实验部分所示）
1）通过识别时间序列中特定模式，提高时间序列的聚类质量；
2）面向子序列和原始时间序列，分别设计不同的映射表征。
3）最终的聚类计算成本不取决于原始时间序列的长度，而是与映射表征的长度有关。对于维度较高的时间序列数据集，显示出更好的性能和计算时间；
4）分割误差阈值作为TS3C 的主要参数，根据评估聚类质量的内部准则自动调整。
TS3C 模型
第一阶段
TS3C的第一阶段包括：分割时间序列、子序列的映射及子序列的聚类，如图1所示。
对于一个给定的时间序列长度，分割在于通过分割点，将时间序列分为m个子序列。
使用SwiftSeg算法：通过不断扩展窗口，增加窗口内数据点的个数，并对该窗口内的时间序列片段进行多项式拟合，设置拟合值和真实值的误差平方和为目标函数，直到目标函数超过分割误差阈值【用户自定义的参数】。此时，将确定一个分割点 ()，重复该过程直到到达时间序列的末尾。
本文中考虑以SEP作为目标函数：
子序列的映射：在分割处理之后，将每个子序列映射为一个l维的数组(l=c+f)，其中 c 是多项式拟合的参数个数，f 是统计特征的数量（f=3），p_s(向量)是近似线段 s 的多项式近似的参数。
子序列的聚类：对所有具有相同长度(l=c+f)的时间序列片段，采用以ward距离进行凝聚式层次聚类。设置子序列的聚类数量 k = 2（研究表明两组片段足以表征序列内部特征信息）。
第二阶段
时间序列的映射、聚类及评估质量。如图2：
对于每个时间序列Y_i，通过第一阶段的子序列聚类，可以获取k个簇类。对于任意一个簇类，选取两个重要信息：
①簇类的质心( )
②簇类中方差最高的子序列，记为（极端子序列，即簇中最具特征的子序列）。
将子序列的簇类映射为一个向量w(长度=2l)：
若一个时间序列的子序列有k个簇类，则有k个长度为2l的向量。
除了每个簇类的表示之外，本文还考虑了时间序列的另外两个特征：
①与质心最不相似的片段和与其质心最相似的片段之间的误差差 ( )， 通过使用相应多项式近似的均方误差（MSE）来评估分段的误差。
②时间序列的段数 因此，时间序列的映射长度为 ，k 是簇的数量，v 是时间序列的额外信息的数量，在我们的例子中为 2（即 和）。
时间序列聚类 对所有具有相同长度的时间序列，采用凝聚式层次聚类算法进行聚类。
参数调整TS3C 算法中仅涉及一个必须由用户调整的重要参数：分割错误阈值。建议考虑内部聚类评估指标来调整，提出两种不同的策略来选择最佳参数值：
①选择最佳 CH 指数的聚类结果对应的值，因为CH指数已被证明非常稳健；
②选择在多个内部评价指标上表现最佳的。
实验结果
数据集
84个UCR数据集，并按照时间序列的数量和时间序列的长度分为三组：
Group 1：序列个数>200，长度>300
Group 2：序列个数>200，长度<300
Group 3：其他
参数设置
多项式次数=1，分段聚类个数=2【一个序列分成两种模式】；
参数SEP_max考虑的范围为{10,20,30,...,100}；
结果展示
本文算法TS3C在Group 1的大规模数据集上表现更优。
致谢作者，感谢论文解读小沛同学！！转载请注明出处！关于论文的详细实施过程和具体解释请阅读论文原文哦～❤️❤️ /欢迎投稿
喜欢的话，请别忘记点赞👍➕关注哦
推荐阅读
港中文、UCL、武大联手攻关！NeurIPS 2024 全新多模态情绪分析模型，精准应对不完整数据挑战！
ECCV 2024｜解锁多模态自监督学习！深度解耦常见与独特表示的创新突破
CVPR 2024｜突破模态瓶颈！交替单模态适应引领多模态表示学习，攻克模态惰性与遗忘难题！
CVPR 2024｜拥抱单模态不确定性，实现稳健多模态融合！电子科大与同济等联手突破多模态技术瓶颈！
🌟投稿必读
