论文标题
基于近似$ k $的邻居图的快速而有效的更改点检测框架
A Fast and Efficient Change-point Detection Framework based on Approximate $k$-Nearest Neighbor Graphs
论文作者
论文摘要
在这个大数据时代，变化点分析正在蓬勃发展，以解决在许多领域中收集大量数据序列以研究复杂现象随着时间的流逝而产生的问题。它通过将长序列分为均匀的部分进行后续研究来在处理这些数据中起重要作用。该任务要求该方法能够快速处理大型数据集并处理高维数据的各种更改。我们提出了一种新方法，利用从观测值中使用大约$ k $ neart的邻居信息，并得出一个分析公式来控制I型错误。我们提出的方法的时间复杂度为$ o \ left（dn（\ log n+k \ log d）+nk^2 \ right）$ $ n $ ltength序列的$ d $ d $维数据。我们考虑的测试统计量合并了中等至高维数据的有用模式，因此所提出的方法可以检测序列中的各种变化。新方法也无渐进的分布，促进了其对更广泛社区的使用。我们将我们的方法应用于fMRI数据集和神经质子数据集，以说明其有效性。
Change-point analysis is thriving in this big data era to address problems arising in many fields where massive data sequences are collected to study complicated phenomena over time. It plays an important role in processing these data by segmenting a long sequence into homogeneous parts for follow-up studies. The task requires the method to be able to process large datasets quickly and deal with various types of changes for high-dimensional data. We propose a new approach making use of approximate $k$-nearest neighbor information from the observations, and derive an analytic formula to control the type I error. The time complexity of our proposed method is $O\left(dn(\log n+k \log d)+nk^2\right)$ for an $n$-length sequence of $d$-dimensional data. The test statistic we consider incorporates a useful pattern for moderate- to high- dimensional data so that the proposed method could detect various types of changes in the sequence. The new approach is also asymptotic distribution free, facilitating its usage for a broader community. We apply our method to fMRI datasets and Neuropixels datasets to illustrate its effectiveness.
