MML inference of decision graphs with multi-way joins

Jing P Tan, David L Dowe

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

    15 Citations (Scopus)


    A decision tree is a comprehensible representation that has been widely used in many machine learning domains. But in the area of supervised learning, decision trees have their limitations. Two notable problems are those of replication and fragmentation. One way of solving these problems is to introduce decision graphs, a generalization of the decision tree, which address the above problems by allowing for disjunctions, or joins. While various decision graph systems are available, all of these systems impose some forms of restriction on the proposed representations, often leading to either a new redundancy or the original redundancy not being removed. In this paper, we propose an unrestricted representation called the decision graph with multi-way joins, which has improved representative power and is able to use training data efficiently. An algorithm to infer these decision graphs with multi-way joins using the Minimum Message Length (MML) principle is also introduced. On both real-world and artificial data with only discrete attributes (including at least five UCI data-sets), and in terms of both “right”/“wrong” classification accuracy and I.J. Good’s logarithm of probability “bit-costing” predictive accuracy, our novel multi-way join decision graph program significantly out-performs both C4.5 and C5.0. Our program also out-performs the Oliver and Wallace binary join decision graph program on the only data-set available for comparison.
    Original languageEnglish
    Title of host publicationAI 2002: Advances in Artificial Intelligence
    Subtitle of host publication15th Australian Joint Conference on Artificial Intelligence Canberra, Australia, December 2-6, 2002 Proceedings
    EditorsBob McKay, John Slaney
    Place of PublicationBerlin Germany
    Number of pages12
    ISBN (Print)3540001972
    Publication statusPublished - 2002
    EventAustralasian Joint Conference on Artificial Intelligence 2002 - Canberra, Australia
    Duration: 2 Dec 20026 Dec 2002
    Conference number: 15th (Proceedings)

    Publication series

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


    ConferenceAustralasian Joint Conference on Artificial Intelligence 2002
    Abbreviated titleAI 2002
    Internet address

    Cite this