Estudo e construção de árvores de decisão: aplicação ao ensino

Universidade do Minho Escola de Ciências Paulina Da Silva Orlando Suquina outubro de 2019 Estudo e Construção de árvores de decisão: aplicação ao ensino Paulina Da Silva Orlando Suquina Estudo e Construção de árvores de decisão: aplicação ao ensino UMinho|2019 Universidade do Minho Escola de Ciências Paulina Da Silva Orlando Suquina outubro de 2019 Estudo e Construção de árvores de decisão: aplicação ao ensino Trabalho efetuado sob a orientação da Professor Doutor Stéphane Louis Clain Dissertação de Mestrado Mestrado em Matemática e Computação DIREITOS DO AUTOR E CONDIÇÕES DE UTILIZAÇÃO DO TRABALHO POR TERCEIROS Este é um trabalho académico que pode ser utilizado por terceiros desde que respeitadas as regras e boas práticas internacionalmente aceites, no que concerne aos direitos de autor e direitos conexos. Assim, o presente trabalho pode ser utilizado nos termos previstos na licença abaixo indicada. Caso o utilizador necessite de permissão para poder fazer um uso do trabalho em condições não previstas no licenciamento indicado, deverá contactar o autor, através do RepositóriUM da Universidade do Minho. Licença concedida aos utilizadores deste trabalho https://pt.wikibooks.org/wiki/Latex i Agradecimetos Primeiramente agradeço a Deus por ter me dado força e coragem para enfrentar as dificuldades. Não posso deixar de agradecer ao meu orientador, Professor Doutor Stéphane Louis Clain, por toda paciência, empenho, motivação com que sempre me orientou neste trabalho. Obrigada por me corrigir sempre que foi necessário. Agradeço também aos Professores do departamento do Mestrado em Matemática e Computação, que mesmo com a chegada tardia a Universidade, deram-nos o apoio incondicional de que precisávamos. A Doutora Paula Henriques, pela oportunidade que me deu de poder fazer parte deste projeto. Desejo igualmente agradecer aos meus colegas, em especial o Incansável Pedro Vicente, Schields Pedro, a irmã que ganhei em Braga Maria Tómas, Gerson Hungulu, Osvaldo Jamba e Nunes Rafael, cujo apoio e amizade estiveram presentes em todos os momentos. Agradeço ao meu esposo Eduardo Nangacovie, pelo incentivo, apoio e por acreditar que eu era capaz de concluir este trabalho. Ao meu filho David Nangacovie, por suportar a minha ausência por varias horas ao longo do dia e por vezes aos fins de semana. Agradeço também a Tia Maria Silva, Por cuidar do David nos momentos que mais precisei. A Tia Helena Canhici, por ter me indicado as pessoas certas cá em Braga. Aos meus irmãos pelo amor, incentivo e apoio incondicional. Ao meu Pai Domingos Suquina, pelo amor, dedicação e por ter apostado na minha formação. Agradeço a minha mãe Irene Henriques da Silva, meu porto seguro que sempre me apoiou nas horas mais difíceis de desânimo e cansaço. Por ultimo agradeço a minha família e amigos, pelo apoio incondicional que me deram. ii DECLARAÇÃO DE INTEGRIDADE Declaro ter atuado com integridade na elaboração do presente trabalho académico e confirmo que não recorri à prática de plágio nem a qualquer forma de utilização indevida ou falsificação de informações ou resultados em nenhuma das etapas conducente à sua elaboração. Mais declaro que conheço e que respeitei o Código de Conduta Ética da Universidade do Minho. iii Resumo As árvores de decisão são ferramentas muito utilizadas em áreas como as de Extração de Conhecimento de Dados (ECD), devido à eficiência que elas possuem em produzir classificadores. As mesmas são vantajosas devido à sua capacidade em dividir um espaço de exemplos em subespaços, e ajustar cada subespaço recorrendo a diferentes modelos de classificação. Este trabalho pretende fazer um estudo relativamente à construção de árvores de decisão utilizando diferentes técnicas de pré-poda, que têm como finalidade melhorar a qualidade de um classificador. Assim, com a utilização de uma Base de Dados (BD) real ligada à área do ensino, referente a escola secundaria Conde de Monsaraz, à qual pertence ao agrupamento vertical de Escolas de Reguengos de Monsaraz, são feitas várias experiências com diferentes critérios de paragem, obtendo como resultado duas Matrizes de Confusão (MC) referentes aos dados de treino e de teste. Assim, a utilização de indicadores como o Recall e a Especificity, que são adequados ao problema em causa, possibilitam a quantificação do erro do classificador. No final das experiências obtém-se um gráfico que corresponde ao valor do indicador vs o critério de paragem utilizado. Desta forma, o resultado deste gráfico são duas curvas, uma associada aos dados de treino e outra associada aos dados de teste. Palavras-chave: Árvore de decisão, Poda, Pré-poda, Classificação, Matriz de Confusão. iv Abstract Decision trees are widely used as inference tools in areas such as Data Extraction, due to their efficiency in producing classifiers. Their ability to partition the attribute space into subspaces labeled with class values. This work aims at studing the construction of decision trees using different pruning techniques to improve the quality and the efficiency of a classifier. We shall apply the methodology to real Databases connected to the teaching area, namely the secondary school Conde de Monsaraz. Several experiments were carried out with different stopping criteria, to provide two Confusion Matrices (for the training and test dataset) that enable the accuracy of the method. More specifically, indicators such as Recall and Especificity are appropriate to our real problem for quantifying the classifier error. At the end of the experiments, a figure displays the correspondance of the indicator vs. the stopping criterion threshold and provide two curves that give a prediction of the most effective decision tree. keywords:Decision tree, Pruning, Pre-pruning, Classification, Confusion matrices. v Índice Geral 1 Introdução 1 1.1 Objetivos..................................... 2 1.2 Estrutura da Dissertação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Dados e árvores 4 2.1 AtributoseClasses................................ 4 2.2 Partição associada aos atributos . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.3 Árvores...................................... 8 2.4 Representação de partição com uma árvore . . . . . . . . . . . . . . . . . . . 11 3 Probabilidade e Teoria da Informação 14 3.1 Frequências.................................... 14 3.2 NoçãodeImpureza ............................... 16 3.2.1 Construção da função impureza . . . . . . . . . . . . . . . . . . . . . 18 3.3 Noção de Ganho da informação . . . . . . . . . . . . . . . . . . . . . . . . . 20 4 Árvore de decisão 24 4.1 Primeiroexemplo ................................ 24 4.1.1 Construção da árvore de decisão a partir do primeiro nível de partição . 24 4.1.2 Construção da árvore a partir do segundo nível de partição . . . . . . . 29 4.1.3 Construção da árvore a partir do terceiro nível de partição . . . . . . . 36 4.1.4 Poda elementar da árvore . . . . . . . . . . . . . . . . . . . . . . . . 41 4.2 Segundoexemplo ................................ 43 4.2.1 Primeiro nível de partição . . . . . . . . . . . . . . . . . . . . . . . . 43 vi ÍNDICE GERAL vii 4.2.2 Segundo nível de partição . . . . . . . . . . . . . . . . . . . . . . . . 45 4.2.3 Terceiro nível de partição . . . . . . . . . . . . . . . . . . . . . . . . 49 4.2.4 Poda elementar da árvore . . . . . . . . . . . . . . . . . . . . . . . . 51 5 Qualidade da Árvore 54 5.1 MatrizdeConfusão(MC) ............................ 54 5.2 Exemplos..................................... 55 5.2.1 PrimeiroExemplo ............................ 55 5.2.2 SegundoExemplo ............................ 58 6 Poda 61 6.1 Utilização de métodos de Poda em árvores de decisão . . . . . . . . . . . . . 61 6.2 TécnicasdePré-poda .............................. 62 6.3 Aplicações usando critérios de pré-poda . . . . . . . . . . . . . . . . . . . . . 63 6.3.1 Árvore de decisão sem poda . . . . . . . . . . . . . . . . . . . . . . . 64 6.3.2 Poda utilizando o critério de Profundidade máxima . . . . . . . . . . . 67 6.3.3 Poda utilizando o critério de percentagem mínima de elementos num nó 68 6.3.4 Poda utilizando o critério de percentagem mínima em um nó filho . . . 70 6.3.5 Poda utilizando o critério de impureza mínima . . . . . . . . . . . . . 72 7 Aplicação 76 7.1 Análisedosresultados .............................. 76 7.1.1 Descrição da base de dados . . . . . . . . . . . . . . . . . . . . . . . 76 7.1.2 Análise dos resultados em relação ao parâmetro de profundidade . . . . 77 7.1.3 Análise dos resultados em relação ao parâmetro de impureza . . . . . . 78 7.1.4 Análise dos resultados em relação ao parâmetro de percentagem mínima deelementosnumnó .......................... 79 8 Conclusões 81 Bibliografia 84 9 Anexos 85 Capítulo 1 Introdução Atualmente com o aumento do volume de dados gerados em diferentes ramos de atividade, surge a necessidade de serem criadas ferramentas computacionais mais complexas e independentes, capazes de a partir de experiências passadas, criar hipóteses que possam resolver um determinado problema. A tais experiências dão-se o nome de ECD. Assim, as Organizações, têm a vantagem de, a partir da ECD, poderem tomar melhores decisões, com vista a rever decisões anteriores, elaborar estratégias para tomada de decisões futuras, obter melhor conhecimento sobre os dados da organização, entre outras. A área de ECD apresenta vários métodos para extrair informações, designadamente a classificação,associação, clustering, padrões sequenciais, regressão e detecção de desvios. Neste trabalho, abordaremos sobre o método de classificação. Este método permite obter padrões através da construção de classificadores e, neste caso em particular, as árvores de decisão como uma técnica de representação do conhecimento contido no conjunto de dados analisado. As árvores de decisão são ferramentas poderosas de classificação consideradas como uma das técnicas mais eficientes aplicadas em vários campos científicos, tais como Machine Learning e Inteligência Artificial [EMS02][Qui86]. Elas permitem, com base num conjunto de atributos extremamente diversificados, classificar populações, eventos, produtos, e posteriormente auxiliar na tomada de decisões [Loh11]. Uma árvore de decisão utiliza, uma estratégia 1 2CAPÍTULO 1. INTRODUÇÃO de dividir-para-conquistar, onde um problema complexo é decomposto em sub-problemas mais simples. Por sua vez, esta estratégia é aplicada recursivamente a cada sub-problema. Áreas como: •A Saúde: na aprendizagem de diagnósticos médicos,no controlo de gastos hospitalares, entre outros; •As Finanças: na aprendizagem e avaliação do risco de crédito dos solicitantes de empréstimo entre outros; •A Astronomia: em observações atmosféricas, em análise de informações espaciais; •A Agricultura: na identificação de doenças em produções agrícolas; •A Gestão de recursos e muitas outras, utilizam as árvores de decisão, devido à sua flexibilidade, robustez, facilidade de compreensão e velocidade de processamento. 1.1 Objetivos 1. Fazer um estudo sobre as várias técnicas de construção de árvores de decisão nas diferentes literaturas apresentadas, para perceber o contexto e expor vantagens em relação a técnicas de Poda adequadas, tomando em conta o tipo de dados específicos da área do ensino. 2. Desenvolver uma script para construção de árvore de decisão usando linguagem de programação Python e a biblioteca scikit-learn para análise dos dados. 1.2 Estrutura da Dissertação Para além do presente capítulo, esta dissertação está organizada em mais 7 capítulos, nomeadamente: 1.2. ESTRUTURA DA DISSERTAÇÃO 3 Capítulo 2, que fornece alguns conceitos básicos muito utilizados acerca dos dados, tais como a informação, os atributos e as classes. Apresenta-se, igualmente, as noções de níveis de partição associados a atributos, árvore e grafos. No Capítulo 3, são apresentadas as funções de impureza, bem como a noção de frequência e a classificação do melhor atributo por meio do ganho de informação. No Capítulo 4, por meio de dois exemplos, são construídas árvores de decisão, utilizando o ganho como argumento para a construção das mesmas. É também apresentado neste capítulo, a poda elementar utilizando critérios simples, como nós puros ou nós sem elementos. Capítulo 5, em que se aborda sobre a quantificação do erro da árvore de decisão utilizando a MC e indicadores. Para o efeito são usados dados de treinamento e de teste. Capítulo 6, em que se apresenta o uso da poda de uma árvore de decisão, em particular o método de pré-poda e, os seus respetivos critérios de paragem. As aplicações da técnica de árvores de decisão são detalhadas no Capítulo 7, onde é apresentada a aplicação do modelo de classificação, utilizando uma BD da área do ensino. Por fim, no capítulo 8 apresentam-se as conclusões finais do trabalho. Capítulo 2 Dados e árvores No presente trabalho consideram-se dados como sendo equivalente a informação. Os dados podem aparecer em formas diversificadas e esta diversidade torna-os mais ricos e complexos. Um conjunto de dados ou "dataset" é um conjunto de dados normalmente organizado em tabelas. Por cada elemento indicam-se várias características. Cada coluna representa uma variável particular. Cada linha corresponde a um determinado membro do conjunto de dados em questão. Cada valor é conhecido como um dado. O conjunto de dados pode incluir dados para um ou mais membros, correspondente ao número de linhas. Ou seja, Um conjunto D de dados é caracterizado por d(t)=(t, x(t), c(t)), onde: •té o índice, t= 1, ..., N •d(t)é uma ocorrência constituída por: x(t)=(x1(t), x2(t), ..., xI(t)) são as variáveis ou atributos e também são considerados como dados de entrada(input) c(t)é a classe, que é considerada como dado de saída(output) 2.1 Atributos e Classes Chamaremos A a um atributo, quando se tratar de dados de entrada(input) e C a uma classe quando se tratar de dados de saída(output). 4 2.1. ATRIBUTOS E CLASSES 5 Figura 2.1: Atributo-Classe Sejam A1, A2, ..., AI, um conjunto de atributos, notamos por A=A1×A2, ..., ×AI, e C uma classe. Para cada valor de xi, temos um conjunto Ai de J valores: Ai={ai1, ai2, ...aij , ..., aiJ }. Para a classe C, temos um conjunto de Kdecisões: C=c1, ..., ck, ..., cK Exemplo1: Dada a tabela 2.1 onde, a última coluna representa a classe: Tabela 2.1: Tab.Eventos NoSexo TrabalhoM TrabalhoP RazãoEsEscola ApoioEF 1 F Em casa Professor Curso Não 2 F Em casa Outro Curso Sim 3 F Em casa Outro Outro Não 4 F Saúde Serviços Casa Sim 5 F Outro Outro Casa Sim 6 M Serviços Outro Reputação Sim 7 M Outro Outro Casa Não 8 F Outro Professor Casa Sim 9 M Serviços Outro Casa Sim 10 M Outro Outro Casa Sim 11 F Professora Saúde Reputação Sim 12 F Saúde Outro Reputação Sim 13 M Serviços serviços Curso Sim 14 M Saúde Outro Curso Sim 15 M Professora Outro Casa Sim 6CAPÍTULO 2. DADOS E ÁRVORES os atributos são: A1= {F, M}, J= 2; A2= {Em casa, Saúde, Outro, Serviços, Professora}, J= 5; A3= {Saúde, Outro, Serviços, Professor}, J= 4; A4= {Curso, Outro, Casa, Reputação, }, J= 4; C= {Sim, Não}, K= 2. Exemplo2: Neste exemplo temos a tabela 2.2, na qual os valores são numéricos: Tabela 2.2: Tab.Eventos só com atributos NoTEstudo TEscolaCasa TLivres RFamiliar NAcademiPai 1 2 2 3 4 4 2 2 1 3 5 1 3 2 1 3 4 1 4 3 1 2 3 2 5 2 1 3 4 3 6 2 1 4 5 3 7 2 1 4 4 2 8 2 2 1 4 4 9 2 1 2 4 2 10 2 1 5 5 2 11 2 1 3 3 4 12 3 3 2 5 4 13 1 1 3 4 1 14 2 2 4 5 4 15 1 1 5 4 3 e os atributos são: A1= {1, 2, 3}, J= 3 (Referente a TEstudo); A2= {1, 2, 3}, J= 3 (Referente a TEscolaCasa); A3= {1, 2, 3, 4, 5}, J= 5 (Referente a TLivres); A4= {1, 2, 3, 4, 5}, J= 5 (Referente a RFamiliar); 2.2. PARTIÇÃO ASSOCIADA AOS ATRIBUTOS 7 A5= {1, 2, 3, 4}, J= 4 (Referente a NAcademiPai). Os atributos ou variáveis podem ser de natureza muito diversificada e podem ser classificados segundo[Mar07][McC98] em atributos qualitativos e quantitativos. Atributos qualitativos são aqueles cuja escala de medida apenas indica a sua presença em categorias de classificação discreta exaustivas e mutuamente exclusivas: Eles podem ser Nominais, binárias e Ordinais. •Nominais: é apenas uma lista não ordenada de valores que não tem qualquer ligação entre eles. Por exemplo, o atributo Sexo ={masculino, feminino} •Ordinais: são atributos constituídos por uma lista ordenada, segundo uma relação descritível mas não quantificável. Por exemplo, habilitações literárias={Básico, Secundário, Universitário} Atributos quantitativos: são atributos cuja escala de medida permite a ordenação e quantificação de diferenças entre elas. Podem ser: •intervalar: integram dados quantitativos, numa escala numérica com intervalos iguais, como por exemplo a temperatura medida em graus Celsius ou em graus Faherenheit. Estas escalas não possuem zero absoluto, isto é não possuem uma medida de ausência de atributo. •Razão: assumem uma escala numérica de valores quantitativos cuja relação exata entre estes é possível definir porque esta escala possui um zero absoluto , como por exemplo o peso ou altura. 2.2 Partição associada aos atributos Seja Dum conjunto de dados. Uma partição Pde Dé constituída de subconjuntos {D1, D2, ..., DN}tal que: 1. DiTDj=∅, i 6=j; 2. SN i=1 Di=D 8CAPÍTULO 2. DADOS E ÁRVORES Seja Aium atributo de valores, {ai1, ai2, ..., aij}: Dj= (x(t), y(t)). Onde y(t)são os valores das classes tal que, xi(t) = aij,i= 1, ..., I. j = 1, ..., N Por exemplo, a base de dados representada pela tabela 2.1, será particionada pelo atributo; A1={F, M}a11 =F, a12 =MeP={D1, D2}D1={1,2,3,4,5,8,11,12}D2= {6,7,9,10,13,14,15} A partir dos subconjuntos D1, D2, podem ser feitas outras partições. Para isso são particionadas cada uma das partições com um outro atributo da base de dados, tendo assim um segundo nível de partição. Neste caso, a partição D1do exemplo anterior, será particionada pelo atributo: A4={Curso, Casa, Reputação, outro}com os valores a41 =Curso, a42 =Casa, a43 = reputação, a44 =Outro. Assim sendo, teremos as seguintes partições: D11 ={1,2},D12 ={4,5,8},D13 ={11,12},D14 ={3} A partição D2será particionada, com o atributo: A2={Em casa, Saúde, Outro, Serviços, Professora} com a21 =Em casa, a22 =Saúde, a23 =outro, a24 =Serviços, a25 =Professora Assim sendo, teremos as seguintes partições: D21 =∅,D22 ={14},D23 ={7,10},D24 ={6,9,13},D25 ={15} 2.3 Árvores Antes de começarmos a falar de árvore, vamos entender o que é um grafo. Um Grafo é uma estrutura de dados não linear, constituído por nós ou vértices e arestas ou ramos, G= (V, A), 2.3. ÁRVORES 9 em que V representa o vértice e A representa a aresta. No qual os vértices ou nós representam dados tais como: Pessoas, Cidades, números etc. e as arestas representam a existência de ligações entre nós. Os grafos geralmente podem ser representados de várias formas, uma delas é a que vemos na figura abaixo: Figura 2.2: Um grafo com 5 vértices e 6 arestas 10 CAPÍTULO 2. DADOS E ÁRVORES Na figura 2.2, considerou-se um grafo com cinco vértices e seis arestas, na qual 5 vértices são não orientados: A1={v1v5}={v5v1};A2={v1v4}={v4v1};A4={v1v2}={v2v1};A5= {v2v3}={v3v2};A6={v3v4}={v4v3}, e um vértice que é orientado: A3={v3v1} 6= {v1v3}. Entre as diferentes estruturas que podem ser representadas por um grafo, está a Árvore, entendida como um grafo sem ciclo que têm uma origem, o nó raiz. Os nós situados a uma distância n chamam-se nós de nível n e os nós que não possuem ramos são chamados de nó folha ou nó terminal. Há diversas formas de representação de uma árvore: hierárquica, diagrama de inclusão, diagrama de barras, numeração por níveis, entre outras. Neste trabalho usaremos a forma hierárquica, representada como na figura 2.3: Figura 2.3: árvore 3.2. NOÇÃO DE IMPUREZA 17 impureza, que vai avaliar ou quantificar a quantidade de informação que estamos a perder quando passamos a esta transformação. Seguidamente, é mostrado um exemplo de como quantificar estas perdas, utilizando F como o conjunto de informação macroscópica. Figura 3.1: Níveis de impureza 18 CAPÍTULO 3. PROBABILIDADE E TEORIA DA INFORMAÇÃO Na figura 3.1, temos três situações diferentes de quantificação de impureza: 1. pF= 1 epM= 0 logo, não há perda de informação porque a classificação é pura, todos os elementos do conjunto pertencem a uma única classe ; 2. pF=2 3epM=1 3, logo, o nível de impureza é médio e há uma perda média de 1 3da informação; 3. pF=pM=1 2, atingiu o nível de impureza máximo, visto que estamos a perder metade da informação. É considerada a pior situação. 3.2.1 Construção da função impureza Nesta secção, quantificaremos a noção de impureza na base das frequências. Dado E, um subconjunto da base de dados, a partir deste subconjunto podemos construir E1, E2, ..., EK, onde são associadas probabilidades p1, p2, ..., pK. Desta matéria, vamos construir uma nova informação, a impureza e que, será representada por três funções: 1. A entropia é dada pela fórmula: IE(E) = − K X k=1 (pklog2pk) onde, Eé o conjunto de amostras, pké a frequência de cada valor da classe, e K é o número de classes; 2. Índice de Gini é dado pela fórmula: IG(E)=1− K X k=1 p2 k onde Kepkrepresentam o que foi referenciado no item anterior; 3. Misclassification, é dada pela fórmula: IM(E)=1−max(p1, ..., pK) . 3.2. NOÇÃO DE IMPUREZA 19 Em seguida, representamos graficamente estas três medidas de impureza considerando que K= 2, assim, p1+p2= 1 então, p2= 1 −p1. Considerando pi,onde, i = 1,2, .. teremos: Para a Entropia teremos: IE(E) = −p1ln2p1−p2lg2p2, teremos: IE(E) = −p1lg2p1. Para o Índice Gini teremos:IG(E)=1−p2 1−(1 −p1)2= 2p1(1 −p1). Para o Misclassification teremos: IM(E)=1−max(p1, p2)=(p1,1−p1) Sendo assim, a baixo é apresentado o gráfico no qual estão presentes as três funções: Figura 3.2: Funções de Impureza(adaptado de [GCF+15]) 20 CAPÍTULO 3. PROBABILIDADE E TEORIA DA INFORMAÇÃO Em seguida, apresentamos exemplos, em que utilizaremos as três funções de impureza. Em um primeiro exemplo, utilizaremos o quinto atributo da tabela 2.1, que para este caso é a classe com dois valores Sim(S) e Não(N). Utilizando as frequências obtidas a partir da tabela 3.1, em que, pS=4 5epN=1 5. Assim, temos as seguintes funções: Entropia:−(4/5) log2(4/5) −(1/5) log2(1/5) = 0.721; Índice Gini:1−(4/5)2−(1/5)2= 0.4; Misclassification:1−max(4/5,1/5) = 0.2 Para um segundo exemplo, utilizamos a classe nível de segurança da escola, tirada da base de dados sobre o desempenho dos alunos. Esta possui 365 eventos e a classe tem cinco valores que são: Bom, Mau, Muito bom(MB), péssimo(PS) e Razoável(RZ). Calculando as frequências: pBom = 271/365 = 0.742; pMau = 13/365 = 0.036; pMB = 39/365 = 0.107; pP S = 14/365 = 0.038; pRZ = 28/365 = 0.077 Desta forma, calculando as funções teremos: Entropia:−(0.742) log2(0.742) −(0.036) log2(0.036) −(0.107) log2(0.107) − (0.038) log2(0.038) −(0.077) log2(0.077) = 1.2995; Índice Gini:1−(0.742)2−(0.036)2−(0.107)2−(0.038)2−(0.077)2= 0.4287; Misclassification:1−max(0.742,0.036,0.107,0.038,0.077) = 0.2575. 3.3 Noção de Ganho da informação Como vimos anteriormente, utilizamos os atributos para definir partições e as classes para definir probabilidades ou frequências. Nesta secção, vamos escolher um atributo, através do qual faremos uma partição e desta partição calcular qual é o ganho de informação relacionado a este atributo ou partição. Assim sendo, comecemos por definir o ganho associado a uma partição: Seja um conjunto D, que representa o atributo tempo, particionado em dois conjuntos: o conjunto Sol e o conjunto Chuva. O ganho de informação relacionado ao melhor agrupamento 3.3. NOÇÃO DE GANHO DA INFORMAÇÃO 21 de Sim(S) e Não(N) deste atributo é representado da seguinte forma: G(D) = I(D)−Ifinal(Tempo) A impureza final é calculada pela fórmula: Ifinal(Tempo) = |Sol| |D|∗I(Sol) + |Chuva| |D|∗I(Chuva) e a impureza inicial é calculada a partir da fórmula da entropia vista anteriormente: I(D) = − 2 X k=1 (pklog2pk) onde, k∈ {S, N}. Tendo os conjuntos D={17S, 13N}, Sol ={11S, 6N}, Chuva ={6S, 7N}, podemos calcular o ganho do atributo Tempo como se segue: Primeiramente calculamos as frequências de cada um deles: pS(D) = 17 30;pN(D) = 13 30;pS(Sol) = 11 17;pN(Sol) = 6 17;pS(Chuva) = 6 13; pN(Chuva) = 7 13 e q(Sol) = 17 30;q(Chuva) = 13 30 onde, q(Sol)e q(Chuva)são as frequências de Sol e chuva em 30 dias. Assim: I(D) = −17 30 log 17 30 −13 30 log 13 30 = 0,987 . I(Sol) = −11 17 log 11 17 −6 17 log 6 17 = 0,936 . I(Chuva) = −6 13 log 6 13 −7 13 log 7 13 = 0,996 Logo: I(Tempo) = 0,936 ∗17 30 + 0,996 ∗13 30 = 0,962 22 CAPÍTULO 3. PROBABILIDADE E TEORIA DA INFORMAÇÃO G(Tempo) = 0,987 −0,962 = 0,025 No exemplo anterior, classificamos o atributo tempo mediante uma classe binária (Sim e Não). Neste exemplo, classificaremos os alunos, que estão representados pelo atributo Sexo, com valores Feminino(F) e Masculino(M). Esta classificação será com base nas notas do primeiro período, utilizando assim uma classe multi-nominal que possui quatro valores: Péssimo(PS), Mau, Bom e Muito Bom(MB). Assim, os valores serão classificados com base nas ocorrências escritas na figura 3.3: Figura 3.3: Figura das ocorrências utizando uma classe com 4 valores 3.3. NOÇÃO DE GANHO DA INFORMAÇÃO 23 Como visto anteriormente, para calcularmos o ganho de informação de um atributo, precisamos saber quais são as frequências relacionas a cada uma das ocorrências. Assim, pP S(D) = 0; pMau(D) = 4 15;pBom(D) = 1 2;pMB(D) = 7 30;q(F) = 13 30;q(M) = 17 30;pP S(F) = pP S(M) = 0; pMau(F) = 3 13;pBom(F) = 8 13;pMB(F) = 2 13;pMau(M) = 5 17;pBom(M) = 7 17;pMB(M) = 5 17. Logo: I(D) = −4 15 log 4 15 −1 2log 1 2−7 30 log 7 30 = 1,498 I(F) = −3 13 log 3 13 −8 13 log 8 13 −2 13 log 2 13 = 1,407 I(M) = −5 17 log 5 17 −7 17 log 7 17 −5 17 log 5 17 = 1,565 Assim: I(Sexo) = 13 30 ∗1,407 + 17 30 ∗1,567 = 1,497 G(Sexo) = 1,498 −1,497 = 0,001 Capítulo 4 Árvore de decisão Neste capítulo, consolidamos o que estudamos nos capítulos anteriores, implementando assim a construção elementar de uma árvore de decisão, onde, iremos utilizar simplesmente o ganho como argumento para a construção da mesma. Para isso, utilizamos dois exemplos: 4.1 Primeiro exemplo Nesta secção veremos um primeiro exemplo em que usamos uma classe binária composta pelos elementos{Sim(S) e Não(N)}, correspondentes a frequência dos alunos em aulas de apoio. Dado um conjunto D= (x1, x2, x3;y), que contem 30 observações, onde, x1∈ A1={F, M};x2∈A2={[15,16] = Id1,[17,18] = Id2,[19,20] = Id3}eA3= {Muito Bom(MB),Bom,Razoável(Rz),Mau},y∈C={Sim, Não}. A1representa o atributo "Sexo", A2o atributo "Idade"e A3o atributo "Qualidade das relações com os colegas". 4.1.1 Construção da árvore de decisão a partir do primeiro nível de partição Para começar a construção da árvore de decisão, precisamos de calcular o ganho de cada um dos atributos, para podermos avaliar qual deles possui o melhor ganho, e desta forma, poder 24 4.1. PRIMEIRO EXEMPLO 25 determinar o primeiro nível de partição. Assim, para o atributo A1, os valores são classificados como se segue: Figura 4.1: Figura das ocorrências do atributo A1 26 CAPÍTULO 4. ÁRVORE DE DECISÃO Assim teremos as seguintes frequências: Tabela 4.1: Tab.Frequências de A1 q p1p2 D13/30 17/30 F13/30 6/13 7/13 M17/30 7/17 10/17 onde, qcorresponde a probabilidade de ocorrer F ou M nas 30 observações. Por conseguinte, calculando as impurezas teremos: I(D) = −13 30 log2 13 30 −17 30 log2 17 30 = 0,987 I(F) = −6 13 log2 6 13 −7 13 log2 7 13 = 0,996 I(M) = −7 17 log2 7 17 −10 17 log2 10 17 = 0,997 I(A1) = 13 30 ∗0,996 + 17 30 ∗0,977 = 0,986 Desta forma, o ganho associado ao atributo A1é: G(A1) = 0,987 −0,986 = 0,001 4.1. PRIMEIRO EXEMPLO 33 Figura 4.7: Figura das ocorrências de Id2em relação ao atributo A3 Os valores correspondentes das frequências de Id2estão representados na tabela 4.9. Tabela 4.9: Tab.Frequências de Id2em relação a A3 q p1p2 D8/13 5/13 MB 8/13 5/8 3/8 Bom 1/13 1 0 Rz 3/13 2/3 1/3 Mau 1/13 0 1 Fazendo o cálculo dos ganhos, teremos os seguintes resultados: Tabela 4.10: Tab.Ganhos referentes a Id2em relação a A3 Id2Impurezas Ganhos A10,927 0,034 A30,799 0,162 Onde podemos constatar, que Id2têm o melhor ganho no atributo A3 Id3em relação a A1: 34 CAPÍTULO 4. ÁRVORE DE DECISÃO Figura 4.8: Figura das ocorrências de Id3em relação ao atributo A1 Os valores correspondentes ás frequências de Id3, são: Tabela 4.11: Tab.Frequências de Id3 qp1p2 D1/4 3/4 F1/2 1/2 1/2 M1/2 0 1 Id3, em relação a A3: Figura 4.9: Figura das ocorrências de Id3em relação ao atributo A3 4.1. PRIMEIRO EXEMPLO 35 Os valores correspondentes ás frequências de Id3, estão representados na tabela 4.12. Tabela 4.12: Tab.Frequências de Id3em relação aA3 q p1p2 D1/4 3/4 MB 5/8 2/5 3/5 Bom 1/8 0 1 Rz 1/8 0 1 Mau 1/8 0 1 Fazendo o cálculo dos ganhos, teremos os seguintes resultados: Tabela 4.13: Tab.Ganhos referentes a Id3em relação a A3 Id3Impurezas Ganhos A10,75 0,061 A30,607 0,204 36 CAPÍTULO 4. ÁRVORE DE DECISÃO Onde podemos constatar que Id3, tem o melhor ganho também no atributo A3 Assim, podemos concluir que, para os três nós, o atributo A3é o que teve o melhor ganho. No entanto, daremos continuidade à construção da árvore a partir deste atributo. 4.1.3 Construção da árvore a partir do terceiro nível de partição Dando continuidade à construção da árvore, para o terceiro nível estará disponível apenas o atributo A1. Portanto, não precisamos de calcular o ganho e a entropia, porque não teremos outra escolha se não a deste atributo. Como nos casos anteriores, há a necessidade de se fazer a classificação dos valores de A3 em relação a A1. Assim, ao fazer a classificação dos valores, teremos dose sub-árvores, em que faremos a apresentação de apenas quatro delas referentes ao nó Id1, visto que se mantém a estrutura e diferenciam-se somente os valores. Figura 4.10: Figura das ocorrências de MB em relação A1no nó Id1 4.1. PRIMEIRO EXEMPLO 37 Para ás frequências, temos os seguintes valores: Tabela 4.14: Tab.Frequências de MB em relação a A1no nó Id1 q p1p2 D1/3 2/3 F1/2 1/3 2/3 M1/2 1/3 2/3 Bom em relação a A1no nó Id1teremos a seguinte classificação: Figura 4.11: Ocorrências de Bom em relação A1no nó Id1 Valores das frequências: Tabela 4.15: Tab.Frequências de Bom em relação a A1no nó Id1 q p1p2 D0 1 F0 0 0 M1 0 1 Rz em relação a A1no nó Id1teremos a seguinte classificação: 38 CAPÍTULO 4. ÁRVORE DE DECISÃO Figura 4.12: Figura das ocorrências de Rz em relação a A1no nó Id1 Valores das frequências: Tabela 4.16: Tab.Frequências de Rz em relação a A1no nó Id1 q p1p2 D1/2 1/2 F0 0 0 M1 1/2 1/2 Mau em relação a A1no nó Id1temos a seguinte classificação: 4.1. PRIMEIRO EXEMPLO 39 Figura 4.13: Figura das ocorrências de Mau em relação a A1no nó Id1 Valores das frequências: Tabela 4.17: Tab.Frequências de Mau em relação a A1no nó Id1 q p1p2 D0 0 F0 0 0 M0 0 0 Conforme foi dito na secção anterior, já não haverá continuidade da construção da árvore porque temos apenas um atributo por classificar. Assim, obtivemos a seguinte árvore de decisão: 40 CAPÍTULO 4. ÁRVORE DE DECISÃO Figura 4.14: Árvore completa Depois de construída a árvore, é preciso contabilizar o número total de nós, o número total de ramos e o número total de folhas que ela contem, pois este procedimento permite saber a dimensão da nossa árvore e, posteriormente, permite avaliar a complexidade de determinar o número de ramos ou de folhas que são necessários para fazer a predição baseada nesta árvore. Em seguida teremos os elementos caraterísticos da árvore, representados na tabela abaixo: Tabela 4.18: Elementos característicos da árvore Node Nós Node Ramos Node Folhas 40 39 24 4.1. PRIMEIRO EXEMPLO 41 4.1.4 Poda elementar da árvore Nesta subsecção, podamos a árvore inicial, ou seja, fazemos uma primeira poda com critérios simples, que nos possibilitam eliminar alguns ramos que dão a um nó puro ou a um nó que não tenha elementos. Desta forma, estaremos perante dois critérios: •O nó que Não tem elementos e não vale a pena continuar a particionar; •Quando o nó é puro, não vale a pena continuar a particionar porque já temos toda a informação de que precisamos neste nó. Assim, este processo tem, como consequência, a redução da árvore, em que teremos algumas folhas de nível dois e algumas de nível três. Figura 4.15: Árvore podada Como feito anteriormente, vamos contabilizar o número total de nós, ramos e folhas da árvore podada: Tabela 4.19: Elementos característicos da árvore Node Nós Node Ramos Node Folhas 26 25 17 42 CAPÍTULO 4. ÁRVORE DE DECISÃO Para concluir este exemplo, vamos calcular o ganho total da árvore de decisão podada, a partir da diferença da entropia entre o nó inicial e todos os nós finais. Para isto, começaremos por determinar as frequências de todas as folhas: Tabela 4.20: Frequência das folhas em relação ao ramo Id1 (a) q p1p2 MB(F) 1/10 1/3 2/3 MB(M) 1/10 1/3 2/3 (b) q p1p2 Rz(F) 0 0 0 Rz(M) 1/15 1/2 1/2 Tabela 4.21: Frequência das folhas em relação ao ramo Id2 (a) q p1p2 MB(F) 2/15 3/4 1/4 MB(M) 2/15 1/2 1/2 (b) q p1p2 Rz(F) 1/30 0 1 Rz(M) 1/15 1 0 Em relação ao ramo Id3, as as funções de impureza serão iguais a 0. Visto que todas folhas são nós puros. Assim, efetuando o cálculo da entropia das folhas teremos que: I(Folhas) = 1 10 ∗0,918 + 1 10 ∗0,918 + 1 15 +2 15 ∗0,811 + 2 15 = 0,492. A impureza inicial têm como valor I(D) = 0,987. Logo, G(Total)=0,987 −0,492 = 0,495 4.2. SEGUNDO EXEMPLO 49 Nó número (4): Para este nó, o ganho é igual a 0, tanto na classificação para o atributo A1, como para o atributo A2. Consequentemente, não há ganho neste nó e não vale a pena continuar a ramificar a árvore nele. Assim, para este caso, chegamos á conclusão de que o atributo A2é o atributo com melhor ganho nos três nós. Logo, daremos sequência na construção da árvore a partir deste atributo. 4.2.3 Terceiro nível de partição Para este nível, resta apenas o atributo A1, logo, não há necessidade de calcularmos o ganho, visto que não haverão outros atributos disponíveis a serem classificados. Assim, faremos a classificação dos valores de A2, em relação a A1. Ao fazer a classificação dos valores, teremos nove sub-árvores a partir do segundo nível de partição. Mas serão apresentadas apenas três referentes ao valor MB. (a) MB(Id1)(b) MB(Id2) (c) MB(Id3) Figura 4.17: Ocorrências de MB em relação ao atributo A1 50 CAPÍTULO 4. ÁRVORE DE DECISÃO Tendo como frequências os seguintes valores: MB Id1Id2Id3 qpqpqp F 11/17 7/11 1/11 3/11 1/2 3/5 2/5 0 2/5 1/4 3/4 0 M 6/17 1/6 1/3 1/2 1/2 3/5 1/5 1/5 3/5 1/3 1/3 1/3 Tabela 4.35 Como já não haverá continuidade da construção da árvore, visto que temos apenas um atributo por classificar. Assim, teremos a seguinte árvore de decisão: Figura 4.18: Árvore Completa2 4.2. SEGUNDO EXEMPLO 51 Em seguida teremos os elementos caraterísticos da árvore, representados na tabela abaixo: Tabela 4.36: Elementos característicos da árvore Node Nós Node Ramos Node Folhas 32 31 19 4.2.4 Poda elementar da árvore Nesta secção, vamos podar a árvore inicial, conforme foi explicado na secção 4.1.4 do exemplo anterior. Onde, teremos a seguinte árvore: Figura 4.19: Árvore Podada2 52 CAPÍTULO 4. ÁRVORE DE DECISÃO Em seguida, contabilizamos o número total de nós, ramos e folhas da árvore podada: Tabela 4.37: Elementos característicos da árvore Podada Node Nós Node Ramos Node Folhas 28 27 17 Para terminar este exemplo, calculamos o ganho total da árvore de decisão. Começamos por determinar as frequências de todas as folhas de nível três: Tabela 4.38: Frequência das folhas em relação ao ramo MB (a) q p Id1(F) 11/60 7/11 1/11 3/11 Id1(M) 1/10 1/6 1/3 1/2 (b) q p Id2(F) 1/12 3/5 2/5 0 Id2(M) 1/12 3/5 1/5 1/5 (c) q p Id3(F) 1/15 1/4 3/4 0 Id3(M) 1/10 1/3 1/3 1/3 Tabela 4.39: Frequência das folhas em relação ao ramo Bom (a) q p Id1(F) 1/60 1 0 0 Id1(M) 1/30 1/2 1/2 0 (b) q p Id2(F) 1/30 1 0 0 Id2(M) 1/30 1/2 1/2 0 (c) q p Id3(F) 1/20 1/3 2/3 0 Id3(M) 1/60 1 0 0 4.2. SEGUNDO EXEMPLO 53 Para o ramo Rz, teremos apenas frequências relacionadas ao ramo Id1. Tabela 4.40: Frequência das folhas em relação ao ramo Rz q p Id1(F) 1/30 1 0 0 Id1(M) 1/20 1/3 2/3 0 Assim, fazendo o cálculo da entropia das folhas temos: I(Folhas) = 11 60 ∗1,240 + 1 10 ∗1,459 + 1 12 ∗0,971 +1 12 ∗1,370 + 1 15 ∗0,811 + 1 10 ∗1,584 +1 30 +1 30 +1 20 ∗0,918 + 1 20 ∗0,918 = 0,905. A impureza inicial têm como valor I(D)=1,391. Logo, G(Total)=1,391 −0,905 = 0,486 A partir dos dois exemplos, podemos notar que a poda elementar não reduz a complexidade da árvore inicial, ou seja, a árvore continuará a ter grandes dimensões. Para resolver este problema, é preciso tentar encontrar outros critérios para que se possa fazer uma poda mais eficiente. Estes critérios serão abordados com mais detalhes nos capítulos posteriores. Capítulo 5 Qualidade da Árvore Neste capítulo, quantificamos o erro da árvore de decisão, através da matriz de confusão. Utilizaremos os dois exemplos anteriores para a construção das duas matrizes.E em seguida serão propostos indicadores para determinar a percentagem de erro. 5.1 Matriz de Confusão(MC) A MC, é uma das formas que nos possibilita visualizar o desempenho de um classificador. Ela ilustra o número de predições corretas e incorrectas em cada classe. Para um determinado conjunto de dados, as linhas desta matriz representam as classes que são reais e as colunas, as classes preditas pelo classificador. Para J classes, teremos uma MC de dimensão J×J. Na tabela 5.1, podemos ver como é composta uma MC. Para este caso temos apenas duas classes: Tabela 5.1: Esquema de uma MC(adaptada de [GCF+15]) S(Sim) Predição N(Não) Predição S(Sim) Real TP(True Positive) FN(False Negative) N(Não) Real FP(False Positive) TN(True Negative) Onde: 54 5.2. EXEMPLOS 55 •TP, refere-se aos casos em que na base de dados real, o valor é positivo e o da predição também é positivo: •FN, o real é positivo, mas o predito é negativo: •TN, o real é negativo e o predito também é negativo: •FP, o real é negativo, mas o predito é positivo. Assim, seja D uma base de dados, dela vamos retirar dois subconjuntos distintos. Um primeiro subconjunto que se chamará DT raining e um segundo que se chamará DT est. O DT raining é o subconjunto que usaremos para construir a árvore de decisão. Desta maneira, construímos dois tipos de MC. Uma que vai reutilizar o DTraining e a outra que utilizará o DT est. Por conseguinte, cada MC pode gerar um erro com naturezas diferente. Com o DTraining, encontramos o In Sample Error(ISR). Neste tipo de erro, utilizamos a MC, para comparar os dados reais com os dados da predição usando o DTraining. E para o DTest, encontramos o Out Sample Error(OSE), que também usa a matriz de confusão para comparar os dados reais com os dados da predição, mas, usando o conjunto de dados DTest. 5.2 Exemplos Nesta secção, apresentamos dois exemplos: no primeiro exemplo usamos uma classe binária e no segundo usamos uma multi-classe com 3 valores. 5.2.1 Primeiro Exemplo Em sequência, utilizamos os dados do primeiro exemplo da secção 4.1, onde temos uma base de dados composta pelos 30 primeiros eventos do conjunto D(chamamos esta base de dados de DTraining) e uma classe binária composta por {Sim(N) e Não(N)}, classificada em 13Se17N. Para o DTest, utilizamos 39 eventos, que têm origem também do conjunto D, começando de 101 −140 eventos. Este subconjunto é classificado em 19Se20N. Desta forma, tendo os dados dos dois subconjuntos, podemos calcular as duas MC. A primeira será calculada com o DTraining e a segunda com DTest. 56 CAPÍTULO 5. QUALIDADE DA ÁRVORE Assim, comparando os valores de S e N, da árvore de decisão da figura 4.15(Predição), com os do DTraining e do DTest, obtemos as seguintes MC: Tabela 5.2: MC com DTraining S (Predição) N (Predição) S (Real) 11 2 N (Real) 3 14 Tabela 5.3: MC com DTest S (Predição) N (Predição) S (Real) 7 12 N (Real) 6 14 Em seguida, a partir destas MC, criamos indicadores, que quantificarão o erro da árvore. Os indicadores utilizados com mais frequência são: 1. Accuracy, indicador usado em BD com o mesmo número de exemplos para cada classe e também, quando as penalidades de acertos e erros para cada classe forem as mesmas. Aaccuracy pode ser definida como na fórmula abaixo: Accuracy =TP +TN n. onde, n é o número total de exemplos. 2. Precision, número de exemplos que são previstos pertencerem a uma classe e que realmente são dessa classe. A precisão, pode ser definida como: Precision =TP TP +FP 3. Recall, frequência em que o classificador encontra os exemplos numa classe. Ou seja, quando um exemplo é realmente de uma determinada classe: o quão frequente é classi- 5.2. EXEMPLOS 57 ficado como sendo dessa classe. O recall pode ser definido como: Recall =TP TP +FN 4. F1 Score, combina a precision e o recall, de modo a trazer um número único que indique a qualidade geral do modelo de classificação. Este indicador tem melhor funcionamento em base de dados com classes desproporcionais. O F1 Score pode ser definido como: F1Score =2∗(Precision ∗Recall) Precision +Recall 5. Especificity, indicador que mostra a proporção de TN, ou seja, a capacidade do classificador para dizer correctamente a ausência da condição para casos que realmente não a tem. A Especificidade pode ser definida como: Especificity =TN TN +FP . Ao escolher um indicador, deve-se ter em conta factores como a proporção de dados de cada classe no conjunto de dados e, principalmente qual o objectivo da aplicação prática do modelo de classificação. Para o nosso modelo, estamos a classificar o desempenho dos alunos quanto à frequência em aulas de apoio ou explicações fora da sala de aulas. O erro mais significativo para este caso, consiste no facto de o classificador prever que o aluno não frequenta aulas de apoio, mas a Base de dados dizer o contrario, ou seja, que frequenta. Assim, para este caso é mais importante minimizar os FN. Logo, podemos escolher o Recall como nosso indicador. Para a MC do DT raining, temos: RecallT raining =11 11 + 2 = 0,846. Para a MC do DT est, temos: RecallT est =7 7 + 12 = 0,333. 58 CAPÍTULO 5. QUALIDADE DA ÁRVORE Ao avaliarmos o classificador por meio do Recall, devemos ter em conta que este terá um resultado satisfatório quando está próximo de 1. Ou seja quanto mais ele se aproximar de 0, o resultado não é satisfatório. Assim, podemos observar pelos resultados acima, que a MC da base de dados do DT est tem um valor muito baixo de Recall, isto significa que o nosso classificador não esta a funcionar como deve ser. Achamos que a razão para este mau funcionamento, se deva ao facto de não utilizarmos um número suficiente de dados para o training. Uma maneira de resolver este problema seria fazer o training com muito mais dados. E é isto que faremos no capítulo a seguir. Podemos também utilizar o indicador Specificity, que é o complementar do Recall, onde minimizaremos os FP. Consequentemente, utilizando a MC do DT raining, obtivemos: SpecificityT raining =14 14 + 3 = 0,824. Utilizando a MC do DT est, temos: SpecificityT est =14 14 + 6 = 0,7. Assim, é possível verificar através dos dados acima, que para a Specificity os resultados dos dados de teste estão mais próximos de 1, do que os resultados dos dados de teste do Recall. O que indica que o classificador nos dados de teste está a funcionar melhor com aSpecificity. 5.2.2 Segundo Exemplo Em seguida, apresentamos o segundo exemplo, em que, utilizaremos os dados do segundo exemplo da secção 4.2. Temos uma base de dados composta pelos primeiros 60 eventos do conjunto D(DT raining), e as classes{B, M e E}, classificada em 34B, 17Me9E. Para o DT est, utilizamos outros 59 eventos, que também têm origem no conjunto D, mas que são diferentes do (DT raining). Este subconjunto é classificado em 31B, 19Me9E. Como estamos perante 3 classes, a construção da MC difere um pouco da MC com a classe binária. Neste caso, teremos uma matriz 3×3, os valores da diagonal principal constituem 6.3. APLICAÇÕES USANDO CRITÉRIOS DE PRÉ-PODA 65 Figura 6.1: Árvore com os parâmetros sem poda 66 CAPÍTULO 6. PODA Tabela 6.2: MC com os dados de treinamento S (Predição) N (Predição) S (Real) 34 12 N (Real) 23 31 Tabela 6.3: MC com os dados de teste S (Predição) N (Predição) S (Real) 7 8 N (Real) 7 8 Entretanto, para o nosso modelo, minimizamos os FN, utilizando o indicador Recall e a sua inversa, pelas mesmas razões que as do exemplo 5.2.1. Visto que a classe é a mesma. Para os dados de treinamento obtivemos, RecallT raining =34 34 + 12 = 0,739. EspecificityT raining =31 31 + 23 = 0.574 E para os dados de teste obtivemos, RecallT est =7 7+8 = 0,466. EspecificityT est =8 8+7 = 0.533 É de notar que os resultados são muito baixos, tanto para o recall dos dados de treinamento, como para o recall dos dados de teste. Assim, com esta experiência, estamos a ver que esta árvore, não vai funcionar bem e não vai oferecer grande possibilidade de melhoria, porque os atributos que estamos a utilizar não são muito diferenciadores. Desta maneira, os níveis de impureza continuam muito elevados mesmo ao nível das folhas. A razão para este problema deveu-se ao fato de os três atributos utilizados terem sido escolhidos aleatoriamente em um 6.3. APLICAÇÕES USANDO CRITÉRIOS DE PRÉ-PODA 67 conjunto de 49 atributos da base de dados. como consequência, nenhum deles está a ser capaz de diferenciar corretamente a informação. Para resolver este problema, precisamos de encontrar um outro tipo de atributo na base de dados. Para isso, calculamos o ganho de impureza em todos os atributos disponíveis na base de dados e verificamos qual deles tinha o nível de impureza mais baixo. Este processo é apresentado no próximo capítulo, onde, utilizaremos uma aplicação em python para agilizar o processo de busca e construção da árvore de decisão. 6.3.2 Poda utilizando o critério de Profundidade máxima Nesta secção, podamos á árvore de decisão, utilizando como critério da profundidade máxima, com o parâmetro dmax = 2 e, em seguida, fazemos as MC, para avaliação da qualidade da árvore. Assim obtivemos a seguinte árvore de decisão: Figura 6.2: Profundidade máxima dmax = 2 Tabela 6.4: MC com os dados de treinamento, utilizando o parâmetro dmax S (Predição) N (Predição) S (Real) 28 17 N (Real) 19 36 68 CAPÍTULO 6. PODA Tabela 6.5: MC com os dados de teste, utilizando o parâmetro dmax S (Predição) N (Predição) S (Real) 7 9 N (Real) 6 8 Calculando o Recall eEspecificity para os dados de treinamento, RecallT raining =28 28 + 17 = 0,622 EspecificityTraining =36 36 + 19 = 0.655. E calculando Recall eEspecificity para os dados de teste, RecallT est =7 7+9 = 0,466 EspecificityT est =8 8+6 = 0.571. 6.3.3 Poda utilizando o critério de percentagem mínima de elementos num nó Nesta secção, podamos á árvore de decisão, utilizando como critério de paragem a percentagem mínima de elementos num nó, com o parâmetro β= 0.10 e, em seguida, fazemos as MC, para avaliação da qualidade da árvore. Assim obtivemos a seguinte árvore de decisão: 6.3. APLICAÇÕES USANDO CRITÉRIOS DE PRÉ-PODA 69 Figura 6.3: Número mínimo de elementos em um nó Com está poda, avaliamos as consequências para os dados de treinamento e para os dados de teste, através das duas MC. E, por fim, as avaliações do Recall eEspecificity para ambas MC. Tabela 6.6: MC com os dados de treinamento, utilizando o parâmetro β S (Predição) N (Predição) S (Real) 30 15 N (Real) 22 33 Tabela 6.7: MC com os dados de teste, utilizando o parâmetro β S (Predição) N (Predição) S (Real) 4 11 N (Real) 7 8 70 CAPÍTULO 6. PODA Calculando o Recall eEspecificity para os dados de treinamento, RecallT raining =30 30 + 15 = 0,666 EspecificityTraining =33 33 + 22 = 0.6. E calculando o Recall eEspecificity para os dados de teste, RecallT est =4 4 + 11 = 0,266 EspecificityT est =8 8+7 = 0.533. 6.3.4 Poda utilizando o critério de percentagem mínima em um nó filho Nesta secção, da-se continuidade a poda da árvore, utilizando o critério de percentagem mínima de elementos em um nó filho em relação ao nó pai. Para este critério, seria vantajoso, se os valores de αvariassem em torno de [0.80, 0.95]. Mas, para este caso, usamos a percentagem de α= 0.60, porque com valores acima de 0.60 não houve uma poda significativa da árvore. Assim, obtivemos a seguinte árvore e as respectivas MC: 6.3. APLICAÇÕES USANDO CRITÉRIOS DE PRÉ-PODA 71 Figura 6.4: Número mínimo de elementos em um nó filho em relação ao nó pai Tabela 6.8: MC com os dados de treinamento, utilizando o parâmetro α S (Predição) N (Predição) S (Real) 24 21 N (Real) 18 37 Tabela 6.9: MC com os dados de teste, utilizando o parâmetro α S (Predição) N (Predição) S (Real) 4 11 N (Real) 6 9 72 CAPÍTULO 6. PODA Calculando o Recall eEspecificity para os dados de treinamento, RecallT raining =24 24 + 21 = 0,533 EspecificityTraining =37 37 + 18 = 0.673. E calculando o Recall eEspecificity para os dados de teste, RecallT est =4 4 + 11 = 0,266 EspecificityT est =9 9+6 = 0.6. 6.3.5 Poda utilizando o critério de impureza mínima Para este critério, fizemos uma experiência de poda, com três valores do parâmetro ε. ε= 0.1; ε= 0.3e ε = 0.5.Em que, dos três valores, os dois primeiros eliminavam apenas nós puros e, com terceiro valor eliminou-se mais um nó que não era puro, o que ñ se pode considerar como sendo uma poda considerável. Não testamos com valores mais elevados de ε, porque 0.5é o nível de impureza mais elevado. Ou seja, acima deste valor a impureza demasiadamente grande. No entanto, obtivemos a seguinte árvore de decisão e as respectivas MC, com ε= 0.5: 6.3. APLICAÇÕES USANDO CRITÉRIOS DE PRÉ-PODA 73 Figura 6.5: Impureza mínima Tabela 6.10: MC com os dados de treinamento, utilizando o parâmetro ε S (Predição) N (Predição) S (Real) 34 12 N (Real) 22 32 Tabela 6.11: MC com os dados de teste, utilizando o parâmetro ε S (Predição) N (Predição) S (Real) 6 9 N (Real) 7 8 Calculando o Recall eEspecificity para os dados de treinamento, RecallT raining =34 34 + 12 = 0,739 EspecificityTraining =32 32 + 22 = 0.593. 74 CAPÍTULO 6. PODA E calculando o Recall eEspecificity para os dados de teste, RecallT est =6 6+9 = 0,4 EspecificityT est =8 8+7 = 0.533. O objetivo deste capítulo foi essencialmente, exemplificar a utilização da poda e dos critérios de poda. Como referenciado anteriormente, uma poda consiste em reduzir o número de ramos em uma árvore de decisão. E, para que os ramos sejam reduzidos, são necessários os critérios de poda. Cada critério foi caracterizado por um parâmetro que irá definir o nível de poda deste critério. Assim, Neste capítulo foram apresentados quatro critérios de poda, foram feitas experiências com cada critério, para vermos como eles funcionam. E obteve-se os resultados do ISE e OSR para o Recall, representados na tabela 6.12. Tabela 6.12: MC com os dados de treinamento, utilizando o parâmetro ε ISE OSE Profundidade máxima 0.622 0.466 Percentagem mínima de elementos 0.666 0.266 Percentagem mínima num nó 0.533 0.266 Impureza mínima 0.739 0.4 Assim, pelos resultados apresentados na tabela 6.12 podemos observar que os critérios de Profundidade máxima e de Impureza mínima, apresentam uma taxa de erro menos elevada do que os outros dois critérios. No entanto, esperavam-se resultados mais próximos ao valor 1. Ao observamos as árvores de decisão dos critérios de profundidade máxima e de impureza mínima das figuras 6.2 e 6.5. Há mais proximidade ao tamanho da árvore de decisão sem poda a árvore do critério da impureza mínima, porque não foram eliminados muitos ramos nesta árvore. Logo para fazer a classificação podia-se usar o critério de profundidade máxima, visto que os resultados referentes a ele não se distanciam muito dos resultados do critério da Capítulo 8 Conclusões Com este trabalho foi possível compreender e aprofundar os conhecimentos obtidos acerca da ECD, precisamente o método de classificação aplicado à construção de árvores de decisão e do método de Pré-poda. Foi possível a compreensão de certos conceitos sobre teoria da informação, nomeadamente as frequências ou probabilidades, e de como estas são definidas através da informação referente à correlação entre os atributos e as classes. Podemos ver também que a impureza, avalia a quantidade de informação que se perde quando passamos os dados de uma visão microscópica para uma visão macroscópica. Desta maneira, o ganho de informação de um determinado atributo é calculado por meio de funções de impureza. Ademais, por meio do ganho de informação podemos construir uma árvore de decisão, começando por avaliar qual dos atributos obteve o melhor ganho, decidindo quem é a raiz da árvore e, assim por diante, até atingirmos o último nível da árvore. Desta maneira, faz-se uma poda elementar da árvore com critérios simples o que não reduz em grande escala a complexidade da árvore. No capítulo 5 foram feitas várias experiências sucintas de validação com um número reduzido de elementos da BD e, como o classificador não apresentava bons resultados, deduziu-se que o problema deveu-se à falta de mais dados. 81 82 CAPÍTULO 8. CONCLUSÕES Neste trabalho também foi possível compreender conceitos ligados ao método de pré-poda bem como os diferentes critérios de paragem utilizados no método em questão. E, mais uma uma vez, testamos o método de pré-poda com os diferentes critérios de paragem e os resultados continuavam a não ser satisfatórios. Desta vez deduziu-se que a escolha aleatória dos atributos em um conjunto de 47 da BD não foi satisfatória, visto que os três atributos não estavam a ser diferenciadores. Com isto tem de se escolher entre todos os atributos da BD qual é que está a reduzir o nível de impureza. Por fim, através da realização de experiências, testou-se a eficácia dos critérios de paragem do método de pré-poda para uma base de dados aplicada ao ensino. Podendo-se assim concluir que nenhum dos critérios utilizados apresentava melhorias para o classificador, devido aos atributos não apresentarem correlação com os resultados. Assim, com extensão a este trabalho, seria necessário considerar a constituição de uma nova BD mais adequada para indicar os atributos implícitos ao sucesso do aluno na escola. Bibliografia [EMS02] Zied Elouedi, Khaled Mellouli, and Philippe Smets. A pre-pruning method in belief decision trees. In The Ninth International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems IPMU, volume 1, pages 579–586, 2002. [GCF+15] João Gama, André Carlos Ponce de Leon Carvalho, Katti Faceli, Ana Carolina Lorena, Márcia Oliveira, et al. Extracção de conhecimento de dados: data mining. Available in the net, 2015. [JM15] Michael I Jordan and Tom M Mitchell. Machine learning: Trends, perspectives, and prospects. Science, 349(6245):255–260, 2015. [Loh11] Wei-Yin Loh. Classification and regression trees. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 1(1):14–23, 2011. [Mar07] João Maroco. Análise estatística com utilização do SPSS. Edições Sílabo, 2007. [McC98] RB McCall. Fundamental statistics for behavioral sciences, brooks, 1998. [PF91] Gregory Piateski and William Frawley. Knowledge discovery in databases. MIT press, 1991. [Qui86] J. Ross Quinlan. Induction of decision trees. Machine learning, 1(1):81–106, 1986. [Qui87] JR Quinlan. Simplifying decision trees. int j human-computer studies. 51 (2), pages 497–510, 1987. [Qui92] JR Quinlan. C4. 5: Programs for machine learning. los atos morgan kaufmann. Available in the net, 1992. 83 84 BIBLIOGRAFIA [RM05] Lior Rokach and Oded Maimon. Clustering methods. In Data mining and knowledge discovery handbook, pages 321–352. Springer, 2005. [RM08] Lior Rokach and Oded Z Maimon. Data mining with decision trees: theory and applications, volume 69. World scientific, 2008. [Wir85] N Wirth. Algorithms and data structures. oberon version: August 2004. Available in the net, 1985. Capítulo 9 Anexos Script em Python 1%import numpy as np 2#! python 3 4# Run t h i s program on your l o c a l python 5# i n t e r p r e t e r , pr ovide d you have i n s t a l l e d 6# the r e q u i r e d l i b r a r i e s . 7 8# I mpo rti ng the r e q u i r e d packages 9import numpy as np 10 import pandas as pd 11 import graphviz 12 from s k l e a r n import tree 13 from s k l e a r n import preprocessing 14 from s k l e a r n . metr ic s import confusion_matrix 15 from sklearn . model_selection import train_test_split 16 from s k l e a r n . t r e e import DecisionTreeClassifier 17 from s k l e a r n . metr ic s import accuracy_score 18 from s k l e a r n . metr ic s import classification_report 19 20 # Function i mpor ting Dataset 85 86 CAPÍTULO 9. ANEXOS 21 def importdata () : 22 #balance_data = pd . read_csv ( ’ h tt ps :// a r c h i v e . i c s . u c i . edu /ml/ machine−l e a r n i n g −databases / balance −s c a l e / balance −s c a l e . data ’ , sep= ’ , ’ , header = None ) 23 #balance_data = pd . read_csv ( ’ . / student −s m a l l . csv ’) 24 balance_data = pd . read_csv ( ’ ./ Dados_Filtrados . csv ’ ) 25 # P r i n t i n g the dataswet shape 26 print ( " Dataset ␣ Lenght : ␣" , len (balance_data)) 27 print ( " Dataset ␣Shape : ␣" , balance_data . shape ) 28 # P r i n t i n g the d at a se t o b s e r v a t i o n s 29 #p r i n t (" Dataset : " , balance_data . head (1) ) 30 #p r i n t ( balance_data . axes ) 31 return balance_data 32 33 # Function to s p l i t the d ataset 34 def s p l i t d a t a s e t ( balance_data ) : 35 begin_x =1;end_x=46; begin_y =46;end_y=47 36 in dex=balance_data . axes 37 X_features=np . a s a r r a y ( i nd ex [ 1 ] [ begin_x : end_x ] ) 38 Y_features=np . a s a r r a y ( i nd ex [ 1 ] [ begin_y : end_y ] ) 39 #p r i n t ("−−−−−") 40 #p r i n t ( X_features , Y_features ) 41 # Separ a ting the t a rg e t v a r i a b l e 42 f e a t u r e s=balance_data . to_numpy( dtype=s t r ) 43 X = f e a t u r e s [ : , begin_x : end_x ] 44 Y = f e a t u r e s [ : , begin_y : end_y ] 45 #p r i n t ("−−−−−") 46 #p r i n t (X,Y) 47 #p r i n t ("−−−−−") 48 # S p l i t i n g the dataset i n t o t r a i n and t e s t 49 X_train , X_test , y_train , y_test = t r a i n _ t e s t _ s p l i t (X, Y, t e s t _ s i z e = 0 .3 , random_state = 100) 87 50 return X, Y, X_train , X_test , y_train , y_test , X_features , Y_features 51 52 # Function to encode data 53 def encodedataset(X,leX): 54 Xencode =[]; 55 for row in X: 56 Xencode . append ( leX . transform ( row ) ) 57 return Xencode 58 59 # Function to perform t r a i n i n g with g i n i I n d e x . 60 def train_using_gini ( X_train , Y_train , d , epsi , alpha ) : 61 alpha=alpha+1e−5 62 c l f _ g i n i = D e c i s i o n T r e e C l a s s i f i e r ( c r i t e r i o n = " g i n i " , min_impurity_split=epsi , 63 max_depth=d , min_samples_split= alpha ) 64 c l f _ g i n i . f i t ( X_train , Y_train , check_input=True ) 65 return clf_gini 66 67 # Function to perform t r a i n i n g with entropy . 68 def train_using_entropy ( X_train , Y_train , d , eps i , alpha ) : 69 alpha=alpha+1e−5 70 clf _entr o py = D e c i s i o n T r e e C l a s s i f i e r ( c r i t e r i o n = " entropy " , min_impurity_split=epsi , 71 max_depth=d , min_samples_split=alpha) 72 clf _entr o py . f i t ( X_train , Y_train ) 73 return clf_entropy 74 75 76 # Function to make p r e d i c t i o n s 77 def p r e d i c t i o n ( X_test , c lf _ob je c t ) : 88 CAPÍTULO 9. ANEXOS 78 Y_pred = c l f _ o b j e c t . p r e d i c t ( X_test ) 79 return Y_pred 80 81 # Function to c a l c u l a t e accuracy 82 def ConfusionMatrix ( Y_test , Y_pred , leY ) : 83 nn=(leY . cla sses _ ) . s i z e 84 CM=np . z er os ( [ nn , nn ] ) 85 for iin range (0 , len ( Y_test ) −1) : 86 CM[ Y_test [ i ] , Y_pred [ i ]]+=1 87 return CM 88 89 # D r i v e r code 90 def main () : 91 92 # B u i l d i n g Phase 93 data = importdata () 94 X, Y, X_train , X_test , Y_train , Y_test , X_features , Y_features = splitdataset(data) 95 leX = p r e p r o c e s s i n g . LabelEncoder ( ) 96 leY = p r e p r o c e s s i n g . LabelEncoder ( ) 97 leX . f i t (X. f l a t t e n ( ) ) 98 leY . f i t (Y. f l a t t e n ( ) ) 99 #p r i n t ( leX . classes_ , leY . clas ses_ ) 100 Xencode=encodedataset (X, leX ) 101 Xencode_train=encodedatase t ( X_train , leX ) 102 Xencode_test=encodedataset ( X_test , leX ) 103 Yencode=encodedataset (Y, leY ) 104 Yencode_train=encodedatase t ( Y_train , leY ) 105 Yencode_test=encodedataset ( Y_test , leY ) 106 107 108 #p r i n t ( Xencode [ 2 ] ) 109 #p r i n t ( leX . invers e _ t ransfor m ( Xencode [ 2 ] ) ) 89 110 #d=25; e p s i =0.0; alpha =0.05; 111 d = i n t (input( " profund ida de ␣maxima : " ) ) 112 e p s i=f l o a t (input( " impuresa ␣minima : " ) ) 113 alpha=f l o a t (input( " r a c i o ␣de␣ p o p u l a a o ␣minima␣ nos : " ) ) 114 #−−−−−−−−− with g i n i index −−−−−−−−−− 115 c l f _ g i n i = t r a i n _ u s i n g _ g i n i ( Xencode_train , Yencode_train , d , epsi , alpha ) 116 pr int ( " T ra i ni ng ␣ with ␣ G i ni : " ) 117 Yencode_pred_gini_train = p r e d i c t i o n ( Xencode_train , c l f _ g i n i ) 118 CM_train=ConfusionMatrix ( Yencode_train , Yencode_pred_gini_train , leY ) 119 pr int ( " Confusion ␣ Matrix ␣ t r a i n " ) ; pr in t ( CM_train ) 120 Yencode_pred_gini_test = p r e d i c t i o n ( Xencode_test , c l f _ g i n i ) 121 CM_test=ConfusionMatrix ( Yencode_test , Yencode_pred_gini_test , leY ) 122 pr int ( " Con fus ion ␣ Matrix ␣ t e s t " ) ; print( CM_test) 123 dot_data = t r e e . e xp or t_ gra ph vi z ( c l f _ g i n i , o u t _ f i l e=None , f i l l e d= True , rounded=True , s p e c i a l _ c h a r a c t e r s=True ) 124 graph = g r a p hviz . Source ( dot_data ) 125 graph . r end e r ( " g i n i " ) 126 #−−−−−−−−− with entropy −−−−−−−−−− 127 ’ ’ ’ 128 clf _entr o py = train_using_entropy ( Xencode_train , Yencode_train , d , epsi , alpha ) 129 p r i n t (" Tr a ining with Entropy : " ) 130 Yencode_pred_entropy_train = p r e d i c t i o n ( Xencode_train , clf_entropy) 131 CM_train=ConfusionMatrix ( Yencode_train , Yencode_pred_entropy_train , leY) 132 p r i n t (" Confusion Matrix t r a i n ") ; p r i n t ( CM_train ) 133 Yencode_pred_entropy_test = p r e d i c t i o n ( Xencode_test , c lf_en tropy ) 134 CM_test=ConfusionMatrix ( Yencode_test , Yencode_pred_entropy_test , leY ) 135 p r i n t (" Confusion Matrix t e s t ") ; p r i n t ( CM_test) 90 CAPÍTULO 9. ANEXOS 136 dot_data = t r e e . e xp or t_gra ph viz ( c lf_ ent ropy , o u t _ f i l e=None , f i l l e d =True , rounded=True , s p e c i a l _ c h a r a c t e r s=True ) 137 graph = g r a p hviz . Source ( dot_data ) 138 graph . r ender (" entropy ") 139 ’ ’ ’ 140 # C a l l i n g main f u n c t i o n 141 i f __name__=="__main__" : 142 main ()