Aggregating time partitions
- 20 August 2006
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 347-356
- https://doi.org/10.1145/1150402.1150442
Abstract
Partitions of sequential data exist either per se or as a result of se- quence segmentation algorithms. It is often the case that the same timeline is partitioned in many different ways. For example, dif- ferent segmentation algorithms produce different partitions of the same underlying data points. In such cases, we are interested in producing an aggregate partition, i.e., a segmentation that agrees as much as possible with the input segmentations. Each partition is defined as a set of continuous non-overlapping segments of the timeline. We show that this problem can be solved optimally in polynomial time using dynamic programming. We also propose faster greedy heuristics that work well in practice. We experiment with our algorithms and we demonstrate their utility in clustering the behavior of mobile-phone users and combining the results of different segmentation algorithms on genomic sequences.Keywords
This publication has 24 references indexed in Scilit:
- Efficient algorithms for sequence segmentationPublished by Society for Industrial & Applied Mathematics (SIAM) ,2006
- Combining partitions by probabilistic label aggregationPublished by Association for Computing Machinery (ACM) ,2005
- Combining multiple clusterings using evidence accumulationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2005
- Reliable detection of episodes in event sequencesKnowledge and Information Systems, 2005
- A dynamic programming algorithm for haplotype block partitioningProceedings of the National Academy of Sciences, 2002
- Blocks of Limited Haplotype Diversity Revealed by High-Resolution Scanning of Human Chromosome 21Science, 2001
- A framework for constructing features and models for intrusion detection systemsACM Transactions on Information and System Security, 2000
- 10.1162/153244303321897735Applied Physics Letters, 2000
- Temporal sequence learning and data reduction for anomaly detectionACM Transactions on Information and System Security, 1999
- On the approximation of curves by line segments using dynamic programmingCommunications of the ACM, 1961