前沿速递：集群时间序列变点检测的高阶拓扑特征提取

导语

高阶拓扑特征提取将𝑁×d×𝑇维时间序列数据转化为𝑀×𝑇维，进而采用变点检测估计集群状态变化的时间点。近日发表在Chaos上的一篇文章，作者通过提取时间切片上的Betti数和持久性两类高阶拓扑特征，实现数据降维和缺失数据插补，从而识别集群系统的状态变化，显示出了在时间序列分析、复杂网络等领域的应用潜力。该研究受到了集智高阶网络读书会第三期内容的启发。

关键词：变点检测，代数拓扑，多智能体集群，时间序列分析

顾孔静、晏良、李翔、段晓君、梁靖婕 | 作者

邓一雪 | 编辑

论文题目：

Change point detection in multi-agent systems based on higher-order features[1]

论文链接：https://doi.org/10.1063/5.0126848

1. 简介

根据时间序列识别集群运动的状态变化有助于揭示其机理并进一步控制集群系统，对集群状态变化的识别可以归结为变点检测问题，它可以辨识集群序列数据的生成参数突变。常见的无监督、离线多变量变点检测算法包括基于模型的贝叶斯变点检测（BCP）、基于统计量的非参数方法，如E-Agglo、E-Divisive、E-CP3O、KS-CP3O，与基于核函数的核变点分析（KCPA）等。一般算法已经解决d×𝑇维时间序列的变点检测问题，而集群观测往往得到𝑁×d×𝑇维度数据，其中𝑁指集群中的个体数。高阶拓扑特征可将𝑁×d×𝑇维度数据转换为𝑀×𝑇维。具体地，采用拓扑数据分析工具——持续同调，研究时间切片上的数据分布“形状”，获得拓扑不变性（Betti数）和同调类的持久性（Persistence）作为高阶拓扑特征，并代入一般变点检测方法得到变点估计。

二、方法

（a）整体：将时间序列分解为一系列时间切片，并在每个时间切片上采用具有不同直径ε的Vietoris-Rips复形构建拓扑结构，如图1（a）所示。

（b）部分：在每个时间切片上计算Betti数或持久性，得到高阶拓扑特征向量。如图1（b）所示，通过可视化不同直径ε下同源类的生灭得到条形码，Betti数是与垂直线相交的水平线条数，持久性是每个同调类[𝑧]的持续长度。从复杂网络的角度，在间距小于直径ε的节点间建立连接，Betti数即连通分支数。

（c）整体：所有时间切片的高阶拓扑特征向量集成为Betti数矩阵𝐵和持久性矩阵𝑃，并采用一般变点检测方法得到变点估计，如图1（c）所示，其中垂直线是变化时间点。

图1  Betti数和持久性特征提取示意图

3. 结果分析

准确性：下表展示了针对一维速度分量、二维速度和四维速度位置时间序列与基准方法的准确性比较，结果显示高阶拓扑特征（Betti number和Persistence）对基准方法的提升效果显著。

缺失数据：高阶拓扑特征本质是度量时间切片上的数据相对分布，与时间切片之间的节点对应关系无关。针对缺失数据存在的情况，在连续性假设下可以从相邻时间切片采样以恢复数据分布。

图2（a）展示了不同缺失数据比例下的Betti数和持久性特征提取的表现，其中黑色水平线是E-Agglo方法在无缺失数据情况下的表现，结果表明高阶拓扑特征对缺失数据具有较强稳定性。

图2 不同比例缺失数据实验

实例一：图3展示了对MSRC-12 数据集中一系列鞠躬动作的阶段划分，深色与浅色块的交界点为手动标注的变点。结果表明，Betti数和持久性特征提取方法均能合理划分动作序列，提高基准E-Agglo方法的性能。

图3  鞠躬动作序列的变点检测

实例二：图4展示了对具有缺失数据的鱼群运动阶段的划分，（a）和（b）中垂直黑色线段为高阶拓扑特征得到的变点，与（c）中依据序参量划分的阶段大致吻合。

图4 鱼群轨迹的变点检测

4. 展望

本文提出高阶拓扑特征提取方法可以实现数据降维和缺失数据插补，并提升高维时序数据的变点检测精度，可用于无人集群、社会及经济多主体系统、生物群落演化、语音和图像分析等领域的研究。此外，高阶拓扑特征还可为时间序列降维、复杂网络多尺度建模提供新的思路。

附录：

本文所有代码已上传Github https://github.com/gukongjing.

参考文献：

[1] Gu, K., Yan, L., Li, X., Duan, X., & Liang, J. (2022). Change point detection in multi-agent systems based on higher-order features. Chaos: An Interdisciplinary Journal of Nonlinear Science, 32(11), 111102. https://doi.org/10.1063/5.0126848

高阶网络读书会启动

随着对现实世界探索的不断深入，人们发现在许多真实的复杂系统中，组成系统的个体之间不仅存在二元交互关系，也广泛存在多个体同时（或以特定顺序）进行交互，即高阶交互现象。为此，研究人员分别发展出了基于超图、单纯复形、依赖关系等的网络高阶表示模型，为复杂网络分析和研究提供了新的思路。为了促进此领域的交流与合作，我们发起了【高阶网络读书会】。

集智俱乐部读书会是面向广大科研工作者的系列论文研读活动，其目的是共同深入学习探讨某个科学议题，激发科研灵感，促进科研合作。【高阶网络读书会】由电子科技大学吕琳媛老师、任晓龙老师及中国地质大学（北京）管青老师联合发起，每周分享时间为每周四 19:30-21:30 进行，预计持续 10-12 周。期间，我们将围绕高阶交互网络的基本概念、模型、方法与应用等研究进行研讨，本次读书会分享会按照「基础理论」+「深入理论」+「案例研讨」的模式展开。

详情请见：

推荐阅读

点击“阅读原文”，报名读书会