Nonparametric tests for homogeneity based on non-bipartite matching
Abstract
Given a sequence of observations, has a change occurred in the underlying probability distribution with respect to observation order? This
problem of detecting change points arises in a variety of applications including health prognostics for mechanical systems, syndromic
disease surveillance in geographically dispersed populations, anomaly detection in information networks, and multivariate process control
in general. Detecting change points in high-dimensional settings is challenging, and most change-point methods for multidimensional
problems rely upon distributional assumptions or the use of observation history to model probability distributions. We present three new
nonparametric statistical tests for heterogeneity based on the combinatorial properties of minimum non-bipartite matching (MNBM). The
key idea underlying each of these tests is that if a sequence of independent random observations undergoes a change in distribution—either
an abrupt “shift” or a gradual “drift”—a MNBM based on inter-point distances tends to produce pairings that are closer in the sequence
labeling than would be the case if the observations were drawn from the same distribution. Our tests follow on the work of Rosenbaum
(2005) who used MNBM to derive a simple cross-match test statistic for the two-sample problem based on this idea. Similar ideas are
present in the minimum spanning tree (MST) test derived by Friedman and Rafsky (1979, 1981). We extend these approaches by utilizing
ensembles of orthogonal MNBMs which greatly increase information extraction from the data, leading to tests that compare favorably to
parametric procedures while maintaining level and good power properties across distributions.
Description
The article of records as published may be located at http://dx.doi.org/10.1198/Jasa.2011.tm10576
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.Collections
Related items
Showing items related by title, author, creator and subject.
-
Applications of assignment algorithms to nonparametric tests for homogeneity
Ruth, David M. (Monterey, California: Naval Postgraduate School, 2009-09);We propose new nonparametric statistical tests to identify whether each element in a sequence of independent multivariate observations is drawn from a common probability distribution or if some distributional change has ... -
Design of a decentralized asynchronous group membership protocol and an implementation of its communications layer
Pires, Fernando Jorge. (Monterey, California. Naval Postgraduate School, 1993-03);For development of group-oriented distributed applications, a group membership protocol provides the mechanisms to dynamically adapt to changes in the membership, ensuring consistent views among all members of the group. ... -
Group membership in asynchronous distributed environments using logically ordered views
Shukla, Shridhar B.; Raghuram, Devalla (Monterey, California. Naval Postgraduate School, 1992-09-16); NPS-EC-92-009A group membership protocol ensures agreement and consistent commit actions among group members to maintain a sequence of identical group views in spite of continuous changes, either voluntary or otherwise, in processors' ...