Aggregating time partitions

ABSTRACT

Partitions of sequential data exist either per se or as a result of sequence segmentation algorithms. It is often the case that the same timeline is partitioned in many different ways. For example, different 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.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Mining Sequential Patterns, Proceedings of the Eleventh International Conference on Data Engineering, p.3-14, March 06-10, 1995
• 2: Nir Ailon , Moses Charikar , Alantha Newman, Aggregating inconsistent information: ranking and clustering, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060692]
• 3: ANDERSON, E. C., AND NOVEMBRE, J. Finding haplotype block boundaries by using the minimum-description-length principle. American Journal of Human Genetics 73 (2003).
• 4: Richard Bellman, On the approximation of curves by line segments using dynamic programming, Communications of the ACM, v.4 n.6, p.284, June 1961 [doi>10.1145/366573.366611]
• 5: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 6: Michael Collins , Robert E. Schapire , Yoram Singer, Logistic Regression, AdaBoost and Bregman Distances, Machine Learning, v.48 n.1-3, p.253-285, 2002 [doi>10.1023/A:1013912006537]
• 7: DALY, M. J., RIOUX, J. D., SCHAFFNER, S. F., HUDSON,T. J., AND LANDER, E. S. High-resolution haplotype structure in the human genome. Nature Genetics 29 (2001), 229--232.
• 8: Cynthia Dwork , Ravi Kumar , Moni Naor , D. Sivakumar, Rank aggregation methods for the Web, Proceedings of the 10th international conference on World Wide Web, p.613-622, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372165]
• 9: EAGLE, N. Machine perception and learning of complex social systems. PhD Thesis, Program in Media Arts and Sciences, Massachusetts Institute of Technology (2005).
• 10: Ronald Fagin , Ravi Kumar , Mohammad Mahdian , D. Sivakumar , Erik Vee, Comparing and aggregating rankings with ties, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055568]
• 11: FAN, W., AND STOLFO, S. J. Ensemble-based adaptive intrusion detection. In SDM (2002).
• 12: Ana L. N. Fred , Anil K. Jain, Combining Multiple Clusterings Using Evidence Accumulation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.27 n.6, p.835-850, June 2005 [doi>10.1109/TPAMI.2005.113]
• 13: Yoav Freund , Raj Iyer , Robert E. Schapire , Yoram Singer, An efficient boosting algorithm for combining preferences, The Journal of Machine Learning Research, 4, p.933-969, 12/1/2003
• 14: Aristides Gionis , Heikki Mannila, Finding recurrent sources in sequences, Proceedings of the seventh annual international conference on Research in computational molecular biology, p.123-130, April 10-14, 2003, Berlin, Germany [doi>10.1145/640075.640091]
• 15: Aristides Gionis , Heikki Mannila , Panayiotis Tsaparas, Clustering Aggregation, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.341-352, April 05-08, 2005 [doi>10.1109/ICDE.2005.34]
• 16: Sudipto Guha , Nick Koudas , Kyuseok Shim, Data-streams and histograms, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.471-475, July 2001, Hersonissos, Greece [doi>10.1145/380752.380841]
• 17: Dan Gusfield, An Overview of Haplotyping via Perfect Phylogeny: Theory, Algorithms and Programs, Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence, p..18, November 03-05, 2003
• 18: Robert Gwadera , Mikhail J. Atallah , Wojciech Szpankowski, Reliable detection of episodes in event sequences, Knowledge and Information Systems, v.7 n.4, p.415-437, May 2005 [doi>10.1007/s10115-004-0174-5]
• 19: Johan Himberg , Kalle Korpiaho , Heikki Mannila , Johanna Tikanmäki , Hannu Toivonen, Time Series Segmentation for Context Recognition in Mobile Devices, Proceedings of the 2001 IEEE International Conference on Data Mining, p.203-210, November 29-December 02, 2001
• 20: JOHNSON, N., KOTZ, Z., AND BALAKRISHNAN, N. Discrete multivariate distributions. John Wiley & Sons, 1997.
• 21: Eamonn J. Keogh , Selina Chu , David Hart , Michael J. Pazzani, An Online Algorithm for Segmenting Time Series, Proceedings of the 2001 IEEE International Conference on Data Mining, p.289-296, November 29-December 02, 2001
• 22: Jon Kleinberg, Bursty and Hierarchical Structure in Streams, Data Mining and Knowledge Discovery, v.7 n.4, p.373-397, October 2003 [doi>10.1023/A:1024940629314]
• 23: KOIVISTO, M., PEROLA, M., VARILO, T., ET AL. An MDL method for finding haplotype blocks and for estimating the strength of haplotype block boundaries. In Pacific Symposium on Biocomputing (2003), pp. 502--513.
• 24: Terran Lane , Carla E. Brodley, Temporal sequence learning and data reduction for anomaly detection, ACM Transactions on Information and System Security (TISSEC), v.2 n.3, p.295-331, Aug. 1999 [doi>10.1145/322510.322526]
• 25: Tilman Lange , Joachim M. Buhmann, Combining partitions by probabilistic label aggregation, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081890]
• 26: Wenke Lee , Salvatore J. Stolfo, A framework for constructing features and models for intrusion detection systems, ACM Transactions on Information and System Security (TISSEC), v.3 n.4, p.227-261, Nov. 2000 [doi>10.1145/382912.382914]
• 27: Wentian Li, DNA segmentation as a model selection process, Proceedings of the fifth annual international conference on Computational biology, p.204-210, April 22-25, 2001, Montreal, Quebec, Canada [doi>10.1145/369133.369202]
• 28: Yingjiu Li , Ningning Wu , Sean Wang , Sushil Jajodia, Enhancing profiles for anomaly detection using time granularities, Journal of Computer Security, v.10 n.1-2, p.137-157, 2002
• 29: Heikki Mannila , Hannu Toivonen , A. Inkeri Verkamo, Discovery of Frequent Episodes in Event Sequences, Data Mining and Knowledge Discovery, v.1 n.3, p.259-289, 1997 [doi>10.1023/A:1009748302351]
• 30: PATIL, N., BERNO, A. J., HINDS, D. A., ET AL. Blocks of limited haplotype diversity revealed by high-resolution scanning of human chromosome 21. Science 294 (2001),1669--70.
• 31: Yossi Rubner , Carlo Tomasi , Leonidas J. Guibas, The Earth Mover's Distance as a Metric for Image Retrieval, International Journal of Computer Vision, v.40 n.2, p.99-121, Nov. 2000 [doi>10.1023/A:1026543900054]
• 32: SALMENKIVI, M., KERE, J., AND MANNILA, H. Genome segmentation using piecewise constant intensity models and reversible jump MCMC. In Proceedings of the European Conference on Computational Biology (2002), pp. 211--218.
• 33: Alexander Strehl , Joydeep Ghosh, Cluster ensembles --- a knowledge reuse framework for combining multiple partitions, The Journal of Machine Learning Research, 3, p.583-617, 3/1/2003
• 34: TERZI, E., AND TSAPARAS, P. Efficient algorithms for sequence segmentation. In SDM (2006), p. To appear.
• 35: ZHANG, K., CHENG, M., CHEN, T., WATERMAN, M.,AND SUN, F. A dynamic programming algorithm for haplotype block partitioning. PNAS 99 (2002), 7335--7339.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Time series analysis

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Experimentation, Theory