An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation

  1. (PDF, 427 KB)
AuthorSearch for: ; Search for: ; Search for:
ConferenceIEEE International Conference on Data Mining (ICDM), November 27-30, 2005., New Orleans, Louisiana, USA
AbstractMonotonicity is a simple yet significant qualitative characteristic. We consider the problem of segmenting an array in up to K segments. We want segments to be as monotonic as possible and to alternate signs. We propose a quality metric for this problem, present an optimal linear time algorithm based on novel formalism, and compare experimentally its performance to a linear time top-down regression algorithm. We show that our algorithm is faster and more accurate. Applications include pattern recognition and qualitative modeling.<br /><br />Note: A detailed version of this paper is available by contacting one of the NRC authors.
Publication date
AffiliationNRC Institute for Information Technology; National Research Council Canada
Peer reviewedNo
NRC number48277
NPARC number5763338
Export citationExport as RIS
Report a correctionReport a correction
Record identifier67ba23e4-431c-4a75-9ad7-475f28c1d1a7
Record created2009-03-29
Record modified2016-05-09
Bookmark and share
  • Share this page with Facebook (Opens in a new window)
  • Share this page with Twitter (Opens in a new window)
  • Share this page with Google+ (Opens in a new window)
  • Share this page with Delicious (Opens in a new window)