A rvore de deciso consiste de uma hierarquia de ns internos e externos que so conectados por ramos.O n interno, tambm conhecido como n decisrio ou n intermedirio, a unidade de tomada de deciso que avalia atravs de teste lgico qual ser o prximo n descendente ou filho.Em contraste, um n externo (no tem n descendente), tambm conhecido como folha ou n terminal, est associado a um rtulo ou a um valor.Em geral, o procedimento de uma rvore de deciso o seguinte, apresenta-se um conjunto de dados ao n inicial (ou n raiz que tambm um n interno) da rvore dependendo do resultado do teste lgico usado pelo n, a rvore ramifica-se para um dos ns filhos e este procedimento repetido at que um n terminal alcanado.A repetio deste procedimento caracteriza a recursividade da rvore de deciso.No caso das rvores de deciso binria, cada n intermedirio divide-se exatamente em dois ns descendentes, o n esquerdo e o n direito.Quando os dados satisfazem o teste lgico do n intermedirio seguem para o n esquerdo e quando no satisfazem seguem para o n direito.Logo, uma deciso sempre interpretada como verdadeira ou falsa.Deve ser mencionado que, restringimos a nossa descrio de diviso para rvores binrias, pois estas sero empregadas nesta tese.Contudo, na literatura h rvore de deciso com vrias divises e sua descrio pode ser encontrada em Zighed. uma representao grfica de uma rvore de deciso binria.rvore de Deciso Binria.Na figura anterior, os crculos representam os ns internos (intermedirios ou decisrios) os quadrados representam os ns folhas ou terminais as linhas representam os ramos que interligam dois ns e x1 e xrepresentam as variveis decisrias.Chama-se de varivel decisria a varivel de entrada que levar a uma nova diviso da rvore de deciso, em relao a um possvel valor.A interpretao da representao grfica da rvore de deciso ilustrada anteriormente descri da seguinte forma, Quando a condio satisfeita, os dados seguem para o n esquerdo (SIM) e, caso contrrio, os dados seguem para o n direito (NO) O aprendizado de uma rvore de deciso supervisionado, ou seja, o mtodo aproxima funes-alvo de valor discreto, na qual a funo aprendida representada por uma rvore de deciso.As rvores treinadas podem ser representadas como um conjunto de regras "Se-Ento" para melhoria da compreenso e interpretao.As rvores de deciso so estudadas em vrios campos de pesquisa como cincias sociais, estatstica, engenharia e inteligncia artificial.Atualmente, elas tm sido aplicadas, com sucesso, em um enorme campo de tarefas desde diagnstico de casos mdicos at avaliao de risco de crdito de requerentes de emprstimo.rvores de deciso usadas para problemas de classificao so chamadas de rvores de Classificao.Em algumas referncias bibliogrficas, a rvore de classificao pode ser denominada, simplesmente, como rvore de deciso.Nas rvores de classificao, cada n terminal ou folha contm um rtulo que indica a classe predita para um determinado conjunto de dados.Neste tipo de rvore pode existir dois ou mais ns terminais com a mesma classe.Para ilustrar uma rvore de classificao, encontra-se na Figura a representao grfica deste tipo de rvore para duas classes.rvore de Classificao.Na rvore de classificao ilustrada na figura anterior as classes formadas so Classe 1, representada pelos ns e 5, e a Classe 2, representada pelo n 4.As regras obtidas aps a rvore treinada so, Regra para Classe 1 Se (x1 >) ou Se (x1 = e x>) Regra para Classe Se (x1 = e x=) rvores de deciso usadas para problemas de regresso so chamadas de rvores de Regresso.Nas rvores de regresso, cada n terminal ou folha contm uma constante, geralmente, uma mdia ou uma equao para o valor previsto de um determinado conjunto de dados.Empregando a mesma representao grfica da rvore de classificao, temos para cada n terminal um modelo linear.Existem dois aspectos que merecem destaques em uma rvore de deciso, o crescimento e a poda, que sero abordados na seo.Por fim, um dos mais conhecidos e mais completos algoritmos de rvore de deciso o CART "Classification and Regression Tree" que foi proposto por Breiman.Como este algoritmo ser empregado em uma das etapas da modelagem proposta nesta tese, conveniente realizar uma breve descrio do CART na seo 3.As rvores de deciso so construdas usando um algoritmo de partio recursiva.Este algoritmo constri uma rvore por divises recursivas binrias que comea no n raiz e desce at os ns folhas.Tm-se dois fatores principais no algoritmo de partio, a forma para selecionar uma diviso para cada n intermedirio (Crescimento) e uma regra para determinar quando um n terminal.O problema chave, no algoritmo de partio recursiva, a confiabilidade das estimativas do erro usado para selecionar as divises.As escolhas da diviso em nveis maiores da rvore produzem, freqentemente, estatsticas no-confiveis apesar da estimativa do "erro de resubstituio" (estimativa obtida com os dados de treinamento usado durante o crescimento da rvore) manter-se decrescendo.Com isto, a preciso das estimativas do erro fortemente dependente da qualidade da amostra.Como o algoritmo divide recursivamente o conjunto de dados de treinamento original, as divises esto sendo avaliadas com amostras cada vez menores.Isto significa que as estimativas de erro tm menos confiabilidade medida que crescemos a rvore.Com intuito de minimizar este problema e evitar o superajustamento dos dados de treinamento com rvores muito complexas, tem-se a estratgia conhecida como mtodo de podagem.H dois procedimentos alternativos para podagem da rvore de deciso, a ps-podagem e a pr-podagem.A ps-podagem o processo pelo qual uma rvore crescida ao tamanho mximo e ento mtodos de evoluo confiveis so usados para selecionar a rvore podada de tamanho certo desde o modelo inicial.Este algoritmo considera a podagem como um processo de "dois-estgios".No primeiro estgio, um conjunto de rvores podadas de Tmax (rvore de tamanho mximo) gerado de acordo com algum critrio, enquanto no segundo estgio uma dessas rvores selecionada como o modelo final.Os mtodos de ps-podagem podem ser computacionalmente ineficientes, no sentido que no usual achar domnios onde uma rvore extremamente grande (por exemplo, com milhares de ns) ps-podada em poucas centenas de ns isto parece um desperdcio computacional.Uma alternativa de parada no procedimento de crescimento da rvore interromper o crescimento to logo a diviso seja considerada no-confivel.Isto conhecido como a pr-podagem da rvore.O mtodo de pr-podagem usa um procedimento "passo nico".Este algoritmo corre atravs dos ns da rvore ou "de baixo para cima" ou "de cima para baixo", decidindo para cada n, se para podar de acordo com algum critrio de avaliao.Os mtodos de pr-podagem tambm apresentam um ponto negativo no seu algoritmo.A pr-podagem corre o risco de selecionar uma rvore subtima ao interromper o crescimento da rvore.Breiman descreveu duas alternativas para a seleo da rvore final baseada nas estimativas dos erros obtidos.Ou seleciona a rvore com menor erro estimado ou escolhe a menor rvore na seqncia, cujo erro estimado est dentro do intervalo, Errb + SE(Err, onde Errb o menor erro estimado e SE, Err o erro padro desta estimativa).Mas tarde, este mtodo ser conhecido como a regra "SE".Para maiores detalhes sobre essas alternativas consultar Breiman ou Zighed.Destaca-se que para rvores de classificao a podagem em funo da complexidade do custo mnimo (erro de resubstituio) e para rvores de regresso, a podagem em funo da complexide do erro mnimo.A metodologia do modelo CART tecnicamente conhecida como partio recursiva binria.O processo binrio porque os ns pais so sempre divididos exatamente em dois ns filhos e recursivamente porque o processo pode ser repetido tratando cada n filho como um n pai.As principais caractersticas do CART so, definir o conjunto de regras para dividir cada n da rvore decidir quando a rvore est completa associar cada n terminal a uma classe ou a um valor preditivo no caso da regresso.Para dividir um n em dois ns filhos, o algoritmo sempre faz perguntas que tem apenas um "sim" ou um "no" como resposta.Por exemplo, as questes podem ser, a idade