Measuring the Shattering coefficient of Decision Tree models

Autor(es)

de Mello, Rodrigo E. ^[1] ; Manapragada, Chaitanya ^[2] ; Bifet, Albert ^[3]

Afiliação do(s) autor(es)

^[1] Av Trabalhador Saocarlense 400, BR-13560970 Sao Carlos, SP - Brazil

^[2] Monash Univ, Wellington Rd, Clayton, Vic 3800 - Australia

^[3] Telecom ParisTech, LTCI, Off C201-2, 46 Rue Barrault, F-75634 Paris 13 - France

• Tipo de documento: Artigo Científico
• Fonte: EXPERT SYSTEMS WITH APPLICATIONS; v. 137, p. 443-452, DEC 15 2019.
• Citações Web of Science: 0

Resumo

In spite of the relevance of Decision Trees (DTs), there is still a disconnection between their theoretical and practical results while selecting models to address specific learning tasks. A particular criterion is provided by the Shattering coefficient, a growth function formulated in the context of the Statistical Learning Theory (SLT), which measures the complexity of the algorithm bias as sample sizes increase. In attempt to establish the basis for a relative theoretical complexity analysis, this paper introduces a method to compute the Shattering coefficient of DT models using recurrence equations. Next, we assess the bias of models provided by DT algorithms while solving practical problems as well as their overall learning bounds in light of the SLT. As the main contribution, our results support other researchers to decide on the most adequate DT models to tackle specific supervised learning tasks. (C) 2019 Elsevier Ltd. All rights reserved. (AU)

• Processo FAPESP: 17/16548-6 - Proposta de uma abordagem com garantias teóricas para a detecção de mudanças de conceito em fluxos de dados
• Beneficiário: Rodrigo Fernandes de Mello
• Modalidade de apoio: Bolsas no Exterior - Pesquisa