Analysis of Decision Tree Induction Algorithms

Authors

DOI:

https://doi.org/10.33448/rsd-v8i11.1473

Keywords:

Data Structure; Artificial intelligence; Computational decision; C4.5; CART.

Abstract

Decision trees are data structures or computational methods that enable nonparametric supervised machine learning and are used in classification and regression tasks. The aim of this paper is to present a comparison between the decision tree induction algorithms C4.5 and CART. A quantitative study is performed in which the two methods are compared by analyzing the following aspects: operation and complexity. The experiments presented practically equal hit percentages in the execution time for tree induction, however, the CART algorithm was approximately 46.24% slower than C4.5 and was considered to be more effective.

References

Barbosa, J.M., Carneiro,T.G.S. & Tavares, A.L. (2012). Métodos de Classificação por Árvores de Decisão. Disciplina de Projeto e Análise de Algoritmos do PPGCC - Programa de Pós-Graduação em Ciência da Computação do Departamento de Computação (DECOM) da Universidade Federal de Ouro Preto (UFOP). Disponível em: <http://www.decom.ufop.br/menotti/paa111/files/PCC104-111-ars-11.1-JulianaMoreiraBarbosa.pdf>. Acesso em: 03 Ago. 2019.

Bittencourt, H. R. & Clarke, R. T. (2003). Use of classification and regression trees (CART) to classify remotely-sensed digital images. In: Anais do International Geoscience and Remote Sensing Symposium. pp. 3751-3753. Disponível em: Acesso em: 02 ago. 2019.

Carvalho, D.R. (2005). Árvore de decisão / algoritmo genético para tartar o problema de pequenos disjuntos em classificação de dados. Tese (Doutorado) no Programa de Pós-Graduação em computação de alto desempenho / sistemas computacionais do Programa de Engenharia Civil da Universidade Federal do Rio de Janeiro. Disponível em: http://www.ipardes.gov.br/biblioteca/docs/tese_deborah_carvalho.pdf. Acesso: 6 ago. 2019.

Cormen, T. H. (2009). Introduction to algorithms. MIT press, USA.

Garcia, S. C. (2003). O uso de árvores de decisão na descoberta de conhecimento na área da saúde. Tese (Doutorado) na Universidade Federal doRio Grande do Sul. Disponível em: <http://hdl.handle.net/10183/4703>. Acesso em: 03 ago. 2019.

Giasson, E, Hartemink, A.E, Tornquist, C.G., Teske, R, & Bagatini, T. (2013). Avaliação de cinco algoritmos de árvores de decisão e três tipos de modelos digitais de elevação para mapeamento digital de solos a nível semidetalhado na Bacia do Lageado Grande, RS, Brasil. Ciência Rural, 43(11): 1967-1973. https://dx.doi.org/10.1590/S0103-84782013001100008

Han, J. & Kamber, M. (2002). Data Mining: Concepts and Techniques. 3.ed. Morgan Kaufmann/Elsevier, Waltham, MA, USA.

Nascimento, P. T. S. & Façanha, S. L. O. (2008). Árvore de decisão incompleta: reduzindo a complexidade para acelerar a decisão. In: Anais do Encontro da Associação Nacional de Pós-Graduação e Pesquisa em Administração, 32(1). Disponível em: <http://www.anpad.org.br/admin/pdf/ESO-A1183.pdf>. Acesso em: 3 ago. 2019.

Nascimento Jr., L.A.F. (2017). Aplicando método do gradiente ótimo na otimização do cálculo do grau de cobertura das regras em árvores de decisão Fuzzy. Revista Brasileira de Computação Aplicada (ISSN 2176-6649), Passo Fundo, 9(3):31-43, out. 2017.

Pereira, A.S., Shitsuka, D.M., Parreira, F.J. & Shitsuka, R. (2018). Metodologia da pesquisa cientifica. Santa Maria/RS, Ed. UAB/NTE/UFSM. Disponível em: https://repositorio.ufsm.br/bitstream/handle/1/15824/Lic_Computacao_Metodologia-Pesquisa-Cientifica.pdf?sequence=1. Acesso em: 3 ago. 2019.

Ragsdale, C. T. (2010). Spreadsheet modeling and decision analysis. 6.ed. Cengage Learning, USA.

Ruggieri, S. (2002). Efficient C4.5. Knowledge and Data Engineering, IEEE Transactions, 14(2):438-444. Available from: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=991727&tag=1. Acess on: Aug., 3rd, 2019.

Wu, X. & Kumar, V. (2009). The top ten algorithms in data mining. Chapman & Hall/CRC, Boca Ratton, USA.

Published

24/08/2019

How to Cite

OKADA, H. K. R.; NEVES, A. R. N. das; SHITSUKA, R. Analysis of Decision Tree Induction Algorithms. Research, Society and Development, [S. l.], v. 8, n. 11, p. e298111473, 2019. DOI: 10.33448/rsd-v8i11.1473. Disponível em: https://rsdjournal.org/index.php/rsd/article/view/1473. Acesso em: 24 sep. 2021.

Issue

Section

Exact and Earth Sciences