Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes

Azimkhon Ostonov; Mikhail Moshkov

doi:10.1007/978-3-031-50959-9_7

Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes

Azimkhon Ostonov^*, Mikhail Moshkov

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

Decision rules and decision trees are studied intensively in rough set theory. The following questions seem to be important for this theory: relations between decision trees and decision rule systems, and dependence of the complexity of decision trees and decision rule systems on the complexity of the set of attributes attached to columns of the decision table. In this paper, instead of decision rule systems we study nondeterministic decision trees that can be considered as representations of decision rule systems. We consider classes of decision tables with many-valued decisions (multi-label decision tables) closed relative to removal of attributes (columns) and changing sets of decisions assigned to rows. For tables from an arbitrary closed class, we study functions that characterize the dependence in the worst case of the minimum complexity of deterministic and nondeterministic decision trees on the complexity of the set of attributes attached to columns. We enumerate all types of behavior of these functions. We also study the dependence in the worst case of the minimum complexity of deterministic decision trees on the minimum complexity of nondeterministic decision trees. This study leads to understanding of the nontrivial relationships between deterministic decision trees and systems of decision rules represented by nondeterministic decision trees.

Original language	English (US)
Title of host publication	Rough Sets - International Joint Conference, IJCRS 2023, Proceedings
Editors	Andrea Campagner, Oliver Urs Lenz, Shuyin Xia, Dominik Ślęzak, Jarosław Wąs, JingTao Yao
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	89-104
Number of pages	16
ISBN (Print)	9783031509582
DOIs	https://doi.org/10.1007/978-3-031-50959-9_7
State	Published - 2023
Event	International Joint Conference on Rough Sets, IJCRS 2023 - Krakow, Poland Duration: Oct 5 2023 → Oct 8 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14481 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	International Joint Conference on Rough Sets, IJCRS 2023
Country/Territory	Poland
City	Krakow
Period	10/5/23 → 10/8/23

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.

Keywords

Closed classes of decision tables
Decision tables with many-valued decisions
Deterministic decision trees
Nondeterministic decision trees

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-50959-9_7

Cite this

Ostonov, A., & Moshkov, M. (2023). Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes. In A. Campagner, O. Urs Lenz, S. Xia, D. Ślęzak, J. Wąs, & J. Yao (Eds.), Rough Sets - International Joint Conference, IJCRS 2023, Proceedings (pp. 89-104). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14481 LNAI). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-50959-9_7

Ostonov, Azimkhon ; Moshkov, Mikhail. / Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes. Rough Sets - International Joint Conference, IJCRS 2023, Proceedings. editor / Andrea Campagner ; Oliver Urs Lenz ; Shuyin Xia ; Dominik Ślęzak ; Jarosław Wąs ; JingTao Yao. Springer Science and Business Media Deutschland GmbH, 2023. pp. 89-104 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{85413a4e0a4c4c11a3571ce9a474358d,

title = "Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes",

abstract = "Decision rules and decision trees are studied intensively in rough set theory. The following questions seem to be important for this theory: relations between decision trees and decision rule systems, and dependence of the complexity of decision trees and decision rule systems on the complexity of the set of attributes attached to columns of the decision table. In this paper, instead of decision rule systems we study nondeterministic decision trees that can be considered as representations of decision rule systems. We consider classes of decision tables with many-valued decisions (multi-label decision tables) closed relative to removal of attributes (columns) and changing sets of decisions assigned to rows. For tables from an arbitrary closed class, we study functions that characterize the dependence in the worst case of the minimum complexity of deterministic and nondeterministic decision trees on the complexity of the set of attributes attached to columns. We enumerate all types of behavior of these functions. We also study the dependence in the worst case of the minimum complexity of deterministic decision trees on the minimum complexity of nondeterministic decision trees. This study leads to understanding of the nontrivial relationships between deterministic decision trees and systems of decision rules represented by nondeterministic decision trees.",

keywords = "Closed classes of decision tables, Decision tables with many-valued decisions, Deterministic decision trees, Nondeterministic decision trees",

author = "Azimkhon Ostonov and Mikhail Moshkov",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.; International Joint Conference on Rough Sets, IJCRS 2023 ; Conference date: 05-10-2023 Through 08-10-2023",

year = "2023",

doi = "10.1007/978-3-031-50959-9_7",

language = "English (US)",

isbn = "9783031509582",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "89--104",

editor = "Andrea Campagner and {Urs Lenz}, Oliver and Shuyin Xia and Dominik {\'S}l{\c e}zak and Jaros{\l}aw W{\c a}s and JingTao Yao",

booktitle = "Rough Sets - International Joint Conference, IJCRS 2023, Proceedings",

address = "Germany",

}

Ostonov, A & Moshkov, M 2023, Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes. in A Campagner, O Urs Lenz, S Xia, D Ślęzak, J Wąs & J Yao (eds), Rough Sets - International Joint Conference, IJCRS 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14481 LNAI, Springer Science and Business Media Deutschland GmbH, pp. 89-104, International Joint Conference on Rough Sets, IJCRS 2023, Krakow, Poland, 10/5/23. https://doi.org/10.1007/978-3-031-50959-9_7

Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes. / Ostonov, Azimkhon ; Moshkov, Mikhail.
Rough Sets - International Joint Conference, IJCRS 2023, Proceedings. ed. / Andrea Campagner; Oliver Urs Lenz; Shuyin Xia; Dominik Ślęzak; Jarosław Wąs; JingTao Yao. Springer Science and Business Media Deutschland GmbH, 2023. p. 89-104 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14481 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes

AU - Ostonov, Azimkhon

AU - Moshkov, Mikhail

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.

PY - 2023

Y1 - 2023

N2 - Decision rules and decision trees are studied intensively in rough set theory. The following questions seem to be important for this theory: relations between decision trees and decision rule systems, and dependence of the complexity of decision trees and decision rule systems on the complexity of the set of attributes attached to columns of the decision table. In this paper, instead of decision rule systems we study nondeterministic decision trees that can be considered as representations of decision rule systems. We consider classes of decision tables with many-valued decisions (multi-label decision tables) closed relative to removal of attributes (columns) and changing sets of decisions assigned to rows. For tables from an arbitrary closed class, we study functions that characterize the dependence in the worst case of the minimum complexity of deterministic and nondeterministic decision trees on the complexity of the set of attributes attached to columns. We enumerate all types of behavior of these functions. We also study the dependence in the worst case of the minimum complexity of deterministic decision trees on the minimum complexity of nondeterministic decision trees. This study leads to understanding of the nontrivial relationships between deterministic decision trees and systems of decision rules represented by nondeterministic decision trees.

AB - Decision rules and decision trees are studied intensively in rough set theory. The following questions seem to be important for this theory: relations between decision trees and decision rule systems, and dependence of the complexity of decision trees and decision rule systems on the complexity of the set of attributes attached to columns of the decision table. In this paper, instead of decision rule systems we study nondeterministic decision trees that can be considered as representations of decision rule systems. We consider classes of decision tables with many-valued decisions (multi-label decision tables) closed relative to removal of attributes (columns) and changing sets of decisions assigned to rows. For tables from an arbitrary closed class, we study functions that characterize the dependence in the worst case of the minimum complexity of deterministic and nondeterministic decision trees on the complexity of the set of attributes attached to columns. We enumerate all types of behavior of these functions. We also study the dependence in the worst case of the minimum complexity of deterministic decision trees on the minimum complexity of nondeterministic decision trees. This study leads to understanding of the nontrivial relationships between deterministic decision trees and systems of decision rules represented by nondeterministic decision trees.

KW - Closed classes of decision tables

KW - Decision tables with many-valued decisions

KW - Deterministic decision trees

KW - Nondeterministic decision trees

UR - http://www.scopus.com/inward/record.url?scp=85181984993&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-50959-9_7

DO - 10.1007/978-3-031-50959-9_7

M3 - Conference contribution

AN - SCOPUS:85181984993

SN - 9783031509582

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 89

EP - 104

BT - Rough Sets - International Joint Conference, IJCRS 2023, Proceedings

A2 - Campagner, Andrea

A2 - Urs Lenz, Oliver

A2 - Xia, Shuyin

A2 - Ślęzak, Dominik

A2 - Wąs, Jarosław

A2 - Yao, JingTao

PB - Springer Science and Business Media Deutschland GmbH

T2 - International Joint Conference on Rough Sets, IJCRS 2023

Y2 - 5 October 2023 through 8 October 2023

ER -

Ostonov A , Moshkov M. Deterministic and Nondeterministic Decision Trees for Decision Tables with Many-Valued Decisions from Closed Classes. In Campagner A, Urs Lenz O, Xia S, Ślęzak D, Wąs J, Yao J, editors, Rough Sets - International Joint Conference, IJCRS 2023, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. p. 89-104. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-50959-9_7