Change-Point Analysis for Multivariate and Object Data

技术进步使人们能够收集大量数据，研究各种领域的时间和/或空间的复杂现象。其中许多数据涉及高维或非欧几里德测量序列，其中变点分析是理解数据的关键早期步骤：分段或离线变点分析将数据划分为同质的时间或空间段，使后续分析更容易；其在线对应项检测顺序观测数据的变化，从而实现实时异常检测。传统的变点分析主要关注单变量测量。有一些关于多变量数据的文献，但关于对象数据的文献很少。该项目考虑了多变量和对象数据的离线和在线变化点分析，例如，用于多传感器系统、图像和社会网络的时间分析。所提出的方法和相应的理论建立在PI的前人工作的基础上，该方法将基于非参数图的两样本测试应用于分割问题。PI已经表明，基于图形的方法可以灵活地扩展到高维和对象数据，并允许通用的解析置换p值近似，该近似与特定于应用程序的建模分离。尽管最近取得了这些进展，但仍然存在许多挑战。该项目确定了这些挑战，将它们制定为可接近的框架，并开发了适当的方法和理论处理方法。特别是，这个项目将(1)研究更敏感的基于距离的测试，以测试高维或非欧几里德空间中分布的相等性，这将适用于变点测试和估计问题，从而更敏感和更准确地检测一般变化；(2)解决将离线情况下的非参数图框架扩展到在线场景的方法和理论问题；以及(3)将基于图的分割和在线检测扩展到圆形块排列框架，使其能够处理具有弱局部相关性的多变量和对象数据。

Technological advances allow for the collection of massive data in the study of complex phenomena over time and/or space in various fields. Many of these data involve sequences of high dimensional or non-Euclidean measurements, where change-point analysis is a crucial early step in understanding the data: Segmentation or offline change-point analysis divides data into homogeneous temporal or spatial segments, making subsequent analysis easier; its online counterpart detects changes in sequentially observed data, allowing for real-time anomaly detection. Traditional change-point analyses primarily focus on univariate measurements. There is some literature on multivariate data, but very little on object data. This project considers both offline and online change-point analysis for multivariate and object data, for instance, for temporal analysis of multiple sensor systems, images, and social networks. The proposed methods and corresponding theory build on previous work of the PI, which adapts nonparametric graph-based two-sample tests to the segmentation problem. The PI has shown that the graph-based approach scales flexibly to high dimensional and object data, and allows for a universal analytic permutation p-value approximation that is decoupled from application-specific modeling. Despite this recent development, many challenges remain. This project identifies these challenges, formulates them into approachable frameworks, and develops appropriate methods and theoretical treatments. In particular, this project will (1) study more sensitive distance-based tests for testing equality of distributions in high dimensional or in non-Euclidean spaces, which will be adapted to the change-point testing and estimation problem, resulting in a more sensitive and accurate detection of general changes; (2) address methodological and theoretical issues in extending the nonparametric graph-based framework on the offline case to the online scenario; and (3) extend graph-based segmentation and online detection to a circular block permutation framework, enabling them to work for multivariate and object data with weak local dependence.