Minimizing Number of Nodes in Decision Trees with Hypotheses

Mohammad Azad; Igor Chikalov; Shahid Hussain; Mikhail Moshkov

doi:10.1016/j.procs.2021.08.024

Minimizing Number of Nodes in Decision Trees with Hypotheses

Mohammad Azad, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

In this paper, we consider decision trees that use both conventional queries based on one attribute each and queries based on hypotheses about values of all attributes. This approach is similar to one studied in exact learning, where membership and equivalence queries are considered. We propose dynamic programming algorithms for the minimization of the number of nodes in such decision trees and discuss results of computer experiments.

Original language	English (US)
Pages (from-to)	232-240
Number of pages	9
Journal	Procedia Computer Science
Volume	192
DOIs	https://doi.org/10.1016/j.procs.2021.08.024
State	Published - 2021

Bibliographical note

KAUST Repository Item: Exported on 2021-10-04
Acknowledgements: Research reported in this publication was supported by King Abdullah University of Science and Technology (KAUST). The authors are greatly indebted to anonymous reviewers for useful comments and suggestions.

Access to Document

10.1016/j.procs.2021.08.024

https://repository.kaust.edu.sa/bitstream/10754/672059/1/1-s2.0-S1877050921015118-main.pdf

Cite this

@article{248fdedbef214080bbbd6e2c1e496fc7,

title = "Minimizing Number of Nodes in Decision Trees with Hypotheses",

abstract = "In this paper, we consider decision trees that use both conventional queries based on one attribute each and queries based on hypotheses about values of all attributes. This approach is similar to one studied in exact learning, where membership and equivalence queries are considered. We propose dynamic programming algorithms for the minimization of the number of nodes in such decision trees and discuss results of computer experiments.",

author = "Mohammad Azad and Igor Chikalov and Shahid Hussain and Mikhail Moshkov",

note = "KAUST Repository Item: Exported on 2021-10-04 Acknowledgements: Research reported in this publication was supported by King Abdullah University of Science and Technology (KAUST). The authors are greatly indebted to anonymous reviewers for useful comments and suggestions.",

year = "2021",

doi = "10.1016/j.procs.2021.08.024",

language = "English (US)",

volume = "192",

pages = "232--240",

journal = "Procedia Computer Science",

issn = "1877-0509",

publisher = "Elsevier",

}

TY - JOUR

T1 - Minimizing Number of Nodes in Decision Trees with Hypotheses

AU - Azad, Mohammad

AU - Chikalov, Igor

AU - Hussain, Shahid

AU - Moshkov, Mikhail

N1 - KAUST Repository Item: Exported on 2021-10-04 Acknowledgements: Research reported in this publication was supported by King Abdullah University of Science and Technology (KAUST). The authors are greatly indebted to anonymous reviewers for useful comments and suggestions.

PY - 2021

Y1 - 2021

N2 - In this paper, we consider decision trees that use both conventional queries based on one attribute each and queries based on hypotheses about values of all attributes. This approach is similar to one studied in exact learning, where membership and equivalence queries are considered. We propose dynamic programming algorithms for the minimization of the number of nodes in such decision trees and discuss results of computer experiments.

AB - In this paper, we consider decision trees that use both conventional queries based on one attribute each and queries based on hypotheses about values of all attributes. This approach is similar to one studied in exact learning, where membership and equivalence queries are considered. We propose dynamic programming algorithms for the minimization of the number of nodes in such decision trees and discuss results of computer experiments.

UR - http://hdl.handle.net/10754/672059

UR - https://linkinghub.elsevier.com/retrieve/pii/S1877050921015118

U2 - 10.1016/j.procs.2021.08.024

DO - 10.1016/j.procs.2021.08.024

M3 - Article

SN - 1877-0509

VL - 192

SP - 232

EP - 240

JO - Procedia Computer Science

JF - Procedia Computer Science

ER -

Minimizing Number of Nodes in Decision Trees with Hypotheses

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this