Relationships between Average Depth and Number of Misclassifications for Decision Trees

• Autorzy: Chikalov, I. , Hussain, S. , Moshkov, M.
• Języki publikacji: EN

Abstrakty

EN

This paper presents a new tool for the study of relationships between the total path length or the average depth and the number of misclassifications for decision trees. In addition to algorithm, the paper also presents the results of experiments with datasets from UCI ML Repository [9] and datasets representing Boolean functions with 10 variables.

Słowa kluczowe

EN

average depth; decision tree; total path length

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 129, nr 1/2
• Strony: 15--26
• Opis fizyczny: Bibliogr. 15 poz.., wykr.

Twórcy

autor

Chikalov, I.

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

autor

Hussain, S.

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

autor

Moshkov, M.

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

Bibliografia

• [1] 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: Computational Informatics, Social Factors and New Information Technologies: Hypermedia Perspectives and Avant-Garde Experiencies in the Era of Communicability Expansion (F. V. C. Ficarra, A. Kratky, K. H. Veltman, M. C. Ficarra, E. Nicol, M. Brie, Eds.), Blue Herons, 2011, 29–39.
• [2] Alkhalid, A., Chikalov, I., Hussain, S., Moshkov: Extensions of dynamic programming as a new tool fordecision tree optimization, in: Emerging Paradigms in Machine Learning (S. Ramanna, L. C. Jain, R. J. Howlett, Eds.), vol. 13 of Smart Innovation, Systems and Technologies, Springer Berlin Heidelberg, 2013,11–29.
• [3] Alkhalid, A., Chikalov, I., Moshkov, M.: On Algorithm for Building of Optimal _-Decision Trees, RSCTC(M. S. Szczuka, M. Kryszkiewicz, S. Ramanna, R. Jensen, Q. Hu, Eds.), Springer, Heidelberg, 2010.
• [4] Alkhalid, A., Chikalov, I., Moshkov, M.: A Tool for Study of Optimal Decision Trees, RSKT (J. Yu, S. Greco,P. Lingras, G. Wang, A. Skowron, Eds.), LNCS 6401, Springer, 2010.
• [5] Breiman, L., Friedman, J., Olshen, R., Stone, C.: Classification and Regression Trees, Wadsworth and Brooks, Monterey, CA, 1984.
• [6] Chikalov, I., Hussain, S., Moshkov, M.: Relationships between Depth and Number of Misclassifications for Decision Trees, in: Rough Sets, Fuzzy Sets, Data Mining and Granular Computing (S. O. Kuznetsov,D. Ślęzak, D. H. Hepting, B. Mirkin, Eds.), vol. 6743 of Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2011, ISBN 978-3-642-21880-4, 286–292.
• [7] Chikalov, I., Hussain, S., Moshkov, M.: Average Depth and Number of Misclassifications for Decision Trees, 21st International Workshop on Concurrency, Specification and Programming (L. Popova-Zeugmann, Ed.),2012.
• [8] Chikalov, I., Hussain, S., Moshkov, M.: Relationships for Cost and Uncertainty of Decision Trees, in: Rough Sets and Intelligent Systems - Professor Zdzisław Pawlak in Memoriam (A. Skowron, Z. Suraj, Eds.), vol. 43of Intelligent Systems Reference Library, Springer Berlin Heidelberg, 2013, ISBN 978-3-642-30340-1, 203–222.
• [9] Frank, A., Asuncion, A.: UCI Machine Learning Repository, 2010.
• [10] Hastie, T., Tibshirani, R., Friedman, J. H.: The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Springer-Verlag, New York, 2001.
• [11] Hyafil, L., Rivest, R. L.: Constructing Optimal Binary Decision Trees is NP-Complete, Inf. Process. Lett.,5(1), 1976, 15–17.
• [12] Moshkov, M. J.: Time Complexity of Decision Trees, in: T. Rough Sets (J. F. Peters, A. Skowron, Eds.), vol.3400 of Lecture Notes in Computer Science, Springer, Heidelberg, 2005, 244–459.
• [13] Nguyen, H. S.: From optimal hyperplanes to optimal decision trees, Fundamenta Informaticae, 34(1-2), 1998, 145–174.
• [14] Pawlak, Z.: Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Dordrecht, 1991.
• [15] Skowron, A., Rauszer, C.: The discernibility matrices and functions in information systems, Intelligent Decision Support. Handbook of Applications and Advances of the Rough Set Theory (R. Slowinski, Ed.),Kluwer Academic Publishers, Dordrecht, 1992.

Identyfikatory

DOI

10.3233/FI-2014-957