Homogeneity and change-point detection tests for multivariate data using rank statistics

Lung-Yut-Fong, Alexandre; Lévy-Leduc, Céline; Cappé, Olivier

Journal de la société française de statistique, Tome 156 (2015) no. 4, pp. 133-162.

La détection et la localisation de changements dans des données de très grande dimension est un problème majeur dans plusieurs domaines d’applications. Dans ce contexte, la première contribution de notre papier est un nouveau test d’homogénéité non-paramétrique à deux échantillons pour des données multivariées fondé sur la statistique de rang de Wilcoxon. Le test d’homogénéité à deux échantillons que nous proposons peut être étendu au cas de données censurées et pour proposer un test d’homogénéité pour plus de deux échantillons. Nous proposons également une analyse détaillée du calcul de la puissance de notre statistique de test vis à vis de certaines alternatives locales. La seconde contribution de notre papier concerne l’utilisation de notre statistique de test pour faire de la détection rétrospective de ruptures. Nous montrons que notre méthode peut-être implémentée de façon efficace d’un point de vue algorithmique grâce à la programmation dynamique et nous proposons une méthode pour calculer les $p$-valeurs. Nous recommandons particulièrement notre approche dans les situations suivantes : lorsque les corrélations entre les coordonnées des observations sont modérées, lorsque les lois marginales ne peuvent pas être modélisées par les lois paramétriques usuelles ou lorsque les changements n’affectent qu’une partie des coordonnées des observations.

Detecting and locating changes in highly multivariate data is a major concern in several current statistical applications. In this context, the first contribution of the paper is a novel non-parametric two-sample homogeneity test for multivariate data based on the well-known Wilcoxon rank statistic. The proposed two-sample homogeneity test statistic can be extended to deal with ordinal or censored data as well as to test for the homogeneity of more than two samples. We also provide a detailed analysis of the power of the proposed test statistic (in the two sample case) against asymptotic local shift alternatives. The second contribution of the paper concerns the use of the proposed test statistic to perform retrospective change-point detection. It is first shown that the approach is computationally feasible even when looking for a large number of change-points thanks to the use of dynamic programming. Computable asymptotic $p$-values for the test are available in the case where a single potential change-point is to be detected. The proposed approach is particularly recommendable in situations where the correlations between the coordinates of the data are moderate, the marginal distributions are not well modelled by usual parametric assumptions (e.g., in the presence of outliers) and when faced with highly variable change patterns, for instance, if the potential changes only affect subsets of the coordinates of the data.

Keywords: change-point detection, homogeneity test, Kruskal-Wallis test, Mann-Whitney/Wilcoxon test, multivariate data, rank statistics
Mot clés : détection de ruptures, test d’homogénéité, test de Kruskal-Wallis, test de Mann-Whitney/Wilcoxon, données multivariées, statistiques de rang

[1] Brodsky, B. E.; Darkhovsky, B. S. Non-parametric statistical diagnosis, Kluwer Academic Publishers, Dordrecht, 2000 | Zbl

[2] Bellman, R. On the approximation of curves by line segments using dynamic programming, Communications of the ACM, Volume 4 (1961) no. 6, pp. 284-286 | DOI | Zbl

[3] Barry, D.; Hartigan, J. A. Product partition models for change point models, Ann. Statist., Volume 20 (1992), pp. 260-279 | Zbl

[4] Bickel, P.J. On some asymptotically nonparametric competitors of Hotelling’s $T^2$., Ann. Math. Stat., Volume 36 (1965), pp. 160-173 | Zbl

[5] Basseville, M.; Nikiforov, I. V. Detection of Abrupt Changes: Theory and Applications, Prentice-Hall, 1993

[6] Bai, J.; Perron, P. Computation and Analysis of Multiple Structural Change Models, Journal of Applied Econometrics, Volume 18 (2003) no. 1, pp. 1-22

[7] Bleakley, Kevin; Vert, Jean-Philippe The group fused Lasso for multiple change-point detection (2011) (Technical report arXiv:1106.4199)

[8] Chen, Jie; Gupta, A. K. Parametric statistical change point analysis, Birkhäuser, Boston, MA, 2000, viii+184 pages | MR | Zbl

[9] Csörgő, M.; Horváth, L. Limit theorems in change-point analysis, Wiley, New-York, 1997 | Zbl

[10] Désobry, Frédéric; Davy, Manuel; Doncarli, Christian An Online Kernel Change Detection Algorithm, IEEE Trans. Signal Process., Volume 53 (2005) no. 8, pp. 2961-2974 | Zbl

[11] Estrella, Arturo Critical values and $p$-values of Bessel process distributions: computation and application to structural break tests, Econometric Theory, Volume 19 (2003) no. 6, pp. 1128-1143 | MR | Zbl

[12] Fearnhead, P. Exact and Efficient Bayesian inference for Multiple Changepoint Problems, Statist. Comput., Volume 16 (2006), pp. 203-213

[13] Gretton, Arthur; Borgwardt, Karsten M.; Rasch, Malte J.; Schölkopf, Bernhard; Smola, Alexander J. A Kernel Method for the Two-Sample-Problem, Advances in Neural Information Processing Systems (2006), pp. 513-520

[14] Harchaoui, Z.; Bach, F.; Moulines, E. Kernel change-point analysis, Advances in Neural Information Processing Systems (2008)

[15] Harchaoui, Z.; Cappé, O. Retrospective Multiple Change-point Estimation with Kernels, IEEE Workshop on Statistical Signal Processing (2007)

[16] Harchaoui, Z.; Lévy-Leduc, C. Multiple change-point estimation with a total variation penalty, J. Amer. Statist. Assoc., Volume 105 (2010) no. 492, pp. 1480-1493 | Zbl

[17] Hettmansperger, T. P.; Möttönen, J.; Oja, Hannu Affine invariant multivariate rank tests for several samples, Statist. Sinica, Volume 8 (1998) no. 3, pp. 785-800 | MR | Zbl

[18] Jurečková, Jana; Kalina, Jan Nonparametric multivariate rank tests and their unbiasedness., Bernoulli, Volume 18 (2012) no. 1, pp. 229-251 | Zbl

[19] Kay, S.M. Fundamentals of statistical signal processing: detection theory, Prentice-Hall, Inc., 1993 | Zbl

[20] Kiefer, J. $K$-sample analogues of the Kolmogorov-Smirnov and Cramér-V. Mises tests, Ann. Math. Statist., Volume 30 (1959), pp. 420-447 | MR | Zbl

[21] Kruskal, W.H. Ordinal Measures of Association, J. Amer. Statist. Assoc., Volume 53 (1958) no. 284, pp. 814-861 | MR | Zbl

[22] Lavielle, M. Using penalized contrasts for the change-points problems, Signal Processing, Volume 85 (2005) no. 8, pp. 1501-1510 | Zbl

[23] Lehmann, E.L. Nonparametrics: statistical methods based on ranks, Holden-Day Inc., 1975, xvi+457 pages | MR | Zbl

[24] Lung-Yut-Fong, A.; Lévy-Leduc, C.; Cappé, O. Distributed detection/localization of change-points in high-dimensional network traffic data, Statist. Comput., Volume 22 (2012) no. 12, pp. 485-496 | arXiv | MR | Zbl

[25] Lévy-Leduc, C.; Roueff, F. Detection and localization of change-points in high-dimensional network traffic data, Ann. Applied Statist., Volume 3 (2009) no. 2, pp. 637-662 | MR | Zbl

[26] Möttönen, Jyrki; Oja, Hannu; Tienari, Juha On the efficiency of multivariate spatial sign and rank tests, Ann. Statist., Volume 25 (1997) no. 2, pp. 542-552 | MR | Zbl

[27] Oja, Hannu Affine invariant multivariate sign and rank tests and corresponding estimates: a review, Scand. J. Statist., Volume 26 (1999) no. 3, pp. 319-343 | MR | Zbl

[28] Page, E. S. Continuous inspection schemes, Biometrika, Volume 41 (1954), pp. 100-115 | MR | Zbl

[29] Poor, H.V.; Hadjiliadis, O. Quickest Detection, Cambridge University Press, Cambridge, 2009 | MR | Zbl

[30] Picard, Franck; Robin, Stephane; Lavielle, Marc; Vaisse, Christian; Daudin, Jean-Jacques A statistical approach for array CGH data analysis, BMC Bioinformatics, Volume 6 (2005) | DOI

[31] Siegmund, David Sequential analysis, Springer Series in Statistics, Springer-Verlag, New York, 1985 | MR | Zbl

[32] Srivastava, M. S.; Worsley, K. J. Likelihood ratio tests for a change in the multivariate normal mean, J. Amer. Statist. Assoc., Volume 81 (1986) no. 393, pp. 199-204 | MR | Zbl

[33] Talih, Makram; Hengartner, Nicolas Structural learning with time-varying components: tracking the cross-section of the financial time series, J. Royal Statist. Soc. B, Volume 67 (2005) no. 3, pp. 321-341 | MR | Zbl

[34] Tartakovsky, A.; Nikiforov, I.; Basseville, M. Sequential Analysis : Hypothesis Testing and Changepoint Detection, CRC Press, Taylor & Francis Group, 2014 | MR

[35] Tartakovsky, A.G.; Rozovskii, B.L.; Blazek, R.B.; Kim, H. A novel approach to detection of intrusions in computer networks via adaptive sequential and batch-sequential change-point detection methods, IEEE Trans. Signal Process., Volume 54 (2006) no. 9, pp. 3372 -3382 | Zbl

[36] Topchii, A.; Tyurin, Y.; Oja, H. Inference based on the affine invariant multivariate Mann-Whitney-Wilcoxon statistic, J. Nonparametr. Stat., Volume 15 (2003) no. 4-5, pp. 403-419 | MR | Zbl

[37] Vert, J.P.; Bleakley, K. Fast detection of multiple change-points shared by many signals using group LARS, Advances in Neural Information Processing Systems 23 (2010)

[38] van der Vaart, A. W. Asymptotic statistics, Cambridge University Press, 1998, xvi+443 pages | MR | Zbl

[39] Wei, L. J.; Lachin, J. M. Two-sample asymptotically distribution-free tests for incomplete multivariate observations, J. Amer. Statist. Assoc., Volume 79 (1984) no. 387, pp. 653-661 | MR | Zbl