Graph-Based Change-Point Detection

• Activity Number: 173
• Type: Contributed
• Date/Time: Monday, July 30, 2012 : 10:30 AM to 12:20 PM
• Sponsor: Section on Nonparametric Statistics
• Author(s): Hao Chen*+ and David Oliver Siegmund and Nancy R. Zhang
• Companies: Stanford University and Stanford University and The Wharton School
• Keywords: change-point model ; graph-based test ; high dimensional data ; nonparametric

Abstract

Given a sequence of independent observations, we are concerned with testing for no change in distribution versus alternatives with a square-wave change. When the observations are in low dimension and from a known parametric family, existing parametric approaches can be applied. However, for non-Euclidean or high-dimensional observations, the change-point problem has not been well studied. We develop a general framework for change-point detection under all scenarios as long as the metric space on the observations is well defined. We suggest a statistic based on a graph that could reflect the similarity of the data points, such as a minimum spanning tree or a minimum distance pairing graph. An analytic approximation for the false positive error probability is derived and shown to be reasonably accurate by simulation.