Como funciona um algoritmo de Árvore de Decisão

Vamos entender o conceito e o método por trás de um dos principais algoritmos de aprendizagem de máquina, dentro do grupo dos modelos chamados "supervisionados" (em que se conhece a variável dependente).

A ideia central das árvores de decisão é encontrar a sequência de condições de repartição das variáveis preditoras que melhor qualifique a variável dependente de um modelo.

Vamos entender a partir de um exemplo bem simples e conhecido. Suponha que você seja o administrador de uma quadra de tênis e tenha um registro histórico de condições climáticas do dia e se houve uso ou não da quadra:

Digamos que você pretenda criar um modelo preditivo que, diante das condições climáticas do dia, indique se vai haver ou não uso da quadra. Seu modelo será "treinado" por esse histórico, então será um modelo supervisionado. Uma árvore de decisão modelada a partir dos dados parecerá com o seguinte:

Perceba que, na base histórica, todas as vezes em que o dia parecia nublado (overcast) houve uso da quadra. Isso se reflete no primeiro nó de decisão. Esses nós, ou etapas de decisão, foram identificados no processo de modelagem como parte da sequência que garante maior acerto nas previsões.

Mas como exatamente funciona o processo de modelagem? Veremos a seguir.

Processo de modelagem: Árvore de Decisão para classificação

No exemplo anterior estamos diante de um problema de classificação, pois nossa variável dependente (uso da quadra) é uma classe (uma categoria) e não uma variável contínua.

Pois bem, vamos entender o processo de modelagem visualmente. No exemplo abaixo temos um plano cartesiano, onde pretendemos encontrar a melhor forma de separar os pontos azuis dos vermelhos. A escolha do plano cartesiano é proposital, pois consiste em 2 dimensões (o que facilita essa explicação visual). Então vamos entender nossas variáveis preditoras como a coordenada x,y da posição de cada ponto. E a variável dependente, a qual queremos prever, é a cor dos pontos:

Pois bem, o objetivo da modelagem é encontrar a melhor sequência de decisões sobre as 2 coordenadas que minimize a mistura de classes nas regiões resultantes desses cortes.

Uma árvore de decisão é composta por nós e por folhas. Os nós são as condições e as folhas são a decisão de classificação em si. Esta é nossa árvore, a partir da qual irei explicar o método:

Veja que o primeiro nó da árvore tem a condição y≤5,4. Isso separa horizotalmente o diagrama, na posição y=5,4. Veja:

Perceba que, dessa divisão, resulta que todos os casos fora da condição são pontos vermelhos. Por isso temos como resultado uma decisão logo abaixo (quando a condição é falsa).

Se verdadeira, ainda temos pontos misturados, então vem uma nova condição (nó), desta vez x<=5,4:

Mais uma vez, a região fora da condição apresenta todos os pontos vermelhos. Temos mais uma decisão. Na região em que a condição é verdadeira, temos pontos mistos.

Necessária mais uma etapa de decisão, com x≤-3,75:

Nesse caso, na nossa esfera atual de decisão restam 15 pontos (8 já foram marcados). 3 deles cumprem a condição, 1 azul e 2 vermelhos. Não cumprindo a condição, temos 10 azuis e 2 vermelhos.

Nossa árvore de exemplo termina aqui, com 3 camadas de decisão (veja mais abaixo o porquê). A partir daqui, um novo ponto que apareça pode ter sua cor prevista com base nas coordenadas e nas respostas às condições da árvore.

Mas vamos entender melhor o processo de modelagem, agora analisando cada componente da árvore:

Nó inicial

Esse acima é o nosso nó inicial. Ele informa algumas coisas, iremos entender de baixo pra cima:

• value = [11, 12]: isso indica que temos inicialmente nos dados 11 bolas azuis e 12 vermelhas
• samples = 23: isso é o total de elementos (pontos) não classificados
• gini = 0.499: Gini é um indicador de desigualdade, quanto mais perto de 1 menos homogêneo o recorte
• y≤5.4: Decisão proposta no nó. Mas por que esse valor em específico? Porque ele é o valor que mais diretamente reduz o valor gini do próximo nível da árvore, garante mais homogeneidade.

Segunda camada

Então temos acima o desmembramento da árvore a partir da primeira decisão. Veja que as setas para a esquerda sempre significarão o cumprimento da condição e as da direita, o descumprimento.

• O retângulo verde apresenta gini = 0. Isso ocorre porque todos os pontos desse recorte são vermelhos.
• Esse retângulo encerra a decisão para esse grupo. A árvore aprendeu que, descumprida essa primeira condição, todos os pontos devem ser classificados como vermelhos.
• O retângulo da esquerda apresenta o gini atualizado do que restou, e propõe uma nova divisão que minimiza o gini daí pra baixo.

A árvore segue até o último nível:

Últimas folhas

Aqui, não temos mais decisões subsequentes. A árvore decide classificar o recorte pela classe mais presente (vermelho na folha da esquerda e azul na da direita).

Como que o processo de modelagem entende se é hora de parar e classificar determinado recorte ou seguir com novas decisões?

Isso está relacionado à profundidade da árvore (ver mais abaixo) e com as condições de "paragem" da mesma. Essas condições podem ser, por exemplo, o indicador gini ("ficando menor de determinado valor, está bom, pode parar") ou do número mínimo de elementos no recorte.

Por que a árvore finalizou em 3 camadas de decisão, já que haveria possibilidade de se incluir mais camadas e se ter mais homogeneidade (veja que encerramos nas últimas folhas com alguma mistura)?

Perceba que o seu objetivo aqui é criar um modelo preditivo. Ao surgir um novo ponto no futuro, de cor desconhecida, você pretende, com base apenas nas suas coordenadas, classificá-lo como azul ou vermelho.

A profundidade da árvore pode ser bem maior nesse caso, certamente. Mas a questão é: O quanto que esse modelo seria generalizável / adaptável a novos dados? Uma árvore muito profunda seria perfeitamente aderente aos dados já conhecidos, mas poderia estar superajustada a características de ruído dos dados de treino.

O que se quer é que o modelo pegue as características mais perenes, não casuais (o sinal, não o ruído). Se você quisesse estabelecer características dos ataques das seleções campeãs do mundo e "treinasse" seu modelo com a seleção de 94, não deveria se prender a coisas casuais como a altura média dos atacantes (1,65m). Aí como ficaria a de 2002? Você quer entender o sinal, a característica subjacente, como a capacidade de posicionamento e visão de jogo deles, por exemplo. Isso é o que vai garantir que seu modelo sirva pra prever o futuro.

Por isso, num processo de modelagem preditiva, é necessário separar os dados em treino e teste. O modelo evolui no treino, mas seu desempenho final só é medido nos dados de teste, de forma a simular a capacidade de generalização do mesmo. Na etapa de evolução com dados de treino, deve-se chegar aos parâmetros ideais (como a profundidade máxima da árvore) que maximize a capacidade preditiva com dados novos.

Até a próxima.