Algorithms for unimodal segmentation with applications to unimodality detection

Niina Haiminen*, Aristides Gionis, Kari Laasonen

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

3 Citations (Scopus)

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 methods for testing if a sequence behaves unimodally or not. The methods include segmentation error comparisons, permutation testing, and a BIC-based scoring scheme. Our experimental evaluation shows that our algorithms and the proposed unimodality tests give very intuitive results, for both real-valued and binary data.

Original languageEnglish
Pages (from-to)39-57
Number of pages19
JournalKnowledge and Information Systems
Volume14
Issue number1
DOIs
Publication statusPublished - Jan 2008
MoE publication typeA1 Journal article-refereed

Keywords

  • Algorithms
  • BIC
  • Binary data
  • Regression
  • Segmentation
  • Unimodal

Fingerprint

Dive into the research topics of 'Algorithms for unimodal segmentation with applications to unimodality detection'. Together they form a unique fingerprint.

Cite this