Sequential change-point detection based on nearest neighbors

2019/02/13 by Hao Chen · 89 citations
Computer Science · Mathematics · Medicine · #Algorithm #Anomaly Detection Techniques and Applications #Artificial intelligence #Change detection #Computer science #Data mining #Data-Driven Disease Surveillance #Euclidean distance #Euclidean geometry #Machine learning #Mathematics #Multivariate statistics #Pattern recognition (psychology) #Point (geometry) #Time Series Analysis and Forecasting #k-nearest neighbors algorithm

paper · pdf · doi:10.1214/18-aos1718

published in The Annals of Statistics 47(3) (Institute of Mathematical Statistics)

openalex publication_date 2019/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06

Abstract

We propose a new framework for the detection of change-points in online, sequential data analysis. The approach utilizes nearest neighbor information and can be applied to sequences of multivariate observations or non-Euclidean data objects, such as network data. Different stopping rules are explored, and one specific rule is recommended due to its desirable properties. An accurate analytic approximation of the average run length is derived for the recommended rule, making it an easy off-the-shelf approach for real multivariate/object sequential data monitoring applications. Simulations reveal that the new approach has better performance than likelihood-based approaches for high dimensional data. The new approach is illustrated through a real dataset in detecting global structural changes in social networks.

Cited by

• An Efficient Likelihood Ratio Test for Online Changepoint Detection in the Presence of Autocorrelation
• Optimal network online change point localisation
• Online Change-Point Detection in High-Dimensional Covariance Structure with Application to Dynamic Networks
• Weighted-Graph-Based Change Point Detection
• A review on minimax rates in change point detection and localisation
• A Normality Test for High-dimensional Data based on a Nearest Neighbor Approach
• Optimal Online Change Detection via Random Fourier Features
• Sequential Multivariate Change Detection with Calibrated and Memoryless False Detection Rates
• Max-Type and Sum-Type Procedures for Online Change-Point Detection in the Mean of High-Dimensional Data
• Sequential Change Point Detection with FDR Control in Reconfigurable Sensor Networks

Related

• Sequential change-point detection based on nearest neighbors
• Sequential change-point detection for mutually exciting point processes over networks
• A Fast and Efficient Change-point Detection Framework based on Approximate k-Nearest Neighbor Graphs
• Change-point detection for multivariate and non-Euclidean data with local dependency
• Detecting change points in the large-scale structure of evolving networks