Algorithms for unimodal segmentation with applications to unimodality detection

作     者：Haiminen, Niina Gionis, Aristides Laasonen, Kari 

作者机构：Univ Helsinki Helsinki Inst Informat Technol BRU Dept Comp Sci FIN-00014 Helsinki Finland 

出 版 物：《KNOWLEDGE AND INFORMATION SYSTEMS》 (知识和信息系统季刊)

年 卷 期：2008年第14卷第1期

页      面：39-57页

核心收录：

学科分类：0711[理学-系统科学] 07[理学] 08[工学] 070105[理学-运筹学与控制论] 081101[工学-控制理论与控制工程] 0701[理学-数学] 071101[理学-系统理论] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：unimodal segmentation regression algorithms BIC binary data 

摘      要：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.