Uniform histograms for change detection in multivariate data

We address change-detection problems in the challenging conditions where data are multivariate and no a priori information or experimental evidence suggests a specific family of distributions to match stationary data. In such nonparametric settings, one typically resorts to computing an empirical model for the distribution of stationary data in the form of histograms. We here analyze two ways for building histograms in the change-detection context. In particular, we consider histograms following a uniformity criterion: uniformity in the volume and uniformity in the density. In the former case the input domain is divided into a regular grid, while in the latter the input domain is adaptively partitioned to yield subsets having the same probability to contain stationary data. For both histograms we discuss nonparametric monitoring procedures which implement likelihood-based and distance-based approaches to detect changes in the distribution. In our experiments, performed both on synthetic and real-world datasets, we show that the combination of uniform density histograms and distance-based approaches achieves the best change-detection performance.