Árvores de Decisão
O objetivo desse post é explicar o que são árvores de decisão, para que servem, como construir uma a partir dos dados, entre outras coisas.
Pré-requisitos
Eu não vou entrar em muitos detalhes em alguns assuntos, portanto vou assumir que saibam um pouco sobre:
- Estrutura de Dados: Árvore Binária (conhecimento básico)
- Aprendizado de Máquina Supervisionado (conhecimento básico)
- Recursão (conhecimento intermediário)
- Programação em Python com numpy (apenas para implementação)
O que são?
Árvores de decisão são métodos de aprendizado de máquinas supervisionado não-paramétricos, muito utilizados em tarefas de classificação e regressão.
WTF?!?! Muita calma nessa hora. Antes de explicarmos melhor o significado dessa definição, vamos entender o que é uma árvore de decisão a partir de uma perspectiva mais geral.
Provavelmente, você já deve ter visto ou utilizado uma árvore de decisão em sua vida. Por exemplo, você já deve ter utilizado ou visto um fluxograma, não é mesmo? Espero que sim (senão dê uma olhada na figura abaixo). Isso mesmo! Um fluxograma pode ser considerado uma árvore de decisão (caso não contenha loop).
Árvores, de um modo geral em computação, são estruturas de dados formadas por um conjunto de elementos que armazenam informações chamadas nós. Na figura acima, os nós são representados pelos quadradinhos com as perguntas e as informações podem ser consideradas as perguntas e suas possíveis respostas. Além disso, toda árvore possui um nó chamado raiz, que possui o maior nível hierárquico (o ponto de partida) e ligações para outros elementos, denominados filhos. Esses filhos podem possuir seus próprios filhos que por sua vez também possuem os seus. O nó que não possui filho é conhecido como nó folha ou terminal (representado pelo símbolo arredondado na figura). Tendo essas definições esclarecidas, uma árvore de decisão nada mais é que uma árvore que armazena regras em seus nós, e os nós folhas representam a decisão a ser tomada (no caso do exemplo, qual jogo escolher).
Em uma árvore de decisão, uma decisão é tomada através do caminhamento a partir do nó raiz até o nó folha. Para elucidar melhor, suponha que tenhamos essa situação: você vai fazer uma reunião com seus amigos em sua casa, e vai rolar comidas e bebidas. Você quer jogar um jogo de tabuleiro, mas não sabe qual o melhor para essa situação, portanto, você vai recorrer a árvore de decisão para tomar sua decisão de forma mais correta. Para isso vamos caminhar por ela a partir do nó raiz, que contém a pergunta: Está jogando com crianças? Não, então iremos para nó filho da esquerda. Vamos jogar por mais de duas horas? Acho que sim! Assim, o próximo é: Regras difíceis? Vou tomar uma, logo não vou querer pensar muito rsrs. Reposta é não. Todos os jogadores vão ficar até o final? Vamos supor que sim! Desse modo, chegamos ao nó folha, com jogo Le Havre.
Simples assim! Mas o que isso tem a ver com aprendizado de máquina? De fato, uma árvore de decisão por si só não é aprendizado de máquina já que eu posso criar uma sem auxílio de um computador e utilizá-la para organizar melhor minhas ideias e tomada de decisão (como alguém fez com o problema de escolher jogos de tabuleiro). Todavia, seu processo de construção automático, a partir de um conjunto de dados, é. No geral, os algoritmos para isso o fazem de forma não-paramétrica (termo estatístico que significa, em termos gerais: não assumir nada sobre os dados de antemão) e supervisionada (os dados devem conter as respostas/rótulos, mais detalhes aqui).
Tendo tudo isso em vista, na próxima seção veremos como aprender a estrutura da árvore de decisão de forma automática a partir dos dados.
Então diga-me, como construo uma?
A ideia geral de métodos baseados em árvores é particionar o espaço recursivamente em retângulos (sub-regiões), nos quais um modelo simples é aprendido.
Para elucidar melhor como a árvore de decisão particiona o espaço em sub-regiões, vamos introduzir o conjunto de dados de flores de íris.
Esse conjunto de dados contém exemplos de três espécies de flor de Íris. Cada um dos quais possui 4 atributos, que são a largura e comprimento da pétala e da sépala da flor.
Nós iremos utilizar apenas 2 atributos em nosso exemplo (comprimento e largura da pétala), já que é mais fácil para visualização no plano 2d. Além disso, conseguimos dividir o espaço satisfatoriamente apenas com esses dois atributos, ou seja, são dois atributos bem discriminativos para esse problema.
O espaço é representado pelo gráfico ao lado, onde cada uma das três cores representa uma espécie da flor de íris, são elas: setosa (amarela), versicolor (verde) e viriginica (roxa). Tendo isso em vista, nos queremos construir uma árvore de decisão para determinar a qual espécie uma nova flor de íris pertence dada suas características (nesse caso, comprimento e largura da pétala). Para isso, vamos particionar o espaço recursivamente, fazendo cortes ortogonais, levando em consideração uma variável por vez, que maximiza a pureza das sub-regiões resultantes (pureza = homogeneidade no que diz respeito às espécies/rótulos). Cada divisão do espaço é representada por um nó na árvore de decisão. A primeira divisão (nós raiz da árvore) leva em consideração todos os exemplos (pontos) do espaço ao encontrar o ponto de corte que maximiza a pureza, de acordo com algum critério de impureza (veremos adiante), das sub-regiões resultantes. Vamos supor que o comprimento da pétala de valor 2,45 cm é o ponto de corte que melhor divide o espaço. Portanto, essa será o nó raiz de nossa árvore de decisão.
A figura acima mostra como fica essa divisão (esquerda) e nosso nó raiz (direita). De fato, esse corte nos deu uma região totalmente pura (conseguimos separa as setosas do restante) e uma outra heterogênea. Agora, vamos recursivamente particionar as duas sub-regiões do espaço (da esquerda e da direita). Na esquerda, temos uma região completamente pura e isso significa que qualquer corte que fizermos nessa região teremos como resultados regiões puras. Portanto, podemos parar o particionamento, ou seja, essa região será considerada um nó folha em nossa árvore. Já a região da direita não é pura, assim devemos continuar o particionamento por ela até que cheguemos em sub-regiões puras. Figura a seguir mostra a próxima partição.
A partição na sub-região da direita, foi feita no eixo da largura da pétala no valor 1,75 cm. Como pode-se notar, foram gerados mais duas novas sub-regiões disjuntas, que, por sua vez, não estão completamente puras. Esse processo é repetido recursivamente até que um critério de parada seja alcançado (i.e., profundidade, número de folhas) ou que todas as folhas sejam puras, que implica na costrução até sua profundidade máxima . A figura a seguir mostra como ficaria nossa árvore e as partições (quase) puras do espaço.
Essa é a intuição do algoritmo de construção de uma árvore de decisão. Há vários algoritmos para aprender sua estrutura, são eles CART, ID3 e C4.5, todos seguem mais ou menos essa lógica. Nesse artigo, vamos focar no algoritmo CART, pois é um dos mais intuitivos e simples de implementar, além de sua implementação estar disponível em várias bibliotecas de aprendizado de máquinas, tal como scikit-learn. O código a seguir sintetiza o algoritmo.
Nas seções subsequentes iremos destrinchar cada parte do algoritmo acima.
Encontrando "melhor" ponto de corte
Nós estamos interessados em encontrar a melhor divisão em termos de alguma medida de impureza, tal como Gini Index, Entropia ou taxa de erro (detalharemos mais adiante). Encontrar o ponto de corte que leva a árvore de decisão ótima pode ser computacionalmente inviável (construir a árvore de decisão binária ótima é um problema np-completo). Portanto, nós nos contentamos em fazer escolhas locais ótimas (não garantindo o ótimo global) para encontrar o melhor atributo e limiar para o particionamento (linha 7 do código acima).
Para encontrar melhor ponto de corte, nós temos de testar todos os possíveis, ou seja, para cada atributo e valores possíveis calcular o ganho de informação (quão pura a divisão torna o espaço) para cada um dos pontos de corte candidatos. Após essa etapa, nós escolhemos o candidato com maior ganho de informação para ser o ponto de corte do nó em questão. O código para isso ficaria o seguinte.
Calculando o ganho de informação
O ganho de informação, de grosso modo, representa a informação aprendida sobre os rótulos (no nosso exemplo, as espécies) quando dividimos uma região do espaço em duas sub-regiões de acordo com ponto de corte. E é definida pela fórmula:
InfoGain(R, R_e, R_d) = H(R) - (|R_e|*H(R_e) + |R_d|*H(R_d)) / |R|,
onde H é a impureza da região, R é a região atual, R_e é sub-região da esquerda, R_d é sub-região da direita e |.| é quantidade de exemplos na dada região. Os critérios de impureza mais comuns para classificação são a Entropia e o índice Gini, definidos a seguir:
entropia(R) = -∑ p(c|R) log (p(c|R)) ,
gini(R) = ∑ p(c|R) (1 - p(c|R)),
onde p(c|R) é a probabilidade de um ponto da região R pertencer a classe c. Essa probabilidade é estimada pela razão entre quantidade de pontos da classe c e o total de pontos em R.
Para ficar mais claro, vamos calcular o ganho de informação para o ponto de corte mostrado na figura utilizando tanto a entropia quanto o gini. Vamos iniciar calculando p(c|R) para cada região e espécie.
Sabendo que temos 50 exemplos de cada espécie, a p(c|R) para todas as espécies é 50 / 150 ~ 0.33 . Calculando para a sub-região da esquerda, temos que p(c = setosa | R_e) = 1.0 (só temos setosa nessa região) e p(c = versicolor | R_e) = p(c = virginica | R_e) = 0.0. Para direita, p(c = setosa | R_d) = 0.0 e p(c = versicolor | R_d) = p(c = virginica | R_d) = 0.5.
Com esses valores em mãos, fica fácil calcular a entropia e gini de cada região e, por consequência, obter o ganho de informação.
entropia(R) = -∑ p(c|R) log (p(c|R)) =- 3 * (0.33 log(0.33)) ~0.48
entropia(R_e) =-(1.0 log(1.0) + 0.0 log(0.0) + 0.0 log(0.0)*) = 0
entropia(R_d) =-(0.0 log(0.0) + 0.5 log(0.5) + 0.5 log(0.5)*) ~0.30
Portanto, o ganho de informação usando entropia como critério de impureza é:
InfoGain = 0.48 - (50*0 + 100*0.30) / 150 = 0.28
Calculando o gini de maneira análoga,
gini(R) = ∑ p(c|R) (1 - p(c|R)) = 3 * (0.33 *(1 - 0.33)) ~0.66
gini(R_e) =(1.0 * (1.0 - 1.0) + 0.0 * (1 - 0.0) + 0.0 * (1 - 0.0)) = 0
gini(R_d) =(0.0 * (1 - 0.0) + 0.5 * (1 - 0.5) + 0.5 * (1 - 0.5)) ~0.5
Portanto, o ganho de informação usando gini como critério de impureza é:
InfoGain = 0.66 - (50*0 + 100*0.50) / 150 = 0.16
As implementações desses critérios de impureza seriam:
O algoritmo está praticamente finalizado, só precisamos definir nosso critério de parada e pronto (essa é parte mais fácil).
Traduzindo o código, nosso critério é verdadeiro se atingir uma profundidade máxima preestabelecida ou se a região é pura (caso max_depth seja None a árvore crescerá até sua profundidade máxima). O código completo pode ser encontrado no link a seguir:
Por que árvores de decisão são tão populares?
Como pode-se ver, árvores de decisões são conceitualmente simples, porém poderosas. Sua popularidade é, principalmente, devido a suas características singulares:
- Fácil explicabilidade e interpretação, já que podemos facilmente visualizá-las (quando não são muito profundas).
- Requerem pouco esforço na preparação dos dados, métodos baseados em árvores normalmente não requerem normalização dos dados. Além disso, conseguem lidar com valores faltantes, categóricos e numéricos (não é o caso da CART que implementamos).
- Complexidade logarítmica na etapa de predição.
- São capazes de lidar com problemas com múltiplos rótulos.
As árvores de decisão muito populares para problemas de classificação, regressão, análise exploratória entre outras tarefas.
Nem tudo são flores!
Árvores de decisão possuem alguns probleminhas que podem degradar seu poder preditivo, são eles:
- Árvore crescida até sua profundidade máxima pode decorar o conjunto de treino (o temido overfitting), o que pode degradar seu poder preditivo quando aplicado a novos dados. Isso pode ser mitigado "podando" a árvore de decisão ao atribuir uma profundidade máxima ou uma quantidade máxima de folhas.
- São modelos instáveis (alta variância), pequena variações nos dados de treino podem resultar em árvores completamente distintas. Isso pode ser evitado ao treinarmos várias árvores distintas e agregar suas predições (que veremos em outro post).
- Como vimos, o algoritmo de construção da árvore de decisão é guloso, ou seja, não garante a construção da melhor estrutura para o dados de treino em questão. Esse problema também pode ser mitigado ao treinarmos várias árvores distintas e agregar suas predições (veremos em outro post como fazer).
Conclusões
Nesse post mostramos o que são árvores de decisão, para que servem. Além do mais, mostramos de forma detalhada como construir uma a partir dos dados e disponibilizamos uma implementação do algoritmo CART (mesmo implemento pelo scikit-learn, porém sem otimização alguma).
Com esse artigo, espero que tenham ter uma ideia num bom nível de como as árvores de decisão funcionam.
O que vem a seguir?
Nos próximos episódios falaremos mais sobre árvores de decisão, sobretudo como mitigar os problemas enfrentados por ela através do uso de comitês de árvores de decisão (métodos ensemble). O primeiro que falaremos é o Bagging (Bootstrap Aggregating) que é base para entendermos as Random Forests.
