Construindo Árvores de Decisão

Neste capitulo será estudado como o algoritmo gera uma árvore de decisão a partir de um conjunto de casos de treinamento.As idéias para a construção das árvores de decisão surgiram de um livro escrito por Hunt, Experiments in Induction [Hunt,Marin, and Stone, 1966]

Algoritmo Dividir para Conquistar

Seja o conjunto de treinamento T, composto pelas classes {c1,c2,...,cn}, existem três possibilidades para T:

  1. T contém um ou mais casos, todos pertencendo a uma classe cj:A árvore de decisão para T é uma folha identificando a classe cj.
  2. T não contém casos:A árvore de decisão é uma folha.Como T é um conjunto vazio, não pode ser usado para definir a classe para esta folha, logo e necessário olhar para outras informações.O c4.5 utiliza a classe mais frequênte que ocorre nos pais desse nó.
  3. T contém varios casos, pertencendo a uma mistura de classes:A idéia e dividir T em subconjuntos que se classifiquem nas possibilidades citadas anteriormente.Essa divisão é feita baseada em um atributo que possua valores mutualmente exclusivos {v1,v2,v3,...,vn}.T é particionado em subconjuntos T1, T2, T3,..., Tn, onde Ti contém todos os casos com valores vi.A árvore de decisão para T consiste de um nó de decisão identificando o teste para o atributo, e um galho para cada valor do atributo.Agora recursivamente cada subconjunto Ti é visto como T, que irá se encaixar em uma das três possibilidades.

Uma Ilustração

 Agora o algoritmo acima será aplicado em um pequeno conjunto de casos, mostrados na figura 2-1.Inicialmente, T e composto por todos os casos da figura 2-1.Como todos os casos que pertencem a T não fazem parte da mesma classe, será aplicado o passo 3 do algoritmo dividir para conquistar.Supondo agora que seja escolhido o atributo outlook como teste, na divisão dos casos, já que ainda nao foi estudado a maneira como é feita esta escolha, T será dividido em três subconjuntos:T1 para os casos com resultado sunny, T2 overcast e T3 rain.Como T1 recai no passo 3 do algoritmo, ele será dividido em outros subconjuntos.Para fazer essa divisão o teste será realizado no atributo humity.Será aplicado o teste humity <=75 e humity >75, desta maneira os casos pertencentes a cada subconjunto de T1 pertencerão a apenas uma classe e pode ser aplicado o passo 1 do algoritmo.Como todos os casos pertencentes ao conjunto T2 possuem a mesma classe, é aplicado o passo 1 do algoritmo.Sendo o subconjunto T3 composto mais de uma classe será aplicado o passo 3, usando o atributo windy no agrupamento.T3 será dividido em outros dois subconjuntos, um para o teste windy=true e o outro para windy=false. Com essa divisão ambos os subconjuntos conterão apenas uma classe.As divisões finais e a árvore de decisão correspondente são mostradas na figura 2-2.

Avaliando os Testes

Para se conseguir gerar uma árvore de decisão com uma alta taxa de predicão e necessário fazer a escolha correta dos atributos que serão usados como teste no agrupamento dos casos.Estes testes devem gerar uma árvore com o menor número possível de subconjuntos, assim chegaram em cada folha da árvore um número significante de casos.Ou seja, o ideal e escolher os testes de modo que a árvore final seja a menor possivel.

Como analisar todas as possibilidades possiveis seria algo absurdo, foram desemvolvidos vários métodos aplicados na escolha dos atributos e dos testes a serem utilizados, e uma vez feita a escolha as outras possibilidades não são mais exploradas.

Critério Gain

Como não é possível olhar para todas as possibilidades de agrupamento esse criterio, e o próximo a ser apresentado, fazem uso apenas da distribuicao das classes em T e em seus subconjuntos.

Para utilizar esse critério de escolha será necessário entender algumas notações.Sendo S um conjunto de casos, freq(cj,S) representa o número de vezes que a classe cj aparece em S e |S| denota o número de casos do conjunto S.

Esse critério de escolha, proposto por Hunt, usa um método baseado na teoria da informação:A informação carregada por uma mensagem depende da sua probabilidade e pode ser medida em bits como menos o logaritmo na base 2 dessa probabilidade.

Para este critério, a nossa mensagem vai ser dada como a frequência que uma classe qualquer cj aparece em um conjunto de casos S.Esta mensagem pode ocorrer com a probabilidade de

freq(cj,S) ----------- |S|

Assim, a informação que ela carrega e dada por

freq(cj,S) log ( -----------) bits 2 |S|

Para encontrar a informação esperada de tal mensagem para cada classe pertencente ao conjunto S, é feita a soma das classes em proporção as suas probabilidades em S:

info(S)= ....

Quando esta fórmula é aplicada para o conjunto de casos de treinamento, info(T) é a média da informação necessária para identificar a classe de um caso pertencente a T.

A próxima funcao mede a informação depois de feita a divisão de T em subconjuntos Ti, de acordo com os n valores de um teste X para um atributo.

infox(T)=....

O atributo escolhido será aquele que apresentar o maior ganho de informação para o teste X, na partição de T.Este ganho e dado por

gain(X)=info(T)-infox(T)

****Colocar o exemplo****

Criterio Gain Ratio

Apesar do critério apresentado anteriormente fornecer bom resultados, ele possui um problema, pois favorece os atributos com muitos valores, já que a maioria dos subconjuntos gerados vai possuir apenas uma classe, ou todos os subconjuntos, e com isso infox(T)=0, assim a informacao ganha por particionar esse conjunto de treinamento será máxima.Já foi visto anteriormente que a árvore de decisão deve ser a menor possível, ou seja, deve-se escolher os testes que irão fornecer o menor número de blocos na divisão dos casos de treinamento, portando, apesar de o critério nos informar que o teste seria ótimo, isso não é verdade.

Para contornar esse problema, o critério gain será alterado acresentado-se um normalizador, para que esse aparente ganho seja ajustado. Esse normalizador será

split info(X)=...

O ganho calculado, utilizando esse normalizador, será chamado gain ratio e e dado pela formula

gain ratio(X)=gain(X)/split info(X)

****colocar exemplo*******

Possíveis Testes

Depois de selecionado os atributos que serão utilizados como teste é necessário escolher o tipo de teste que será feito nesse atributo.O c4.5 possui três tipos de testes:

  • O teste "padrão" para os atributos discretos, com um resultado e um galho para cada valor possível do atributo.
  • Um teste ainda para atributos discretos, só que um pouco mais complexo.Os valores são divididos em grupos, assim temos um galho para cada grupo.
  • Um teste para atributos continuos, baseado em comparar o valor de um atributo A com um valor Z, A<=Z e A>Z.

    Testes em Atributos Continuos

    Já vimos que para o c4.5 os testes em atributos continuos são apresentados na forma A<=Z e A>Z, sendo A o atributo teste escolhido e Z um de seus valores.Agora será visto como é calculado o gain ratio para o atributo A e como o valor de Z e escolhido.

    Primeiramente o conjunto de casos T e ordenado nos valores do atributo A.Para cada valor vi é calculado (vi + vi+1)/2 como sendo o valor que será utilizado no teste para fazer a divisão do atributo A em dois subconjuntos T1 e T2.Baseado nesses subconjuntos é então calculado o gain ratio.Sendo m o conjunto de valores do atributo A teremos que calcular m-1 possibilidades para Z e seu ganho.O Z que apresentar o maior ganho será então o representante do atributo A.O c4.5 não escolhe a média entre os valores como Z, mas sim o maior valor do atributo A, que não excede essa media.

    Como ilustração adotaremos o exemplo do capitulo 1 e o atributo wify.Dos 40 casos existem 14 valores distintos, com isso teremos 13 possibilidades para Z.Na figura 2-3 e mostrado o gain e gain ratio para cada um desses critérios.Para representar o atributo wify será escolhido o maior ganho e como Z o valor que gerou esse ganho, nesse caso 2,5.