A survey of methods for time series change point detection
---
paper_title: Contrast and change mining

paper_content:

Because the world with its markets, innovations, and customers is changing faster than ever before, the key to survival for businesses is the ability to detect, assess, and respond to changing conditions timely and intelligently. Understanding changes and reacting to or acting upon them therefore become a strategic issue not only for companies but also in many other domains. The corresponding need for knowledge has been answered by data mining research by proposing a multitude of methods for analyzing different aspects of change. This article provides an overview of recent works on methods for change analysis, thereby focusing on contrast mining and change mining, the two emerging subfields of contemporary data mining research. © 2011 John Wiley & Sons, Inc. WIREs Data Mining Knowl Discov 2011 1 215–230 DOI: 10.1002/widm.27
---
paper_title: Boosting Classifiers for Drifting Concepts

paper_content:

In many real-world classification tasks, data arrives over time and the target concept to be learned from the data stream may change over time. Boosting methods are well-suited for learning from data streams, but do not address this concept drift problem. This paper proposes a boosting-like method to train a classifier ensemble from data streams that naturally adapts to concept drift. Moreover, it allows to quantify the drift in terms of its base learners. Similar as in regular boosting, examples are re-weighted to induce a diverse ensemble of base models. In order to handle drift, the proposed method continuously re-weights the ensemble members based on their performance on the most recent examples only. The proposed strategy adapts quickly to different kinds of concept drift. The algorithm is empirically shown to outperform learning algorithms that ignore concept drift. It performs no worse than advanced adaptive time window and example selection strategies that store all the data and are thus not suited for mining massive streams. The proposed algorithm has low computational costs.
---
paper_title: Inertial hidden markov models: modeling change in multivariate time series

paper_content:

Faced with the problem of characterizing systematic changes in multivariate time series in an unsupervised manner, we derive and test two methods of regularizing hidden Markov models for this task. Regularization on state transitions provides smooth transitioning among states, such that the sequences are split into broad, contiguous segments. Our methods are compared with a recent hierarchical Dirichlet process hidden Markov model (HDP-HMM) and a baseline standard hidden Markov model, of which the former suffers from poor performance on moderate-dimensional data and sensitivity to parameter settings, while the latter suffers from rapid state transitioning, over-segmentation and poor performance on a segmentation task involving human activity accelerometer data from the UCI Repository. The regularized methods developed here are able to perfectly characterize change of behavior in the human activity data for roughly half of the real-data test cases, with accuracy of 94% and low variation of information. In contrast to the HDP-HMM, our methods provide simple, drop-in replacements for standard hidden Markov model update rules, allowing standard expectation maximization (EM) algorithms to be used for learning.
---
paper_title: Unsupervised change analysis using supervised learning

paper_content:

We propose a formulation of a new problem, which we call change analysis, and a novel method for solving the problem. In contrast to the existing methods of change (or outlier) detection, the goal of change analysis goes beyond detecting whether or not any changes exist. Its ultimate goal is to find the explanation of the changes.While change analysis falls in the category of unsupervised learning in nature, we propose a novel approach based on supervised learning to achieve the goal. The key idea is to use a supervised classifier for interpreting the changes. A classifier should be able to discriminate between the two data sets if they actually come from two different data sources. In other words, we use a hypothetical label to train the supervised learner, and exploit the learner for interpreting the change. Experimental results using real data show the proposed approach is promising in change analysis as well as concept drift analysis.
---
paper_title: Adaptive Change Detection in Heart Rate Trend Monitoring in Anesthetized Children

paper_content:

The proposed algorithm is designed to detect changes in the heart rate trend signal which fits the dynamic linear model description. Based on this model, the interpatient and intraoperative variations are handled by estimating the noise covariances via an adaptive Kalman filter. An exponentially weighted moving average predictor switches between two different forgetting coefficients to allow the historical data to have a varying influence in prediction. The cumulative sum testing of the residuals identifies the change points online. The algorithm was tested on a substantial volume of real clinical data. Comparison of the proposed algorithm with Trigg's approach revealed that the algorithm performs more favorably with a shorter delay. The receiver operating characteristic curve analysis indicates that the algorithm outperformed the change detection by clinicians in real time
---
paper_title: Automatic change detection in multimodal serial MRI: application to multiple sclerosis lesion evolution

paper_content:

The automatic analysis of subtle changes between MRI scans is an important tool for assessing disease evolution over time. Manual labeling of evolutions in 3D data sets is tedious and error prone. Automatic change detection, however, remains a challenging image processing problem. A variety of MRI artifacts introduce a wide range of unrepresentative changes between images, making standard change detection methods unreliable. In this study we describe an automatic image processing system that addresses these issues. Registration errors and undesired anatomical deformations are compensated using a versatile multiresolution deformable image matching method that preserves significant changes at a given scale. A nonlinear intensity normalization method is associated with statistical hypothesis test methods to provide reliable change detection. Multimodal data is optionally exploited to reduce the false detection rate. The performance of the system was evaluated on a large database of 3D multimodal, MR images of patients suffering from relapsing remitting multiple sclerosis (MS). The method was assessed using receiver operating characteristics (ROC) analysis, and validated in a protocol involving two neurologists. The automatic system outperforms the human expert, detecting many lesion evolutions that are missed by the expert, including small, subtle changes.
---
paper_title: Online Bayesian change point detection algorithms for segmentation of epileptic activity

paper_content:

Epilepsy is a dynamic disease in which the brain transitions between different states. In this paper, we focus on the problem of identifying the time points, referred to as change points, where the transitions between these different states happen. A Bayesian change point detection algorithm that does not require the knowledge of the total number of states or the parameters of the probability distribution modeling the activity of epileptic brain in each of these states is developed in this paper. This algorithm works in online mode making it amenable for real-time monitoring. To reduce the quadratic complexity of this algorithm, an approximate algorithm with linear complexity in the number of data points is also developed. Finally, we use these algorithms on ECoG recordings of an epileptic patient to locate the change points and determine segments corresponding to different brain states.
---
paper_title: Change-Point Detection of Climate Time Series by Nonparametric Method

paper_content:

In one of the data mining techniques, change-point detection is of importance in evaluating time series measured in real world. For decades this technique has been developed as a nonlinear dynam- ics. We apply the method for detecting the change points, Singular Spectrum Transformation (SST), to the climate time series. To know where the struc- tures of climate data sets change can reveal a climate background. In this paper we discuss the structures of precipitation data in Kenya and Wrangel Island (Arctic land) by using the SST.
---
paper_title: Comparison of techniques for detection of discontinuities in temperature series

paper_content:

Several techniques for the detection of discontinuities in temperature series are evaluated. Eight homogenization techniques were compared using simulated datasets reproducing a vast range of possible situations. The simulated data represent homogeneous series and series having one or more steps. Although the majority of the techniques considered in this study perform very well, two methods seem to work slightly better than the others: the standard normal homogeneity test without trend, and the multiple linear regression technique. Both methods are distinctive because of their sensitivity concerning homogeneous series and their ability to detect one or several steps properly within an inhomogeneous series. Copyright © 2003 Environment Canada. Published by John Wiley & Sons, Ltd.
---
paper_title: Audio segmentation for speech recognition using segment features

paper_content:

Audio segmentation is an essential preprocessing step in several audio processing applications with a significant impact e.g. on speech recognition performance. We introduce a novel framework which combines the advantages of different well known segmentation methods. An automatically estimated log-linear segment model is used to determine the segmentation of an audio stream in a holistic way by a maximum a posteriori decoding strategy, instead of classifying change points locally. A comparison to other segmentation techniques in terms of speech recognition performance is presented, showing a promising segmentation quality of our approach.
---
paper_title: Bayesian on-line spectral change point detection: a soft computing approach for on-line ASR

paper_content:

Current automatic speech recognition (ASR) works in off-line mode and needs prior knowledge of the stationary or quasi-stationary test conditions for expected word recognition accuracy. These requirements limit the application of ASR for real-world applications where test conditions are highly non-stationary and are not known a priori. This paper presents an innovative frame dynamic rapid adaptation and noise compensation technique for tracking highly non-stationary noises and its application for on-line ASR. The proposed algorithm is based on a soft computing model using Bayesian on-line inference for spectral change point detection (BOSCPD) in unknown non-stationary noises. BOSCPD is tested with the MCRA noise tracking technique for on-line rapid environmental change learning in different non-stationary noise scenarios. The test results show that the proposed BOSCPD technique reduces the delay in spectral change point detection significantly compared to the baseline MCRA and its derivatives. The proposed BOSCPD soft computing model is tested for joint additive and channel distortions compensation (JAC)-based on-line ASR in unknown test conditions using non-stationary noisy speech samples from the Aurora 2 speech database. The simulation results for the on-line AR show significant improvement in recognition accuracy compared to the baseline Aurora 2 distributed speech recognition (DSR) in batch-mode.
---
paper_title: Image change detection algorithms: a systematic survey

paper_content:

Detecting regions of change in multiple images of the same scene taken at different times is of widespread interest due to a large number of applications in diverse disciplines, including remote sensing, surveillance, medical diagnosis and treatment, civil infrastructure, and underwater sensing. This paper presents a systematic survey of the common processing steps and core decision rules in modern change detection algorithms, including significance and hypothesis testing, predictive models, the shading model, and background modeling. We also discuss important preprocessing methods, approaches to enforcing the consistency of the change mask, and principles for evaluating and comparing the performance of change detection algorithms. It is hoped that our classification of algorithms into a relatively small number of categories will provide useful guidance to the algorithm designer.
---
paper_title: Scalable Time Series Change Detection for Biomass Monitoring Using Gaussian Process.

paper_content:

Biomass monitoring, specifically, detecting changes in the biomass or vegetation of a geographical region, is vital for studying the carbon cycle of the system and has significant implications in the context of understanding climate change and its impacts. Recently, several time series change detection methods have been proposed to identify land cover changes in temporal profiles (time series) of vegetation collected using remote sensing instruments. In this paper, we adapt Gaussian process regression to detect changes in such time series in an online fashion. While Gaussian process (GP) has been widely used as a kernel based learning method for regression and classification, their applicability to massive spatio-temporal data sets, such as remote sensing data, has been limited owing to the high computational costs involved. In our previous work we proposed an efficient Toeplitz matrix based solution for scalable GP parameter estimation. In this paper we apply these solutions to a GP based change detection algorithm. The proposed change detection algorithm requires a memory footprint which is linear in the length of the input time series and runs in time which is quadratic to the length of the input time series. Experimental results show that both serial and parallel implementations of our proposed method achieve significant speedups over the serial implementation. Finally, we demonstrate the effectiveness of the proposed change detection method in identifying changes in Normalized Difference Vegetation Index (NDVI) data. Increasing availability of high resolution remote sensing data has encouraged researchers to extract knowledge from these massive spatio-temporal data sets in order to solve different problems pertain- ing to our ecosystem. Land use land cover (LULC) monitoring, specifically identifying changes in land cover, is one such problem that has significant applications in detecting deforestation, crop ro- tation, urbanization, forest fires, and other such phenomenon. The knowledge about the land cover changes can then be used by policy makers to take important decisions regarding urban planning, natural resource management, water source management, etc. In this paper we focus on the problem of identifying changes in the biomass or vegetation in a geographical region. Biomass is defined as the mass of living biological organisms in a unit area. In the context of this study, we restrict our monitoring to plant (specifically crop) biomass over large geographic regions. In recent years biomass monitoring is increasingly becoming important, as biomass is a great source of renewable energy. Moreover, biomass monitoring is also important from the changing climate perspective, as changes in climate are reflected in the change in biomass, and vice versa. The knowledge about biomass changes over time across a geographical region can be used estimate quantitative biophysical parameters which can be incorporated into global climate models. The launch of NASA's Terra satellite in December of 1999, with the Moderate Resolution Imag- ing Spectroradiometer (MODIS) instrument aboard, introduced a new opportunity for terrestrial remote sensing. MODIS data sets represent a new and improved capability for terrestrial satel- lite remote sensing aimed at meeting the needs of global change research. With thirty-six spectral bands, seven designed for use in terrestrial application, MODIS provides daily coverage, of moderate spatial resolution, of most areas on the earth. Land cover products are available in 250m, 500m, or 1000m resolutions (17). MODIS land products are generally available within weeks or even days
---
paper_title: Graph-Based Change-Point Detection

paper_content:

We consider the testing and estimation of change-points -- locations where the distribution abruptly changes -- in a data sequence. A new approach, based on scan statistics utilizing graphs representing the similarity between observations, is proposed. The graph-based approach is non-parametric, and can be applied to any data set as long as an informative similarity measure on the sample space can be defined. Accurate analytic approximations to the significance of graph-based scan statistics for both the single change-point and the changed interval alternatives are provided. Simulations reveal that the new approach has better power than existing approaches when the dimension of the data is moderate to high. The new approach is illustrated on two applications: The determination of authorship of a classic novel, and the detection of change in a network over time.
---
paper_title: Multiple-change-point detection for high dimensional time series via sparsified binary segmentation

paper_content:

Time series segmentation, which is also known as multiple-change-point detection, is a well-established problem. However, few solutions have been designed specifically for high dimensional situations. Our interest is in segmenting the second-order structure of a high dimensional time series. In a generic step of a binary segmentation algorithm for multivariate time series, one natural solution is to combine cumulative sum statistics obtained from local periodograms and cross-periodograms of the components of the input time series. However, the standard 'maximum' and 'average' methods for doing so often fail in high dimensions when, for example, the change points are sparse across the panel or the cumulative sum statistics are spuriously large. We propose the sparsified binary segmentation algorithm which aggregates the cumulative sum statistics by adding only those that pass a certain threshold. This 'sparsifying' step reduces the influence of irrelevant noisy contributions, which is particularly beneficial in high dimensions. To show the consistency of sparsified binary segmentation, we introduce the multivariate locally stationary wavelet model for time series, which is a separate contribution of this work.
---
paper_title: Gaussian process for nonstationary time series prediction

paper_content:

In this paper, the problem of time series prediction is studied. A Bayesian procedure based on Gaussian process models using a nonstationary covariance function is proposed. Experiments proved the approach effectiveness with an excellent prediction and a good tracking. The conceptual simplicity, and good performance of Gaussian process models should make them very attractive for a wide range of problems.
---
paper_title: Estimation and comparison of multiple change-point models

paper_content:

This paper provides a new Bayesian approach for models with multiple change points. The centerpiece of the approach is a formulation of the change-point model in terms of a latent discrete state variable that indicates the regime from which a particular observation has been drawn. This state variable is specified to evolve according to a discrete-time discrete-state Markov process with the transition probabilities constrained so that the state variable can either stay at the current value or jump to the next higher value. This parameterization exactly reproduces the change point model. The model is estimated by Markov chain Monte Carlo methods using an approach that is based on Chib (1996). This methodology is quite valuable since it allows for the fitting of more complex change point models than was possible before. Methods for the computation of Bayes factors are also developed. All the techniques are illustrated using simulated and real data sets.
---
paper_title: Bayesian on-line spectral change point detection: a soft computing approach for on-line ASR

paper_content:

Current automatic speech recognition (ASR) works in off-line mode and needs prior knowledge of the stationary or quasi-stationary test conditions for expected word recognition accuracy. These requirements limit the application of ASR for real-world applications where test conditions are highly non-stationary and are not known a priori. This paper presents an innovative frame dynamic rapid adaptation and noise compensation technique for tracking highly non-stationary noises and its application for on-line ASR. The proposed algorithm is based on a soft computing model using Bayesian on-line inference for spectral change point detection (BOSCPD) in unknown non-stationary noises. BOSCPD is tested with the MCRA noise tracking technique for on-line rapid environmental change learning in different non-stationary noise scenarios. The test results show that the proposed BOSCPD technique reduces the delay in spectral change point detection significantly compared to the baseline MCRA and its derivatives. The proposed BOSCPD soft computing model is tested for joint additive and channel distortions compensation (JAC)-based on-line ASR in unknown test conditions using non-stationary noisy speech samples from the Aurora 2 speech database. The simulation results for the on-line AR show significant improvement in recognition accuracy compared to the baseline Aurora 2 distributed speech recognition (DSR) in batch-mode.
---
paper_title: Long-term temperature trends and variability on Spitsbergen: the extended Svalbard Airport temperature series, 1898–2012

paper_content:

One of the few long instrumental records available for the Arctic is the Svalbard Airport composite series that hitherto began in 1911, with observations made on Spitsbergen, the largest island in the Svalbard Archipelago. This record has now been extended to 1898 with the inclusion of observations made by hunting and scientific expeditions. Temperature has been observed almost continuously in Svalbard since 1898, although at different sites. It has therefore been possible to create one composite series for Svalbard Airport covering the period 1898–2012, and this valuable new record is presented here. The series reveals large temperature variability on Spitsbergen, with the early 20th century warming as one striking feature: an abrupt change from the cold 1910s to the local maxima of the 1930s and 1950s. With the inclusion of the new data it is possible to show that the 1910s were colder than the years at the start of the series. From the 1960s, temperatures have increased, so the present temperature level is significantly higher than at any earlier period in the instrumental history. For the entire period, and for all seasons, there are positive, statistically significant trends. Regarding the annual mean, the total trend is 2.6°C/century, whereas the largest trend is in spring, at 3.9°C/century. In Europe, it is the Svalbard Archipelago that has experienced the greatest temperature increase during the latest three decades. The composite series may be downloaded from the home page of the Norwegian Meteorological Institute and should be used with reference to the present article. Keywords: Arctic; homogenization; Spitsbergen; Svalbard; temperature records; temperature trends. (Published: 22 January 2014) To access the supplementary material for this article, please see Supplementary files in the column to the right (under Article Tools). Citation: Polar Research 2014, 33 , 21349, http://dx.doi.org/10.3402/polar.v33.21349
---
paper_title: Time Series Analysis and Its Applications

paper_content:

Characteristics of time series.- Time series regression and exploratory data analysis.- ARIMA models.- Spectral analysis and filtering.- Additional time domain topics.- State-space models.- Statistical methods in the frequency domain.
---
paper_title: Semi-supervised time series classification

paper_content:

The problem of time series classification has attracted great interest in the last decade. However current research assumes the existence of large amounts of labeled training data. In reality, such data may be very difficult or expensive to obtain. For example, it may require the time and expertise of cardiologists, space launch technicians, or other domain specialists. As in many other domains, there are often copious amounts of unlabeled data available. For example, the PhysioBank archive contains gigabytes of ECG data. In this work we propose a semi-supervised technique for building time series classifiers. While such algorithms are well known in text domains, we will show that special considerations must be made to make them both efficient and effective for the time series domain. We evaluate our work with a comprehensive set of experiments on diverse data sources including electrocardiograms, handwritten documents, and video datasets. The experimental results demonstrate that our approach requires only a handful of labeled examples to construct accurate classifiers.
---
paper_title: Clustering of time-series subsequences is meaningless: implications for previous and future research

paper_content:

Time series data is perhaps the most frequently encountered type of data examined by the data mining community. Clustering is perhaps the most frequently used data mining algorithm, being useful in it's own right as an exploratory technique, and also as a subroutine in more complex data mining algorithms such as rule discovery, indexing, summarization, anomaly detection, and classification. Given these two facts, it is hardly surprising that time series clustering has attracted much attention. The data to be clustered can be in one of two formats: many individual time series, or a single time series, from which individual time series are extracted with a sliding window. Given the recent explosion of interest in streaming data and online algorithms, the latter case has received much attention. We make an amazing claim. Clustering of streaming time series is completely meaningless. More concretely, clusters extracted from streaming time series are forced to obey a certain constraint that is pathologically unlikely to be satisfied by any dataset, and because of this, the clusters extracted by any clustering algorithm are essentially random. While this constraint can be intuitively demonstrated with a simple illustration and is simple to prove, it has never appeared in the literature. We can justify calling our claim surprising, since it invalidates the contribution of dozens of previously published papers. We will justify our claim with a theorem, illustrative examples, and a comprehensive set of experiments on reimplementations of previous work.
---
paper_title: Change-Point Detection in Time-Series Data by Relative Density-Ratio Estimation

paper_content:

The objective of change-point detection is to discover abrupt property changes lying behind time-series data. In this paper, we present a novel statistical change-point detection algorithm that is based on non-parametric divergence estimation between two retrospective segments. Our method uses the relative Pearson divergence as a divergence measure, and it is accurately and efficiently estimated by a method of direct density-ratio estimation. Through experiments on real-world human-activity sensing, speech, and Twitter datasets, we demonstrate the usefulness of the proposed method.
---
paper_title: Graph-Based Change-Point Detection

paper_content:

We consider the testing and estimation of change-points -- locations where the distribution abruptly changes -- in a data sequence. A new approach, based on scan statistics utilizing graphs representing the similarity between observations, is proposed. The graph-based approach is non-parametric, and can be applied to any data set as long as an informative similarity measure on the sample space can be defined. Accurate analytic approximations to the significance of graph-based scan statistics for both the single change-point and the changed interval alternatives are provided. Simulations reveal that the new approach has better power than existing approaches when the dimension of the data is moderate to high. The new approach is illustrated on two applications: The determination of authorship of a classic novel, and the detection of change in a network over time.
---
paper_title: A regularized kernel-based approach to unsupervised audio segmentation

paper_content:

We introduce a regularized kernel-based rule for unsupervised change detection based on a simpler version of the recently proposed kernel Fisher discriminant ratio. Compared to other kernel-based change detectors found in the literature, the proposed test statistic is easier to compute and has a known asymptotic distribution which can effectively be used to set the false alarm rate a priori. This technique is applied for segmenting tracks from TV shows, both for segmentation into semantically homogeneous sections (applause, movie, music, etc.) and for speaker diarization within the speech sections. On these tasks, the proposed approach outperforms other kernel-based tests and is competitive with a standard HMM-based supervised alternative.
---
paper_title: A novel changepoint detection algorithm

paper_content:

We propose an algorithm for simultaneously detecting and locating changepoints in a time series, and a framework for predicting the distribution of the next point in the series. The kernel of the algorithm is a system of equations that computes, for each index i, the probability that the last (most recent) change point occurred at i. We evaluate this algorithm by applying it to the change point detection problem and comparing it to the generalized likelihood ratio (GLR) algorithm. We find that our algorithm is as good as GLR, or better, over a wide range of scenarios, and that the advantage increases as the signal-to-noise ratio decreases.
---
paper_title: Graph-Based Change-Point Detection

paper_content:

We consider the testing and estimation of change-points -- locations where the distribution abruptly changes -- in a data sequence. A new approach, based on scan statistics utilizing graphs representing the similarity between observations, is proposed. The graph-based approach is non-parametric, and can be applied to any data set as long as an informative similarity measure on the sample space can be defined. Accurate analytic approximations to the significance of graph-based scan statistics for both the single change-point and the changed interval alternatives are provided. Simulations reveal that the new approach has better power than existing approaches when the dimension of the data is moderate to high. The new approach is illustrated on two applications: The determination of authorship of a classic novel, and the detection of change in a network over time.
---
paper_title: Optimal Composition of Real-Time Systems

paper_content:

Abstract Real-time systems are designed for environments in which the utility of actions is strongly time-dependent. Recent work by Dean, Horvitz and others has shown that anytime algorithms are a useful tool for real-time system design, since they allow computation time to be traded for decision quality. In order to construct complex systems, however, we need to be a ble to compose larger systems from smaller, reusable anytime modules. This paper addresses two basic problems associated with composition: how to ensure the interruptibility of the composed system; and how to allocate computation time optimally among the components. The first problem is solved by a simple and general construction that incurs only a small, constant penalty. The second is solved by an off-line compilation process. We show that the general compilation problem is NP-complete. However, efficient local compilation techniques, working on a single program structure at a time, yield glo bally optimal allocations for a large class of programs. We illustrate these results with two simple applications.
---
paper_title: Polishing the Right Apple: Anytime Classification Also Benefits Data Streams with Constant Arrival Times

paper_content:

Classification of items taken from data streams requires algorithms that operate in time sensitive and computationally constrained environments. Often, the available time for classification is not known a priori and may change as a consequence of external circumstances. Many traditional algorithms are unable to provide satisfactory performance while supporting the highly variable response times that exemplify such applications. In such contexts, anytime algorithms, which are amenable to trading time for accuracy, have been found to be exceptionally useful and constitute an area of increasing research activity. Previous techniques for improving anytime classification have generally been concerned with optimizing the probability of correctly classifying individual objects. However, as we shall see, serially optimizing the probability of correctly classifying individual objects K times, generally gives inferior results to batch optimizing the probability of correctly classifying K objects. In this work, we show that this simple observation can be exploited to improve overall classification performance by using an anytime framework to allocate resources among a set of objects buffered from a fast arriving stream. Our ideas are independent of object arrival behavior, and, perhaps unintuitively, even in data streams with constant arrival rates our technique exhibits a marked improvement in performance. The utility of our approach is demonstrated with extensive experimental evaluations conducted on a wide range of diverse datasets.
---
paper_title: Scalable machine learning for massive datasets: Fast summation algorithms

paper_content:

Huge data sets containing millions of training examples with a large number of attributes are relatively easy to gather. However one of the bottlenecks for successful inference is the computational complexity of machine learning algorithms. Most state-of-the-art nonparametric machine learning algorithms have a computational complexity of either O (N2) or O (N3), where N is the number of training examples. This has seriously restricted the use of massive data sets. The bottleneck computational primitive at the heart of various algorithms is the multiplication of a structured matrix with a vector, which we refer to as matrix-vector product (MVP) primitive. The goal of my thesis is to speedup up some of these MVP primitives by fast approximate algorithms that scale as O (N) and also provide high accuracy guarantees . I use ideas from computational physics, scientific computing, and computational geometry to design these algorithms. The proposed algorithms have been applied to speedup kernel density estimation, optimal bandwidth estimation, projection pursuit, Gaussian process regression, implicit surface fitting, and ranking.
---
paper_title: An Algorithm Based on Singular Spectrum Analysis for Change-Point Detection

paper_content:

This paper is devoted to application of the singular-spectrum analysis to sequential detection of changes in time series. An algorithm of change-point detection in time series, based on sequential application of the singular-spectrum analysis is developed and studied. The algorithm is applied to different data sets and extensively studied numerically. For specific models, several numerical approximations to the error probabilities and the power function of the algorithm are obtained. Numerical comparisons with other methods are given.
---
paper_title: Learning transportation mode from raw gps data for geographic applications on the web

paper_content:

Geographic information has spawned many novel Web applications where global positioning system (GPS) plays important roles in bridging the applications and end users. Learning knowledge from users' raw GPS data can provide rich context information for both geographic and mobile applications. However, so far, raw GPS data are still used directly without much understanding. In this paper, an approach based on supervised learning is proposed to automatically infer transportation mode from raw GPS data. The transportation mode, such as walking, driving, etc., implied in a user's GPS data can provide us valuable knowledge to understand the user. It also enables context-aware computing based on user's present transportation mode and design of an innovative user interface for Web users. Our approach consists of three parts: a change point-based segmentation method, an inference model and a post-processing algorithm based on conditional probability. The change point-based segmentation method was compared with two baselines including uniform duration based and uniform length based methods. Meanwhile, four different inference models including Decision Tree, Bayesian Net, Support Vector Machine (SVM) and Conditional Random Field (CRF) are studied in the experiments. We evaluated the approach using the GPS data collected by 45 users over six months period. As a result, beyond other two segmentation methods, the change point based method achieved a higher degree of accuracy in predicting transportation modes and detecting transitions between them. Decision Tree outperformed other inference models over the change point based segmentation method.
---
paper_title: Time Series Epenthesis: Clustering Time Series Streams Requires Ignoring Some Data

paper_content:

Given the pervasiveness of time series data in all human endeavors, and the ubiquity of clustering as a data mining application, it is somewhat surprising that the problem of time series clustering from a single stream remains largely unsolved. Most work on time series clustering considers the clustering of individual time series, e.g., gene expression profiles, individual heartbeats or individual gait cycles. The few attempts at clustering time series streams have been shown to be objectively incorrect in some cases, and in other cases shown to work only on the most contrived datasets by carefully adjusting a large set of parameters. In this work, we make two fundamental contributions. First, we show that the problem definition for time series clustering from streams currently used is inherently flawed, and a new definition is necessary. Second, we show that the Minimum Description Length (MDL) framework offers an efficient, effective and essentially parameter-free method for time series clustering. We show that our method produces objectively correct results on a wide variety of datasets from medicine, zoology and industrial process analyses.
---
paper_title: Using mobile phones to determine transportation modes

paper_content:

As mobile phones advance in functionality and capability, they are being used for more than just communication. Increasingly, these devices are being employed as instruments for introspection into habits and situations of individuals and communities. Many of the applications enabled by this new use of mobile phones rely on contextual information. The focus of this work is on one dimension of context, the transportation mode of an individual when outside. We create a convenient (no specific position and orientation setting) classification system that uses a mobile phone with a built-in GPS receiver and an accelerometer. The transportation modes identified include whether an individual is stationary, walking, running, biking, or in motorized transport. The overall classification system consists of a decision tree followed by a first-order discrete Hidden Markov Model and achieves an accuracy level of 93.6p when tested on a dataset obtained from sixteen individuals.
---
paper_title: Graph-Based Change-Point Detection

paper_content:

We consider the testing and estimation of change-points -- locations where the distribution abruptly changes -- in a data sequence. A new approach, based on scan statistics utilizing graphs representing the similarity between observations, is proposed. The graph-based approach is non-parametric, and can be applied to any data set as long as an informative similarity measure on the sample space can be defined. Accurate analytic approximations to the significance of graph-based scan statistics for both the single change-point and the changed interval alternatives are provided. Simulations reveal that the new approach has better power than existing approaches when the dimension of the data is moderate to high. The new approach is illustrated on two applications: The determination of authorship of a classic novel, and the detection of change in a network over time.
---
paper_title: Semi-supervised time series classification

paper_content:

The problem of time series classification has attracted great interest in the last decade. However current research assumes the existence of large amounts of labeled training data. In reality, such data may be very difficult or expensive to obtain. For example, it may require the time and expertise of cardiologists, space launch technicians, or other domain specialists. As in many other domains, there are often copious amounts of unlabeled data available. For example, the PhysioBank archive contains gigabytes of ECG data. In this work we propose a semi-supervised technique for building time series classifiers. While such algorithms are well known in text domains, we will show that special considerations must be made to make them both efficient and effective for the time series domain. We evaluate our work with a comprehensive set of experiments on diverse data sources including electrocardiograms, handwritten documents, and video datasets. The experimental results demonstrate that our approach requires only a handful of labeled examples to construct accurate classifiers.
---
paper_title: An online kernel change detection algorithm

paper_content:

A number of abrupt change detection methods have been proposed in the past, among which are efficient model-based techniques such as the Generalized Likelihood Ratio (GLR) test. We consider the case where no accurate nor tractable model can be found, using a model-free approach, called Kernel change detection (KCD). KCD compares two sets of descriptors extracted online from the signal at each time instant: The immediate past set and the immediate future set. Based on the soft margin single-class Support Vector Machine (SVM), we build a dissimilarity measure in feature space between those sets, without estimating densities as an intermediary step. This dissimilarity measure is shown to be asymptotically equivalent to the Fisher ratio in the Gaussian case. Implementation issues are addressed; in particular, the dissimilarity measure can be computed online in input space. Simulation results on both synthetic signals and real music signals show the efficiency of KCD.
---
paper_title: Understanding mobility based on GPS data

paper_content:

Both recognizing human behavior and understanding a user's mobility from sensor data are critical issues in ubiquitous computing systems. As a kind of user behavior, the transportation modes, such as walking, driving, etc., that a user takes, can enrich the user's mobility with informative knowledge and provide pervasive computing systems with more context information. In this paper, we propose an approach based on supervised learning to infer people's motion modes from their GPS logs. The contribution of this work lies in the following two aspects. On one hand, we identify a set of sophisticated features, which are more robust to traffic condition than those other researchers ever used. On the other hand, we propose a graph-based post-processing algorithm to further improve the inference performance. This algorithm considers both the commonsense constraint of real world and typical user behavior based on location in a probabilistic manner. Using the GPS logs collected by 65 people over a period of 10 months, we evaluated our approach via a set of experiments. As a result, based on the change point-based segmentation method and Decision Tree-based inference model, the new features brought an eight percent improvement in inference accuracy over previous result, and the graph-based post-processing achieve a further four percent enhancement.
---
paper_title: Comprehensive Context Recognizer Based on Multimodal Sensors in a Smartphone

paper_content:

Recent developments in smartphones have increased the processing capabilities and equipped these devices with a number of built-in multimodal sensors, including accelerometers, gyroscopes, GPS interfaces, Wi-Fi access, and proximity sensors. Despite the fact that numerous studies have investigated the development of user-context aware applications using smartphones, these applications are currently only able to recognize simple contexts using a single type of sensor. Therefore, in this work, we introduce a comprehensive approach for context aware applications that utilizes the multimodal sensors in smartphones. The proposed system is not only able to recognize different kinds of contexts with high accuracy, but it is also able to optimize the power consumption since power-hungry sensors can be activated or deactivated at appropriate times. Additionally, the system is able to recognize activities wherever the smartphone is on a human's body, even when the user is using the phone to make a phone call, manipulate applications, play games, or listen to music. Furthermore, we also present a novel feature selection algorithm for the accelerometer classification module. The proposed feature selection algorithm helps select good features and eliminates bad features, thereby improving the overall accuracy of the accelerometer classifier. Experimental results show that the proposed system can classify eight activities with an accuracy of 92.43%.
---
paper_title: Unsupervised change analysis using supervised learning

paper_content:

We propose a formulation of a new problem, which we call change analysis, and a novel method for solving the problem. In contrast to the existing methods of change (or outlier) detection, the goal of change analysis goes beyond detecting whether or not any changes exist. Its ultimate goal is to find the explanation of the changes.While change analysis falls in the category of unsupervised learning in nature, we propose a novel approach based on supervised learning to achieve the goal. The key idea is to use a supervised classifier for interpreting the changes. A classifier should be able to discriminate between the two data sets if they actually come from two different data sources. In other words, we use a hypothetical label to train the supervised learner, and exploit the learner for interpreting the change. Experimental results using real data show the proposed approach is promising in change analysis as well as concept drift analysis.
---
paper_title: Learning transportation mode from raw gps data for geographic applications on the web

paper_content:

Geographic information has spawned many novel Web applications where global positioning system (GPS) plays important roles in bridging the applications and end users. Learning knowledge from users' raw GPS data can provide rich context information for both geographic and mobile applications. However, so far, raw GPS data are still used directly without much understanding. In this paper, an approach based on supervised learning is proposed to automatically infer transportation mode from raw GPS data. The transportation mode, such as walking, driving, etc., implied in a user's GPS data can provide us valuable knowledge to understand the user. It also enables context-aware computing based on user's present transportation mode and design of an innovative user interface for Web users. Our approach consists of three parts: a change point-based segmentation method, an inference model and a post-processing algorithm based on conditional probability. The change point-based segmentation method was compared with two baselines including uniform duration based and uniform length based methods. Meanwhile, four different inference models including Decision Tree, Bayesian Net, Support Vector Machine (SVM) and Conditional Random Field (CRF) are studied in the experiments. We evaluated the approach using the GPS data collected by 45 users over six months period. As a result, beyond other two segmentation methods, the change point based method achieved a higher degree of accuracy in predicting transportation modes and detecting transitions between them. Decision Tree outperformed other inference models over the change point based segmentation method.
---
paper_title: Using mobile phones to determine transportation modes

paper_content:

As mobile phones advance in functionality and capability, they are being used for more than just communication. Increasingly, these devices are being employed as instruments for introspection into habits and situations of individuals and communities. Many of the applications enabled by this new use of mobile phones rely on contextual information. The focus of this work is on one dimension of context, the transportation mode of an individual when outside. We create a convenient (no specific position and orientation setting) classification system that uses a mobile phone with a built-in GPS receiver and an accelerometer. The transportation modes identified include whether an individual is stationary, walking, running, biking, or in motorized transport. The overall classification system consists of a decision tree followed by a first-order discrete Hidden Markov Model and achieves an accuracy level of 93.6p when tested on a dataset obtained from sixteen individuals.
---
paper_title: Change Detection in Streaming Multivariate Data Using Likelihood Detectors

paper_content:

Change detection in streaming data relies on a fast estimation of the probability that the data in two consecutive windows come from different distributions. Choosing the criterion is one of the multitude of questions that need to be addressed when designing a change detection procedure. This paper gives a log-likelihood justification for two well-known criteria for detecting change in streaming multidimensional data: Kullback-Leibler (K-L) distance and Hotelling's T-square test for equal means (H). We propose a semiparametric log-likelihood criterion (SPLL) for change detection. Compared to the existing log-likelihood change detectors, SPLL trades some theoretical rigor for computation simplicity. We examine SPLL together with K-L and H on detecting induced change on 30 real data sets. The criteria were compared using the area under the respective Receiver Operating Characteristic (ROC) curve (AUC). SPLL was found to be on the par with H and better than K-L for the nonnormalized data, and better than both on the normalized data.
---
paper_title: Change-Point Detection in Time-Series Data by Relative Density-Ratio Estimation

paper_content:

The objective of change-point detection is to discover abrupt property changes lying behind time-series data. In this paper, we present a novel statistical change-point detection algorithm that is based on non-parametric divergence estimation between two retrospective segments. Our method uses the relative Pearson divergence as a divergence measure, and it is accurately and efficiently estimated by a method of direct density-ratio estimation. Through experiments on real-world human-activity sensing, speech, and Twitter datasets, we demonstrate the usefulness of the proposed method.
---
paper_title: Cusum techniques for timeslot sequences with applications to network surveillance

paper_content:

We develop two cusum change-point detection algorithms for data network monitoring applications where numerous and various performance and reliability metrics are available to aid with the early identification of realized or impending failures. We confront three significant challenges with our cusum algorithms: (1) the need for nonparametric techniques so that a wide variety of metrics can be included in the monitoring process, (2) the need to handle time varying distributions for the metrics that reflect natural cycles in work load and traffic patterns, and (3) the need to be computationally efficient with the massive amounts of data that are available for processing. The only critical assumption we make when developing the algorithms is that suitably transformed observations within a defined timeslot structure are independent and identically distributed under normal operating conditions. To facilitate practical implementations of the algorithms, we present asymptotically valid thresholds. Our research was motivated by a real-world application and we use that context to guide the design of a simulation study that examines the sensitivity of the cusum algorithms.
---
paper_title: Multiple-change-point detection for high dimensional time series via sparsified binary segmentation

paper_content:

Time series segmentation, which is also known as multiple-change-point detection, is a well-established problem. However, few solutions have been designed specifically for high dimensional situations. Our interest is in segmenting the second-order structure of a high dimensional time series. In a generic step of a binary segmentation algorithm for multivariate time series, one natural solution is to combine cumulative sum statistics obtained from local periodograms and cross-periodograms of the components of the input time series. However, the standard 'maximum' and 'average' methods for doing so often fail in high dimensions when, for example, the change points are sparse across the panel or the cumulative sum statistics are spuriously large. We propose the sparsified binary segmentation algorithm which aggregates the cumulative sum statistics by adding only those that pass a certain threshold. This 'sparsifying' step reduces the influence of irrelevant noisy contributions, which is particularly beneficial in high dimensions. To show the consistency of sparsified binary segmentation, we introduce the multivariate locally stationary wavelet model for time series, which is a separate contribution of this work.
---
paper_title: A unifying framework for detecting outliers and change points from non-stationary time series data

paper_content:

We are concerned with the issues of outlier detection and change point detection from a data stream. In the area of data mining, there have been increased interest in these issues since the former is related to fraud detection, rare event discovery, etc., while the latter is related to event/trend by change detection, activity monitoring, etc. Specifically, it is important to consider the situation where the data source is non-stationary, since the nature of data source may change over time in real applications. Although in most previous work outlier detection and change point detection have not been related explicitly, this paper presents a unifying framework for dealing with both of them on the basis of the theory of on-line learning of non-stationary time series. In this framework a probabilistic model of the data source is incrementally learned using an on-line discounting learning algorithm, which can track the changing data source adaptively by forgetting the effect of past data gradually. Then the score for any given data is calculated to measure its deviation from the learned model, with a higher score indicating a high possibility of being an outlier. Further change points in a data stream are detected by applying this scoring method into a time series of moving averaged losses for prediction using the learned model. Specifically we develop an efficient algorithms for on-line discounting learning of auto-regression models from time series data, and demonstrate the validity of our framework through simulation and experimental applications to stock market data analysis.
---
paper_title: Break detection in the covariance structure of multivariate time series models

paper_content:

In this paper, we introduce an asymptotic test procedure to assess the stability of volatilities and cross-volatilites of linear and nonlinear multivariate time series models. The test is very flexible as it can be applied, for example, to many of the multivariate GARCH models established in the literature, and also works well in the case of high dimensionality of the underlying data. Since it is nonparametric, the procedure avoids the difficulties associated with parametric model selection, model fitting and parameter estimation. We provide the theoretical foundation for the test and demonstrate its applicability via a simulation study and an analysis of financial data. Extensions to multiple changes and the case of infinite fourth moments are also discussed.
---
paper_title: Change-Point Detection with Feature Selection in High-Dimensional Time-Series Data

paper_content:

Change-point detection is the problem of finding abrupt changes in time-series, and it is attracting a lot of attention in the artificial intelligence and data mining communities. In this paper, we present a supervised learning based change-point detection approach in which we use the separability of past and future data at time t (they are labeled as +1 and -1) as plausibility of change-points. Based on this framework, we propose a detection measure called the additive Hilbert-Schmidt Independence Criterion (aHSIC), which is defined as the weighted sum of the HSIC scores between features and its corresponding binary labels. Here, the HSIC is a kernel-based independence measure. A novel aspect of the aHSIC score is that it can incorporate feature selection during its detection measure estimation. More specifically, we first select features that are responsible for an abrupt change by using a supervised approach, and then compute the aHSIC score by employing the selected features. Thus, compared with traditional detection measures, our approach tends to be robust as regards noise features, and so the aHSIC is suitable for a use with high-dimensional time-series change-point detection problems. We demonstrate that the proposed change-point detection method is promising through extensive experiments on synthetic data sets and a real-world human activity data set.
---
paper_title: PCA Feature Extraction for Change Detection in Multidimensional Unlabeled Data

paper_content:

When classifiers are deployed in real-world applications, it is assumed that the distribution of the incoming data matches the distribution of the data used to train the classifier. This assumption is often incorrect, which necessitates some form of change detection or adaptive classification. While there has been a lot of work on change detection based on the classification error monitored over the course of the operation of the classifier, finding changes in multidimensional unlabeled data is still a challenge. Here, we propose to apply principal component analysis (PCA) for feature extraction prior to the change detection. Supported by a theoretical example, we argue that the components with the lowest variance should be retained as the extracted features because they are more likely to be affected by a change. We chose a recently proposed semiparametric log-likelihood change detection criterion that is sensitive to changes in both mean and variance of the multidimensional distribution. An experiment with 35 datasets and an illustration with a simple video segmentation demonstrate the advantage of using extracted features compared to raw data. Further analysis shows that feature extraction through PCA is beneficial, specifically for data with multiple balanced classes.
---
paper_title: Change Detection in Multivariate Datastreams: Likelihood and Detectability Loss

paper_content:

We address the problem of detecting changes in multivariate datastreams, and we investigate the intrinsic difficulty that change-detection methods have to face when the data dimension scales. In particular, we consider a general approach where changes are detected by comparing the distribution of the log-likelihood of the datastream over different time windows. Despite the fact that this approach constitutes the frame of several change-detection methods, its effectiveness when data dimension scales has never been investigated, which is indeed the goal of our paper. We show that the magnitude of the change can be naturally measured by the symmetric Kullback-Leibler divergence between the pre- and post-change distributions, and that the detectability of a change of a given magnitude worsens when the data dimension increases. This problem, which we refer to as \emph{detectability loss}, is due to the linear relationship between the variance of the log-likelihood and the data dimension. We analytically derive the detectability loss on Gaussian-distributed datastreams, and empirically demonstrate that this problem holds also on real-world datasets and that can be harmful even at low data-dimensions (say, 10).
---
paper_title: Change-Point Detection in Time-Series Data Based on Subspace Identification

paper_content:

In this paper, we propose series of algorithms for detecting change points in time-series data based on subspace identification, meaning a geometric approach for estimating linear state-space models behind time-series data. Our algorithms are derived from the principle that the subspace spanned by the columns of an observability matrix and the one spanned by the subsequences of time-series data are approximately equivalent. In this paper, we derive a batch-type algorithm applicable to ordinary time-series data, i.e. consisting of only output series, and then introduce the online version of the algorithm and the extension to be available with input-output time-series data. We illustrate the effectiveness of our algorithms with comparative experiments using some artificial and real datasets.
---
paper_title: Change-Point Detection in Time-Series Data by Relative Density-Ratio Estimation

paper_content:

The objective of change-point detection is to discover abrupt property changes lying behind time-series data. In this paper, we present a novel statistical change-point detection algorithm that is based on non-parametric divergence estimation between two retrospective segments. Our method uses the relative Pearson divergence as a divergence measure, and it is accurately and efficiently estimated by a method of direct density-ratio estimation. Through experiments on real-world human-activity sensing, speech, and Twitter datasets, we demonstrate the usefulness of the proposed method.
---
paper_title: Change-Point Detection of Climate Time Series by Nonparametric Method

paper_content:

In one of the data mining techniques, change-point detection is of importance in evaluating time series measured in real world. For decades this technique has been developed as a nonlinear dynam- ics. We apply the method for detecting the change points, Singular Spectrum Transformation (SST), to the climate time series. To know where the struc- tures of climate data sets change can reveal a climate background. In this paper we discuss the structures of precipitation data in Kenya and Wrangel Island (Arctic land) by using the SST.
---
paper_title: An Algorithm Based on Singular Spectrum Analysis for Change-Point Detection

paper_content:

This paper is devoted to application of the singular-spectrum analysis to sequential detection of changes in time series. An algorithm of change-point detection in time series, based on sequential application of the singular-spectrum analysis is developed and studied. The algorithm is applied to different data sets and extensively studied numerically. For specific models, several numerical approximations to the error probabilities and the power function of the algorithm are obtained. Numerical comparisons with other methods are given.
---
paper_title: Scalable Time Series Change Detection for Biomass Monitoring Using Gaussian Process.

paper_content:

Biomass monitoring, specifically, detecting changes in the biomass or vegetation of a geographical region, is vital for studying the carbon cycle of the system and has significant implications in the context of understanding climate change and its impacts. Recently, several time series change detection methods have been proposed to identify land cover changes in temporal profiles (time series) of vegetation collected using remote sensing instruments. In this paper, we adapt Gaussian process regression to detect changes in such time series in an online fashion. While Gaussian process (GP) has been widely used as a kernel based learning method for regression and classification, their applicability to massive spatio-temporal data sets, such as remote sensing data, has been limited owing to the high computational costs involved. In our previous work we proposed an efficient Toeplitz matrix based solution for scalable GP parameter estimation. In this paper we apply these solutions to a GP based change detection algorithm. The proposed change detection algorithm requires a memory footprint which is linear in the length of the input time series and runs in time which is quadratic to the length of the input time series. Experimental results show that both serial and parallel implementations of our proposed method achieve significant speedups over the serial implementation. Finally, we demonstrate the effectiveness of the proposed change detection method in identifying changes in Normalized Difference Vegetation Index (NDVI) data. Increasing availability of high resolution remote sensing data has encouraged researchers to extract knowledge from these massive spatio-temporal data sets in order to solve different problems pertain- ing to our ecosystem. Land use land cover (LULC) monitoring, specifically identifying changes in land cover, is one such problem that has significant applications in detecting deforestation, crop ro- tation, urbanization, forest fires, and other such phenomenon. The knowledge about the land cover changes can then be used by policy makers to take important decisions regarding urban planning, natural resource management, water source management, etc. In this paper we focus on the problem of identifying changes in the biomass or vegetation in a geographical region. Biomass is defined as the mass of living biological organisms in a unit area. In the context of this study, we restrict our monitoring to plant (specifically crop) biomass over large geographic regions. In recent years biomass monitoring is increasingly becoming important, as biomass is a great source of renewable energy. Moreover, biomass monitoring is also important from the changing climate perspective, as changes in climate are reflected in the change in biomass, and vice versa. The knowledge about biomass changes over time across a geographical region can be used estimate quantitative biophysical parameters which can be incorporated into global climate models. The launch of NASA's Terra satellite in December of 1999, with the Moderate Resolution Imag- ing Spectroradiometer (MODIS) instrument aboard, introduced a new opportunity for terrestrial remote sensing. MODIS data sets represent a new and improved capability for terrestrial satel- lite remote sensing aimed at meeting the needs of global change research. With thirty-six spectral bands, seven designed for use in terrestrial application, MODIS provides daily coverage, of moderate spatial resolution, of most areas on the earth. Land cover products are available in 250m, 500m, or 1000m resolutions (17). MODIS land products are generally available within weeks or even days
---
paper_title: Change-point detection for recursive Bayesian geoacoustic inversions

paper_content:

In order to carry out geoacoustic inversion in low signal-to-noise ratio (SNR) conditions, extended duration observations coupled with source and/or receiver motion may be necessary. As a result, change in the underlying model parameters due to time or space is anticipated. In this paper, an inversion method is proposed for cases when the model parameters change abruptly or slowly. A model parameter change-point detection method is developed to detect the change in the model parameters using the importance samples and corresponding weights that already are available from the recursive Bayesian inversion. If the model parameter change abruptly, a change-point will be detected and the inversion will restart with the pulse measurement after the changepoint. If the model parameters change gradually, the inversion (based on constant model parameters) may proceed until the accumulated model parameter mismatch is significant and triggers the detection of a change-point. These change-point detections form the heu...
---
paper_title: A Bayesian Analysis for Change Point Problems

paper_content:

A sequence of observations undergoes sudden changes at unknown times. We model the process by supposing that there is an underlying sequence of parameters partitioned into contiguous blocks of equal parameter values; the beginning of each block is said to be a change point. Observations are then assumed to be independent in different blocks given the sequence of parameters. In a Bayesian analysis it is necessary to give probability distributions to both the change points and the parameters. We use product partition models (Barry and Hartigan 1992), which assume that the probability of any partition is proportional to a product of prior cohesions, one for each block in the partition, and that given the blocks the parameters in different blocks have independent prior distributions. Given the observations a new product partition model holds, with posterior cohesions for the blocks and new independent block posterior distributions for parameters. The product model thus provides a convenient machinery for allo...
---
paper_title: Gaussian process for nonstationary time series prediction

paper_content:

In this paper, the problem of time series prediction is studied. A Bayesian procedure based on Gaussian process models using a nonstationary covariance function is proposed. Experiments proved the approach effectiveness with an excellent prediction and a good tracking. The conceptual simplicity, and good performance of Gaussian process models should make them very attractive for a wide range of problems.
---
paper_title: Gaussian Process Change Point Models

paper_content:

We combine Bayesian online change point detection with Gaussian processes to create a nonparametric time series model which can handle change points. The model can be used to locate change points in an online manner; and, unlike other Bayesian online change point detection algorithms, is applicable when temporal correlations in a regime are expected. We show three variations on how to apply Gaussian processes in the change point context, each with their own advantages. We present methods to reduce the computational burden of these models and demonstrate it on several real world data sets.
---
paper_title: Bayesian online changepoint detection to improve transparency in human-machine interaction systems

paper_content:

This paper discusses a way to improve transparency in human-machine interaction systems when no force sensors are available for both the human and the machine. In most cases, position-error based control with fixed proportional-derivative (PD) controllers provides poor transparency. We resolve this issue by utilizing a gain switching method, switching them to be high or low values in response to estimated force changes at the slave environment. Since the slave-environment forces change abruptly in real time, it is difficult to set the precise value of the threshold for these gain switching decisions. Moreover, the threshold value has to be observed and tuned in advance to utilize the gain switching approach. Thus, we adopt Bayesian online changepoint detection to detect the abrupt slave environment change. This changepoint detection is based on the Bayes' theorem which is typically used in probability and statistics applications to generate the posterior distribution of unknown parameters given both data and prior distribution. We then show experimental results which demonstrate the Bayesian online changepoint detection has the ability to discriminate both free motion and hard contact. Additionally, we incorporate the online changepoint detection in our proposed gain switching controller and show the superiority of our proposed controller via experiment.
---
paper_title: Estimation and comparison of multiple change-point models

paper_content:

This paper provides a new Bayesian approach for models with multiple change points. The centerpiece of the approach is a formulation of the change-point model in terms of a latent discrete state variable that indicates the regime from which a particular observation has been drawn. This state variable is specified to evolve according to a discrete-time discrete-state Markov process with the transition probabilities constrained so that the state variable can either stay at the current value or jump to the next higher value. This parameterization exactly reproduces the change point model. The model is estimated by Markov chain Monte Carlo methods using an approach that is based on Chib (1996). This methodology is quite valuable since it allows for the fitting of more complex change point models than was possible before. Methods for the computation of Bayes factors are also developed. All the techniques are illustrated using simulated and real data sets.
---
paper_title: Online Bayesian change point detection algorithms for segmentation of epileptic activity

paper_content:

Epilepsy is a dynamic disease in which the brain transitions between different states. In this paper, we focus on the problem of identifying the time points, referred to as change points, where the transitions between these different states happen. A Bayesian change point detection algorithm that does not require the knowledge of the total number of states or the parameters of the probability distribution modeling the activity of epileptic brain in each of these states is developed in this paper. This algorithm works in online mode making it amenable for real-time monitoring. To reduce the quadratic complexity of this algorithm, an approximate algorithm with linear complexity in the number of data points is also developed. Finally, we use these algorithms on ECoG recordings of an epileptic patient to locate the change points and determine segments corresponding to different brain states.
---
paper_title: Graph-Based Change-Point Detection

paper_content:

We consider the testing and estimation of change-points -- locations where the distribution abruptly changes -- in a data sequence. A new approach, based on scan statistics utilizing graphs representing the similarity between observations, is proposed. The graph-based approach is non-parametric, and can be applied to any data set as long as an informative similarity measure on the sample space can be defined. Accurate analytic approximations to the significance of graph-based scan statistics for both the single change-point and the changed interval alternatives are provided. Simulations reveal that the new approach has better power than existing approaches when the dimension of the data is moderate to high. The new approach is illustrated on two applications: The determination of authorship of a classic novel, and the detection of change in a network over time.
---
paper_title: A regularized kernel-based approach to unsupervised audio segmentation

paper_content:

We introduce a regularized kernel-based rule for unsupervised change detection based on a simpler version of the recently proposed kernel Fisher discriminant ratio. Compared to other kernel-based change detectors found in the literature, the proposed test statistic is easier to compute and has a known asymptotic distribution which can effectively be used to set the false alarm rate a priori. This technique is applied for segmenting tracks from TV shows, both for segmentation into semantically homogeneous sections (applause, movie, music, etc.) and for speaker diarization within the speech sections. On these tasks, the proposed approach outperforms other kernel-based tests and is competitive with a standard HMM-based supervised alternative.
---
paper_title: Kernel change-point analysis

paper_content:

We introduce a kernel-based method for change-point analysis within a sequence of temporal observations. Change-point analysis of an unlabelled sample of observations consists in, first, testing whether a change in the distribution occurs within the sample, and second, if a change occurs, estimating the change-point instant after which the distribution of the observations switches from one distribution to another different distribution. We propose a test statistic based upon the maximum kernel Fisher discriminant ratio as a measure of homogeneity between segments. We derive its limiting distribution under the null hypothesis (no change occurs), and establish the consistency under the alternative hypothesis (a change occurs). This allows to build a statistical hypothesis testing procedure for testing the presence of a change-point, with a prescribed false-alarm probability and detection probability tending to one in the large-sample setting. If a change actually occurs, the test statistic also yields an estimator of the change-point location. Promising experimental results in temporal segmentation of mental tasks from BCI data and pop song indexation are presented.
---
paper_title: Graph-Based Change-Point Detection

paper_content:

We consider the testing and estimation of change-points -- locations where the distribution abruptly changes -- in a data sequence. A new approach, based on scan statistics utilizing graphs representing the similarity between observations, is proposed. The graph-based approach is non-parametric, and can be applied to any data set as long as an informative similarity measure on the sample space can be defined. Accurate analytic approximations to the significance of graph-based scan statistics for both the single change-point and the changed interval alternatives are provided. Simulations reveal that the new approach has better power than existing approaches when the dimension of the data is moderate to high. The new approach is illustrated on two applications: The determination of authorship of a classic novel, and the detection of change in a network over time.
---
paper_title: Complex network from pseudoperiodic time series: topology versus dynamics.

paper_content:

We construct complex networks from pseudoperiodic time series, with each cycle represented by a single node in the network. We investigate the statistical properties of these networks for various time series and find that time series with different dynamics exhibit distinct topological structures. Specifically, noisy periodic signals correspond to random networks, and chaotic time series generate networks that exhibit small world and scale free features. We show that this distinction in topological structure results from the hierarchy of unstable periodic orbits embedded in the chaotic attractor. Standard measures of structure in complex networks can therefore be applied to distinguish different dynamic regimes in time series. Application to human electrocardiograms shows that such statistical properties are able to differentiate between the sinus rhythm cardiograms of healthy volunteers and those of coronary care patients.
---
paper_title: An exact distribution-free test comparing two multivariate distributions based on adjacency

paper_content:

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.
---
paper_title: From time series to complex networks: the visibility graph

paper_content:

In this work we present a simple and fast computational method, the visibility algorithm, that converts a time series into a graph. The constructed graph inherits several properties of the series in its structure. Thereby, periodic series convert into regular graphs, and random series do so into random graphs. Moreover, fractal series convert into scale-free networks, enhancing the fact that power law degree distributions are related to fractality, something highly discussed recently. Some remarkable examples and analytical tools are outlined in order to test the method's reliability. Many different measures, recently developed in the complex network theory, could by means of this new approach characterize time series from a new point of view.
---
paper_title: An online algorithm for segmenting time series

paper_content:

In recent years, there has been an explosion of interest in mining time-series databases. As with most computer science problems, representation of the data is the key to efficient and effective solutions. One of the most commonly used representations is piecewise linear approximation. This representation has been used by various researchers to support clustering, classification, indexing and association rule mining of time-series data. A variety of algorithms have been proposed to obtain this representation, with several algorithms having been independently rediscovered several times. In this paper, we undertake the first extensive review and empirical comparison of all proposed techniques. We show that all these algorithms have fatal flaws from a data-mining perspective. We introduce a novel algorithm that we empirically show to be superior to all others in the literature.
---
paper_title: Time Series Epenthesis: Clustering Time Series Streams Requires Ignoring Some Data

paper_content:

Given the pervasiveness of time series data in all human endeavors, and the ubiquity of clustering as a data mining application, it is somewhat surprising that the problem of time series clustering from a single stream remains largely unsolved. Most work on time series clustering considers the clustering of individual time series, e.g., gene expression profiles, individual heartbeats or individual gait cycles. The few attempts at clustering time series streams have been shown to be objectively incorrect in some cases, and in other cases shown to work only on the most contrived datasets by carefully adjusting a large set of parameters. In this work, we make two fundamental contributions. First, we show that the problem definition for time series clustering from streams currently used is inherently flawed, and a new definition is necessary. Second, we show that the Minimum Description Length (MDL) framework offers an efficient, effective and essentially parameter-free method for time series clustering. We show that our method produces objectively correct results on a wide variety of datasets from medicine, zoology and industrial process analyses.
---
paper_title: Clustering Time Series Using Unsupervised-Shapelets

paper_content:

Time series clustering has become an increasingly important research topic over the past decade. Most existing methods for time series clustering rely on distances calculated from the entire raw data using the Euclidean distance or Dynamic Time Warping distance as the distance measure. However, the presence of significant noise, dropouts, or extraneous data can greatly limit the accuracy of clustering in this domain. Moreover, for most real world problems, we cannot expect objects from the same class to be equal in length. As a consequence, most work on time series clustering only considers the clustering of individual time series "behaviors," e.g., individual heart beats or individual gait cycles, and contrives the time series in some way to make them all equal in length. However, contriving the data in such a way is often a harder problem than the clustering itself. In this work, we show that by using only some local patterns and deliberately ignoring the rest of the data, we can mitigate the above problems and cluster time series of different lengths, i.e., cluster one heartbeat with multiple heartbeats. To achieve this we exploit and extend a recently introduced concept in time series data mining called shapelets. Unlike existing work, our work demonstrates for the first time the unintuitive fact that shapelets can be learned from unlabeled time series. We show, with extensive empirical evaluation in diverse domains, that our method is more accurate than existing methods. Moreover, in addition to accurate clustering results, we show that our work also has the potential to give insights into the domains to which it is applied.
---
paper_title: Automated Change Detection and Reactive Clustering in Multivariate Streaming Data

paper_content:

Many automated systems need the capability of automatic change detection without the given detection threshold. This paper presents an automated change detection algorithm in streaming multivariate data. Two overlapping windows are used to quantify the changes. While a window is used as the reference window from which the clustering is created, the other called the current window captures the newly incoming data points. A newly incoming data point can be considered a change point if it is not a member of any cluster. As our clustering-based change detector does not require detection threshold, it is an automated detector. Based on this change detector, we propose a reactive clustering algorithm for streaming data. Our empirical results show that, our clustering-based change detector works well with multivariate streaming data. The detection accuracy depends on the number of clusters in the reference window, the window width.
---
paper_title: A Bayesian Approach to Concept Drift

paper_content:

To cope with concept drift, we placed a probability distribution over the location of the most-recent drift point. We used Bayesian model comparison to update this distribution from the predictions of models trained on blocks of consecutive observations and pruned potential drift points with low probability. We compare our approach to a non-probabilistic method for drift and a probabilistic method for change-point detection. In our experiments, our approach generally yielded improved accuracy and/or speed over these other methods.
---
paper_title: Concept Drift Detection Through Resampling

paper_content:

Detecting changes in data-streams is an important part of enhancing learning quality in dynamic environments. We devise a procedure for detecting concept drifts in data-streams that relies on analyzing the empirical loss of learning algorithms. Our method is based on obtaining statistics from the loss distribution by reusing the data multiple times via resampling. We present theoretical guarantees for the proposed procedure based on the stability of the underlying learning algorithms. Experimental results show that the method has high recall and precision, and performs well in the presence of noise.
---

Title: A Survey of Methods for Time Series Change Point Detection

Section 1: Introduction
Description 1: Introduce the significance of time series analysis and change point detection in various fields and provide motivating examples.

Section 2: Background
Description 2: Clarify the basic concepts related to change point detection, including definitions and problem formulation.

Section 3: Criteria
Description 3: Discuss the practical challenges in applying change point detection, such as online detection, scalability, algorithm constraints, and performance evaluation.

Section 4: Review
Description 4: Provide an overview of the main categories of change point detection algorithms, including both supervised and unsupervised methods.

Section 5: Supervised Methods
Description 5: Detail various supervised learning approaches used in change point detection, such as binary and multi-class classifiers.

Section 6: Unsupervised Methods
Description 6: Explore different unsupervised learning techniques applied to time series change point detection.

Section 7: Likelihood Ratio Methods
Description 7: Discuss methods that utilize likelihood ratios to compare probability distributions and identify change points.

Section 8: Subspace Model Methods
Description 8: Present approaches based on subspace modeling for analyzing changes in time series sequences.

Section 9: Probabilistic Methods
Description 9: Outline probabilistic techniques like Bayesian methods for change point detection.

Section 10: Kernel-Based Methods
Description 10: Describe kernel-based methods which employ test statistics to assess the homogeneity of data.

Section 11: Graph-Based Methods
Description 11: Introduce graph-based frameworks that apply two-sample tests on equivalent graphs to detect change points.

Section 12: Clustering Methods
Description 12: Explain clustering approaches that use techniques like sliding window and minimum description length for change point detection.

Section 13: Discussion and Comparison
Description 13: Compare and contrast the surveyed methods based on key criteria to help practitioners choose the most appropriate algorithm.

Section 14: Conclusions and Challenges for Future Work
Description 14: Summarize the state of change point detection research, identify challenges, and suggest directions for future research.