On the depth of decision trees over infinite 1-homogeneous binary information systems

Mikhail Moshkov

doi:10.1016/j.array.2021.100060

On the depth of decision trees over infinite 1-homogeneous binary information systems

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

Abstract

In this paper, we study decision trees, which solve problems defined over a specific subclass of infinite information systems, namely: 1-homogeneous binary information systems. It is proved that the minimum depth of a decision tree (defined as a function on the number of attributes in a problem’s description) grows – in the worst case – logarithmically or linearly for each information system in this class. We consider a number of examples of infinite 1-homogeneous binary information systems, including one closely related to the decision trees constructed by the CART algorithm.

Original language	English (US)
Pages (from-to)	100060
Journal	Array
DOIs	https://doi.org/10.1016/j.array.2021.100060
State	Published - Apr 2021

Bibliographical note

KAUST Repository Item: Exported on 2021-04-05
Acknowledgements: Research reported in this publication was supported by King Abdullah University of Science and Technology (KAUST). The author is thankful to Dr. Michal Mankowski for the helpful comments. The author gratefully acknowledges the useful suggestions of the anonymous reviewers.

Access to Document

10.1016/j.array.2021.100060

https://repository.kaust.edu.sa/bitstream/10754/668498/1/On%20the%20depth%20of_1-s2.0-S2590005621000084-main.pdf

Cite this

@article{f4953f2672b4460b98e2eacd972f73a6,

title = "On the depth of decision trees over infinite 1-homogeneous binary information systems",

abstract = "In this paper, we study decision trees, which solve problems defined over a specific subclass of infinite information systems, namely: 1-homogeneous binary information systems. It is proved that the minimum depth of a decision tree (defined as a function on the number of attributes in a problem{\textquoteright}s description) grows – in the worst case – logarithmically or linearly for each information system in this class. We consider a number of examples of infinite 1-homogeneous binary information systems, including one closely related to the decision trees constructed by the CART algorithm.",

author = "Mikhail Moshkov",

note = "KAUST Repository Item: Exported on 2021-04-05 Acknowledgements: Research reported in this publication was supported by King Abdullah University of Science and Technology (KAUST). The author is thankful to Dr. Michal Mankowski for the helpful comments. The author gratefully acknowledges the useful suggestions of the anonymous reviewers.",

year = "2021",

month = apr,

doi = "10.1016/j.array.2021.100060",

language = "English (US)",

pages = "100060",

journal = "Array",

issn = "2590-0056",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - On the depth of decision trees over infinite 1-homogeneous binary information systems

AU - Moshkov, Mikhail

N1 - KAUST Repository Item: Exported on 2021-04-05 Acknowledgements: Research reported in this publication was supported by King Abdullah University of Science and Technology (KAUST). The author is thankful to Dr. Michal Mankowski for the helpful comments. The author gratefully acknowledges the useful suggestions of the anonymous reviewers.

PY - 2021/4

Y1 - 2021/4

N2 - In this paper, we study decision trees, which solve problems defined over a specific subclass of infinite information systems, namely: 1-homogeneous binary information systems. It is proved that the minimum depth of a decision tree (defined as a function on the number of attributes in a problem’s description) grows – in the worst case – logarithmically or linearly for each information system in this class. We consider a number of examples of infinite 1-homogeneous binary information systems, including one closely related to the decision trees constructed by the CART algorithm.

AB - In this paper, we study decision trees, which solve problems defined over a specific subclass of infinite information systems, namely: 1-homogeneous binary information systems. It is proved that the minimum depth of a decision tree (defined as a function on the number of attributes in a problem’s description) grows – in the worst case – logarithmically or linearly for each information system in this class. We consider a number of examples of infinite 1-homogeneous binary information systems, including one closely related to the decision trees constructed by the CART algorithm.

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

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

U2 - 10.1016/j.array.2021.100060

DO - 10.1016/j.array.2021.100060

M3 - Article

SN - 2590-0056

SP - 100060

JO - Array

JF - Array

ER -

On the depth of decision trees over infinite 1-homogeneous binary information systems

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this