Experimental Study of Totally Optimal Decision Trees

• Autorzy: Aldilaijan Abdulla , Azad Mohammad , Moshkov Mikhail

Identyfikatory

DOI

10.3233/FI-2019-1784

• Języki publikacji: EN

Abstrakty

EN

In this paper, we present results of experimental studies related to the existence of totally optimal decision trees (which are optimal relative to two or more cost functions simultaneously) for nine decision tables from the UCI Machine Learning Repository. Such trees can be useful when we consider decision trees as algorithms for problem solving or as a way for knowledge representation. For cost functions, we use depth, average depth, and number of nodes. We study not only exact but also approximate decision trees based on five uncertainty measures: entropy, Gini index, misclassification error, relative misclassification error, and number of unordered pairs of rows with different decisions. To investigate the existence of totally optimal trees, we use an extension of dynamic programming that allows us to make multi-stage optimization of decision trees relative to a sequence of cost functions. Experimental results show that totally optimal decision trees exist in many cases. The behavior of graphs that describe how the number of decision tables with totally optimal decision trees depends on their accuracy is mainly irregular. However, one can observe some trends, in particular, an upward trend when accuracy is decreasing.

Słowa kluczowe

EN

cost function; decision tree; multistage optimization; totally optimal decision tree; uncertainty measure

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 165, nr 3-4
• Strony: 245--261
• Opis fizyczny: Bibliogr. 13 poz., rys., tab., wykr.

Twórcy

autor

Aldilaijan Abdulla

• Brown University, Department of Computer Science, Providence, Rhode Island 02912 USA

autor

Azad Mohammad

• Computer, Electrical and Mathematical Sciences & Engineering Division, King Abdullah University of Science and Technology, Thuwal 23955-6900, Saudi Arabia

autor

Moshkov Mikhail

• Computer, Electrical and Mathematical Sciences & Engineering Division, King Abdullah University of Science and Technology, Thuwal 23955-6900, Saudi Arabia

Bibliografia

• [1] Moshkov M. Time complexity of decision trees. In: Peters JF, Skowron A (eds.), Trans. Rough Sets III, volume 3400 of Lecture Notes in Computer Science, Springer, 2005 pp. 244-459. doi:10.1007/11427834_12.
• [2] Rokach L, Maimon O. Data Mining with Decision Trees: Theory and Applications. World Scientific Publishing, River Edge, NJ, 2008. doi:10.1142/6604.
• [3] Azad M, Chikalov I, Hussain S, Moshkov M. Multi-pruning of decision trees for knowledge representation and classification. In: 3rd IAPR Asian Conference on Pattern Recognition, ACPR 2015, Kuala Lumpur, Malaysia, November 3-6, 2015. IEEE, 2015 pp. 604-608. doi:10.1109/ACPR.2015.7486574.
• [4] Moshkov M, Chikalov I. Consecutive optimization of decision trees concerning various complexity measures. Fundam. Inform., 2004.61(2):87-96. URL http://content.iospress.com/articles/fundamenta-informaticae/fi61-2-02.
• [5] Alkhalid A, Amin T, Chikalov I, Hussain S, Moshkov M, Zielosko B. DAGGER: a tool for analysis and optimization of decision trees and rules. In: Ficarra FVC, Kratky A, Veltman KH, Ficarra MC, Nicol E, BrieM(eds.), Computational Informatics, Social Factors and New Information Technologies: Hypermedia Perspectives and Avant-Garde Experiencies in the Era of Communicability Expansion, Blue Herons, 2011 pp. 29-39. ISBN- 9788896471043.
• [6] Alkhalid A, Amin T, Chikalov I, Hussain S, Moshkov M, Zielosko B. Optimization and analysis of decision trees and rules: dynamic programming approach. International Journal of General Systems, 2013.42(6):614-634. URL https://doi.org/10.1080/03081079.2013.798902.
• [7] Lichman M. UCI Machine Learning Repository. University of California, Irvine, School of Information and Computer Sciences, 2013. URL http://archive.ics.uci.edu/ml.
• [8] Pawlak Z. Rough Sets - Theoretical Aspect of Reasoning About Data. Kluwer Academic Publishers, Dordrecht, 1991. doi:10.1007/978-94-011-3534-4.
• [9] Pawlak Z, Skowron A. Rudiments of rough sets. Information Sciences, 2007.177(1):3-27. URL https://doi.org/10.1016/j.ins.2006.06.003.
• [10] Chikalov I, Hussain S, Moshkov M. Totally optimal decision trees for Boolean functions. Discrete Applied Mathematics, 2016.215:1-13. URL https://doi.org/10.1016/j.dam.2016.07.009.
• [11] Azad M, Moshkov M. Multi-stage optimization of decision and inhibitory trees for decision tables with many-valued decisions. European Journal of Operational Research, 2017.263(3):910-921. URL https://doi.org/10.1016/j.ejor.2017.06.026.
• [12] Aldilaijan A, Azad M, Moshkov M. Experimental study of totally optimal decision trees. In: 26th International Workshop on Concurrency, Specification and Programming, Warsaw, Poland, September 25-27, 2017. URL http://csp2017.mimuw.edu.pl/data/uploads/papers/CSP2017_paper_2.pdf.
• [13] AbouEisha H, Amin T, Chikalov I, Hussain S, Moshkov M. Extensions of Dynamic Programming for Combinatorial Optimization and Data Mining, volume 146 of Intelligent Systems Reference Library. Springer, 2019. doi:10.1007/978-3-319-91839-6.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).