Avaliação da performance do algoritmo J48 para construção de modelos baseados em árvores de decisão

Decision trees are hierarchical models used in several areas of knowledge due to their predictive capacity and problem solving in a simple and objective way. However, they present some limitations related to their adequacy to the database and in regard to paying attention to the procedures for selection of growth and pruning parameters to be adopted. In this way, the objective is to evaluate and discuss the performance of the J48 algorithm for the construction of tree decision-making models in databases with attributes of di erent types. Therefore, experiments in 10 databases available in international repository were carried out, considering as variants the training, testing and pruning methods, applied throughout the database and using the Wrapper and Correlation-based Feature Selection (CFS) methods for attribute selection. It was identi ed that in the presence of continuous data, the only models that presented good predictive capacity were present in situations in which the large number of examples could compensate for such de ciency. The cross-validation and percentage split training modes were similar in their predictions when adjusted to 10 folds and 75%, respectively. Furthermore, the selection of attributes was unable to generate better predictions denoting that such a method, in an isolated way, does not compensate for possible inadequacies in the database. It can be realized that the results regarding the predictive capacity of the models are strongly guided by the number of examples belonging to the base, presence of continuous data and noisy data. keywords: Decision tree. J48. Decision model. 80 Vieira et al./ Revista Brasileira de Computação Aplicada (2018), v.10, n.2, pp.80–90 | 81 1 Introdução A tomada de decisão é um processo de escolha entre duas ou mais alternativas para alcançar um ou mais objetivos de forma e ciente, podendo utilizar-se para tanto de modelos que subsidiem a fase de escolha e implementação da decisão mais apropriada (Turban et al.; 2011).As árvores de decisão têm sido usadas como técnicas con áveis para desenvolvimento de modelos preditivos de apoio à tomada de decisão por se tratarem de estruturas grá cas hierárquicas de fácil entendimento e aplicação, caracterizadas por segmentar dados heterogêneos de acordo com suas similaridades de maneira que se tornem mais homogêneos em relação à variável alvo (Cervantes et al.; 2015); (Ramya et al.; 2015). A relevância de tais árvores para a tomada de decisão se dá por sua capacidade preditiva, ou seja, a capacidade do modelo em predizer no presente as interações que ocorrerão no futuro com um nível de certeza, auxiliando na resolução de problemas em diferentes áreas (Evangeline and Sudhasini (2016); Sousa et al. (2011)),incluindo a área da saúde como apresentado nos trabalhos de (Funchal et al. (2015), Maciel et al. (2015) e Kamadi et al. (2016)). Um dos mais conhecidos algoritmos de indução de árvore de decisão, o C4.5 criado inicialmente por Ross Quinlan na década de 90 e implementado na linguagem JAVA sob o nome “J48” vem sendo popularmente utilizado por apresentar um determinado padrão de comportamento em conjuntos de dados de diferentes formas de representação, ou seja, apresenta poucas restrições quanto às características dos atributos adotados mostrandose adequado para os procedimentos envolvendo atributos qualitativos, contínuos e discretos, além disso, não exige uma distribuição de probabilidade especí ca (Chauhan and Chauhan (2013); Lin and Chen (2012)). As principais vantagens de tal técnica estão relacionadas ao fato de que têm a capacidade de processar valores em falta ou dados com ruídos (incertos), e ainda, assim, terem resultados de alto desempenho com baixo custo computacional (Cervantes et al. (2015);Bhargava et al. (2013)). Entretanto, este método possui algumas limitações relacionadas, principalmente, a sua avaliação focal do potencial preditor de uma covariável em relação à variável alvo, ou seja, o quanto um nó é informativo para o outro sem, no entanto, atentar para a sequência que produz a melhor predição, resultando em soluções simplistas para problemas complexos, e que associado ao fato de cada tipo de variável apresentar um tratamento distinto em relação à construção do modelo (Nong; 2014) pode resultar em di culdades para adequação à determinadas bases de dados. Desta forma, considerando tais limitações e a gama de possibilidades que o método oferece em termos de modo de crescimento e de poda da árvore, questiona-se sobre qual comportamento de tais modelos ao se atentar para os procedimentos de seleção dos atributos relevantes, tendo em vista que problemas que envolvem uma grande quantidade de atributos podem se tornar demasiadamente complexos. Ademais, sabendo-se que critérios de partição dos dados e a escolha dos parâmetros a serem adotados para cada tipo de base re etem diretamente no sucesso e fracasso dos modelos questiona-se sobre qual a melhor con guração dos modos de treinamento, teste e poda da árvore de decisão, se a caracterização dos dados afeta a acurácia da classi cação/predição e, nalmente, se o número de exemplos da base de dados afeta a acurácia da classi cação. Logo, têm-se como objetivo avaliar e discutir a performance do algoritmo J48 para construção de modelos de tomada de decisão em árvore em bases de dados com atributos de diferentes tipos. Nas seções subsequentes são apresentados um breve referencial teórico da literatura pertinente e atualizada em relação ao tema em questão, em seguida são expostos os procedimentos metodológicos que contemplam aspectos de treinamento e teste da árvore de decisão, métodos de seleção de atributos, processo de poda e medidas de acurácia. A seção dos resultados e discussão é descrita em dois momentos: Fase I, que compõe experimentos sem seleção de atributos e a fase II, que compõe experimentos com seleção de atributos. Por m, uma breve conclusão dos achados relevantes. 2 Referencial teórico Uma árvore de decisão é constituída de uma cadeia de nós de decisão, conectados por rami cações, estendendo-se desde o nó raiz até os nós folhas, tendo como requisitos básicos a existência de um atributo alvo (Last et al. (2016); Larose (2014)). Sua construção é viabilizada por algoritmos, dentre os quais o J48, um algoritmo de código aberto, implementado pelo software WEKA (Witten et al.; 2016), em que a estruturação do modelo adota a estratégia “dividir para conquistar”, baseando-se no conceito de razão de ganho de informação que identi ca por meio da redução de entropia o quanto informativo um atributo é, para então selecionar a separação ótima, ou seja, o quanto espera-se que a entropia se reduza caso um determinado nó seja escolhido para fazer a partição dos dados (Larose; 2014); (Bhargava et al. (2013); Lin and Chen (2012)). Para cada atributo no conjunto de dados a razão de ganho de informação é calculada como pode ser vista na equação 4 e utilizada como critério de partição do atributo, e commaior razão de ganho de informação o nó será utilizado como raiz (Lavanya and Rani (2011); Venkatadri and Lokanatha (2010)). O J48 é um algoritmo que pode lidar tanto com atributos contínuos e discretos, quanto com valores categóricos e valores ausentes. O tratamento de atributos contínuos envolve a consideração de todos os valores presentes no conjunto de treinamento, fazendo com que sejam ordenados de forma crescente considerando todos os valores presente nos dados de treinamento e, após esta ordenação, seja selecionado o valor que favorecerá a redução da entropia (Camargo et al. (2016); Ramya et al. (2015)). )). Os cálculos para escolha do atributo referente ao nó raiz são realizados da seguinte maneira: Equação 1 – Redução de Entropia: Cálculo Info(S) para identi car a classe no conjunto de treinamento 82 | Vieira et al./ Revista Brasileira de Computação Aplicada (2018), v.10, n.2, pp.80–90 S: Info(S) = – k ∑ i=1 {[ freq(Ci, S) |S| ] log2 [ freq(Cj, S) |S| ]} (1) |S| é o número de casos no conjunto de treinamento; Ci é a classe: i = 1, 2, 3, ..., k, k = número de classes; freq (Ci,S) = número de casos em Ci.Equação 2 – Redução de Entropia: Cálculo do valor da informação esperada, Infox(S), para o atributo X da partição S. Onde n é o número de valores possíveis que o atributo pode assumir, ou seja, o número de nóslhos, N é o número total de objetos do nó-pai e N (Si) é o número de exemplos associados ao nó lho Si. Infox(S) = – n ∑ i=1 [( |Si| |S| Info(Si) )] (2) Assim, na equação 3, o ganho de informação será dado por: Ganho(X) = Info(S) – Infox(S) (3) O uso do critério de ganho de informação para escolha do nó raiz da árvore favorece dados com grandes variações nos valores, podendo representar um viés. Assim, a razão de ganho de informação, representada pela equação 4, em que o denominador normaliza o conjunto de amostra de atributos que apresentam grandes variações, pode superar tal limitação ao suavizar favorecimentos que por ventura venham a acontecer e certi car que a melhor escolha tenha sido feita (Quinlan; 1993). Equação 4 – Razão do ganho de informação (RG): ganho de informação de um atributo X normalizado pela medida de informação dividida. RG = Ganho(X) ∑k i=1 [ |Si| |S| log2 |Si| |S| ] (4) A partir deste processo, duas fases de construção da árvore podem ser identi cadas: o crescimento, sub composto pelas fases de treinamento e teste; e a poda. Na fase de crescimento os dados são divididos em grupos, podendo ser direcionados para treinamento e aprendizado da estrutura, e ainda para o teste que identi ca a capacidade preditiva da árvore (Last et al. (2016); Larose (2014)). A sequência de passos para construção e poda da árvore está abordada no pseudocódigo do algoritmo descrito por Camilo and Silva (2009), como exposto na Fig. 1. aborda três possibilidades: 1) teste padrão em um atributo discreto, em que há um resultado e um ramo da árvore para cada possível valor desse atributo; 2) teste mais complexo baseado em um atributo discreto, em que os valores po