Title :
Unimodal segmentation of sequences
Author :
Haiminen, Niina ; Gionis, Aristides
Author_Institution :
Dept. of Comput. Sci., Helsinki Univ., Finland
Abstract :
We study the problem of segmenting a sequence into k pieces so that the resulting segmentation satisfies monotonicity or unimodality constraints. Unimodal functions can be used to model phenomena in which a measured variable first increases to a certain level and then decreases. We combine a well-known unimodal regression algorithm with a simple dynamic-programming approach to obtain an optimal quadratic-time algorithm for the problem of unimodal k-segmentation. In addition, we describe a more efficient greedy-merging heuristic that is experimentally shown to give solutions very close to the optimal. As a concrete application of our algorithms, we describe two methods for testing if a sequence behaves unimodally or not. Our experimental evaluation shows that our algorithms and the proposed unimodality tests give very intuitive results.
Keywords :
computational complexity; dynamic programming; greedy algorithms; heuristic programming; merging; regression analysis; sequences; dynamic programming; greedy-merging heuristic; monotonicity constraints; quadratic-time algorithm; unimodal functions; unimodal k-segmentation; unimodal regression algorithm; unimodal sequence segmentation; unimodality constraints; unimodality test; Computer science; Concrete; Data mining; Dynamic programming; Heuristic algorithms; Information technology; Polynomials; Statistical analysis; Statistical distributions; Testing;
Conference_Titel :
Data Mining, 2004. ICDM '04. Fourth IEEE International Conference on
Print_ISBN :
0-7695-2142-8
DOI :
10.1109/ICDM.2004.10109