O algoritmo que foi apresentado no capitulo anterior, para a construcao de arvores de decisao, funciona muito bem quando todos os atributos para o conjunto de casos possuem valores conhecidos.Como isto nao representa a realidade, pois quando se parte para uma coleta de fatos podemos nos deparar com um numero significante de casos com valores de alguns atributos faltando,as vezes ate mesmo valores relevantes na classificacao de uma classe, devemos entao descobrir uma maneira de solucionar este problema.

A solucao pode ser descartar todos os casos que possuem atributos com valores desconhecidos e durante a classificacao de um caso, se algum dos atributos nao possuir valor conhecido, fornecer uma mensagem como inclassificavel.Uma outra solucao e tornar o algoritmo capaz de lidar com casos que possuem valores de atributos desconhecidos, que e a solucao adotada pelo c4.5.Para isso, teremos tres questoes que deverao ser respondidadas.

1.Sendo a selecao de um teste baseado em criterios heuristicos, como gain e gain ratio, como serao calculados esses valores para atributos com valores desconhecidos?

2.Feita a selecao de um atributo para teste, a qual subconjunto Ti os casos com valores desconhecidos para este atributo deverao pertencer?

3.Quando uma arvore de decisao e usada na classificacao de casos, qual deve ser o procedimento adotado se o caso tiver um valor desconhecido para o atributo que esta sendo usado como teste no no de decisao corrente?

Existem varias respostas possiveis para estas tres questoes, como preencher os valores dos atributos que estao faltando.A maneira como o c4.5 lida com esta situacao sera descrita a seguir.

A escolha dos testes para o algoritmo apresentado anteriormente era baseada nos criterios gain e gain ratio, que como ja foi visto sao derivacoes da teoria da informacao.Com um teste para um atributo com um valor desconhecido nao ira prover nenhuma informacao a respeito do conjunto de classes, na hora de calcular o valor de um desses criterios somente os casos que possuem valores conhecidos para o atributo sendo analisado deverao ser levados em conta.

Sendo T um conjunto de casos de treinamento, X um teste baseado em um atributo A, e F representando a probabilidade de A ser conhecido.A definicao do criterio gain pode ser mudada para

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

Para o criterio gain ratio, na hora de calcular o valor de split info, deve-se olhar para os casos com valores desconhecidos com um grupo adicional.Por exemplo, se um atributo teste possuir n valores conhecidos e mais alguns valores desconhecidos, entao, split info sera calculado como se esse conjunto estivesse dividido em n+1 grupos.

O c4.5 segue a mesma tecnica adotada pelo programa ASSISTANT[Cestnik et al, 1987], assumindo aproximacoes probabilisticas.Sendo T o conjunto de casos a ser particionado, de acordo com cada valor do atributo teste escolhido, T sera dividido em subconjuntos Ti, e para cada caso pertencente a cada subconjunto Ti sera associado um peso que representa a probabilidade deste caso pertencer a este subconjunto.Todos os casos pertencentes a um subconjunto Ti, com os valores do atributo teste conhecido, terao peso 1, pois a probabilidade destes casos pertencerem a este subconjunto e 100%.Para os casos com valores desconhecidos para o atributo teste, o peso sera o produto do peso para T pela probabilidade deste caso em Ti. esta probabilidade e calculada obtendo se a soma dos pesos em Ti dividido pela soma dos pesos em T para valores conhecidos.O peso para os atributos desconhecidos para o conjunto de casos inicial sera 1.Os casos com valores desconhecidos para o atributo teste serao associados a todos os subconjuntos Ti, logo, devemos mudar a notacao |Ti| , como sendo a soma dos pesos dos casos para o conjunto, mas o seu significado continua sendo o numero de casos pertencentes a Ti, so que desta vez podemos ter um numero fracionario de casos.

Quando um caso tiver um valor desconhecido para o atributo que esta sendo usado com teste num no de decisao, o programa explora todas as possibilidades a partir deste no ate as folhas.A classe escolhida sera aquela que conter a maior probabilidade de o caso pertencer a ela.

Para apresentar um exemplo do funcionamento do algoritmo para casos desconhecidos, utilizaremos o conjunto de treinamentos do capitulo anterior, com apenas uma modificacao no valor do atributo Tempo, que agora sera desconhecido, para o caso Tempo=nublado, temperatura=72, Humidade=90, Ventando=true.

Usando o criterio gain para determinar o ganho para o atributo Tempo, apenas os casos com valores conhecidos para ete atributo serao considerados, ou seja, dos 14 casos apenas 13.Temos

info(T) = -8/13xlog (8/13) - 5/13xlog (5/13)

2 2

=0.961 bits

infox(T) = 5/13x(-2/5xlog (2/5) - 3/5xlog (3/5))

2 2

+3/13x(-3/3xlog (3/3) - 0/3xlog (0/3))

2 2

+5/13x(-3/5xlog (3/5) - 2/5xlog (2/5))

2 2

=0.747 bits

gain(X) = 13/14x(0.961-0.747)

= 0.199 bits

Notando que o ganho abaixou de 0.246 para 0.199 em relacao ao calculo feito no capitulo anterior.

Para o criterio gain ratio, durante o calculo de split info, todos os casos devem ser levados em conta, portando devemos considerar mais um valor para o atributo Tempo

-5/14xlog (5/14) (Ensolarado)

-3/14xlog (3/14) (nublado)

-5/14xlog (5/14) (chuvoso)

-1/14xlog (1/14) (casos que possuem valores desconhecidos para Tempo)

Fazendo os calculos obteremos split info igual 1809.Com isso temos um gain ratio de 0.110, que e um valor menor que o calculado no capitulo anterior, que foi de 0.156.

Se calculado os valores para os outros atributos sera constatado que o atributo Tempo ainda representa o maior ganho, portanto, sera usado na particao dos casos de treinamento.Com isso teremos tres subconjuntos, correspondendo a Tempo igual a ensolarado, nublado e chuvoso, e os casos com valores desconhecidos para o atributo serao associados aos tres subconjuntos, logo temos

Conjunto de caso de treinamento inicial

Tempo Temperatura Humidade Ventando Class Peso

Ensolarado 75 70 true Play 1

Ensolarado 80 90 true Dont Play 1

Ensolarado 85 85 false Dont Play 1

Ensolarado 72 95 false Dont Play 1

Ensolarado 69 70 false Play 1

? 72 90 true Play 1

nublado 83 78 false Play 1

nublado 64 65 true Play 1

nublado 81 75 false Play 1

nublado 71 80 true Dont Play 1

chuvoso 65 70 true Dont Play 1

chuvoso 75 80 false Play 1

chuvoso 68 80 false Play 1

chuvoso 70 96 false Play 1

Depois da particao realizada no atributo Tempo, temos

Tempo=ensolarado

Tempo Temperatura Humidade Ventando Class Peso

Ensolarado 75 70 true Play 1

Ensolarado 80 90 true Dont Play 1

Ensolarado 85 85 false Dont Play 1

Ensolarado 72 95 false Dont Play 1

Ensolarado 69 70 false Play 1

? 72 90 true Play 5/13(0.4)

Tempo=nublado

Tempo Temperatura Humidade Ventando Class Peso

nublado 83 78 false Play 1

nublado 64 65 true Play 1

nublado 81 75 false Play 1

? 72 90 true Play 3/13(0.2)

Tempo=chuvoso

Tempo Temperatura Humidade Ventando Class Peso

chuvoso 71 80 true Dont Play 1

chuvoso 65 70 true Dont Play 1

chuvoso 75 80 false Play 1

chuvoso 68 80 false Play 1

chuvoso 70 96 false Play 1

? 72 90 true Play 5/13(0.4)

Notando se, que o caso que tinha valor desconhecido para o atributo teste Tempo, foi associado a todos os subconjuntos gerados a partir de T.As divisoes finais que teremos serao,

Tempo=ensolarado

Divisao feita no atributo Humidade

Humidade <= 75

Tempo Temperatura Humidade Ventando Class Peso

Ensolarado 75 70 true Play 1

Ensolarado 69 70 false Play 1

Numero de casos que chegaram a esta folha: (2.0)

Umiade >= 75

Tempo Temperatura Humidade Ventando Class Peso

Ensolarado 80 90 true Dont Play 1

Ensolarado 85 85 false Dont Play 1

Ensolarado 72 95 false Dont Play 1

? 72 90 true Play 5/13(0.4)

Numero de casos que chegaram a esta folha: (3.4)

Tempo = nublado

Como nenhum atributo prove nenhuma melhora, a divisao para por aqui

Tempo Temperatura Humidade Ventando Class Peso

nublado 83 78 false Play 1

nublado 64 65 true Play 1

nublado 81 75 false Play 1

? 72 90 true Play 3/13(0.2)

Numero de casos que chegaram a esta folha: (3.2)

Tempo = chuvoso

Divisao feita no atributo Ventando

Ventando = true

Tempo Temperatura Humidade Ventando Class Peso

chuvoso 71 80 true Dont Play 1

chuvoso 65 70 true Dont Play 1

? 72 90 true Play 5/13(0.4)

Numero de casos que chegaram a esta folha: (2.4)

Ventando = false

Tempo Temperatura Humidade Ventando Class Peso

chuvoso 75 80 false Play 1

chuvoso 68 80 false Play 1

chuvoso 70 96 false Play 1

Numero de casos que chegaram a esta folha: (3.0)

A arvore de decisao sera a mesma que a gerada no capitulo anterior, onde nao tinhamos casos desconhecidos,

Tempo = ensolarado:

Humidade <= 75: Play (2.0)

Humidade > 75:Dont Play (3.4/0.4)

Tempo = nublado: Play (3.2)

Tempo = chuvoso:

Ventando = true:Dont Play (2.4/0.4)

Ventando = false:Play (3.0)

notando-se agora que todas as folhas possuem numeros na forma (N) ou (N/E), onde N e a soma dos pesos de cada caso e representa o numero de casos que chegaram ate a folha, que pode ser fracionario, ja que casos com valores desconhecidos sao associados a varios subconjuntos e E e a soma dos pesos dos casos que estao classificados erradamente por esta folha, ou seja, o numero de casos mal classificados.Como exemplo tempos a folha

Dont Play(3.4/0.4)

significando que 3.4 casos chegaram a esta folha e 0.4 nao pertencem a classe dont play.Olhando para o bloco final para esta folha, podemos ver que 3 caso pertencentem a este bloco com probabilidade 100% e 1 casso com probabilidade 5/13, ou seja, 40%, portanto temos 3.4 casos pertencentes a esta folha, sendo que 0.4 nao deveria estar nessa folha.

Agora usando essa arvore de decisao para classificar um caso com valores Tempo = ensolarado, Temperatura = 70, Humidade = ? e Ventando = false.Tudo ira ocorrer normalmente ate que se chegue ao no de decisao Humidade que e onde o caso nao possui valor conhecido.Explorando as possibilidades a partir deste no, chegaremos a duas classes

Play: 2.0/5.4x100% + 3.4/5.4x12% = 44%

Dont Paly: 3.4/5.4x88% =56%

Dos 5.4 casos pertencentes a este no, temos que 2.0 estao classificados como play corretamente, mas os 12% dos 3.4 casos que estao classificados como dont play pertencem a classe play, logo temos que dos 5.4 casos 44% pertencem a play e 56% a dont play.Logo, dont play e a classe escolhida.