Janelamento
Quando Quilan estava trabalhando no predecessor do c4.5, o ID3, não era comum o uso de memória virtual e a memória fisica era limitada, devido a esse problema Quilan desenvolveu este método que permite trabalhar com conjuntos relativamente grande de dados.
Este método contava inicialmente com um subconjunto do conjunto de casos de treinamento, chamado janela, que era usada então para construir um árvore de decisão.Esta árvore era então usada para classificar todo o conjunto de treinamento e uma parte daqueles que fossem classificados erradamente eram adicionados a janela e a partir dela era gerada uma nova árvore, seguindo-se assim até que todos os casos fossem classificados corretamente pela arvore.No final, normalmente, a janela continha apenas um subconjunto dos casos de treinamento.
O janelamento para o c4.5 é parecido com a do ID3.Com a diferença que enquanto o ID3 selecionava randomicamente os casos que seriam usados na janela inicial, o c4.5 seleciona um subconjunto onde a distribuição das classes é a mais uniforme possível.O c4.5 também trata diferentemente na hora de adicionar os casos mal classificados à janela, enquanto o ID3 tem um número fixo quanto ao número de casos que podem ser adicionados a janela, o c4.5 adiciona pelo menos metade à próxima janela, convergindo mais rapidamente para a árvore final.Outra diferença é que agora o processo pode parar caso as árvores que estejam sendo geradas não apresentem melhoras.Isso evita que no caso do conjunto de treinamento possuir dados inconsistentes as janelas cresçam até conter todo o conjunto de casos de treinamento.
Exemplo
Quando o c4.5 gera uma árvore de decisão usando janelamento apresenta um sumário para cada ciclo, como mostrado na figura 6-1.Para o primeiro ciclo foi gerada uma árvore com 15 nós a partir da janela inicial, que continha 502 casos dos 2514.Esta árvore classificou erradamente 5 casos dos que faziam parte da janela e 15 para os outros casos, num total de 20 casos mal classificados.Os 15 casos classificados erradamente são então adicionados a janela, gerando uma nova árvore a partir desse novo conjunto, composta por 19 nós, com 8 dos casos que fazem parte da janela sendo classificados erradamente e 29 dos outros casos.Finalmente, quando esses 29 casos são adicionados a janela é gerado uma nova árvore que classifica erradamente 8 dos casos pertencentes a janela e nenhum dos outros casos, protanto, o processo termina.A árvore final foi gerada por apenas 546 dos 2514 casos existentes, e mesmo assim é muito semelhante a gerada por todos os casos que é mostrada na figura 5-1.
Cycle Tree ---Objects--- ----------------Errors--------------- size window other window rate other rate total rate ----- ------ ------ ------ ------ ------ ----- ----- ----- ---- 1 15 502 2012 5 1.0% 15 0.7% 20 0.8% 2 19 517 1997 8 1.5% 29 1.5% 37 1.5% 3 21 546 1968 8 1.5% 0 0.0% 8 0.3%
Figura 6-1
Razões para reter o processo de janelamento
Hoje em dia a maioria dos computadores não apresenta problemas de falta de memória, pois esta se tornou muito barata e também devido ao fato da memória virtual atualmente em uso em todos os computadores.Portanto, os argumentos apresentados a seguir vão abordar outros pontos de visão onde o janelamento pode trazer benefícios.
Construção Rápida de Árvores
Isto é algo que pode ser conseguido, mas será necessário contar com uma base de fatos onde os dados sejam consistentes e determinaveis, para que o número de ciclos seja pequeno, proporcionando uma rápida construção da árvore final a partir de um número relativamente pequeno de casos, se comparados ao conjunto total.Nesses casos o janelamento pode chegar a reduzir o tempo necessário para a construção de uma árvore por um fator de três [Catlett, 1991b].
Como a maioria das bases de fatos possuem dados inconsistentes, isso pode gerar processos onde serão necessários muitos ciclos para se chegar a árvore final, assim na maior parte das vezes o tempo usando janelamento será maior.
Predições mais Precisas
O principal benefício em usar janelamento esta em se conseguir gerar árvores com maior poder de predição.Existem vários aspectos presentes neste processo que irão fornecer este resultado.De acordo com experimentos realizados por Jason Catlett quando a janela inicial é composta por um conjunto uniforme de classes isto irá gerar melhores escohar dos limites para os atributos continuos e também nas escolhas dos atributos testes, num nível mais profundo da árvore.O janelamento também permite a geração de várias árvores de decisão diferentes, com isso é possivel fazer a escolha daquela com a menor taxa de erro e também pode-se gerar um conjunto de regras para cada árvore e ao final gerar um classificador a partir de todas elas.
Este processo permite gerar um classificador com alta taxa de predição, mas pode consumir muito tempo computacional.