|
Title
|
|
|
|
Fast sequence segmentation using log-linear models
| |
|
Author
|
|
|
|
| |
|
Abstract
|
|
|
|
| Sequence segmentation is a well-studied problem, where given a sequence of elements, an integer K, and some measure of homogeneity, the task is to split the sequence into K contiguous segments that are maximally homogeneous. A classic approach to find the optimal solution is by using a dynamic program. Unfortunately, the execution time of this program is quadratic with respect to the length of the input sequence. This makes the algorithm slow for a sequence of non-trivial length. In this paper we study segmentations whose measure of goodness is based on log-linear models, a rich family that contains many of the standard distributions. We present a theoretical result allowing us to prune many suboptimal segmentations. Using this result, we modify the standard dynamic program for 1D log-linear models, and by doing so reduce the computational time. We demonstrate empirically, that this approach can significantly reduce the computational burden of finding the optimal segmentation. |
| |
|
Language
|
|
|
|
English
| |
|
Source (journal)
|
|
|
|
Data mining and knowledge discovery. - Boston, Mass., 1997, currens
| |
|
Publication
|
|
|
|
Boston, Mass.
:
2013
| |
|
ISSN
|
|
|
|
1384-5810
[print]
1573-756X
[online]
| |
|
DOI
|
|
|
|
10.1007/S10618-012-0301-Y
| |
|
Volume/pages
|
|
|
|
27
:3
(2013)
, p. 421-441
| |
|
ISI
|
|
|
|
000322454200007
| |
|
Full text (Publisher's DOI)
|
|
|
|
| |
|
Full text (publisher's version - intranet only)
|
|
|
|
| |
|