Complexity of Transforming Decision Rule Systems into Decision Trees and Acyclic Decision Graphs

Kerven Durdymyradov; Mikhail Moshkov

doi:10.1007/978-981-97-5937-8_13

Complexity of Transforming Decision Rule Systems into Decision Trees and Acyclic Decision Graphs

Kerven Durdymyradov^*, Mikhail Moshkov

^*Corresponding author for this work

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

2 Scopus citations

Abstract

Decision trees and systems of decision rules are widely used as classifiers, as a means for knowledge representation, and as algorithms. They are among the most interpretable models for data analysis. The study of the relationships between these two models can be seen as an important task of computer science. Methods for transforming decision trees into systems of decision rules are simple and well-known. In this paper, we consider the inverse transformation problem, which is not trivial. We study the complexity of transforming decision rule systems into decision trees and acyclic decision graphs representing decision trees. Based on the obtained results, we can formulate the next stage of research: instead of constructing the entire decision tree, we will study polynomial time algorithms that simulate the work of the decision tree on a given tuple of attribute values.

Original language	English (US)
Title of host publication	Recent Challenges in Intelligent Information and Database Systems - 16th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2024, Proceedings
Editors	Ngoc Thanh Nguyen, Krystian Wojtkiewicz, Richard Chbeir, Yannis Manolopoulos, Hamido Fujita, Tzung-Pei Hong, Le Minh Nguyen
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	153-163
Number of pages	11
ISBN (Print)	9789819759361
DOIs	https://doi.org/10.1007/978-981-97-5937-8_13
State	Published - 2024
Event	16th Asian Conference on Intelligent Information and Database Systems , ACIIDS 2024 - Ras Al Khaimah, United Arab Emirates Duration: Apr 15 2024 → Apr 18 2024

Publication series

Name	Communications in Computer and Information Science
Volume	2144 CCIS
ISSN (Print)	1865-0929
ISSN (Electronic)	1865-0937

Conference

Conference	16th Asian Conference on Intelligent Information and Database Systems , ACIIDS 2024
Country/Territory	United Arab Emirates
City	Ras Al Khaimah
Period	04/15/24 → 04/18/24

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.

Keywords

Acyclic decision graphs
Decision rule systems
Decision trees

ASJC Scopus subject areas

General Computer Science
General Mathematics

Access to Document

10.1007/978-981-97-5937-8_13

Cite this

Durdymyradov, K., & Moshkov, M. (2024). Complexity of Transforming Decision Rule Systems into Decision Trees and Acyclic Decision Graphs. In N. T. Nguyen, K. Wojtkiewicz, R. Chbeir, Y. Manolopoulos, H. Fujita, T.-P. Hong, & L. M. Nguyen (Eds.), Recent Challenges in Intelligent Information and Database Systems - 16th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2024, Proceedings (pp. 153-163). (Communications in Computer and Information Science; Vol. 2144 CCIS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-981-97-5937-8_13

Durdymyradov, Kerven ; Moshkov, Mikhail. / Complexity of Transforming Decision Rule Systems into Decision Trees and Acyclic Decision Graphs. Recent Challenges in Intelligent Information and Database Systems - 16th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2024, Proceedings. editor / Ngoc Thanh Nguyen ; Krystian Wojtkiewicz ; Richard Chbeir ; Yannis Manolopoulos ; Hamido Fujita ; Tzung-Pei Hong ; Le Minh Nguyen. Springer Science and Business Media Deutschland GmbH, 2024. pp. 153-163 (Communications in Computer and Information Science).

@inproceedings{b090dcfcf08147ce80a12aed4b8816e2,

title = "Complexity of Transforming Decision Rule Systems into Decision Trees and Acyclic Decision Graphs",

abstract = "Decision trees and systems of decision rules are widely used as classifiers, as a means for knowledge representation, and as algorithms. They are among the most interpretable models for data analysis. The study of the relationships between these two models can be seen as an important task of computer science. Methods for transforming decision trees into systems of decision rules are simple and well-known. In this paper, we consider the inverse transformation problem, which is not trivial. We study the complexity of transforming decision rule systems into decision trees and acyclic decision graphs representing decision trees. Based on the obtained results, we can formulate the next stage of research: instead of constructing the entire decision tree, we will study polynomial time algorithms that simulate the work of the decision tree on a given tuple of attribute values.",

keywords = "Acyclic decision graphs, Decision rule systems, Decision trees",

author = "Kerven Durdymyradov and Mikhail Moshkov",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.; 16th Asian Conference on Intelligent Information and Database Systems , ACIIDS 2024 ; Conference date: 15-04-2024 Through 18-04-2024",

year = "2024",

doi = "10.1007/978-981-97-5937-8\_13",

language = "English (US)",

isbn = "9789819759361",

series = "Communications in Computer and Information Science",

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

pages = "153--163",

editor = "Nguyen, \{Ngoc Thanh\} and Krystian Wojtkiewicz and Richard Chbeir and Yannis Manolopoulos and Hamido Fujita and Tzung-Pei Hong and Nguyen, \{Le Minh\}",

booktitle = "Recent Challenges in Intelligent Information and Database Systems - 16th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2024, Proceedings",

address = "Germany",

}

Durdymyradov, K & Moshkov, M 2024, Complexity of Transforming Decision Rule Systems into Decision Trees and Acyclic Decision Graphs. in NT Nguyen, K Wojtkiewicz, R Chbeir, Y Manolopoulos, H Fujita, T-P Hong & LM Nguyen (eds), Recent Challenges in Intelligent Information and Database Systems - 16th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2024, Proceedings. Communications in Computer and Information Science, vol. 2144 CCIS, Springer Science and Business Media Deutschland GmbH, pp. 153-163, 16th Asian Conference on Intelligent Information and Database Systems , ACIIDS 2024, Ras Al Khaimah, United Arab Emirates, 04/15/24. https://doi.org/10.1007/978-981-97-5937-8_13

Complexity of Transforming Decision Rule Systems into Decision Trees and Acyclic Decision Graphs. / Durdymyradov, Kerven ; Moshkov, Mikhail.
Recent Challenges in Intelligent Information and Database Systems - 16th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2024, Proceedings. ed. / Ngoc Thanh Nguyen; Krystian Wojtkiewicz; Richard Chbeir; Yannis Manolopoulos; Hamido Fujita; Tzung-Pei Hong; Le Minh Nguyen. Springer Science and Business Media Deutschland GmbH, 2024. p. 153-163 (Communications in Computer and Information Science; Vol. 2144 CCIS).

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

TY - GEN

T1 - Complexity of Transforming Decision Rule Systems into Decision Trees and Acyclic Decision Graphs

AU - Durdymyradov, Kerven

AU - Moshkov, Mikhail

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

PY - 2024

Y1 - 2024

N2 - Decision trees and systems of decision rules are widely used as classifiers, as a means for knowledge representation, and as algorithms. They are among the most interpretable models for data analysis. The study of the relationships between these two models can be seen as an important task of computer science. Methods for transforming decision trees into systems of decision rules are simple and well-known. In this paper, we consider the inverse transformation problem, which is not trivial. We study the complexity of transforming decision rule systems into decision trees and acyclic decision graphs representing decision trees. Based on the obtained results, we can formulate the next stage of research: instead of constructing the entire decision tree, we will study polynomial time algorithms that simulate the work of the decision tree on a given tuple of attribute values.

AB - Decision trees and systems of decision rules are widely used as classifiers, as a means for knowledge representation, and as algorithms. They are among the most interpretable models for data analysis. The study of the relationships between these two models can be seen as an important task of computer science. Methods for transforming decision trees into systems of decision rules are simple and well-known. In this paper, we consider the inverse transformation problem, which is not trivial. We study the complexity of transforming decision rule systems into decision trees and acyclic decision graphs representing decision trees. Based on the obtained results, we can formulate the next stage of research: instead of constructing the entire decision tree, we will study polynomial time algorithms that simulate the work of the decision tree on a given tuple of attribute values.

KW - Acyclic decision graphs

KW - Decision rule systems

KW - Decision trees

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

U2 - 10.1007/978-981-97-5937-8_13

DO - 10.1007/978-981-97-5937-8_13

M3 - Conference contribution

AN - SCOPUS:85201947866

SN - 9789819759361

T3 - Communications in Computer and Information Science

SP - 153

EP - 163

BT - Recent Challenges in Intelligent Information and Database Systems - 16th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2024, Proceedings

A2 - Nguyen, Ngoc Thanh

A2 - Wojtkiewicz, Krystian

A2 - Chbeir, Richard

A2 - Manolopoulos, Yannis

A2 - Fujita, Hamido

A2 - Hong, Tzung-Pei

A2 - Nguyen, Le Minh

PB - Springer Science and Business Media Deutschland GmbH

T2 - 16th Asian Conference on Intelligent Information and Database Systems , ACIIDS 2024

Y2 - 15 April 2024 through 18 April 2024

ER -

Durdymyradov K , Moshkov M. Complexity of Transforming Decision Rule Systems into Decision Trees and Acyclic Decision Graphs. In Nguyen NT, Wojtkiewicz K, Chbeir R, Manolopoulos Y, Fujita H, Hong TP, Nguyen LM, editors, Recent Challenges in Intelligent Information and Database Systems - 16th Asian Conference on Intelligent Information and Database Systems, ACIIDS 2024, Proceedings. Springer Science and Business Media Deutschland GmbH. 2024. p. 153-163. (Communications in Computer and Information Science). doi: 10.1007/978-981-97-5937-8_13