Learning acyclic decision trees with functional dependency network and mdl genetic programming

Wing Ho SHUM, Kwong Sak LEUNG, Man Leung WONG

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

Abstract

One objective of data mining is to discover parent-child relationships among a set of variables in the domain. Moreover, showing parents' importance can further help to improve decision makings' quality. Bayesian Network (BN) is a useful model for multi-class problems and can illustrate parent-child relationships with no cycle. But it cannot show parents' importance. In contrast, decision trees state parents' importance clearly, for instance, the most important parent is put in the first level. However, decision trees are proposed for single-class problems only, when they are applied to multi-class ones, they are likely to produce cycles representing tautologie. In this paper, we propose to use MDL Genetic Programming (MDLGP) and Functional Dependency Network (FDN) to learn a set of acyclic decision trees [9]. The FDN is an extension of BN; it can handle all of discrete, continuous, interval and ordinal values; it guarantees to produce decision trees with no cycle; its learning search space is smaller than decision trees'; and it can represent higher-order relationships among variables. The MDLGP is a robust Genetic Programming (GP) proposed to learn the FDN. We also propose a method to derive acyclic decision trees from the FDN. The experimental results demonstrate that the proposed method can successfully discover the target decision trees, which have no cycle and have the accurate classification results.
Original languageEnglish
Title of host publicationProceedings of the International Multi-Conference on Computing in the Global Information Technology, ICCGI'06
PublisherInstitute of Electrical and Electronics Engineers
DOIs
Publication statusPublished - 1 Jan 2007

Fingerprint

Genetic programming
Decision trees
Bayesian networks
Data mining
Decision making

Bibliographical note

Paper presented at the International Multi-Conference on Computing in the Global Information Technology (ICCGI'06), 1-3 August 2006, Bucharest, Romania.
ISBN of the source publication: 9780769526294

Cite this

SHUM, W. H., LEUNG, K. S., & WONG, M. L. (2007). Learning acyclic decision trees with functional dependency network and mdl genetic programming. In Proceedings of the International Multi-Conference on Computing in the Global Information Technology, ICCGI'06 Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ICCGI.2006.46
SHUM, Wing Ho ; LEUNG, Kwong Sak ; WONG, Man Leung. / Learning acyclic decision trees with functional dependency network and mdl genetic programming. Proceedings of the International Multi-Conference on Computing in the Global Information Technology, ICCGI'06. Institute of Electrical and Electronics Engineers, 2007.
@inproceedings{b79b1451105640d3ac267c6953772dfa,
title = "Learning acyclic decision trees with functional dependency network and mdl genetic programming",
abstract = "One objective of data mining is to discover parent-child relationships among a set of variables in the domain. Moreover, showing parents' importance can further help to improve decision makings' quality. Bayesian Network (BN) is a useful model for multi-class problems and can illustrate parent-child relationships with no cycle. But it cannot show parents' importance. In contrast, decision trees state parents' importance clearly, for instance, the most important parent is put in the first level. However, decision trees are proposed for single-class problems only, when they are applied to multi-class ones, they are likely to produce cycles representing tautologie. In this paper, we propose to use MDL Genetic Programming (MDLGP) and Functional Dependency Network (FDN) to learn a set of acyclic decision trees [9]. The FDN is an extension of BN; it can handle all of discrete, continuous, interval and ordinal values; it guarantees to produce decision trees with no cycle; its learning search space is smaller than decision trees'; and it can represent higher-order relationships among variables. The MDLGP is a robust Genetic Programming (GP) proposed to learn the FDN. We also propose a method to derive acyclic decision trees from the FDN. The experimental results demonstrate that the proposed method can successfully discover the target decision trees, which have no cycle and have the accurate classification results.",
author = "SHUM, {Wing Ho} and LEUNG, {Kwong Sak} and WONG, {Man Leung}",
note = "Paper presented at the International Multi-Conference on Computing in the Global Information Technology (ICCGI'06), 1-3 August 2006, Bucharest, Romania. ISBN of the source publication: 9780769526294",
year = "2007",
month = "1",
day = "1",
doi = "10.1109/ICCGI.2006.46",
language = "English",
booktitle = "Proceedings of the International Multi-Conference on Computing in the Global Information Technology, ICCGI'06",
publisher = "Institute of Electrical and Electronics Engineers",

}

SHUM, WH, LEUNG, KS & WONG, ML 2007, Learning acyclic decision trees with functional dependency network and mdl genetic programming. in Proceedings of the International Multi-Conference on Computing in the Global Information Technology, ICCGI'06. Institute of Electrical and Electronics Engineers. https://doi.org/10.1109/ICCGI.2006.46

Learning acyclic decision trees with functional dependency network and mdl genetic programming. / SHUM, Wing Ho; LEUNG, Kwong Sak; WONG, Man Leung.

Proceedings of the International Multi-Conference on Computing in the Global Information Technology, ICCGI'06. Institute of Electrical and Electronics Engineers, 2007.

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

TY - GEN

T1 - Learning acyclic decision trees with functional dependency network and mdl genetic programming

AU - SHUM, Wing Ho

AU - LEUNG, Kwong Sak

AU - WONG, Man Leung

N1 - Paper presented at the International Multi-Conference on Computing in the Global Information Technology (ICCGI'06), 1-3 August 2006, Bucharest, Romania. ISBN of the source publication: 9780769526294

PY - 2007/1/1

Y1 - 2007/1/1

N2 - One objective of data mining is to discover parent-child relationships among a set of variables in the domain. Moreover, showing parents' importance can further help to improve decision makings' quality. Bayesian Network (BN) is a useful model for multi-class problems and can illustrate parent-child relationships with no cycle. But it cannot show parents' importance. In contrast, decision trees state parents' importance clearly, for instance, the most important parent is put in the first level. However, decision trees are proposed for single-class problems only, when they are applied to multi-class ones, they are likely to produce cycles representing tautologie. In this paper, we propose to use MDL Genetic Programming (MDLGP) and Functional Dependency Network (FDN) to learn a set of acyclic decision trees [9]. The FDN is an extension of BN; it can handle all of discrete, continuous, interval and ordinal values; it guarantees to produce decision trees with no cycle; its learning search space is smaller than decision trees'; and it can represent higher-order relationships among variables. The MDLGP is a robust Genetic Programming (GP) proposed to learn the FDN. We also propose a method to derive acyclic decision trees from the FDN. The experimental results demonstrate that the proposed method can successfully discover the target decision trees, which have no cycle and have the accurate classification results.

AB - One objective of data mining is to discover parent-child relationships among a set of variables in the domain. Moreover, showing parents' importance can further help to improve decision makings' quality. Bayesian Network (BN) is a useful model for multi-class problems and can illustrate parent-child relationships with no cycle. But it cannot show parents' importance. In contrast, decision trees state parents' importance clearly, for instance, the most important parent is put in the first level. However, decision trees are proposed for single-class problems only, when they are applied to multi-class ones, they are likely to produce cycles representing tautologie. In this paper, we propose to use MDL Genetic Programming (MDLGP) and Functional Dependency Network (FDN) to learn a set of acyclic decision trees [9]. The FDN is an extension of BN; it can handle all of discrete, continuous, interval and ordinal values; it guarantees to produce decision trees with no cycle; its learning search space is smaller than decision trees'; and it can represent higher-order relationships among variables. The MDLGP is a robust Genetic Programming (GP) proposed to learn the FDN. We also propose a method to derive acyclic decision trees from the FDN. The experimental results demonstrate that the proposed method can successfully discover the target decision trees, which have no cycle and have the accurate classification results.

UR - http://commons.ln.edu.hk/sw_master/7041

U2 - 10.1109/ICCGI.2006.46

DO - 10.1109/ICCGI.2006.46

M3 - Conference paper (refereed)

BT - Proceedings of the International Multi-Conference on Computing in the Global Information Technology, ICCGI'06

PB - Institute of Electrical and Electronics Engineers

ER -

SHUM WH, LEUNG KS, WONG ML. Learning acyclic decision trees with functional dependency network and mdl genetic programming. In Proceedings of the International Multi-Conference on Computing in the Global Information Technology, ICCGI'06. Institute of Electrical and Electronics Engineers. 2007 https://doi.org/10.1109/ICCGI.2006.46