{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:37:00Z","timestamp":1760236620702,"version":"build-2065373602"},"reference-count":18,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2021,12,7]],"date-time":"2021-12-07T00:00:00Z","timestamp":1638835200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004052","name":"King Abdullah University of Science and Technology","doi-asserted-by":"publisher","award":["N\/A"],"award-info":[{"award-number":["N\/A"]}],"id":[{"id":"10.13039\/501100004052","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Conventional decision trees use queries each of which is based on one attribute. In this study, we also examine decision trees that handle additional queries based on hypotheses. This kind of query is similar to the equivalence queries considered in exact learning. Earlier, we designed dynamic programming algorithms for the computation of the minimum depth and the minimum number of internal nodes in decision trees that have hypotheses. Modification of these algorithms considered in the present paper permits us to build decision trees with hypotheses that are optimal relative to the depth or relative to the number of the internal nodes. We compare the length and coverage of decision rules extracted from optimal decision trees with hypotheses and decision rules extracted from optimal conventional decision trees to choose the ones that are preferable as a tool for the representation of information. To this end, we conduct computer experiments on various decision tables from the UCI Machine Learning Repository. In addition, we also consider decision tables for randomly generated Boolean functions. The collected results show that the decision rules derived from decision trees with hypotheses in many cases are better than the rules extracted from conventional decision trees.<\/jats:p>","DOI":"10.3390\/e23121641","type":"journal-article","created":{"date-parts":[[2021,12,7]],"date-time":"2021-12-07T02:48:13Z","timestamp":1638845293000},"page":"1641","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Decision Rules Derived from Optimal Decision Trees with Hypotheses"],"prefix":"10.3390","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9851-1420","authenticated-orcid":false,"given":"Mohammad","family":"Azad","sequence":"first","affiliation":[{"name":"Department of Computer Science, College of Computer and Information Sciences, Jouf University, Sakaka 72441, Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1010-6605","authenticated-orcid":false,"given":"Igor","family":"Chikalov","sequence":"additional","affiliation":[{"name":"Intel Corporation, 5000 W Chandler Blvd, Chandler, AZ 85226, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1698-2809","authenticated-orcid":false,"given":"Shahid","family":"Hussain","sequence":"additional","affiliation":[{"name":"Department of Computer Science, School of Mathematics and Computer Science, Institute of Business Administration, University Road, Karachi 75270, Pakistan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0085-9483","authenticated-orcid":false,"given":"Mikhail","family":"Moshkov","sequence":"additional","affiliation":[{"name":"Computer, Electrical and Mathematical Sciences & Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal 23955-6900, Saudi Arabia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3788-1094","authenticated-orcid":false,"given":"Beata","family":"Zielosko","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, Faculty of Science and Technology, University of Silesia in Katowice, B\u0119dzi\u0144ska 39, 41-200 Sosnowiec, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,12,7]]},"reference":[{"key":"ref_1","unstructured":"Breiman, L., Friedman, J.H., Olshen, R.A., and Stone, C.J. (1984). Classification and Regression Trees, Chapman and Hall\/CRC."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1007\/11427834_12","article-title":"Time complexity of decision trees","volume":"Volume 3400","author":"Peters","year":"2005","journal-title":"Trans. Rough Sets III"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Rokach, L., and Maimon, O. (2007). Data Mining with Decision Trees\u2014Theory and Applications. Series in Machine Perception and Artificial Intelligence, World Scientific.","DOI":"10.1142\/9789812771728"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"James, G., Witten, D., Hastie, T., and Tibshirani, R. (2021). An Introduction to Statistical Learning: With Applications in R, Springer.","DOI":"10.1007\/978-1-0716-1418-1"},{"key":"ref_5","first-page":"270","article-title":"Logical methods of control of work of electric schemes","volume":"51","author":"Chegis","year":"1958","journal-title":"Trudy Mat. Inst. Steklov"},{"key":"ref_6","first-page":"341","article-title":"Rough sets","volume":"11","author":"Pawlak","year":"1982","journal-title":"Int. J. Parallel Program."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Pawlak, Z. (1991). Rough Sets\u2014Theoretical Aspects of Reasoning about Data. Theory and Decision Library: Series D, Kluwer.","DOI":"10.1007\/978-94-011-3534-4_7"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.ins.2006.06.003","article-title":"Rudiments of rough sets","volume":"177","author":"Pawlak","year":"2007","journal-title":"Inf. Sci."},{"key":"ref_9","first-page":"123","article-title":"Minimizing depth of decision trees with hypotheses","volume":"Volume 12872","author":"Ramanna","year":"2021","journal-title":"Lecture Notes in Computer Science, Proceedings of the Rough Sets\u2014International Joint Conference, IJCRS 2021, Bratislava, Slovakia, 19\u201324 September 2021"},{"key":"ref_10","first-page":"232","article-title":"Minimizing number of nodes in decision trees with hypotheses","volume":"Volume 192","author":"Watrobski","year":"2021","journal-title":"Procedia Computer Science, Proceedings of the 25th International Conference on Knowledge-Based and Intelligent Information & Engineering Systems, KES 2021, Szczecin, Poland, 8\u201310 September 2021"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Azad, M., Chikalov, I., Hussain, S., and Moshkov, M. (2021). Entropy-based greedy algorithm for decision trees using hypotheses. Entropy, 23.","DOI":"10.3390\/e23070808"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Azad, M., Chikalov, I., Hussain, S., and Moshkov, M. (2021). Optimization of decision trees with hypotheses for knowledge representation. Electronics, 10.","DOI":"10.3390\/electronics10131580"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","article-title":"Learning regular sets from queries and counterexamples","volume":"75","author":"Angluin","year":"1987","journal-title":"Inf. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/BF00116828","article-title":"Queries and concept learning","volume":"2","author":"Angluin","year":"1988","journal-title":"Mach. Learn."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/j.tcs.2003.11.004","article-title":"Queries revisited","volume":"313","author":"Angluin","year":"2004","journal-title":"Theor. Comput. Sci."},{"key":"ref_16","unstructured":"Dua, D., Graff, C., and UCI Machine Learning Repository (2017, April 12). University of California, Irvine, School of Information and Computer Sciences. Available online: http:\/\/archive.ics.uci.edu\/ml."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"AbouEisha, H., Amin, T., Chikalov, I., Hussain, S., and Moshkov, M. (2019). Extensions of Dynamic Programming for Combinatorial Optimization and Data Mining. Intelligent Systems Reference Library, Springer.","DOI":"10.1007\/978-3-319-91839-6"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/978-3-642-30344-9_6","article-title":"Dynamic programming approach for exact decision rule optimization","volume":"Volume 42","author":"Skowron","year":"2013","journal-title":"Rough Sets and Intelligent Systems\u2014Professor Zdzis\u0142aw Pawlak in Memoriam\u2014Volume 1"}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/12\/1641\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:42:12Z","timestamp":1760168532000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/23\/12\/1641"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,7]]},"references-count":18,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2021,12]]}},"alternative-id":["e23121641"],"URL":"https:\/\/doi.org\/10.3390\/e23121641","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2021,12,7]]}}}