Data Mining Arvores de Decisao e Regras de Classificacao - Notas de Aula

Notas de Aula da Disciplina de Métodos Quantitativos para Tomada de Decisão Prof Edgard Pedroso Arquivo de aulas n o 15 Data Mining construção de árvores de decisão e regras de classificação usando a função de valor de informação Mineração de dados Data Mining é um dos passos do processo de Descoberta de Conhecimentos em Bases de Dados Knowledge Discovery in Data Bases KDD é usado para produzir um conjunto de regras e padrões sob um custo computacional aceitável DATA MINING mineração de dados Uma breve introdução Encontra padrões anomalias anormalidades e regras para transformar os dados em informações úteis para a tomada de decisão Estatística Mineração de dados Serão abordados somente aspectos básicos sobre Árvores de decisão e Regras de classificação É uma das ferramentas do processo de extração de conhecimento de grandes bases de dados KDD descendência Aprendizagem de Máquina heurísticas estatística Inteligência Artificial heurísticas Árvores de Decisão e Regras de Classificação Quinlan 1993 desenvolveu a técnica que permitiu o uso da representação do conhecimento através das Árvores de Decisão A sua contribuição consistiu na elaboração de um algoritmo chamado ID3 que juntamente com suas evoluções ID4 ID6 C 45 See 5 são ferramentas adaptadas ao uso das árvores de decisão Obs O ID3 será aplicado mais adiante As Árvores de Decisão podem ser usadas em conjunto com a tecnologia de Indução de Regras mas são únicas no sentido de apresentar os resultados num formato com priorização O atributo propriedade mais importante é apresentado na árvore como o primeiro nó No topo da árvore nó raiz e os atributos menos relevantes são mostrados nos nós subsequentes abaixo Uma Árvore de Decisão utiliza a estratégia chamada dividir para conquistar Um problema complexo é decomposto em subproblemas mais simples e recursivamente a mesma estratégia é aplicada a cada subproblema Com a construção de uma Árvore de Decisão é possível obter regras de classificação Conjuntos de regras do tipo IFTHEN SEENTÃO Seja o conjunto de valores dos atributos permitidos para cada classe Valores do atributo Cor vermelho amarelo verde Valores do atributo Forma esfera cubo Exemplo de um conjunto de Regras de classificação Um exemplo simples de Árvore de Decisão COR CLASSE 0 VERMELHO FORMA AMARELO ou VERDE CUBO ESFERA CLASSE 0 CLASSE 1 Exemplo de uma Árvore de Decisão Se a cor for vermelho então classificase como 0 zero Se a cor for amarelo ou verde e a forma for cúbica então classificase como 0 zero Se a cor for amarelo ou verde e a forma for esférica então classificase como 1 um Árvore de Decisão Utilizando os conceitos de Entropia e de Ganho de Informação Seja S uma coleção de registros históricos nS14 referentes ao comportamento de uma pessoa em jogar ou não golfe nS14 casos a11 jogar b3 não jogar m4 atributos Atributos Registros Tempo Temperatura Fº Umidade Relativa Vento Jogar 1 Ensolarado Quente Alta Falso Sim 2 Ensolarado Quente Alta Verdadeira Sim 3 Nublado Quente Alta Falso Sim 4 Chuvoso Ameno Alta Falso Sim 5 Chuvoso Frio Normal Falso Sim 6 Chuvoso Frio Normal Verdadeira Não 7 Nublado Frio Normal Verdadeira Sim 8 Ensolarado Frio Alta Falso Não 9 Ensolarado Frio Normal Falso Sim 10 Chuvoso Ameno Normal Falso Sim 11 Ensolarado Ameno Normal Verdadeira Sim 12 Nublado Ameno Alta Verdadeira Sim 13 Nublado Quente Normal Falso Sim 14 Chuvoso Ameno Alta Verdadeira Não Nº Possibilidades 3x3x2x236 Atributos nós Valores dos atributos ramos Classificações finais folhas Árvore de Decisão terminologia Tempo Ensolarado Nublado Chuvoso Temperatura Quente Ameno Frio SIM SIM Umidade Alta Normal SIM Não O nó testa o atributo O ramo é um valor do atributo testado pelo nó O nó testa o atributo O nó testa o atributo A folha define a classificação finalresposta A folha define a classificação fnal resposta Ex de regra de classificação Se o tempo está ensolarado e a temperatura fria e a umidade alta então a pessoa não joga Nó raiz 1 A decisão é alcançada através de uma sequência de testes 2 Cada nó testa um atributo 3 Os ramos de cada nó são os possíveis valores de teste do atributo 4 As folhas definem a resposta de cada regra estabelecida Ex de uma Regra RAIZ NÓ NÓ NÓ RAMO RAMO RAMO FOLHA RAMO RAMO FOLHA Árvore de Decisão terminologia n 2 n 2 2 2 1 2 1 n 2 1 p log p p log p p log p p E p p Medida de Informação pelo uso da Entropia Entropia O conceito de entropia é usado para se determinar o grau de Homogeneidade purezaimpureza da amostra Computacionalmente A entropia é o número médio de bits p representar a informação em falta 0 Entropia E 1 Se a amostra completamente homogênea então E 0 Se a amostra é igualmente dividida então E 1 b a b b log a b b a a b log a a b a b b a a E E p p ab Info proporção de respostas do tipo B nº de respostas do tipo B p b proporção de respostas do tipo A a nº de respostas do tipo A p Sejam para o caso de tão somente dois tipos de respostas folhas Exemplo 2 2 2 1 2 1 O Algoritmo ID3 usa os conceitos de entropia E e de ganho de informação Gain para a construção das árvores de decisão O ID3 procura um conjunto de atributos que melhor dividam as amostras gerando ramos para a árvore Nota Bit simplificação para dígito binário Binary digit em inglês é a menor unidade de informação que pode ser armazenada ou transmitida usada na Computação e na Teoria da Informação Um bit pode assumir somente 2 valores 0 ou 1 corte ou passagem de energia respectivamente bit 1 05 1 05 1 05 05 log 05 05 log E 05 05 2 2 2 2 2 1 2 1 2 1 p log p p log p E p p n 1 i i 2 i n 2 1 p log p p E p p bits bits bits É convencionado que 0 0 0 e E 0 0 E 1 0 E 0 1 Para exemplos com duas classificações folhas p2 Não p1 Sim 1 2 2 1 p p p p 1 1 1 2 log log 2 2 log 2 log 2 log 2 1 log 50 log 10 10 10 1 10 10 10 2 Tempo Temperatura Fº Umidade Relativa Vento Ensol Nubl Chuv Quente Ameno Frio Alta Normal Falso Verd Sim 4 4 3 4 4 3 5 6 7 4 Não 1 0 2 0 1 2 2 1 1 2 Escolha do nó raiz Qual é nó do atributo mais importante Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Tempo 07496 06046 0145 bits Gain Tempo Info 11 3 Info 4 1 4 0 3 2 Gain ganho de informação do atributo Tempo é o 07496 bits log log Ent Info 3 Não 11 Sim raiz Tempo a 2 2 Então 14 3 14 14 3 11 14 11 14 14 3 11 3 11 logo e é composta por outro lado Por Medida da Informação para o atributo Tempo Tempo Temperatura Fº Umidade Rel Vento Ensol Nubl Chuv Quen Amen Frio Alta Norm Fal Verd Sim 4 4 3 4 4 3 5 6 7 4 Não 1 0 2 0 1 2 2 1 1 2 06046 bits 09709 14 5 14 4 07219 14 5 09709 0 07219 info 414032 09709 bits 5 2 5 log 2 5 3 5 log 3 5 5 2 Entropia 3 Info 32 nº nº Info 0 bits 0 log 0 1 log 1 4 4 0 Entropia 4 Info 40 nº nº Info 2 07219 bits log 5 log 1 5 2 1 log 5 4 log 5 4 5 1 5 log 1 5 4 5 log 4 5 5 1 Entropia 4 Info 41 nº nº Info 2 2 2 2 10 10 10 10 2 2 0 14 2 3 14 0 4 2 3 0 1 4 4 1 4 médio da informação Valor N S Chuv N S Nub N S Ensol 1 0 b e 0 b N X log N de existência Condição b ATENÇÃO Quando o nº de Sim eou o nº de Não é igual a zero E 0 bit Não é Definido Medida da Info para o atributo Tempo Medida da Info para o atributo Temperatura 0145 CÁLULO A CARGO DO ALUNO GainTempe ratura Medida da Info para o atributo Umidade GainUmida de 0022 CÁLULO A CARGO DO ALUNO Medida da Info para o atributo Vento 0045 CÁLULO A CARGO DO ALUNO GainVento Assim o atributo raiz pode ser Tempo ou Temperatura GainTempo 0145 Aqui escolhemos arbitrariamente expandir a árvore a partir da raiz Tempo Calculando a Medida de Ganho de Informação Gain para todos atributos obtémse Ensolarado Nublado Chuvoso Temper Umid Vento Temper Umid Vento Temper Umid Vento Tempo gain 0145 Dandose prosseguimento ao cálculo da Medida de Ganho de Informação Gain para os novos ramos desenvolvidos a partir do nó raiz TEMPO temse Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N TEMPO ENSOLARADO Temperatura Fº Umidade Relativa Vento Quente Ameno Frio Alta Normal Falso Verd Sim 2 1 1 2 2 2 2 Não 0 0 1 1 0 1 0 Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Construção dos quadros ATENÇÃO Quando o nº de Sim e o nº de Não são iguais entre si e diferentes de zero E 1bit veja nos cálculos feitos mais adiante ATENÇÃO Quando o nº de Sim eou o nº de Não é igual a zero E 0 bit veja nos cálculos feitos mais adiante 03219 bits Gain Logo 07219 04 03219 bits Gain Info 4 1 Info 2 0 1 0 1 1 Gain é o ganho de informação do atributo Então 5 07219 bits 1 5 log 1 5 4 5 log 4 5 5 1 41 Entropia 4 Info logo e é composta por outro lado a raiz Por 04 bits 5 1 2 0 5 1 0 5 2 médio da informação info 201011 Valor bit 2 1 2 log 1 2 1 2 log 1 2 2 1 Entropia 1 Frio 11 Info bits 1 1 0 Entropia 1 Ameno 10 Info bits 2 2 0 Entropia 2 Quente 20 Info 2 2 2 2 a Temperatur a Temperatur a Temperatur a Temperatur Não 1 4 Sim Ensolarado Temperatura Tempo 1 0 0 Cálculo da Medida da Informação Gain para o atributo Temperatura Cáculo p os demais atributos Gain Temper 03219 Gain Umid 0171 CÁLULO A CARGO DO ALUNO Gain Vento 0171 CÁLULO A CARGO DO ALUNO TEMPO ENSOLARADO Temperatura Fº Umidade Relativa Vento Quente Ameno Frio Alta Normal Falso Verd Sim 2 1 1 2 2 2 2 Não 0 0 1 1 0 1 0 ATENÇÃO Quando o nº de Sim eou o nº de Não é igual a zero E 0 bit ATENÇÃO Quando o nº de Sim eou o nº de Não é igual a zero E 0 bit ATENÇÃO Quando o nº de Sim e o nº de Não são iguais e diferentes de zero E 1bit Tempo gain 0145 Ensolarado Nublado Chuvoso Temper Umid Vento gain03219 gain0171 gain0171 Fim da Ramificação Fim da Ramificação Melhor gain do ramo Árvore de Decisão até o momento Tempo gain 0145 Ensolarado Nublado Chuvoso Temper gain03219 Dandose prosseguimento ao cálculo da Medida de Ganho de Informação Gain para os novos ramos desenvolvidos a partir do nó raiz TEMPO temse Construção dos quadros Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N TEMPO NUBLADO Temperatura Fº Umidade Relativa Vento Quente Ameno Frio Alta Normal Falso Verd Sim 2 1 1 2 2 2 2 Não 0 0 0 0 0 0 0 Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N ATENÇÃO Observe que todos os ramos a partir do nó tempo nublado levam a uma única decisão SIM LOGO Gain Temper 0 Gain Umid 0 Gain Vento 0 Isto será confirmado mais adiante Medida da Informação para o atributo Temperatura 0 0 bits Gain Info 4 0 Info 2 0 1 0 1 0 Gain é o ganho de informação do atributo Então 4 bits 4 0 40 Entropia 4 Info logo e é composta por outro lado a raiz Por bits 0 4 1 0 4 1 0 4 2 médio da informação info 201010 Valor bits 1 1 0 Entropia 1 Frio 10 Info bits 1 1 0 Entropia 1 Ameno 10 Info bits 2 2 0 Entropia 2 Quente 20 Info 0 a Temperatur a Temperatur a Temperatur 0 0 Não 4 Sim NubladoTemperatura Tempo 0 0 0 0 Cáculo p os demais atributos Gain Temper 0 Gain Umid 0 CÁLULO A CARGO DO ALUNO Gain Vento 0 CÁLULO A CARGO DO ALUNO TEMPO NUBLADO Temperatura Fº Umidade Relativa Vento Quente Ameno Frio Alta Normal Falso Verd Sim 2 1 1 2 2 2 2 Não 0 0 0 0 0 0 0 Sempre Sim Foi confirmado o que tinha sido previsto anteriormente Cálculo desnecessário Tempo gain 0145 Ensolarado Nublado Temper Umid Vento gain0 gain0gain0 SIM SIM SIM Fim da Ramificação Árvore de Decisão até o momento Temper gain03219 Chuvoso Tempo gain 0145 Ensolarado Nublado Chuvoso Temper gain03219 SIM Dandose prosseguimento ao cálculo da Medida de Ganho de Informação Gain para os novos ramos desenvolvidos a partir do nó raiz TEMPO temse Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N TEMPO CHUVOSO Temperatura Fº Umidade Relativa Vento Quente Ameno Frio Alta Normal Falso Verd Sim 0 2 1 1 2 3 0 Não 0 1 1 1 1 0 2 Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Medida da Informação para o atributo Temperatura Temperatura 09709 09509 002 bits Gain Temperatura Info 3 2 Info 0 0 2 1 1 1 Gain o ganho de informação do atributo Temperatur é a Então 5 09709 bits 5 log 2 5 2 3 log 5 3 5 5 2 32 Entropia 3 Info Não logo 2 e ChuvosoTemperatura é composta por 3Sim outro lado a raiz Tempo Por 09509 bits 5 1 2 09183 5 3 0 5 0 médio da informação info 002111 Valor bit 2 2 1 Entropia 1 Info 11 Frio nºsim nº não Info 09183 bits 3 1 3 log 1 3 2 3 log 2 3 3 1 Entropia 2 Info 21 Ameno nºsim nº não Info bits Info 00 Quente nºsim nº não Info 2 2 2 2 1 0 TEMPO CHUVOSO Temperatura Fº Umidade Relativa Vento Quente Ameno Frio Alta Normal Falso Verd Sim 0 2 1 1 2 3 0 Não 0 1 1 1 1 0 2 Cáculo p os demais atributos Gain Temper 002 Gain Umid 002 CÁLULO A CARGO DO ALUNO Gain Vento 09709 CÁLULO A CARGO DO ALUNO Tempo gain 0145 Ensolarado Chuvoso Temper Umid Vento gain002 gain002 gain09709 Fim da Ramificação Fim da Ramificação Melhor gain do ramo Árvore de Decisão até o momento Temper gain03219 Nublado SIM Tempo gain 0145 Ensolarado Nublado Chuvoso Temper gain03219 Vento gain09709 SIM Quen Ameno Frio Falso Verd TEMPO ENSOLARADO TEMPERATURAQUENTE Umidade Vento Alta Normal Falso Verd Sim 2 0 1 1 Não 0 0 0 0 Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Os ramos a partir da sequencia de nós TEMPO ENSOL TEMPERQUENTE levam a uma única decisão SIM Cálculo desnecessário Sempre Sim Tempo gain 0145 Ensolarado Nublado Chuvoso Temper gain03219 Vento gain09709 SIM Árvore de Decisão atualizada Quen Ameno Frio Falso Verd SIM Umid Vento gain0 gain0 SIM Podese finalizar não existe ganho de informação na ramificação ou seja poderíamos concluir de forma direta como segue SIM Quen TEMPO ENSOLARADO TEMPERATURAAMENA Umidade Vento Alta Normal Falso Verd Sim 0 1 0 1 Não 0 0 0 0 Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Os ramos a partir da sequencia de nós TEMPO ENSOL TEMPERAMENA levam a uma única decisão SIM Cálculo desnecessário Sempre Sim Tempo gain 0145 Ensolarado Nublado Chuvoso Temper gain03219 Vento gain09709 SIM Árvore de Decisão atualizada Quen Amenà Frio Falso Verd SIM SIM Umid Vento gain0 gain0 SIM SIM Amena Podese finalizar não existe ganho de informação na ramificação ou seja poderíamos concluir de forma direta como segue TEMPO ENSOLARADO TEMPERATURAFRIO Umidade Vento Alta Normal Falso Verd Sim 0 1 1 0 Não 1 0 1 0 Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Faz a ramificação Cálculo Necessário Tempo gain 0145 Ensolarado Nublado Chuvoso Temper gain03219 Vento gain09709 SIM Árvore de Decisão atualizada Quen Amena Frio Falso Verd SIM SIM Vento Umidade Medida da Informação para o atributo Umidade 1 0 bit Gain Info 1 1 Info 0 1 1 0 Gain é o ganho de informação do atributo Então 11 bit Info logo e composto de é outro lado o ramo Por bit médio da informação Info 0110 Valor bit Normal 10 Info bit Alta 01 Info 1 Umidade Umidade Umidade 1 Não 1 Sim 1 Ensol e Temper FrioUmidade Tempo 0 0 0 2 0 1 2 0 1 Gain Umidade 1 Gain Vento 0 TEMPO ENSOLARADO TEMPERATURAFRIO Umidade Vento Alta Normal Falso Verd Sim 0 1 1 0 Não 1 0 1 0 TEMPO ENSOLARADO TEMPERATURAFRIO Umidade Vento Alta Normal Falso Verd Sim 0 1 1 0 Não 1 0 1 0 1 1 bit Gain Info 1 1 Info 1 1 0 0 Gain é o ganho de informação do atributo Então 11 1bit Info logo e composto de é outro lado o ramo Por bit médio da informação Info 1100 Valor bit Verd 00 Info bit Falso 11 Info 0 Vento Vento Vento Não 1 Sim 1 Ensol e Temper Frio Vento Tempo 1 0 1 2 0 0 2 1 2 Medida da Informação para o atributo Vento Tempo gain 0145 Ensolarado Nublado Chuvoso Temper gain03219 Vento gain09709 SIM Árvore de Decisão atualizada Quen Ameno Frio Falso Verd SIM SIM Vento Umidade gain1 Fim da Ramificação Melhor gain do ramo Normal Alta gain0 Tempo gain 0145 Ensolarado Nublado Chuvoso Temper gain03219 Vento gain09709 SIM Árvore de Decisão atualizada Quen Ameno Frio Falso Verd SIM SIM Umidade gain1 Normal Alta Tempo gain 0145 Ensolarado Nublado Chuvoso Temper gain03219 Vento gain09709 SIM Árvore de Decisão atualizada Quen Ameno Frio SIM SIM Umidade gain1 Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Alta Normal Falso Verd NÃO TEMPO ENSOLARADO TEMPERATURAFRIO Umidade Alta Normal Sim 0 1 Não 1 0 SIM TEMPO ENSOLARADO TEMPERATURA FRIO Umidade Alta Vento Falsa Verd Sim 0 0 Não 1 0 0 0 0 bit Gain Vento TEMPO ENSOLARADO TEMPERATURA FRIO Umidade Normal Vento Falsa Verd Sim 1 0 Não 0 0 0 0 0 bit Gain Vento ou Vento F Vento F Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Tempo gain 0145 Ensolarado Nublado Chuvoso Temper gain03219 Vento gain09709 SIM Árvore de Decisão atualizada Quen Ameno Frio Falso Verd SIM SIM TEMPO CHUVOSO VENTOFALSO Temperatura Umidade Quen Ameno Frio Alta Normal Sim 0 2 1 1 2 Não 0 0 0 0 0 Os ramos a partir da sequencia de nós TEMPO CHUV VENTOFALSO levam a uma única decisão SIM Cálculo desnecessário Sempre Sim Umidade gain1 Alta Normal NÃO SIM SIM Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Tº Tª U V 1 E Q A F S 2 E Q A V S 3 N Q A F S 4 C A A F S 5 C F N F S 6 C F N V N 7 N F N V S 8 E F A F N 9 E F N F S 10 C A N F S 11 E A N V S 12 N A A V S 13 N Q N F S 14 C A A V N Tempo gain 0145 Ensolarado Nublado Chuvoso Temper gain03219 Vento gain09709 SIM Árvore de Decisão atualizada Quen Ameno Frio Falso Verd SIM SIM TEMPO CHUVOSO VENTOVERDADEIRO Temperatura Umidade Quen Ameno Frio Alta Normal Sim 0 0 0 0 0 Não 0 1 1 1 1 Os ramos a partir da sequencia de nós TEMPO CHUV VENTOVERDADEIRO levam a uma única decisão NÃO Cálculo desnecessário Sempre Não SIM Umidade gain1 Alta Normal NÃO SIM NÃO Árvore de Decisão da RESPOSTA Tempo Ensolarado Nublado Chuvoso Temper Vento SIM Quen Ameno Frio Falso Verd SIM SIM Umidade Alta Normal SIM Não SIM Não Registro Tempo Temperatura Fº Umidade Relativa Vento Jogar 1 Ensolarado Quente Alta Falso Sim 2 Ensolarado Quente Alta Verdadeira Sim 3 Nublado Quente Alta Falso Sim 4 Chuvoso Ameno Alta Falso Sim 5 Chuvoso Frio Normal Falso Sim 6 Chuvoso Frio Normal Verdadeira Não 7 Nublado Frio Normal Verdadeira Sim 8 Ensolarado Frio Alta Falso Não 9 Ensolarado Frio Normal Falso Sim 10 Chuvoso Ameno Normal Falso Sim 11 Ensolarado Ameno Normal Verdadeira Sim 12 Nublado Ameno Alta Verdadeira Sim 13 Nublado Quente Normal Falso Sim 14 Chuvoso Ameno Alta Verdadeira Não 15 Chuvoso Quente Normal Verdadeira 16 Nublado Frio Alta Verdadeira 17 Ensolarado Ameno Alta Falso Exemplo de aplicação Usando o conhecimento adquirido suponha que desejássemos decidir sobre jogar ou não jogar golfe tendo como informação novos padrões da sequência de atributos como indicados nas linhas 1516 e 17 da tabela apresentada Qual seria sua decisão em cada caso 15 Chuvoso Quente Normal Verdadeira NÃO 16 Nublado Frio Alta Verdadeira SIM 17 Ensolarado Ameno Alta Falso SIM Tempo Ensolarado Nublado Chuvoso Temper Vento SIM Quen Ameno Frio Falso Verd SIM SIM Umidade Alta Normal SIM Não SIM Não Notas de Aula Prof Edgard 1 GOLDBARG Marco Cesar LUNA Henrique Pacca L Otimização combinatória e programação linear modelos e algoritmos 2 ed rev e atual Rio de Janeiro Campus 2005 2 LOPES Heitor Silvério RODRIGUES Luiz Carlos de Abreu STEINER Maria Teresinha Arns Metaheurísticas em pesquisa operacional Curitiba Omnipax 2013 3 SHIMIZU Tamio Decisão nas organizações introdução aos problemas de decisão encontrados nas organizações e nos sistemas de apoio à decisão São Paulo Atlas 2001 4 ARENALES Marcos Nereu Pesquisa operacional para cursos de engenharia Rio de Janeiro Elsevier 2007 5 HILLIER Frederick S LIEBERMAN Gerald J Introdução à pesquisa operacional Porto Alegre AMGH 2013 6 GOMES Luiz Flavio Autran Monteiro GONZÁLEZ ARAYA Marcela Cecilia CARIGNANO Claudia Tomada de decisões em cenários complexos introdução aos métodos discretos do apoio multicritério à decisão 1 ed São Paulo Cengage Learning 2004 7 DUDA Richard O HART Peter E STORK David G Pattern classification and scene analysis 2nd ed New York J Wiley Sons c2001 8 Bodin L Golden B Assad A and Ball M Routing and Scheduling of veicles and crews Special edition of Computer and Operations Research col 10 n2 1983 9 Bronson R Pesquisa Operacional São Paulo Schaum McGrawHill do Brasil Ltda 1985 10 Murty K Linear and Combinatorial Programming Robert E Krieger Publishing Company Malabar Florida 1985 11 Witten Ian H Frank Eibe Data mining practical machine learning tools and techniques 2nd ed Morgan Kaufmann Publishers is an imprint of Elsevier 500 Sansome Street Suite 400 San Francisco 2005 12 Steiner MT A Notas de Aulas Importante Este material tem finalidade única e exclusivamente didática e serve apenas como notas de apoio às aulas da disciplina de Métodos Quantitativos para Tomada de Decisão do curso de Graduação de Engenharia de Produção Este material não pode ser utilizado como referência bibliográfica e muito menos comercialmente Recomendase consultar as seguintes obras