O sistema de geração das árvores de decisão adotado nos capitulos anteriores pode gerar árvores complexas que acabam perdendo o seu poder de predição.Portanto, o objetivo aqui será tornar árvores de decisão complexas mais simples através da simplificação.

Para ilustrar isso foi montado um exemplo especial utilizado um conjunto de 1000 casos com 10 atributos, cujos valores serão gerados randomicamente.Os atributos só poderão assumir valores 1 ou 0 e ambos terão igual probabilidade.Duas classes serão adotadas, "sim", que corresponde a 25% dos casos e "nao" correspondendo a 75%.Serão reservados 500 casos para o conjunto de treinamento e 500 para o conjunto de teste.Do conjunto de casos de treinamento o c4.5 gerou uma árvore com 119 nós.Fazendo a inserção dos casos testes nessa árvore 35% deles foram classificados erradamente.Se a árvore de decisão fosse apenas uma folha associada a classe "não" o número de erros ocorridos seria de apenas 25%, logo podemos ver o benefício de uma simplificação.Claro que a simplificação não será deletar toda uma árvore em favor de uma folha.

A simplificação pode ser feita enquanto a árvore está sendo gerada, decidindo pela não divisão de um conjunto de casos de treinamento ou removendo estruturas durante o processo de construção.A melhor maneira de tomar estas decisões seria olhar para as distribuições estatísticas, ganho de informação e redução de erro.Se este valor fosse abaixo de algum limite a divisão seria rejeitada e a árvore para este subconjunto seria uma folha.Mas segundo Breiman et al. este é um processo difícil de fazer funcionar adquadamente, pois quando se estabelece um limite alto o processo de divisão pode terminar antes dos benefícios subsequentes aparecerem e no caso de valores baixos o processo resulta em pouca simplificação.

O c4.5 segue por um outro caminho, o mesmo adotado pelo CART, fazendo a simplificação depois de gerada a árvore de decisão.Apesar do custo computacional ser bem maior, tem-se no final melhores simplificações, pois se pode explorar melhor os cortes na árvore.

Existem dois tipos de simplificação que poderão ocorrer na árvore de decisão: A deleção de uma ou mais subárvores, fazendo a substituição por uma folha associada a classe mais frequente e a substituição de uma subárvore por um de seus galhos.Estas operações podem ser visualizadas na figura 4-1, que mostra a árvore de decisão referente a uma base de dados de uma votação congrecional antes e depois da simplificação.Toda a subárvore associada ao teste "physician fee freeze=n" foi deletada se transformando em apenas uma folha identificando a classe "democrat", o mesmo acontecendo para a subárvore relativa ao teste "physician fee freeze=y", já para a subárvore relativa ao teste "physician fee freeze=u" foi feita uma substituição por um de seus galhos, no caso pela subárvore associada ao nó que testa o atributo "mx missile".

Árvore de Decisão Original

physician fee freeze = n:
   adoption of the budget resolution = y: democrat (151)
   adoption of the budget resolution = u: democrat (1) 
   adoption of the budget resolution = n: 
      education spending = n: democrat (6)
      education spending = y: democrat (9)
      education spending = u: republican (1)
physician fee freeze = y:
   synfuels corporation cutback = n: republican (97/3)
   synfuels corporation cutback = u: republican (4)
   synfuels corporation cutback = y: 
      duty free exports = y: democrat(2)
      duty free exports = u: republican (1)
      duty free exports = n:
         education spending = n: democrat (5/2)
         education spending = y: democrat (13/2)
         education spending = u: republican (1)
physician fee freeze = u:
   water project cost sharing = n: democrat (0)
   water project cost sharing = y: democrat (4)
   water project cost sharing = u:
      mx missile = n: republican (0)
      mx missile = n: democrat (3/1)
      mx missile = n: republican (2)

Árvore de Decisão Simplificada

physician fee freeze = n: democrat (168/2.6)
physician fee freeze = y: republican (123/13.9)
physician fee freeze = u:
   mx missile = n: republican (3/1.1)
   mx missile = n: democrat (4/2.2)
   mx missile = n: republican (2/1)

Figura 4-1:Árvore de decisão antes e depois de simplificada.

O algoritmo de simplificação começa pelo nível mais baixo da árvore e vai examinando cada nó.Para cada nó ele verifica se a deleção da subárvore em favor de uma folha ou a substituição pelo galho mais frequente deste nó irá diminuir a predição de erro, caso positivo a operação e realizada.

O problema está em como esta predição de erro pode ser encontrada.A questão principal é que se usado o conjunto de casos de treinamento para calcular esta predição, sempre que tentarmos simplificar a árvore, a predição de erros irá aumentar, pois a árvore absorveu o padrão existente nesse conjunto, e com isso não irá ocorrer simplificação.Por exemplo, na árvore mostrada na figura 4-1, a subárvore associada ao teste "physician fee freeze = n", todos os 168 casos estavam classificados corretamente, mas quando esta subárvore é deletada 1 caso é mal classificado.Para a subárvore referente ao teste "physician fee freeze=y" tinhamos 123 casos, sendo 7 deles mal classificados, com a deleção desta subárvore o número de casos classificados erradamente aumenta de 7 para 10.

Para solucionar este problema pode-se separar um pequeno conjunto de casos e não usá-los na geração da árvore, assim a predição de erro não seria influenciada, pois ela seria feita com um conjunto desconhecido de casos.Apesar de ser uma ótima solução esta técnica traria outros problemas quando o conjunto de dados fosse pequeno.

A solução adotada pelo c4.5 faz uso apenas do conjunto de casos de treinamento, apresentando um artifício para contornar o problema da árvore ter absorvido o conhecimento deste conjunto.Esta técnica é chamada de simplificação pessimista e consiste em aumentar a taxa de erro ocorrida em cada folha e então inserir os casos novamente para encontrar a predição de erros.

*************

Se N casos chegam até uma folha, E sendo classificados erradamente, a probabilidade de erro para esta folha é E/N.No entanto, podemos imaginar E como sendo um número de eventos e N tentativas.Se estes N casos puderem ser olhados com uma amostra, então podemos perguntar o que este resultado nos fornece a respeito da probabilidade de um evento (erro) em relação a todos os casos relacionados a esta folha.A probabilidade de erro não pode ser determinadada exatamente, mas esta tem uma distribuição de probabilidade que normalmente é resumida num par de limites de confiabilidade.Se tivermos uma confiabilidade CF, o limite superior para esta probabilidade pode ser encontrado a partir do limite de confiabilidade para a distribuição binomial; este limite superior será escrito com Ucf(E,N).Então, o c4.5 simplismente iguala esta taxa de predição de erro à uma folha com este limite superior, em argumento que a árvore foi construída para minimizar a taxa de erro observada.Apesar destas violências estatísticas em noções de amostra e limite de confiabilidade, apresenta ótimos resultados, da mesma forma que muitos critérios heuristicos questionados.

*************

Agora as predições de erros para folhas e subárvores serão calculadas assumindo que um conjunto de casos desconhecidos do mesmo tamanho do conjunto de treinamento foram classifacados por estas estruturas.Assim, uma folha associando N casos de treinamento com uma predição de erros de Ucf(E,N) originará uma predição do número de casos que seriam classificados erradamente por ela de NxUcf(E,N).A predição de erro associada à uma subárvore será a soma da predição de erros para seus galhos.

Como exemplo da aplicação desta técnica olharemos para a árvore da figura 4-1, mais especificamente para a subárvore relativa ao teste "physician fee freeze = n"

physician fee freeze = n:
   adoption of the budget resolution = y: democrat (151)
   adoption of the budget resolution = u: democrat (1) 
   adoption of the budget resolution = n: 
      education spending = n: democrat (6)
      education spending = y: democrat (9)
      education spending = u: republican (1)

Seguindo os passos do algoritmo, faremos um teste para ver se a eliminação do nó mais profundo, "education spending", irá acarretar diminuição da predição de erro.Primeiro é encontrada a predição de erro para este nó, que será a soma da predição de erro para cada folha

Agora será calculado a predição de erro no caso de este nó ser substiuído pela folha mais frequente

adoption of the budget resolution = n: democrat (16/1)

16 x Ucf(1,16) =16 x 0,157 = 2,512

Como a predição de erro para a folha foi menor, a subárvore é deletada em favor da folha, ficando

physician fee freeze = n:
   adoption of the budget resolution = y: democrat (151)
   adoption of the budget resolution = u: democrat (1) 
   adoption of the budget resolution = n: democrat (16/1)

Agora, olhando para o nó "adoption of the budget resolution" iremos verificar se a sua deleção em favor de uma folha irá diminuir a predição de erro.Calculando a predição de erro para a subárvore

151 x Ucf(0,151) + 1 x Ucf(0,1) + 16 x Ucf(1,16) = 4,642

Fazendo o cálculo para a folha

physician fee freeze = n: democrat (168/1)

168 x Ucf(1,168) = 2,610

Como a predição de erro para a folha foi menor, a subárvore é deletada.Portando, a árvore final ficou

physician fee freeze = n: democrat (168/1)

Depois de simplificada a árvore de decisão o programa calcula o número de erros previstos para cada folha e os apresenta no formato (N/E), E significando o número de erros previstos se um conjunto de N casos fossem classificados pela folha, E = N x Ucf(E,N).

Assim, para se calcular a estimativa de erro para a árvore basta somar todos os erros previstos para cada folha e dividí-lo pelo número total de casos.No caso do exemplo apresentado na figura 4-1, temos (2.6+13.9+1.1+2.2+1)/300=0,069, portanto a estimativa de erro é de 6,9%.

Uma analise dos dados fornecidos pelo c4.5 é apresentada na figura 4-2.Chamando a atenção para o fato de que a árvore de decisão classificou apneas 2.7% dos casos erradamente quando usado o conjunto de casos de treinamento e 5.2% quando usado casos testes, enquanto a árvore simplificada classificou 4.3% dos casos erradamente quando usado o conjunto de casos de treinamento e 30% quando os casos testes.