Recognizing Properties of Decision Rule Systems Using Deterministic and Nondeterministic Decision Trees
- 1 Computer, Electrical and Mathematical Sciences & Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal, Saudi Arabia
- 2 Computer, Electrical and Mathematical Sciences & Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal, Saudi Arabia
Abstract
We consider various tasks of recognizing properties of DRSs (Decision Rule Systems) in this paper. As solution algorithms, DDTs (Deterministic Decision Trees) and NDTs (Nondeterministic Decision Trees) are used. An NDT can be considered as a representation of a DRS that satisfies the conditions of the considered task and covers all potential inputs. It has been shown that the minimum depth of a DDT solving the task does not exceed the square of the minimum depth of an NDT. The growth of the minimum number of nodes in DDTs and NDTs can be exponential with the size of the original DRSs. Therefore, in the general case, it is better to simulate the behavior of the DT (Decision Tree) on the given tuple of feature values rather than building the entire tree. We propose a greedy algorithm for such modeling and study its efficiency for a class of tasks of recognizing properties of DRSs. The obtained results may be of interest for data analysis in which both DRSs and DTs are intensively studied. In particular, these results make one think about the possibilities of transforming DRSs into DTs.
- Boros, E., Hammer, P.L., Ibaraki, T. and Kogan, A. (1997) Logical Analysis of Numerical Data. Mathematical Programming , 79, 163-190. https://doi.org/10.1007/bf02614316
- Fürnkranz, J., Gamberger, D. and Lavrac, N. (2012) Foundations of Rule Learning. Cognitive Technologies. https://doi.org/10.1007/978-3-540-75197-7
- Moshkov, M. and Zielosko, B. (2011) Combinatorial Machine Learning—A Rough Set Approach. Studies in Computational Intelligence. https://doi.org/10.1007/978-3-642-20995-6
- Pawlak, Z. (1991) Rough Sets—Theoretical Aspects of Reasoning about Data. Theory and Decision Library: Series D.
- Skowron, A. and Rauszer, C. (1992) The Discernibility Matrices and Functions in Information Systems. In: Słowiński, R., Ed., Intelligent Decision Support — Handbook of Applications and Advances of the Rough Sets Theory , Springer, 331-362. https://doi.org/10.1007/978-94-015-7975-9_21
- Breiman, L., Friedman, J.H. and Olshen, R.A. (1984) Classification and Regression Trees. Wadsworth and Brooks.
- Moshkov, M.J. (2005) Time Complexity of Decision Trees. In: Peters, J.F. and Skowron, A., Eds., Transactions on Rough Sets III , Springer, 244-459. https://doi.org/10.1007/11427834_12
- Quinlan, J.R. (1993) C4.5: Programs for Machine Learning. Morgan Kaufmann.
- Rokach, L. and Maimon, O. (2007) Data Mining with Decision Trees—Theory and Applications. World Scientific Publishing Co. Pte. Ltd. https://doi.org/10.1142/9789812771728
- Molnar, C. (2022) Interpretable Machine Learning. A Guide for Making Black Box Models Explainable, Self-Published. https://christophm.github.io/interpretable-ml-book/
- Moshkov, M. (1998) Some Relationships between Decision Trees and Decision Rule Systems. In: Polkowski, L. and Skowron, A., Eds., Rough Sets and Current Trends in Computing , Springer, 499-505. https://doi.org/10.1007/3-540-69115-4_68
- Moshkov, M. (2001) On transformation of Decision Rule Systems into Decision Trees. Proceedings of the Seventh International Workshop Discrete Mathematics and Its Applications , Moscow, 29 January-2 February 2001, 21-26.
- Durdymyradov, K., Moshkov, M. and Ostonov, A. (2025) Decision Trees Versus Systems of Decision Rules: A Rough Set Approach. Springer. https://doi.org/10.1007/978-3-031-71586-0
- Durdymyradov, K. and Moshkov, M. (2025) Deterministic and Nondeterministic Decision Trees for Recognition of All Realizable Decision Rules. In: Nguyen, N.T., et al. , Eds., Lecture Notes in Computer Science , Springer Nature Singapore, 3-17. https://doi.org/10.1007/978-981-96-6005-6_1