Minimum message length grouping of ordered data

Leigh J Fitzgibbon, Lloyd Allison, David L Dowe

    Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

    20 Citations (Scopus)


    Explicit segmentation is the partitioning of data into homogeneous regions by specifying cut-points. W. D. Fisher (1958) gave an early example of explicit segmentation based on the minimisation of squared error. Fisher called this the grouping problem and came up with a polynomial time Dynamic Programming Algorithm (DPA). Oliver, Baxter and colleagues (1996, 1997, 1998) have applied the informationtheoretic Minimum Message Length (MML) principle to explicit segmentation. They have derived formulas for specifying cut-points imprecisely and have empirically shown their criterion to be superior to other segmentation methods (AIC, MDL and BIC). We use a simple MML criterion and Fisher’s DPA to perform numerical Bayesian (summing and) integration (using message lengths) over the cut-point location parameters. This gives an estimate of the number of segments, which we then use to estimate the cut-point positions and segment parameters by minimising the MML criterion. This is shown to have lower Kullback-Leibler distances on generated data.
    Original languageEnglish
    Title of host publicationAlgorithmic Learning Theory
    Subtitle of host publication11th International Conference, ALT 2000 Sydney, Australia, December 11-13, 2000 Proceedings
    EditorsHiroki Arimura, Sanjay Jain, Arun Sharma
    Place of PublicationBerlin Germany
    Number of pages15
    ISBN (Print)3540412379
    Publication statusPublished - 2000
    EventAlgorithmic Learning Theory 2000 - Sydney, Australia
    Duration: 11 Dec 200013 Dec 2000
    Conference number: 11th (Proceedings)

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743


    ConferenceAlgorithmic Learning Theory 2000
    Abbreviated titleALT 2000
    Internet address

    Cite this