Closed Classes of Binary Complete Decision Tables with Many-Valued Decisions
- 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
- 3 Computer, Electrical and Mathematical Sciences & Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal, Saudi Arabia
Abstract
A binary complete decision table with many-valued decisions is a table with n attributes and 2 n pairwise distinct rows filled with numbers from the set { 0 , 1 } . Each row of this table is labeled with a nonempty finite set of decisions. For a given row of the table, the task is to find a decision from the set of decisions attached to the row. Such tables are generalizations of Boolean functions. They can also be viewed as representations of various problems related to systems of decision rules. In this paper, we consider three types of classes of binary complete decision tables with many-valued decisions, closed with respect to removal of columns and changing of decisions. For tables from these classes, we study the relationships between the minimum weighted depth of deterministic, nondeterministic, and (for one type of classes) strongly nondeterministic decision trees and the total weight of attributes attached to columns. Note that nondeterministic decision trees and strongly nondeterministic decision trees for decision tables can be interpreted as a way of representing the two types of systems of decision rules for these tables.
- 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
- Breiman, L., Friedman, J.H. and Olshen, R.A. (1984) Classification and Regression Trees. Chapman and Hall/CRC. https://doi.org/10.1201/9781315139470
- Moshkov, M.J. (2005) Time Complexity of Decision Trees. In: Peters, J.F. and Skowron, A., Eds., Lecture Notes in Computer Science , Springer, 244-459. https://doi.org/10.1007/11427834_12
- Moshkov, M. (2020) Comparative Analysis of Deterministic and Nondeterministic Decision Trees. Springer. https://doi.org/10.1007/978-3-030-41728-4
- Quinlan, J.R. (1993) C4.5: Programs for Machine Learning. Morgan Kaufmann. https://doi.org/10.1007/BF00993309
- 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
- Boros, E., Hammer, P.L., Ibaraki, T., Kogan, A., Mayoraz, E. and Muchnik, I. (2000) An Implementation of Logical Analysis of Data. IEEE Transactions on Knowledge and Data Engineering , 12, 292-306. https://doi.org/10.1109/69.842268
- Chikalov, I., Lozin, V.V., Lozina, I., Moshkov, M., Nguyen, H.S., Skowron, A. and Zielosko, B. (2013) Three Approaches to Data Analysis—Test Theory, Rough Sets and Logical Analysis of Data. Springer. https://doi.org/10.1007/978-3-642-28667-4
- Fürnkranz, J., Gamberger, D. and Lavrac, N. (2012) Foundations of Rule Learning. Springer. https://doi.org/10.1007/978-3-540-75197-7
- Moshkov, M. and Zielosko, B. (2011) Combinatorial Machine Learning—A Rough Set Approach. Springer. https://doi.org/10.1007/978-3-642-20995-6
- Pawlak, Z. and Skowron, A. (2007) Rudiments of Rough Sets. Information Sciences , 177, 3-27. https://doi.org/10.1016/j.ins.2006.06.003
- Molnar, C. (2022) Interpretable Machine Learning. A Guide for Making Black Box Models Explainable, Self-Published https://christophm.github.io/interpretable-ml-book/
- Boutell, M.R., Luo, J., Shen, X. and Brown, C.M. (2004) Learning Multi-Label Scene Classification. Pattern Recognition , 37, 1757-1771. https://doi.org/10.1016/j.patcog.2004.03.009
- Vens, C., Struyf, J., Schietgat, L., Džeroski, S. and Blockeel, H. (2008) Decision Trees for Hierarchical Multi-Label Classification. Machine Learning , 73, 185-214. https://doi.org/10.1007/s10994-008-5077-3