Greedy Algorithm for Construction of Deterministic Decision Trees for Conventional Decision Tables from Closed Classes

Azimkhon Ostonov; Mikhail Moshkov

doi:10.1007/978-3-031-65665-1_6

Greedy Algorithm for Construction of Deterministic Decision Trees for Conventional Decision Tables 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

This paper examines specific classes of conventional decision tables (DTs) that are closed under operations of attribute (column) removal and decision modifications assigned to rows. For DTs belonging to any of these closed classes (CCs), we investigate a greedy algorithm that constructs a deterministic decision tree. We demonstrate that the number of steps performed by this algorithm is limited by twice the number of rows in the table. Furthermore, we compare the behavior of two functions. The first function describes the increase in the minimum complexity of a deterministic decision tree for a DT from the CC in the worst-case scenario, in relation to the complexity of the set of attributes associated with columns of the table. The second function characterizes the worst-case complexity growth of the deterministic decision tree constructed by the greedy algorithm for a DT from the CC, considering the growth of complexity of the set of attributes associated with columns of the table. We divide the entire collection of pairs consisting of a bounded complexity measure (BCM) and a CC into three subsets. For each subset, we establish lower and upper bounds for the second function based on the first function.

Original language	English (US)
Title of host publication	Rough Sets - International Joint Conference, IJCRS 2024, Proceedings
Editors	Mengjun Hu, Pawan Lingras, Chris Cornelis, Yan Zhang, Dominik Ślęzak, JingTao Yao
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	93-104
Number of pages	12
ISBN (Print)	9783031656644
DOIs	https://doi.org/10.1007/978-3-031-65665-1_6
State	Published - 2024
Event	International Joint Conference on Rough Sets, IJCRS 2024 - Halifax, Canada Duration: May 17 2024 → May 20 2024

Publication series

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

Conference

Conference	International Joint Conference on Rough Sets, IJCRS 2024
Country/Territory	Canada
City	Halifax
Period	05/17/24 → 05/20/24

Bibliographical note

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

Keywords

closed class of decision tables
deterministic decision tree
greedy algorithm

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-65665-1_6

Cite this

Ostonov, A., & Moshkov, M. (2024). Greedy Algorithm for Construction of Deterministic Decision Trees for Conventional Decision Tables from Closed Classes. In M. Hu, P. Lingras, C. Cornelis, Y. Zhang, D. Ślęzak, & J. Yao (Eds.), Rough Sets - International Joint Conference, IJCRS 2024, Proceedings (pp. 93-104). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14839 LNAI). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-65665-1_6

Ostonov, Azimkhon ; Moshkov, Mikhail. / Greedy Algorithm for Construction of Deterministic Decision Trees for Conventional Decision Tables from Closed Classes. Rough Sets - International Joint Conference, IJCRS 2024, Proceedings. editor / Mengjun Hu ; Pawan Lingras ; Chris Cornelis ; Yan Zhang ; Dominik Ślęzak ; JingTao Yao. Springer Science and Business Media Deutschland GmbH, 2024. pp. 93-104 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{370f69e92e4e48dfb311f1e564cc4279,

title = "Greedy Algorithm for Construction of Deterministic Decision Trees for Conventional Decision Tables from Closed Classes",

abstract = "This paper examines specific classes of conventional decision tables (DTs) that are closed under operations of attribute (column) removal and decision modifications assigned to rows. For DTs belonging to any of these closed classes (CCs), we investigate a greedy algorithm that constructs a deterministic decision tree. We demonstrate that the number of steps performed by this algorithm is limited by twice the number of rows in the table. Furthermore, we compare the behavior of two functions. The first function describes the increase in the minimum complexity of a deterministic decision tree for a DT from the CC in the worst-case scenario, in relation to the complexity of the set of attributes associated with columns of the table. The second function characterizes the worst-case complexity growth of the deterministic decision tree constructed by the greedy algorithm for a DT from the CC, considering the growth of complexity of the set of attributes associated with columns of the table. We divide the entire collection of pairs consisting of a bounded complexity measure (BCM) and a CC into three subsets. For each subset, we establish lower and upper bounds for the second function based on the first function.",

keywords = "closed class of decision tables, deterministic decision tree, greedy algorithm",

author = "Azimkhon Ostonov and Mikhail Moshkov",

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

year = "2024",

doi = "10.1007/978-3-031-65665-1\_6",

language = "English (US)",

isbn = "9783031656644",

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 = "93--104",

editor = "Mengjun Hu and Pawan Lingras and Chris Cornelis and Yan Zhang and Dominik {\'S}l{\c e}zak and JingTao Yao",

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

address = "Germany",

}

Ostonov, A & Moshkov, M 2024, Greedy Algorithm for Construction of Deterministic Decision Trees for Conventional Decision Tables from Closed Classes. in M Hu, P Lingras, C Cornelis, Y Zhang, D Ślęzak & J Yao (eds), Rough Sets - International Joint Conference, IJCRS 2024, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14839 LNAI, Springer Science and Business Media Deutschland GmbH, pp. 93-104, International Joint Conference on Rough Sets, IJCRS 2024, Halifax, Canada, 05/17/24. https://doi.org/10.1007/978-3-031-65665-1_6

Greedy Algorithm for Construction of Deterministic Decision Trees for Conventional Decision Tables from Closed Classes. / Ostonov, Azimkhon ; Moshkov, Mikhail.
Rough Sets - International Joint Conference, IJCRS 2024, Proceedings. ed. / Mengjun Hu; Pawan Lingras; Chris Cornelis; Yan Zhang; Dominik Ślęzak; JingTao Yao. Springer Science and Business Media Deutschland GmbH, 2024. p. 93-104 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14839 LNAI).

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

TY - GEN

T1 - Greedy Algorithm for Construction of Deterministic Decision Trees for Conventional Decision Tables from Closed Classes

AU - Ostonov, Azimkhon

AU - Moshkov, Mikhail

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

PY - 2024

Y1 - 2024

N2 - This paper examines specific classes of conventional decision tables (DTs) that are closed under operations of attribute (column) removal and decision modifications assigned to rows. For DTs belonging to any of these closed classes (CCs), we investigate a greedy algorithm that constructs a deterministic decision tree. We demonstrate that the number of steps performed by this algorithm is limited by twice the number of rows in the table. Furthermore, we compare the behavior of two functions. The first function describes the increase in the minimum complexity of a deterministic decision tree for a DT from the CC in the worst-case scenario, in relation to the complexity of the set of attributes associated with columns of the table. The second function characterizes the worst-case complexity growth of the deterministic decision tree constructed by the greedy algorithm for a DT from the CC, considering the growth of complexity of the set of attributes associated with columns of the table. We divide the entire collection of pairs consisting of a bounded complexity measure (BCM) and a CC into three subsets. For each subset, we establish lower and upper bounds for the second function based on the first function.

AB - This paper examines specific classes of conventional decision tables (DTs) that are closed under operations of attribute (column) removal and decision modifications assigned to rows. For DTs belonging to any of these closed classes (CCs), we investigate a greedy algorithm that constructs a deterministic decision tree. We demonstrate that the number of steps performed by this algorithm is limited by twice the number of rows in the table. Furthermore, we compare the behavior of two functions. The first function describes the increase in the minimum complexity of a deterministic decision tree for a DT from the CC in the worst-case scenario, in relation to the complexity of the set of attributes associated with columns of the table. The second function characterizes the worst-case complexity growth of the deterministic decision tree constructed by the greedy algorithm for a DT from the CC, considering the growth of complexity of the set of attributes associated with columns of the table. We divide the entire collection of pairs consisting of a bounded complexity measure (BCM) and a CC into three subsets. For each subset, we establish lower and upper bounds for the second function based on the first function.

KW - closed class of decision tables

KW - deterministic decision tree

KW - greedy algorithm

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

U2 - 10.1007/978-3-031-65665-1_6

DO - 10.1007/978-3-031-65665-1_6

M3 - Conference contribution

AN - SCOPUS:85200681906

SN - 9783031656644

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

SP - 93

EP - 104

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

A2 - Hu, Mengjun

A2 - Lingras, Pawan

A2 - Cornelis, Chris

A2 - Zhang, Yan

A2 - Ślęzak, Dominik

A2 - Yao, JingTao

PB - Springer Science and Business Media Deutschland GmbH

T2 - International Joint Conference on Rough Sets, IJCRS 2024

Y2 - 17 May 2024 through 20 May 2024

ER -

Ostonov A , Moshkov M. Greedy Algorithm for Construction of Deterministic Decision Trees for Conventional Decision Tables from Closed Classes. In Hu M, Lingras P, Cornelis C, Zhang Y, Ślęzak D, Yao J, editors, Rough Sets - International Joint Conference, IJCRS 2024, Proceedings. Springer Science and Business Media Deutschland GmbH. 2024. p. 93-104. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-65665-1_6