Online change-point detection (OCPD) is important for application in various areas such as finance, biology, and the Internet of Things (IoT). However, OCPD faces major challenges due to high-dimensionality, and it is still rarely studied in literature. In this paper, we propose a novel, online, graph-based, change-point detection algorithm to detect change of distribution in low- to high-dimensional data. We introduce a similarity measure, which is derived from the graph-spanning ratio, to test statistically if a change occurs. Through numerical study using artificial online datasets, our data-driven approach demonstrates high detection power for high-dimensional data, while the false alarm rate (type I error) is controlled at a nominal significant level. In particular, our graph-spanning approach has desirable power with small and multiple scanning window, which allows timely detection of change-point in the online setting.
Graph-based CPD methods are two-sample tests based on various types of graphs representing the similarity between observations, which are first proposed by Friedman and Rafsky @cite_4 (1979) using minimum-spanning tree (MST) graph. Also, Rosenbaum @cite_10 (2005) propose another test based on the minimum-distance pairing (MDP) using the rank of the distance within the pairs, which is thus restricted to MDP graph. Recently, Chen and Zhang @cite_2 (2015), utilize MST and MDP graph representations onto the data, and construct a test statistic based on counting the number of edges connecting points from different groups. They demonstrate that graph-based CPD has better detection power at high-dimensional data compared to parametric methods, such as Hotelling’s @math and generalized likelihood ratio test. Chen and Zheng develop an algorithm to count the edges between groups before and after the potential change-point. However, this pioneer CPD graph method, firstly, works only for offline detection, which is not sufficient in fields where an immediate reaction is needed when a change-point is detected. Secondly, its detection power is comparably not sensible to the variance change and is limited by the size of the dataset. Our proposed method contributes in filling the aforementioned gaps.
@cite_10 @cite_4 @cite_2
2132138475 2027390033 2038102631
A new test is proposed comparing two multivariate distributions by using distances between observations. Unlike earlier tests using interpoint distances, the new test statistic has a known exact distribution and is exactly distribution free. The interpoint distances are used to construct an optimal non-bipartite matching, i.e. a matching of the observations into disjoint pairs to minimize the total distance within pairs. The cross-match statistic is the number of pairs containing one observation from the first distribution and one from the second. Distributions that are very different will exhibit few cross-matches. When comparing two discrete distributions with finite support, the test is consistent against all alternatives. The test is applied to a study of brain activation measured by functional magnetic resonance imaging during two linguistic tasks, comparing brains that are impaired by arteriovenous abnormalities with normal controls. A second exact distribution-free test is also discussed: it ranks the pairs and sums the ranks of the cross-matched pairs. Copyright 2005 Royal Statistical Society. Multivariate generalizations of the Wald--Wolfowitz runs statistic and the Smirnov maximum deviation statistic for the two-sample problem are presented. They are based on the minimal spanning tree of the pooled sample points. Some null distribution results are derived and a simulation study of power is reported. 5 figures, 2 tables.