Arvore de Decisão

Árvores de Decisão Marcelo S Laurett EACHUSP marcelolaurettuspbr Novembro2010 1 Definições 11 Aprendizado Supervisionado Denotaremos por U o conjunto universo de objetos ou seja o conjunto de todos os objetos que o aprendiz pode encontrar 12 Terminologia Básica de Árvores Uma árvore é uma coleção de elementos chamados nós dentro os quais um é distinguido como uma raiz juntamente com uma relação de paternidade que impõe uma estrutura hierárquica sobre os nós Formalmente Definição informal Árvores de decisão ou árvores de classificação são modelos de aprendizado supervisionado que representam regras de decisão baseadas nos valores dos atributos Uma árvore pode ser definida recursivamente da seguinte maneira 1 Um único nó é uma árvore Este nó é também a raiz da árvore 2 Suponha que t seja um nó e T1 T2 Tk sejam árvores com raízes t1 t2 tk respectivamente Nesta árvore t será a raiz e T1 T2 Tk serão as subárvores ou ramos da raiz Os nós t1 t2 tk são chamados filhos do nó t Exemplo Sumário de um livro a e sua respectiva representação como uma árvore b Árvores de Decisão Uma Árvore de Decisão é um nó folha ou nó resposta que contém o nome de uma classe ou o símbolo nulo nulo indica que não é possível atribuir nenhuma classe ao nó por não haver nenhum exemplo que corresponda a esse nó ou um nó interno ou nó de decisão que contém o nome de um atributo para cada possível valor do atributo corresponde um ramo para uma outra árvore de decisão Uma árvore de decisão possui a seguinte estrutura típica Nós internos são rotulados com atributos Folhas são rotuladas com classes Ramos são rotulados com valores atributos categóricos ou com intervalos atributos numéricos Objeto No TAMANHO FORMATO ORIFÍCIOS CLASSE 01 grande longo 2 tesoura 02 pequeno compacto 1 porca 03 pequeno compacto 1 porca 04 pequeno longo 0 parafuso 05 grande longo 0 caneta 06 pequeno longo 1 chave 07 pequeno longo 0 parafuso 08 pequeno compacto 1 porca 09 grande longo 2 tesoura 10 pequeno longo 1 chave 11 pequeno longo 2 chave 12 grande longo 0 caneta O programa pode extrair alguns valores de atributos de cada imagem que no nosso caso são o tamanho o formato e o número de orifícios de um objeto Os possíveis valores desses atributos são Tamanho pequeno grande Formato longo compacto outro Orifícios 0 1 2 3 muitos Assim cada objeto é representado através de seu respectivo vetor de atributo item b da figura A figura abaixo mostra uma árvore de decisão induzida a partir dos exemplos acima Descreveremos em linhas gerais o processo de construção dessa árvore Iniciamos a construção da árvore com apenas um nó a raíz e associamos a esse nó o conjunto E Como os exemplos não estão na mesma classe decidimos dividir o nó ou seja expandir a árvore Para isso escolhemos um atributo em nossa ilustração Orifícios com o qual rotulamos a raíz Dividimos o conjunto E em subconjuntos disjuntos agrupando exemplos de mesmo valor de Orifícios em cada subconjunto Para cada um desses subconjuntos criamos um novo nófilho do nó Orifícios Em nosso caso os subconjuntos de E são E1 X E tq XOrifícios 0 E2 X E tq XOrifícios 1 E3 X E tq XOrifícios 2 E4 X E tq XOrifícios 3 E5 X E tq XOrifícios muitos Analisemos agora o nó referente ao subconjunto E1 Uma vez que E1 contém exemplos de classes distintas o nó deve ser dividido rotulamos o nó com um novo atributo Tamanho criamos novos filhos para esse nó e dividimos E1 conforme os valores de Tamanho pequeno grande E11 X E1 tq XTamanho pequeno E12 X E1 tq XTamanho grande Todos os exemplos em E1 pertencem a mesma classe Nesse caso simplesmente rotulamos o nó correspondente com a classe à qual aqueles exemplos pertencem parafuso e declaramos esse nó como uma folha passando a examinar outros nós que ainda não tenham sido devidamente tratados O mesmo ocorre com o nó referente ao subconjunto E12 cujos exemplos são todos da classe caneta O procedimento é análogo para os demais subconjuntos E2 E3 E21 E22 etc se o subconjunto é vazio como ocorre em E4 E5 E23 o nó correspondente é rotulado com nulo Suponha agora que a árvore de decisão tenha sido construída e que seja apresentada ao sistema o vetor de atributos de um objeto de classe desconhecida Queremos que o sistema atribua uma classe ao objeto O procedimento para classificação desse objeto é realizar o teste de atributo na raiz ir para o ramo correspondente realizar o teste de atributo no segundo nó ir para o próximo ramo sucessivamente até atingir uma folha Então o objeto será classificado com o rótulo da respectiva folha Por exemplo se tivermos um objeto com vetor de atributos Tamanho grande Formato longo Orifícios 0 a aplicação da árvore sobre esse objeto levará ao nó E12 e o mesmo será portanto classificado como uma caneta 3 Algoritmo de construção Ideia geral do algoritmo Expansão da árvore através de sucessivas partições do conjunto de treinamento até que a condição de parada seja satisfeita Eliminação de algumas partes inferiores poda da árvore através de reagrupamentos dos subconjuntos da partição Algoritmo Dados um conjunto de aprendizado E uma condição de parada PE uma função de avaliação scoreE atributo uma função de classificação classet uma função de categorização categE atributo Se o conjunto E satisfaz a condição de parada PE então a árvore resultante é um único nó t rotulado conforme a regra classet caso contrário 1 para cada atributo ai calcule a função scoreE ai selecione o atributo an arg max scoreE ai 2 sejam I1 I2 IK os intervalos gerados segundo categE an crie o nó e os ramos 3 particione E em K subconjuntos E1 E2 EK segundo os intervalos ou valores de an na árvore de decisão 4 aplique o algoritmo recursivamente para cada um dos subconjuntos Ei 5 após a expansão da árvore ter terminado ajuste seu tamanho eliminando alguns ramos Tt se necessário Fim Os principais elementos do algoritmo são Regra de parada PE é uma condição que o conjunto de treinamento E deve satisfazer para que seu nó correspondente seja considerado um nó terminal Casos mais simples E é vazio ou quando todos os exemplos incidentes sobre t pertencem à mesma classe Contudo existem algoritmos que interrompem a expansão do nó sob condições mais complexas Nesses casos dizemos que ocorre uma prépoda na árvore de decisão Regra classet função que atribui um rótulo de classe a um nó t Critério mais simples classificação por maioria Função scoreai é utilizada para tentar identificar o atributo mais relevante existente sobre E isto é o atributo com maior poder discriminante das classes Método de categorização de atributos categE a Atributos numéricos precisam ser discretizados em subintervalos do tipo I1 c0 c1 I2 c1 c2 IK cn1 cnK onde c0 c1 cK são constantes definidas segundo o critério de categorização categE a A forma mais simples de discretização é a binarização dos atributos através de condições do tipo x c onde c é obtida através de testes exaustivos sobre o conjunto de treinamento disponível Uma vez que os atributos categóricos também podem ser reduzidos a conjuntos I1 a1 IK aK para simplificar a notação não faremos distinção entre atributos ordenados e categóricos exceto em casos explícitos Crítica de poda Após a expansão da árvore pode ocorrer que os subconjuntos de E correspondentes aos nós folhas sejam muito pequenos e com grande efeito de overfitting ajuste muito preciso aos dados de treinamento porém com baixa precisão na classificação de novos exemplos É necessário então eliminarse alguns ramos inferiores da árvore de forma a atenuar o efeito dos ruidosos informações inúteis para a classificação e de forma a manter na árvore apenas regras com mais alto poder de discriminação das classes Esse processo é denominado póspoda ou simplesmente poda das árvores 4 A regra de atribuição de classes Denotaremos por pjt a probabilidade estimada de um exemplo incidente em t possuir classe j Por exemplo pjt pode ser definido como a proporção de exemplos de t que possuem classe j 41 Critério de minimização do erro esperado O critério mais simples de atribuição é adotar a classe de maior probabilidade estimada no nó isto é a classe que maximiza pjt Assim a probabilidade estimada de um exemplo incidente sobre t ser classificado erroneamente é rt 1 maxj pjt minj u2211i j pit 1 42 Critério de minimização do custo do erro de classificação Breiman et al 1984 sugerem um critério de atribuição que minimiza o custo de erro de classificação no nó O custo de erro em classificar um objeto pertencente a classe j como sendo de classe i é denotado por Ci j e satisfaz Ci j 0 i j Ci i 0 Um objeto de classe desconhecida incidente sobre um nó t for classificado como classe i então o custo esperado do erro na classificação será u2211j Ci jpjt Assim um critério natural de atribuição é escolher a classe i que minimiza a expressão acima Sob essa regra o custo esperado no erro de classificação de um objeto incidente sobre t será rt mini u2211j Ci jpjt 2 Observação O critério de escolha pela maior probabilidade estimada é um caso particular do critério de minimização de custos 43 Rotulação dos nós pelas probabilidades das classes Para classificação de um novo objeto pode ser desejável que a árvore T forneça ao invés de sua classe prevista j as probabilidades estimadas desse objeto pertencer a cada uma das classes 1 2 J Exemplo diagnóstico médico Para essas situações a função de atribuição classet pode ser redefinida como classet p1t p2t pJt Nesse caso a árvore T passa a ser chamada de árvore probabilística e não mais árvore de decisão vide Michie et al 1994 Podemos estimar o custo de erro no nó t usando o seguinte raciocínio sendo pjt a probabilidade estimada de um objeto incidente sobre t pertencer à classe j o custo estimado de erro em atribuir a classe i a esse objeto será u2211j Ci jpjt Como a função classet atribui a classe i ao objeto com probabilidade pit o custo estimado de erro no nó t será rt i pit ij Cijpit ij Cijpitpjt 44 Custo total de erro de classificação na árvore Uma vez apresentadas as regras de atribuição de classe e as respectivas estimativas de erro rt é útil definirmos os custos estimados de erros de cada nó e o custo de erro da árvore T Seja Rt o custo total de erro no nó t dado por Rt rtpt onde pt é a proporção de exemplos em E que incidem sobre o nó t O custo total de erros de classificação da árvore RT é dado por RT tT Rt onde T é o conjunto de folhas de T 5 Escolha do Atributo Ótimo Uma vez definidas as possíveis divisões para os nós da árvore critérios de discretização é necessário definir um critério de avaliação que escolha a melhor divisão para cada nó De forma geral a melhor divisão para um nó deve ser aquela que agrupe da melhor forma possível os exemplos de mesma classe Para o problema em que os custos de erro Cij são unitários isto é Cii 0 Cij 1 i j muitos dos critérios de divisões dos nós são baseados no conceito de impureza definido como segue Definição 51 Uma função de impureza é uma função φ definida sobre o conjunto de todas as Jtuplas de números p1p2u2026pJ satisfazendo pj 0 j 12u2026J pj 1 com as propriedades φ atinge seu máximo somente no ponto 1717u202617 φ atinge seu mínimo somente nos pontos 10u20260010u20260u202601 φ é uma função simétrica de p1p2u2026pJ As restrições acima retratam as noções intuitivas de impureza de fato a impureza de um nó é máxima quando todas as classes estão igualmente presentes no nó mínima quando o nó contém apenas uma classe