Árvore de decisão. Exemplo completo.

pois muito bem pois muito bem vamos continuar com a nossa revisão revisão refão 02 eu já dei aqui um Big Data na minha rede que eu adoro estudar deitado na rede deu um Big Data na minha rede é bo já deu um big datea na minha rede agora aqui e nós vamos continuar com a nossa revisão 02 E hoje nós vamos falar agora sobre árvores de decisão ok muito bem deixa eu ajeitar minha águinha aqui do meu lado pap PIP cadê minha água ai Jesus amar tá aqui é vamos lá árvores de decisão então árvores de decisão é um método baseado em árvores Tá certo e a aprendizagem de árvores de decisão é um dos métodos de aprendizagem mais práticos e mais utilizados na aprendizagem indutiva quando a gente usa indução Deixa eu tomar uma aguinha aqui rapidinho muito bem então as características é o seguinte dessa árvore é que o conhecimento da decision 3 é que vai ser todo o conhecimento será baseado e será desenhado e projetado uma árvore para que a gente possa realizar uma decisão Tá certo também podemos fazer com á decisão regressão Tá certo existem aves de regressão é um pouco diferente do que a gente tá trabalhando aqui agora nós vamos trabalhar com classificação mas a base é basicamente a mesma tá ok então os algoritmos de árvore de decisão e regras porque de certa forma eu consigo trabalhar isso com regras adquirem um conhecimento partir dos dados de treinamento né isso aí igual a todo algoritmo de classificação porque ele vai fazer o conhecimento simbólico a base a partir da base de treinamento Tá certo e existe uma ampla classe de algoritmos de aprendizado baseados em árvores de decisão Como por exemplo o mais simples que a gente vai aprender hoje o id3 e depois vocês quiserem pesquisar ação do id3 seria o c4. 5 tem o kart e tem outros aí tá a o viés indutivo da árvore de decisão como sendo mais uma característica dela é a preferência por árvores menores Então você vai ver o seguinte quanto menor for a árvore melhor será a a indução do algoritmo porque se a gente tiver uma árvore grande demais provavelmente a gente vai estar no problema do overfitting que eu não citei ainda para vocês não mostrei ainda a teoria de overfitting para vocês mas que o over eu já só comentei com ele né Ele é aquele causador de problema que gera 100% de acerto então fazer isso com árvor de decisão pode ser problemático tá então a preferência da árvore decisão sempre será por árvores menores uma cois legal da decisão então o seguinte que ela pode ser representada a árvore em si se você não quiser usar uma estrutura em árvore uma estrutura de dados em árvore né Você pode representar essa ávore com regras de si então que simplifica bastante porque se árvore for pequena você não precisa construir uma uma um conjunto de você não precisa criar uma estrutura de dados para representar a nossa árvore desculpa então um exemplo é esse aqui ó por exemplo eu tenho aqui aquele problema de jogar tênis ou não né então lembra que a gente tinha o Outlook né a umidade e o vento Então se o tempo estava solarado nublado ou com chuva quando a umidade Está Alta ou normal e o vento se tá forte ou weak né strong ou weak beleza Então veja eh Quais são as folhas da árvore por exemplo aqui em yes yes yes eu posso transformar essa árvore aqui em um encadeamento né de ifs então só irá jogar se o Outlook for Sunny e umidade for normal certo agora se a umidade for alta não joga ou no caso aqui ou ó o Outlook for overcast certo ou o Outlook for Rain e o Wind foi igual a Wick Então veja que eu para chegar nos is certo eu preciso eu posso modelar essa árvore numa sequência de ifs tá de forma bem simplificada então a representação o que que essa árvore aqui como ela o que que ela está representando Tá Cada nó interno testa um atributo Então eu tenho um nó interno esses nó esses nós aqui são os nós da árvore então o Outlook é um atributo humidade é um atributo o ind é o atributo tá cada ramo ou seja cada linha dessa aqui que é um ramo corresponde ao valor do atributo ou seja tenho no Outlook pode ser Sunny overcast ou rainy em humidade Pode ser ou normal normal n e em Wind pode ser strong ou weak e cada folha Ou seja a folha de uma árvore é sempre a última possibilidade de uma tá vendo aqui serão Opa desculpa cada folha atribui uma classificação no caso aqui não e sim não e sim beleza muito bem então aqui só uma repetição daquele do jogaremos quando né se o encadeamento de if eu tô mostrando aqui transformando em end ou or certo ou or tá muito bem continuando aqui essa árvore decisão é uma árvore que foi gerada a partir do problema do Iris flower tá Então veja que eu posso usar também não somente atributos que são qualitativos mas também quantitativos e quando for quantitativo eu terei o valor que seja maior ou menor coisa assim tá certo na á vai ser mais ou menos isso se a largura da sépala for menor que 5. 45 e for maior que 2.

8 éesse color Mas se for menor será cetosa e assim sucessivamente tá É bem intuitivo então que a gente vai aprender agora aqui é o algoritmo id3 que é um algoritmo básico para aprendizagem de árvores de decisão tá então o algoritmo e D3 ele aprende né árvores de decisão construindo-as de cima para baixo ou seja no modelo top Down e para construir a árvore de D3 a gente começa com a seguinte questão Se você prestar atenção numa árvore quem é o atributo raiz certo quem vai ser o primeiro atributo que a gente coloca lá em cima e quais serão os atributos que vão na sequência para baixo veja aqui eu tenho esse modelinho de áre aqui né ó por exemplo aqui nesse canto aqui quem será o atributo raiz aqui quem vira aqui são os atributos sequentes subsequentes né e os Ramos Tá bom então é isso que a gente vai aprender como montar árvore Então quem é o atributo raiz é aquele que tiver o melhor gan de informação tá nós temos que encontrar então o que é um ganho de informação antes de chegar no ganho de informação eu quero mostrar para vocês o seguinte vou falar um pouco sobre entropia OK ela faz parte do g do cálculo de ganho de informação de cada atributo entropia é uma é um um tipo de medida que ela é muito usada na física Tá certo ela vem da termodinâmica né que correndo aqui atrás de um passarinho o gato pegou um passarinho ali então entropia ele tem a ver com o nível de bagunça ou então na termodinâmica o quanto que as as moléculas estão aqui desculpa o quanto minha irmã fazendo barulho aqui o quanto que as partículas estão agitadas né no nosso caso aqui será nós vamos medir a impureza de uma coleção arbitrária de exemplos Tá certo vamos calcular a impureza de uma coleção arbitrária de exemplos Tá ok então a entropia vai ser o seguinte dada uma coleção S contendo exemplos positivos e negativos ou seja tipo sim não e pneumonia não pneumonia e joga no joga de algum conceito conceito alvo certo no caso alvo aqui é nossas targets Tá certo ou então as classes a entropia S relativa a essa classificação classificação boana é aí tem essa positivos em S tá p+ é a proporção de exemplos positivos em S log na base 2 p+ tá que é a proporção de exemplos positivos em S menos p- que é a proporção de exemplos negativos em S log na base 2 de p Men tá bem tá bom então por exemplo vamos entender melhor essa fórmula né sendo sess um conjunto de coleção de 14 exemplos de algum conceito boleano Como por exemplo o nosso conjunto de dados para ver se a pessoa vai jogar ou não tênis tá ok nós temos aqui o Outlook temperatura umidade Wind Day aqui não me interessa um identificador então ele será excluído né porque senão ele gera ruído no nossos dados nós temos aqui a classificação que é Play tênis onde a saída será sim ou não yes ou no então eu tenho o seguinte ó no desses exemplos de 14 9 são positivos vamos lá 1 2 3 4 5 6 7 8 9 então a proporção ou seja o p+ será 9 sobre 14 certo a proporção será 9 so 14 esse é o nosso p mais agora o p Men será 5 esse menos Aqui tá dizendo que é a quantidade de exemplos negativos Então vamos lá vamos contar ser É isso mesmo ó 1 2 3 4 5 eu tenho C Cinco exemplos da outra classe que eu chamei de menos tá então o p menos será 5 so 14 5 so 14 será o meu p- aí você substitui o p mais aqui esse menos faz parte da da Fórmula p mais aqui p mais aqui p menos aqui p menos aqui e calcula essa entropia do conjunto tá então eu tô calculando a entropia do conjunto inteiro Qual o nível de bagunça do conjunto inteiro tá ou de impureza no caso aqui né chamando de impureza então a entropia desse conjunto será o seguinte ó eu tenho S uma coleção de 14 exemplos de algum conceito boleano incluindo nove exemplos positivos e cinco negativos Então eu tenho aqui que a entropia de 9 + 5 Men será menos 9 so 14 log 9 so 14 - 5 so 14 Log 5 so 14 aqui vai me resultar em 0,90 94 né se zera que não precisaria colocar agora uma coisa interessante aqui da entropia é o seguinte porque eu tenho aqui 14 né eu poderia E se fosse por exemplo S positivos e sete negativos então a minha entropia seria de quanto e se fosse zero positivos e 14 negativos seria de quanto entropia E se fosse 14 positivos zer negativo seria de quanta entropia certo então a entropia ela vai variar sempre de zer a 1 Então veja bem se eu tiver uma proporção igual entre p+ e p Men a entropia calculada né que a metade para cada um será sempre de um ou seja será máxima não é agora se eu tiver uma quantidade eh máxima de positivos então será zero mas se eu também tiver uma quantidade máxima de negativos 14 negativos também será zero então a entropia sempre variar vai variar dessa forma aqui tá se como a minha entropia L foi 0,94 tá para cá né ó bem aqui assim tá então eu ten uma proporção de de e 9 sobre 14 né então vai variar mais ou menos aqui assim ó tá uma coisa mais ou menos aqui assim Então veja que a Veja isso aqui entropia vai de zero até mais um depois ele volta para zero levando em consideração que aqui no meio a quantidade de positivos e negativos são iguais por isso que é 50% para cada um certo então vamos em frente fixem bem esse conceito de Tropia porque ele vai ser importante para calcular o grande informação para multiclasse eu posso generalizar a fórmula da entropia como sendo a somatória certo da probabilidade de i ou seja probabilidade não a proporção desculpa aqui não é probabilidade não que é proporção da proporção de I log na base 2 da proporção de I onde i é a classe n classes vamos supor a primeira classe então proporção de p1 segunda classe proporção de P2 terceira classe proporção de p3 e assim sucessivamente dessa forma eu consigo fazer um cálculo de entropia multiclasse Tá certo ou seja árvore de decisão também pode ser usada para classificar em multiclasse como por exemplo a gente pode usar para cetosa calcular Iris flower que são três classes né cetosa vign E vesicolo tá bom Agora sim agora vamos para o ganho de Formação tem que prestar bastante atenção porque esse cálculo aqui ele é bem Sutil então o ganho de Formação é a redução esperada na entropia devido à ordenação sobre um atributo a Ou seja é a redução esperada na entropia causada pela partição dos exemplos de acordo com esse atributo a com um atributo a qualquer então eu tenho a entropia S que eu calculei certo então o ganho levando em consideração o a entropia do conjunto inteiro e o cálculo da entropia do conjunto do atributo a vamos com calma que a gente chega lá olha só como é que eu vou fazer isso aqui ó o exemplo vamos calcular o ganho de informação levando em consideração somente o atributo Wind certo então o que nós vamos fazer agora é esquecer toda essa parte para cá ó nós vamos esquecer Outlook temperatura umidade certo temperature e humility né Vamos eh Vamos esquecer esses atributos e vamos nos concentrar somente com o Wind tá certo mas só que a gente vai levar em consideração o Wind e play tênis muito bem então o próximo passo é o seguinte ó de todo o conjunto a proporção sem vai ser o seguinte eu tenho nove positivos e cinco negativos tá mas se eu isolar o atributo Wind quando eu isolo só o valor do atributo Wind Wi quantos positivos e negativos eu tenho Então vamos levar ess vamos L assim ó Wi no um Wi S Então tá um a um o S 1 a do né wik Yes 1 a 3 wik no 2 A 3 wik Yes 2 a 4 Wi s ou 2 a me enrolei todinho agora vamos voltar de novo ó vou fazer o seguinte eu vou contar só wik agora wik 1 wik 2 só dois então deu 2 Agora vamos contar os positivos o o is1 is2 is3 is4 is5 E6 Então quando for o ind e o atributo quando for o atributo ind e o valor do atributo for o i Eu tenho seis positivos e dois negativos Entendeu agora quando o atributo for Wind e o valor do atributo for strong Então vamos lá positivo strong positivo 1 2 3 Então eu tenho três positivos e quando atributo strong em relação a negativa vamos lá strong no 1 2 3 então eu tenho três negativos Tá certo que uma proporção vai ser igual aqui no strong Deu para entender quando eu tenho todo o conjunto eu tenho essa proporção mas quando eu separo só o Wing e eu vejo cada valor do atributo eu vou ter essa proporção aqui tá certo vamos PR frente né então o ganho de informação eu tenho que calcular o seguinte eu tenho que calcular a entropia do conjunto inteiro que eu já calculei que é 0,94 e agora vou calcular a entropia quando o conjunto for só esse conjunto do I certo então eu faço uma proporção aqui ó eh do wik aqui eu terei a entropia Geral do conjunto a entropia quando for o Wick e a entropia quando for strong tá eu tenho somatório das duas entropias então eu calculo esse essa entropia aqui de wick Tá certo calculo a entropia de strong aqui e aqui eu vou ter o seguinte ó 0,94 Tá certo e ele faz esse cálculo aqui você pode fazer cálculo matemático aí na calculadora certinho e aí ele acha que o gan de informação para o ind aqui ó será de 0,048 tá então você vai ver que esse ganho de informação é relativamente baixo tá certo então você deve fazer esse cálculo de gan de informação com cada cada coluna digamos assim levando em consideração os valores que ele está eh usando né o wickstrom Então como objetivo de encontrar a raiz da árvore como objetivo de encontrar a raiz calculamos todo o ganho de informação para todos os atributos do dataset né todos os atributos aí do dataset Beleza então quando eu calculo o ganho de informação lá ó usando Outlook Eu achei que o ganho de informação foi 0 V 246 quando eu calculei o ganho de informação pra umidade o ganho de informação foi 0 PR foi 048 e PR temperatura 0,29 0,029 0,048 e 0,29 a raiz da árvore será o atributo que tem maior ganho de informação nesse caso aqui Outlook então eu venho e já coloco o Outlook aqui tá vendo é isso aqui agora o seguinte quando eu tenho o Outlook nesse caso o que vai acontecer é que eu vou separar e quais são os valores de Outlook na sequência que eu achar eu dou digamos assim um Unic né e eu que eu achar eu vou colocando as as informações O Primeiro que Vier que eu da sequência sun eu coloco como um ramo não é E aí desse ramo eu seleciono somente somente todo o subconjunto que é s Deixa eu voltar aqui um pouquinho que aí a gente vai ter uma noção melhor Ó quem é s aqui ó D1 D2 D8 D9 e d11 certo eu vou selecionar todos esses todo esse valor do atributo a partir de eu vou selecionar tudo que for os outros atributos eu vou selecionar essa temperatura hot hot e vou selecionar essa temperatura aqui M aqui vou selecionar a umidade e aqui mais normal aqui norm iar esse subconjunto aqui como sendo o Wind weak o Wind strong e Wick Wick e aqui strong e vou selecionar D subconjunto Quais são os playis né no caso no no e aqui será no também aqui nesse sun aqui será Yes e aqui nesse sun aqui será Yes então eu vou fazer uma seleção de subconjunto baseado somente no atributo s que aqui ó todas as linhas D1 D2 D8 D9 d11 Então esse será meu subconjunto tá E aí eu vou calcular com base nesse subconjunto mais uma vez qual é o atributo mais proeminente digamos assim para ser colocado aqui como é que eu calculo isso faço o ganho de formação da mesma forma Tá certo gan de formação da mesma forma veja que nesse caso aqui em overcast Eu tenho um caso curioso porque em overcast eu tenho que quando o Outlook lá for overcast na D3 D7 D12 d13 todos os atributos serão positivos Ou seja eu tenho quatro atributos que são is e nenhum que é zero quando eu chegi nessa situação então eu sei que quando for overcast seja a árvore decisão decide o seguinte ó toda vez que o Outlook for overcast y e pronto não é agora quando for Rain ele vai pegar o subconjunto da linha D4 D5 D6 D10 e d14 e vai calcular o ganho de informação para todos os outros atributos que não são Outlook né e calcula esse ganho de informação e coloca aqui o que tiver o atributo que tiver tiver m gan de informação conforme eu mostrei o cálculo Beleza então vamos lá quando o atributo for quando atributo Outlook for sun eu seleciono a linha D1 D2 D8 D9 e d11 e vou calcular agora em relação a s certo eh qual é o melhor Qual atributo tem mais ganho de informação excluindo o Outlook então eu selecionei essas linhas e vou calcular e eu eu descobri que é acho que aqui é um igual né vai dar 9. 7 o primeiro aqui é um igual Tem um errinho aqui tá aqui é igual 0. 97 paraa umidade 0.

57 para temperatura e 0. 19 para o Wind ou seja o próximo atributo que virar aqui será o que tiver quem tem maor gan de informação prando todas as linhas que eu Outlook é sun ou seja humidade umidade Vem aqui agora pergunta o que acontece com o atributo umidade o atributo atributo umidade será simplesmente excluído das próximos dos próximos ganos de informação Ou seja quando eu vim aqui em Rain ele não vai calcular Qual é o ganho de umidade porque umidade já foi colocado aqui tá aqui terá que ser o ou temperatura ou Wind Tá bom então esse processo é um processo recursivo né você vai sempre entrar à esquerda sempre entrando na esquerda até achar o fim até chegar num fim num nó folha certo então quando ele entrou aqui no atributo ó ele pegou o Outlook aqui passou pro sun chegou aqui achou umidade da umidade ele vai selecionar as três os quais são os atributos que os valores do atributo que tem aqui quais são os Ramos Ele sempre vai descer à esquerda até achar yes ou no no caso aqui do overcast tá vendo Então depois que ele faz isso recursivo ele passa para o próximo ramo tá igual uma árvore montagem de árvore Então esse processo ele se repete recursiv recursivamente até ele repete o processo de um de selecionar um novo atributo e particiona os exemplos de treinamento e é repetido para Cada nó descendente não terminal até que ele achea um nó terminal Tá certo então recursivamente também são utilizados somente os exemplos de Treinamento Associados a esse nó no caso por exemplo o sun tá então atributos que foram incorporados anteriormente à árvore eles são excluídos como eu tinha falado aqui ó quando eu coloquei tem umidade aqui quando eu vou continuando a montar a árvore recursivamente né no processo ele não vai colocar umidade do lado de cá não vai testar Tá certo e chuva comidade não vai testar isso então os atributos que foram incorporados anteriormente à árvore serão excluídos né são excluídos e qualquer atributo que aparecer somente ele deve aparecer somente uma vez ao longo de qualquer caminho da árvore qualquer atributo deve aparecer somente uma vez ao longo de qualquer caminho na árvore Tá bom então para cada ramo da árvore o processo continua até que uma das condições a seja a baixa seja atendida todos os atributos já estão incluídos ao longo deste caminho da árvore não é por exemplo quando eu venho descendo aqui todos os atributos se eu venho descendo aqui foram incluídos acabou os exemplos de Treinamento Associados com esse nó folha tem o mesmo valor de atributo alvo Então quando você acha um atributo alvo por exemplo aqui ó overc achou is acabou tá certo então Eh o final da nossa árvore quando a gente usando aquele aquele conjunto de dados aqui que a gente estava trabalhando com ele baseado no ganho de informação a árvore final que nos é entregada é isso aqui ó tá então eu tenho o Outlook Sunny overcast Rain e aqui eu tenho a umidade aut normal e o Wind strong Week beleza e os nossos no Folha São no quando tenho outl umidade alta eu não jogo quando eu tenho outl sun normalidade normal eu jogo quando eu tenho over eu jogo quando eu tenho com strong eu não jogo quando eu tenho Rain com eu jogo essa minha árvore decisão então de aprendizagem do id3 como um método de busca em um espaço de hipótese Tá certo então por uma hipótese que se ele se ajusta aos exemplos de treinamento mas veja o seguinte o que eu quero dizer é que ele acha uma possibilidade dentro do conjunto de possibilidades de árvore provavelmente existe uma árvore melhor do que essa para poder classificar o nosso conjunto de treino ass fazer nova classificação mas ela nos retorna uma hipótese dentro do conjunto de hipótese Agora se a árvore for grande demais pode ser que eu entre no super ajustamento tendo um problema tá então É isso aí então a hipótese que a id3 nos retorna espaço hipótese né el é buscado pelo D3 é conjunto de árvores pela decisão pela árvore de decisão possíveis então ele vai buscar uma árvore uma hipótese dentro do conjunto de árvores de decisão possível beleza e usando o pit learning que você pode usar no seu programa né no Python você vai fazer o seguinte from P learning né sk learning Import 3 e aqui eu tenho um vou criar um objeto né chama de clf esse esse objeto clf é muito comum que é um padrão quase né o classificador certo clf 3.