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.
References
[1]
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
[2]
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
[3]
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
[4]
Pawlak, Z. (1991) Rough Sets—Theoretical Aspects of Reasoning about Data. Theory and Decision Library: Series D.
[5]
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
[6]
Breiman, L., Friedman, J.H. and Olshen, R.A. (1984) Classification and Regression Trees. Wadsworth and Brooks.
[7]
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
[8]
Quinlan, J.R. (1993) C4.5: Programs for Machine Learning. Morgan Kaufmann.
[9]
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
[10]
Molnar, C. (2022) Interpretable Machine Learning. A Guide for Making Black Box Models Explainable, Self-Published. https://christophm.github.io/interpretable-ml-book/
[11]
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
[12]
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.
[13]
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
[14]
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
[15]
Durdymyradov, K. and Moshkov, M. (2025) Deterministic and Nondeterministic Decision Trees for Recognition of Properties of Decision Rule Systems. In: Zhang, Q., et al., Eds., Lecture Notes in Computer Science, Springer Nature Switzerland, 426-435. https://doi.org/10.1007/978-3-031-92744-7_29
[16]
Blum, M. and Impagliazzo, R. (1987) Generic Oracles and Oracle Classes. 28th Annual Symposium on Foundations of Computer Science (SFCS 1987), Los Angeles, 12-14 October 1987, 118-126. https://doi.org/10.1109/sfcs.1987.30
[17]
Hartmanis, J. and Hemachandra, L.A. (1987) One-Way Functions, Robustness, and the Non-Isomorphism of NP-Complete Sets. Proceedings of the Second Annual Conference on Structure in Complexity Theory, Ithaca, 16-19 June 1987, 160-174. https://doi.org/10.1109/PSCT.1987.10319267
[18]
Tardos, G. (1989) Query Complexity, or Why Is It Difficult to SeparateNPA ∩ coNPA From PA by Random Oracles A? Combinatorica, 9, 385-392. https://doi.org/10.1007/bf02125350
[19]
Buhrman, H. and de Wolf, R. (2002) Complexity Measures and Decision Tree Complexity: A Survey. Theoretical Computer Science, 288, 21-43. https://doi.org/10.1016/s0304-3975(01)00144-x
[20]
Moshkov, M. (1982) On Conditional Tests. Doklady Physics, 27, 528-530. http://mi.mathnet.ru/dan45454
[21]
Hegedűs, T. (1995) Generalized Teaching Dimensions and the Query Complexity of Learning. Proceedings of the Eighth Annual Conference on Computational Learning theory, Santa Cruz, 5-8 July 1995, 108-117. https://doi.org/10.1145/225298.225311
[22]
Goldman, S.A. and Kearns, M.J. (1995) On the Complexity of Teaching. Journal of Computer and System Sciences, 50, 20-31. https://doi.org/10.1006/jcss.1995.1003
