Como funciona uma árvore de decisão ?

Fabio Duarte Junior

Published in

Data Hackers

24 min readMay 8, 2021

Índice

Introdução
Como as árvores de decisão funcionam ?
Esclarecendo com exemplos
Mas e como a máquina consegue entender como dividir os dados ou decidir qual é a melhor maneira de fazer isso?
Aprendizado de máquina e árvores de decisão
Tipos de abordagem — Regressão e Classificação
Kinect e classificações
Abordagens para o aprendizado — Algorítimos de árvore de decisão
CART — Classification And Regression Trees
Como seria um passo a passo pra criar uma árvore de decisão ?
Desafios das árvores de decisão : overfitting e underfitting
E se ao invés de uma árvore tivermos uma floresta ?
Conclusão
Referências

Introdução — O que é uma árvore de decisão ?

Usado desde datamining até o reconhecimento das partes do corpo utilizado pelo Kinect da microsoft Decision Tree ou árvore de decisão, no contexto de aprendizado de maquina, é o nome de um algorítimo utilizado para fazer previsões usando um principio de “separar” os dados em grupos de forma hierárquica.

Obs: Se você tem conhecimento de probabilidade pode já ter esbarrado no conceito de árvore de probabilidade ou diagrama de árvores de decisão, a ideia deles e do algorítimo de árvores de decisão é a mesma.

Como as árvores de decisão funcionam ?

Conceito geral

De uma forma geral o algorítimo de árvore de decisão tenta encontrar padrões nos dados usando alguns conceitos matemáticos como ‘entropia da informação’, ‘ganho de informação*’ e GINI index .

Não vou entrar muito a fundo na parte acadêmica da coisa, mas se você curte matemática, abaixo esta a formula usada para calculo de information gain:

https://en.wikipedia.org/wiki/Information_gain_in_decision_trees

Bonita não ?

Basicamente o algorítimo aplica nos dados as formulas que eu mencionei acima e assim vai organizando e classificando grupos.
Para cada grupo que encontra ele divide em subgrupos que por sua vez são divididos novamente e assim por diante até não conseguir dividir mais ou até chegar em um limite que pode ser parametrizado.

Ao final do processo os grupos que não tiverem ninguém abaixo deles na hierarquia são chamados leaves(folhas) e eles que vão servir de base para fazermos as predições.

Mas se acalme, haha, como pode ainda estar um pouco nebuloso para você, vamos para um exemplo que vai esclarecer bem as coisas.

Obs: o termo em inglês é ‘information gain’, encontrei o termo sendo usado em português como ‘ganho de informação’. Caso exista um termo mais exato em português para esse conceito, eu agradeço se puder me informar para que eu possa me atualizar e atualizar o artigo.

Esclarecendo com exemplos

Acredito que a forma mais intuitiva para aprender como uma árvore de decisão funciona sera através de exemplos, então, vamos lá :

Apresentando o problema :

Imagine que um grande amigo seu está precisando alugar seu apartamento em São Paulo para poder juntar uma grana, mas não tem ideia de quanto cobrar de aluguel.
Seu amigo sabe que você sempre foi bom em fazer contas na escola e pede sua ajuda para poder definir um preço bom e justo para o aluguel do imóvel.

Ele te manda por e-mail uma planilha do Excel que ele achou na internet que contem algumas informações sobre apartamentos para locação na cidade de São Paulo.
A planilha se parece com isso:

Observando os dados que seu amigo te passou você percebe que os apartamentos que tem acima de 60 m² são em media mais caros, não só isso, aparentemente os imoveis que ficam no centro tem um aluguel mais caro.

Sendo assim você separa os dados em dois grupos os que tem mais de 60 m² e os que são menores. Você os chama de grupo 1 e grupo 2.

Depois, dentro de cada um desses grupos, você separa os que ficam no centro e os que não. Você decide chamar de grupo A os imóveis fora do centro e os demais de B.

No final você tem 4 grupos e um valor médio de aluguel para cada um deles.

Grupo 1 - Menor que 60m²
Grupo 1A - imóveis fora do centro da cidade
valor = 800
Grupo 1B - imóveis no centro de cidade
valor = 1000
Grupo 2 — Mais de 60m²
Grupo 2A — imóveis fora do centro da cidade
valor = 900
Grupo 2B — imoveis no centro da cidade
valor = 1200

Para visualizar melhor você desenha um diagrama com as suas descobertas:

Agora com esse diagrama em mãos você consegue ajudar seu amigo a estimar um preço para o aluguel, basta comparar a metragem e a localização do apartamento dele com o diagrama acima.

O exemplo acima ilustra a dinâmica de como funciona uma árvore de decisão, você passa os dados, o algorítimo separa os grupos e subgrupos ate chegar nas “folhas” e nelas teremos o valor estimado para a previsão.

Esse processo é conhecido como “treinamento” do algorítimo, pois é onde o modelo aprende os padrões que existem nos seus dados.

A segunda parte, conhecida como “predição” é quando comparamos as informações de dados que o algorítimo ainda não viu com os padrões que a árvore encontrou.

Vamos falar um pouco mais sobre esse diagrama.

Os círculos em vermelho indicam os “nós” da árvore enquanto os verdes indicam as folhas.

Mas e como a máquina consegue entender como dividir os dados ou decidir qual é a melhor maneira ?

Os algorítimos de machine learn, inclusive árvores de decisão, procuram aprender padrões.
Para explicar melhor, vamos para um exemplo :

Quero ensinar para um robô, usando árvores de decisão, se ele deve tomar cuidado com os “objetos” e seres que encontra.

Esse robozinho tem a capacidade de catalogar características dos itens que ele vê.

Você tem o conjunto de dados que foi gerado pelo robozinho até agora, a ultima coluna é o resultado da interação do robozinho com o item que ele estava observando.

Dados que o robozinho capturou durante seu passeio.

A ideia é que se eu apresentar pra um robozinho um novo item que ele ainda não viu, mas a partir das características observadas, ele consiga prever se aquilo que ele esta vendo morde ou não morde.

Por exemplo se eu mostrar um animal, gato e branco para meu robozinho ele deve conseguir, com base no que ele aprendeu dos dados acima se um gato é passível de mordê-lo ou não e evitar interagir com ele, se for o caso.

Vamos lá.

Queremos usar esses dados para montar uma árvore de decisão, mas precisamos eleger qual é o melhor nó para começar a árvore.

Então elegemos um valor qualquer desse conjunto de dados para ver se ele daria um bom nó em nossa árvore de decisão:

Vamos pegar a coluna cor e o valor “Preto”, assim pra montar o nó vamos fazer a pergunta:

A cor é igual a “Preto” ?

Para comparação vamos escolher mais um valor pra testar se é um bom nó, agora da coluna tipo e o valor “Fruta”, assim podemos comparar qual dos dois nós é melhor para compor a nossa árvore.

O tipo é igual a “Fruta” ?

No primeiro caso, o nó separando pela cor “preto” , a sugestão seria para o robozinho tomar cuidado com Leopardos, mas não com bananas e com cachorros. Bom, essa não parece ser uma boa forma de dividir os dados para o nosso intuito ( o robozinho evitar ser mordido), pois, dependendo de como montarmos o resto da árvore ele teria um viés de pensar que cachorros e bananas são parecidos só por causa da cor e acabar sendo mordido (pobrezinho)

No segundo caso, separando pelo tipo “Fruta” parece uma ideia melhor, pois ele consegue agrupar bem os itens com características parecidas.

Se fosse pra escolher um desses dois nós para montar uma árvore de decisão o segundo seria uma melhor opção, pois ele é mais “puro” ou seja, ele consegue agrupar os itens de uma forma melhor.

A maquina não consegue fazer isso da mesma forma intuitiva que fazemos, então ela usa um recurso matemático para fazer isso chamado de calculo de impureza, que basicamente tem como finalidade executar essa mesma comparação que fizemos da forma intuitiva acima.

Quando o algorítimo esta decidindo quais nós usar numa árvores o intuito é achar uma combinação que tenha a menor impureza possível e fazer isso recursivamente ate que acabem as perguntas a serem feitas.

Cada nó representa uma pergunta de “sim e não” e as folhas desses nós representam os resultados positivos e negativos.

Vamos a um exemplo agora usando matemática e cerveja para tentar explicar melhor o conceito de impureza :

Então para montar a árvore usamos os nós que tem a impureza mais baixa.

Bom, um exemplo para uma compreensão inicial é o quanto meus dados estão espalhados, para os cervejeiros de plantão temos o caso abaixo que ilustra isso.

Digamos que alguém, com bastante tempo, tirou os rótulos das garradas de cerveja que tinham em um balde numa festa e colocou separado num outro balde.

No balde haviam 2 garrafas da cerveja de marca A(tampa verde) e 3 garrafas da marca B (tampa vermelha).

O pessoal da festa decide criar uma brincadeira : A pessoa deve retirar dos baldes, sem espiar, uma garrafa e um rotulo e ver se batem. Leva o premio quem tiver a sorte de acertar mais .

Você que é uma pessoa que ama matemática e confia mais nela do que na sorte decide calcular qual é a chance de alguém acertar verificando o grau de incerteza associada a essa brincadeira (provavelmente essa festa foi dada pela turma de estatística de uma universidade hahaha)

O raciocínio foi o seguinte :

A impureza é um numero entre 0 e 1, quanto menor o numero menor é a impureza.

Há no total 5 garrafas de cerveja com 5 rótulos

Se todas as 5 garrafas fossem da mesma marca e eu retirasse uma cerveja teria 100% de chance de acertar qual é o rotulo dela.

Se o menor valor de impureza indica que minha chance é maior então o melhor numero que eu posso ter é zero. Zero equivale a 100%.

Então para chegar no valor de impureza zero você usa o seguinte calculo :

Quantidade de garrafas da marca da cerveja que eu retirei, no caso tenho 5 da mesma marca dividido pela quantidade total de rótulos, no caso 5 também No caso eu teria : 5 / 5 = 1

Bom mas eu disse que o resultado deveria ser zero para poder representar 100% ou zero de impureza. Já que meu valor de impureza deve estar entre zero e um, então eu resolvo isso pegando o maior valor de impureza, que é 1 ou seja 1 é totalmente impuro, e subtraio dele o resultado da minha conta acima :

Maior valor possível de impureza - (qtd de cervejas da marca A / qtd total de rótulos )

Nesse caso:

1 -(5 /5 ) = 0

Agora parece certo o calculo, mas antes de por em pratica, você faz mais um teste

Se das 5 garrafas eu tiver 1 da marca A e 4 da marca B

Então quando eu pegar uma garrafa a marca A do balde a minha incerteza, com base no calculo de impureza, vai ser:

1 — (1/ 5) = 0.8

0.8 é um numero bem próximo de 1, ou seja, minha incerteza se vou conseguir retirar do outro balde um rótulo da mesma marca é bem alta, eu estou bem incerto se vou conseguir acertar ou não.

Agora se eu tivesse retirado uma garrafa da marca B o calculo seria :

1 - (4/ 5) = 0.2

0.2 significa que minha incerteza é quase zero! Minhas chances de pegar o rótulo correto é bem grande!
Agora com certeza de que seus cálculos são bons suficientes, você decide ir jogar.

No balde há : 2 garrafas da marca A e 3 garrafas da marca B.

Você retira uma garrafa da marca A, qual a sua incerteza em retirar o rotulo correto do outro balde baseado no calculo de impureza ?

Essa eu deixo pra você calcular =] .

Esse foi o exemplo de uma abordagem para calcular a incerteza, mas como mencionado no artigo existem varias abordagens e algorítimos diferentes pra calcular o quão bom é um nó e se ele deve ser usado na árvore.

O Algorítimo CART, que é o que estou usando de referência pra o artigo, utiliza para esse fim uma métrica/calculo chamada de Gini impurity . Para saber mais : https://en.wikipedia.org/wiki/Decision_tree_learning#Gini_impurity

Só um lembrete por aqui, eu criei os exemplos desse artigo para terem uma abordagem didática, comparados com situações reais onde ha conjuntos de dados com uma gama de características e formatos diferentes, podem parecer bem bobos. Porém eu aposto na simplicidade desses exemplos para trazer a didática e o entendimento para quem não tem afinidade com matemática e logica ou pra quem esta iniciando e tem essa curiosidade. Um outro adendo é que, no mundo real, ha informações que não tem correlação uma com a outra e um dos trabalhos de um cientista de dados ao utilizar árvore de decisão é ter preparado e selecionado bem os dados de entrada. É como dizem “Garbage In Garbage out”, se você mandar lixo pra árvore de decisão ela te devolve lixo.

Aprendizado de máquina e árvores de decisão

De forma bem rasa, aprendizado de maquina ou “machine learn” consiste em dar a uma maquina a capacidade de aprender padrões e depois utilizar esses padrões para diversos fins que podem ser empregados como fazer predições, separar grupos de dados, analisar imagens etc. Existem dezenas de algorítimos, técnicas ou abordagens que podem ser utilizadas para esse fim, desde um encadeamento de IFs até a implementação de algorítimos matemáticos/estatísticos. Esse tipo de aprendizado, apesar de análogo, não tem a ver com consciência e sim a encontrar e reproduzir padrões, a maquina não entende o que esta fazendo e para ela é transparente se você esta inserindo dados de transações financeiras, dados criminalísticos ou dados do campeonato do cartola.

No caso da árvore de decisão a primeira vista pode parecer que é um encadeado de condições “hardcode”, mas ele é na verdade um pequeno grupo de 3 ou 4 funções matemáticas, a “beleza” disso é que o aprendizado de maquina pode ser generalizado para varias situações. As árvores de decisão são tão genéricas que podem ser usadas tanto para auxiliar a estimar o valor de crescimento das ações de uma empresa ou bem, analisar dados de raio-x médicos para analise doenças e ajudar um sistema de jogo a identificar, em tempo real, as partes do corpo de uma pessoa que esta na frente da câmera!

Os algorítimos de machine learn possuem duas abordagens para fazer predições a “regressão” e a “classificação”, alguns dos algorítimos são especializados em uma dessas abordagens e outros são mais genéricos. A depender da implementação as árvores de decisão podem ser genéricas, como é o caso do algorítimo CART, ou podem ser especializadas.

O mais comum em aprendizado de maquina é dividir o processo em duas partes o “fit” que é onde ele efetivamente “aprende” e o “predict” que é quando ele usa esses padrões identificados pra gerar um resultado. Fit é o processo no qual você insere no algorítimo dados de exemplo (“treino”) para que ele possa ir se ajustando e encontrando padrões. “Predict” é o processo realizado em cima de um conjunto de dados que a maquina “ainda não viu” e retorna uma predição baseada nos padrões que foram identificados no processo anterior.

Tipos de abordagem — Regressão e Classificação

Existem basicamente duas formas que utilizamos para abordar um problema de machine learn são eles regressão ou classificação.

Para explicar de uma forma mais “didática” ou simplista podemos dizer que :

Regressão é quando queremos resolver, na maioria dos casos, um problema quantitativo(quando o alvo é um numero/valor) ou um problema relacionado a uma ação que ocorre ao longo do tempo, por exemplo, prever os preços de imoveis para o segundo semestre de 2021 com base num histórico de preços do ano anterior.

Na biblioteca SciKitLearn no Python você pode encontrar uma implementação já pronta de uma árvore de decisão otimizada para regressão com o nome de DecisionTreeRegressor, para mais informações :

https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeRegressor.html

Classificação é um problema mais qualitativo ou de agrupamento, ou seja você vai qualificar uma coisa como sendo A ou B, sim ou não, vivo ou morto, ou até dizer a qual grupo de informações um dado pertence. Por exemplo o Microsoft Kinect que utiliza árvores de decisão de classificação para poder reconhecer as partes do corpo.

Você também pode encontrar no SciKitLearn uma implementação de árvore de decisão otimizada para classificação com o nome de DecisionTreeClassifier, para mais informações :

https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html?highlight=decisiontree#sklearn.tree.DecisionTreeClassifier

Como eu disse, isso é uma versão mais simplista das definições pra dar um entendimento melhor para o próximo tópico.

Tomemos como o exemplo anterior, sobre os preços para aluguel de imoveis na Cidade de São Paulo.

Podemos dizer que o caso do exemplo trata-se de uma regressão, pois, de forma bem grosseira, temos como alvo um valor e não uma categoria .

Vamos então montar o que chamados de “gráfico de dispersão”, não se assuste apesar do nome ele é algo bem simples.

Para montar um gráfico de dispersão simples para o intuito do nosso exemplo vamos usar como base o “valor do aluguel” como nosso eixo X e a “Metragem em M²” como eixo Y.

Em seguida pegamos uma das linhas do nosso conjunto de dados e traçamos um ponto no gráfico.

Na primeira imagem traçamos um ponto referente ao apartamento de tamanho 48 m² e com valor do aluguel igual a 450 reais.

Agora, para efeitos de demonstração, vamos plotar mais alguns pontos, como podem ver na segunda imagem.

Tranquilo até aqui ? Beleza, agora, vamos fazer as perguntas que fizemos para montar a árvore no exemplo.

Primeira : A área do imóvel é maior que 60 M² ?

Com isso separamos nossos dados em duas metades ou podemos dizer que temos duas folhas. Apesar desse nó dividir os dados pela metragem, o que visualmente parece ser uma boa divisão, não é suficiente para chegarmos a uma conclusão. Nesse caso então vamos fazer mais uma pergunta como no exemplo do aluguel : “O imóvel fica localizado no centro da cidade ?”

Vamos continuar usando esse gráfico de duas dimensões pra nossa explicação, apesar de a coluna que diz se o imóvel esta no centro da cidade não estar presente podemos representar essa divisão traçando uma outra reta no gráfico. Só pra lembrar esses são apenas exemplos pra intuição de como funciona, minha preocupação é que você entenda o conceito mas não necessariamente é a melhor forma de fazer essa representação. Uma melhor forma de representar seria usando um gráfico com 3 dimensões com gradientes, mas acredito que a complexidade de explicá-lo não é o ideal para esse artigo, eu vou falar mais sobre isso num futuro artigo sobre gradiente descendente.

Traçamos então uma nova linha pra dividir os nossos dados:

Repare que agora temos 4 folhas assim como no exemplo do aluguel!
Podemos então concluir que, visualmente, o que a árvore aprendeu foi :

Como jargão , ou buzzword hahaha, chamamos de features as colunas com informações.

Quanto mais dados tivermos e quanto mais features com correlação alta (que fazem sentido juntas) mais precisa fica a nossa divisão das folhas. Claro que, mais uma vez esse foi só um exemplo pra ilustrar de uma outra forma como é feita a divisão dos dados pela árvore de decisão

Kinect e classificações

Uma outra abordagem que podemos utilizar a árvore é pra classificação.

Pra exemplificar vamos continuar usando o exemplo do aluguel de imóveis.

Imagine que o nosso desafio agora é o contrario, com base no preço do aluguel nós tenhamos que dizer se esse imóvel fica no centro da cidade ou não.
Ou seja, vamos dar uma classificação para esse imóvel ao invés de um valor numérico.
O termo utilizado em machine learn é “label” (o que seria “legenda” ou “rótulo” em tradução livre, mas usamos em inglês mesmo hahah).

Vamos lá então, temos as features
“Metros Quadrados” e “ Valor do Aluguel”

Nossa label é : “Fica no centro da cidade ?”
Os valores possíveis para nossa label chamamos de categorias (ou classes) dessa forma podemos chamar também de variável categórica.
As categorias que temos para nossa label são “Sim” e “Não”.

Agora imagine que da mesma forma que fizemos acima a gente comece a traçar pontos no nosso gráfico conforme nosso conjunto de dados, porém dessa vez nós traçamos algumas dezenas deles.
Ficaria mais ou menos dessa forma:

A árvore de decisão vai então usar o principio anterior para separar os nós e começar a dividir varias vezes de forma recursiva até chegar num ponto ótimo, então teríamos um processo como o seguinte:

Sequência onde o algorítimo traça várias divisões no gráfico (com base nas features) até chegar num “ponto ótimo”.

Dessa forma temos definida quais são as “áreas” que correspondem a cada grupo e assim se caso a gente plote um novo ponto no nosso gráfico conseguimos classificar a que grupo ele pertence.

Grupo azul : “Não fica no centro da cidade”. Grupo amarelo : “Fica no centro da cidade”.

Por exemplo, se traçarmos um novo ponto, como no gráfico abaixo, a nossa resposta sera de que esse imovel fica no centro. Nossa label ira retornar “Sim”.

Ponto vermelho = ponto plotado com base em dado de teste.

Se mudarmos o ponto de posição no gráfico, como na figura abaixo, nosso label agora seria “Não”, essa é a mesma ideia por trás do Kinect da Microsoft.

Ponto referente ao dado de teste plotado em outro ponto do gráfico.

Semelhante ao nosso exemplo, o Kinect pega uma imagem do sensor e baseado nas características(features) que ele obteve e vai “fatiando” a imagem, assim cada área “fatiada” representa uma folha da árvore, que por sua vez representa uma parte do corpo.

Existem processos que transformam imagens em vetores e que podem ser utilizados como features de entrada para nossa árvore de decisão. Se você se interessou, no final do post eu deixei um link para o documento da Microsoft onde explica, entre outras coisa, o uso que tiveram de árvores de decisão para reconhecimento do corpo humano em tempo real.

https://www.microsoft.com/en-us/research/blog/kinect-body-tracking-reaps-renown/

https://www.microsoft.com/en-us/research/project/human-pose-estimation-for-kinect/ https://www.microsoft.com/en-us/research/blog/kinect-body-tracking-reaps-renown/

Abordagens para o aprendizado — Algorítimos de árvore de decisão

Existem varias formas de implementar uma árvore de decisão, nesse artigo eu estou me baseando no algorítimo CART que vou esclarecer no próximo tópico, uma versão otimizada desse algorítimo é usado na implementação da famosa biblioteca SciKitLearn. Porém há outros algorítimos que devem ser mencionados e vou deixar o link aqui caso tenha curiosidade:

MARS — Multivariate adaptive regression splines — https://en.wikipedia.org/wiki/Multivariate_adaptive_regression_spline

ID3 — Iterative Dichotomiser 3 — https://en.wikipedia.org/wiki/ID3_algorithm

CHAID — Chi-square Automatic Interaction Detector — https://en.wikipedia.org/wiki/Chi-square_automatic_interaction_detection

C4.5 — extensão do algoritimo ID3 https://en.wikipedia.org/wiki/C4.5_algorithm

CART — Classification And Regression Trees

CART é um dos algorítimos usados na abordagem de árvore de decisão para aprendizado de maquina que utiliza os conceitos de entropia, ganho de informação e Gini impurity para decidir os nós das árvores. O CART é o acrônimo de Classification And Regression Trees ou em tradução livre Árvores de Classificação e Regressão.

https://scikit-learn.org/stable/modules/tree.html#tree-algorithms-id3-c4-5-c5-0-and-cart

Como seria um passo a passo pra criar uma árvore de decisão ?

Vamos lá, se me pedissem uma receita de bolo de como implementar passo-a passo uma implementação CART que possa ser replicada em qualquer linguagem eu responderia : (Alerta de cálculos matemáticos!!!)

Ingredientes:

Definir os nós possíveis
Escolher o nó com a menor incerteza ( usando Gini Impurity)
Escolher os nós filhos (com base no information gain)
Repetir até acabarem as perguntas ou se chegou ao numero máximo de profundidade parametrizado para a árvore

Modo de preparo :

Passo 1

1 - Definir os candidatos a nós.

A primeira coisa a fazer é definir quais as perguntas(nós) a fazer, cada valor único de uma coluna pode ser usado como pergunta em potencial.

No nosso caso do robozinho, por exemplo a coluna tipo, nossas classes possíveis de pergunta serão todos os valores, sem repeti-los, que são “Fruta” e “Animal”.

Para a coluna tipo então teríamos as perguntas : É um Animal ? É uma Fruta ?

Vamos chamar cada uma dessas perguntas de nó (da árvore).

Passo 2

2 - Responder as perguntas e guardar os resultados

Para cada pergunta você deve guardar separado as respostas positivas e as negativas (sins e nãos). A resposta consiste nas linhas do conjunto de dados. Usando nosso exemplo anterior para ilustrar, se usarmos a cor “Preto” como pergunta o resultado seria:

A cor é igual a “Preto” ?

Linhas com resultados positivos — Linhas com resultados negativos
      3                         —       1
                                —       2

Essas listas podem ser chamadas de “nós filhos” ou a depender do caso “folhas”. Pois eu posso usa-los para fazer novas divisões, como no primeiro exemplo do artigo. No exemplo dos apartamentos para aluguel o nó pai perguntava se areá era maior que 60 metro quadrados e o nó filho perguntava se a localidade era próxima ao centro, porem o que esse exemplo não mostrou é que não necessariamente os nós filhos precisam fazer a mesma pergunta ou até mesmo o que acontece quando um nó filho ainda tem capacidade de ter nós filhos abaixo dele e o outro não como no caso acima.

No exemplo acima, no nó filho dos resultado negativos ainda temos mais 2 itens e temos como fazer outras perguntas para gerar mais nós, como por exemplo “é um animal?”.

Já o nó filho, como só tem um item, não há mais como fazer nenhuma divisão, isso quer dizer que chegamos num nó folha (leaf). Como já mencionado os nos folhas podem ser caracterizados como aqueles que são indivisíveis ou também aqueles que quando divididos “pioram” o valor de impureza da árvore como um todo, nesse caso deixamos de dividir os nós e o elegemos como nó folha.

Há também parâmetros que podemos colocar para decidir ate quantas árvores candidatas vamos gerar e qual a “profundidade” máxima que cada uma pode ter ( ou o numero máximo de nó filhos).

Passo 3

3 - Reduzir a incerteza

Vamos usar a estratégia de calcular a impureza dos nós. A impureza dos nós é um numero de zero a um, sendo assim, os melhores nós para serem candidatos a formarem nossa árvore de decisão são aqueles com o numero de impureza menor. Para isso se usa o calculo de Gini impurity Lembra do exemplo da cerveja ?

Mas, como diria o Chavinho, “eu só sei fazer essa conta com maçãs”, vamos la então:

Imagine que eu tenho uma cesta com 4 maçãs e uma banana, para calcular a Gini impurity eu poderia fazer a seguinte abordagem :

Itens únicos(Classes) — Quantidade por item
      Maçã            —       4
      Banana          —       1

3.a Calcular a probabilidade de cada item

Probabilidade Maçãs    =  4 / 5 que é igual a 0.2
              Bananas  =  1 / 5 que é igual a 0.8

3.b Calcular a impureza de cada item único

Impureza do item é igual a  "probabilidade do item elevado a 2"Impureza Maçãs   = 0.2 elevado a 2 que é igual a 0.04000000000000001
         Bananas = 0.8 elevado a 2 que é igual a 0.6400000000000001

3.c O valor de impureza do nó deve estar entre 0 e 1.

Para calcular pegamos o valor máximo, que é 1 e desconto(subtraio) o valor de impureza das classes que eu obtive no passo anterior:

Calculamos então :
3.c.1Valor máximo de impureza menos a  impureza das bananas     1                     -      0.6400000000000001 
             Resultado = 0.3599999999999999 3.c.2Resultado da conta anterior menos  a impureza das maças     0.3599999999999999    -     0.04000000000000001 
             Resultado = 0.31999999999999984

3.c.n

Se tivéssemos mais n classes, por exemplo limões, repetiríamos o processo até o ultimo itemResultado da conta anterior  menos impureza da classe n: Gini impurity = 0.31999999999999984

Agora com o Gini impurity podemos eleger qual vai ser o nó “principal” da nossa árvore.

3.d Calcula o “information gain”

Ao tentar reduzir a incerteza é desejável que tenhamos um nó com muitos itens e uma impureza mais baixa do que um nó com poucos itens, mas uma impureza bem alta. Para esse fim utilizamos o information Gain (ganho de informação) onde vamos ponderar os valores, ou seja, dar um peso maior ou menor dependendo de como os dados estão distribuídos. Isso ajuda a encontrar a pergunta (ou nó) que mais reduz a incerteza mostrando o quanto ajuda a colaborar para separar os nós.

Depois de definirmos cada pergunta que podemos fazer separamos os nós filhos e para cada nó filho calculamos novamente a impureza.

Digamos que fizemos todo o calculo de impureza como no passo anterior, chamamos os nós filhos de “A” e “B” , e o calculo tenha retornado o resultado abaixo :

Impureza nó filho A = 0.62
Impureza nó filho B = 0

Porém quando se trata dos nós filhos existe mais uma camada de calculo que deve ser feita calculando um “peso” para cada nó filho

Dessa vez a impureza “final” será calculada com base em uma média ponderada entre a quantidade de itens do nó filho divido pela quantidade total de itens do nó pai.

3.d.1 Calcular Média da impureza

Media da impureza = (qtd itens A / total * impureza de A) + (qtd itens B / total * impureza de B)

Exemplo:
      nó pai(total)      = 5 itens  = 5
      nó filho a           = 4 itens  = 4/5
      nó filho B           = 1 itens  = 1/5   media da impureza =  4/5 *  0.62  + 1/5 * 0 
                   resultado =  0.496

3.d.2 Com isso podemos calcular o information Gain

Information Gain = impureza do nó pai -(menos) média da impureza dos nós filhos  Exemplo     information Gain  = 0.64 - 0.496 =   0.144    Com o information gain podemos eleger as perguntas que vão servir para serem nós filhos, caso em uma das divisões de nós filhos o information gain piore você pode simplesmente ignorar e não dividir mais o nó filho elegendo-o como leaf.

Passo 4

4 - Iterar!

Repetir o processo para cada cadeia de nós até não restar mais pergunta alguma a ser feita ou atinja o valor máximo de profundidade da árvore.

No jargão de machine learn essa etapa do processo de aprendizagem chamamos de FIT, ou treino ( já vi chamarem de aprendizagem), que é onde o algoritmo aprende os padrões dos seus dados que podem levar a uma previsão. Uma vez que esse padrão seja definido, ou “aprendido”, pelo algorítimo basta agora aplicar esse padrão nos dados novos que você deseja prever.

Concluindo

Eu criei esse “passo-a-passo” baseado no notebook criado por Josh Gordon onde ele implementa uma árvore de decisão do zero em python e também nas vídeo aulas do Krish Naik onde ele explica a matemática da coisa. No notebook você vai encontrar uma implementação parecida com esses 4 passos que eu expliquei aqui.

GIT notebook Josh gordon — https://github.com/random-forests/tutorials/blob/master/decision_tree.ipynb

Gini Impurity — https://www.youtube.com/watch?v=5aIFgrrTqOw

Information Gain — https://www.youtube.com/watch?v=FuTRucXB9rA

Entropy — https://www.youtube.com/watch?v=1IQOtJ4NI_0

Desafios das árvores de decisão : overfitting e underfitting

Quando estamos montando qualquer modelo de machine learn existe uma preocupação com o processo de aprendizagem para que nossa resposta não seja um “falso positivo”,geralmente classificamos esses problemas como overfitting e underfitting.

De uma forma geral e simplista podemos definir que:

Overfitting : È quando seu modelo encontra muitos padrões nos dados de treino que não existem (ou são minoria) nos dados em que vamos aplicar o modelo(dados de teste).
Underfitting : É quando seu modelo não encontra um numero suficiente de padrões ou encontra padrões que não são muito relevantes para fazer a predição.

Esses dois problemas levam a uma taxa de erro bem grande na hora de prever os resultados. A árvore de decisão não é uma exceção e também está passível a isso.

Para evitar esses problemas devemos tomar cuidado com a “profundidade” que parametrizarmos na nossa árvore : se ela tiver nós demais, podemos sofrer de overfitting, se os nós forem poucos não teremos encontrado padrões suficientes e cairemos no underfitting.

Ou seja, a uma boa forma de resolver isso seria equilibrando a quantidade de nós mínimo e máximo que podemos utilizar numa árvore.

Apesar de ser importante ter esse desafio em mente não vou me prolongar muito mais no assunto.

Mas, se você quiser conhecer uma maneira pratica de como equilibrar esses parâmetros eu indico esse post do kaggle que faz parte do tutorial de machine learn. Nessa pagina é utilizada a métrica MAE (mean absolute error) de forma recursiva (repetindo varias vezes) até chegar num “ponto ótimo” ou seja, um numero de nós que não seja nem tão baixo nem muito alto a ponto de afetar nossa taxa de sucesso de predição.

https://www.kaggle.com/dansbecker/underfitting-and-overfitting

E se ao invés de uma árvore tivermos uma floresta ?

Como eu já devo ter mencionado, apesar de um resultado muito satisfatório o algorítimo de árvore de decisão já foi “batido” por novos algorítimos na maioria das aplicações.

Porém existe uma implementação que utiliza uma nova abordagem usando as árvores de decisão : a random forest.

Ao invés de utilizar apenas uma árvore de decisão ele vai, de forma aleatória, montando varias árvores e no final junta o resultado de todas as árvores dessa “floresta” para gerar a nossa predição. Se for um caso de classificação o resultado final vai ser a “moda” das respostas de todas as árvores (ou seja, vai ser o resultado que aparece mais vezes, se o SIM saiu mais vezes que o Não, então a resposta final é SIM).

Para os casos de regressão a resposta final vai ser a média do resultado de todas as árvores de decisão.

Conclusão

Como vimos, árvores de decisão “aprendem” procurando padrões no conjunto de dados de como cada grupo de informações se relaciona, chamamos isso de entropia. Existem varias abordagens para implementar uma árvore de decisão, abordamos aqui, de forma simplista, o algorítimo CART. Uma forma melhor de aproveitar o poder das árvores de decisão é utilizando o conceito de random forest, porém ainda assim devemos nos atentar para não cair nos problemas de underfitting e overfitting.

Agradeço pela leitura até aqui, espero que não tenha sido muito pesada. Tentei utilizar um story telling de maneira mais simples (e com exemplos triviais) para ser o mais didático possível para que sirva tanto para leigos como quem já tem experiência

Ah, se você curtiu meu artigo e quiser de uma passadinha no meu blog sinta-se a vontade (ainda não tem muita coisa, mas prometo que vou postar com frequência) :