|
Published Articles >> Table of Contents >> Abstract
Fourth IEEE International Conference on Data Mining (ICDM'04)
pp. 106-113
Unimodal Segmentation of Sequences
Niina Haiminen, University of Helsinki, Finland
Aristides Gionis, University of Helsinki, Finland
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICDM.2004.10109
Send link to a friend
| 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.
|
 Additional Information
|
Citation:
Niina Haiminen, Aristides Gionis,
"Unimodal Segmentation of Sequences,"
icdm,
pp. 106-113,
Fourth IEEE International Conference on Data Mining (ICDM'04),
2004
|
|
