提出一种高维变化点检测新方法，适用于在线与离线数据。
High-Dimensional Change Point Detection via Graph Spanning Ratio
- 基于图跨度比设计，适用于未知分布的欧氏与图结构数据。
- 当变化幅度超过√(nd)量级时，检测功效接近理论最优。
- 在小窗口下仍保持强检测能力，适合实时在线场景。
受图论方法启发，我们提出一种新型图跨度算法，用于低维到高维数据中离线与在线变化点的检测。该方法适用于欧氏空间与图结构数据，且分布未知，同时能控制错误概率。理论上证明，当变化幅度超过最小可分率下界（量级为√(nd)）时，算法具有高检测功效。在高斯与非高斯数据上，其精度优于其他方法。尤其在观测窗口较小时仍具备强检测能力，特别适合对时效性要求高的在线环境。
原文摘要 · Abstract (English)
Inspired by graph-based methodologies, we introduce a novel graph-spanning algorithm designed to identify changes in both offline and online data across low to high dimensions. This versatile approach is applicable to Euclidean and graph-structured data with unknown distributions, while maintaining control over error probabilities. Theoretically, we demonstrate that the algorithm achieves high detection power when the magnitude of the change surpasses the lower bound of the minimax separation rate, which scales on the order of $\sqrt{nd}$. Our method outperforms other techniques in terms of accuracy for both Gaussian and non-Gaussian data. Notably, it maintains strong detection power even with small observation windows, making it particularly effective for online environments where timely and precise change detection is critical.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。