Browse Prior Art Database

A System and Method for Automatic Change Point Identification in Data Streams using Wavelet Transform Filters

IP.com Disclosure Number: IPCOM000029113D
Original Publication Date: 2004-Jun-16
Included in the Prior Art Database: 2004-Jun-16
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Abstract

There is a need for fast (real-time), reliable identification of changepoints in data streams with low-cost hardware requirements. Current methods are too expensive. This article describes a system consisting of a series of wavelet-based filters and with automatic normalization and thresholding to identify changepoints in (possibly noisy) data. The method for identifying changepoints used in the system is competitively accurate, faster (computationally less expensive) than currently available methods and has very little hardware requirements.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 1 of 2

A System and Method for Automatic Change Point Identification in Data Streams using Wavelet Transform Filters

There is a need for fast (real-time), reliable identification of changepoints in data streams with low-cost hardware requirements. Current methods are too expensive. This article describes a system consisting of a series of wavelet-based filters and with automatic normalization and thresholding to identify changepoints in (possibly noisy) data. The method for identifying changepoints used in the system is competitively accurate, faster (computationally less expensive) than currently available methods and has very little hardware requirements.

* Enter the body of your Invention Disclosure Publication below . You may include drawings and highlighting as appropriate .

Proposed below is a new method and system based on a series of wavelet transform filters to:
- automatically identify and remove small noise using normalization and derviative
(i.e., divided difference) computations to facilitate change point identification. - automatically computes and identifies change points in one-dimensional data using transforms of wavelets that have compact support, where the support is long enough to remove noise, but short enough to pinpoint changepoints.

The proposed method is more computationally efiicient, competitively accurate and significantly less expensive to implement than methods currently described in the literature (see, e.g., references [1], [2a,b,c] for singular spectrum methods, and [3a,b] for the CUSUM method). Although wavelet transform have been cited in academic studies (with scalogram pictures) to indicate where edges in a signal are present (see, e.g., references [4],[5]), wavelet-based automated systems to detect change points, have not been published. Inparticular, the success of the proposed system lies in the idea of using series of wavelet transform filters to smooth noise sufficiently before and after changepoint detection filters.

The proposed system assumes that some properties of the signal are known, for example:
(1) binary singals - signal is eiether "on" or "off".
(2) step-like functions
(3) step-like functions with noise
(4) curves (more gradual step-like functions)
(5) curves (more gradual step-like functions) with noise
(6) connected line segments
(7) connected line segments with noise

Depending on the signal type, a different series of filters are needed to identify change points, as described in examples 1&2.

Example 1: Identification of change points in binary, noise-free signals, step functions and/or connected line segments A signal is input into the system, and its 2-point Haar wavelet transform is computed. Edges correspond to where the wavelet transform takes on non-zero values. A wavelet with very short support suffi...