Receive a 20% Discount on All Purchases Directly Through IGI Global's Online Bookstore.

Additionally, libraries can receive an extra 5% discount. Learn More

Additionally, libraries can receive an extra 5% discount. Learn More

Parvathi Chundi (University of Nebraska at Omaha, USA) and Daniel J. Rosenkrantz (University of Albany, SUNY, USA)

Copyright: © 2009
|Pages: 6

DOI: 10.4018/978-1-60566-010-3.ch267

Chapter Preview

TopA time series is simply a sequence of data points. In a segmentation of a given time series, one or more consecutive data points are combined into a single *segment* and represented by a single data point or a model for the data points in the segment. Given a time series *T* of *n* data points, segmentation of *T* results in a sequence of *m* segments, where each segment represents one or more consecutive data points in *T*. The number of segments *m* is typically much less than *n*. The input to a given instance of the segmentation problem is usually a time series and an upper bound on the number of segments.

Since the data points in a segment are represented by a single point or model, there is usually some error in the representation. Formally, the segmentation problem can be defined as follows. Given time series *T* and integer *m,* find a minimum error segmentation of *T* consisting of at most *m* segments. A specific version of this problem depends on the form of the data and how the segmentation error is defined. There are several approaches in the literature for addressing the segmentation problem. An *optimum* solution for the segmentation problem can be found by a dynamic programming based approach. (Duncan & Bryant, 1996; Gionis & Mannila, 2005; Himberg, Korpiaho, Mannila, Tikanmaki & Toivonen, 2001). A dynamic programming algorithm for solving this optimization problem runs in *O(n ^{2}m)* time, and so may not be practical for long time series with thousands of data points. There are more efficient heuristics that can be used to construct a segmentation of a given time series. However, these heuristics generally produce a suboptimal segmentation (Himberg, Korpiaho, Mannila, Tikanmaki & Toivonen, 2001; Keogh, Chu, Hart & Pazzani, 2004). There are also Bayesian based, fuzzy clustering, and genetic algorithm approaches to the segmentation problem (Oliver & Forbes, 1997; Abonyi, Feil, Nemeth, & Arva, 2005; Tseng, Chen, Chen & Hong, 2006). Methods have also been developed where a time series is segmented by converting it into a sequence of discrete symbols (Chung, Fu, Ng & Luk, 2004).

Search this Book:

Reset

Copyright © 1988-2019, IGI Global - All Rights Reserved