Modelos de Predição | Decision Tree
Quão bem você faz perguntas?
Escrito por Guilherme Fernandes, Fernando Matsumoto e Bernardo Coutinho.
Árvores de decisão?
Sim, parece rotineiro abstrair a natureza para elaborar algoritmos, já vimos em algoritmos genéticos, KNN e desta vez temos um modelo de predição baseado em árvores. Curioso, não acha?
Se você já jogou ou conhece esse tipo de jogo, sabe o quão importante é saber fazer boas perguntas.
Nesse jogo, jogam duas pessoas, cada uma escolhe uma face, e a cada rodada os jogadores tentam descobrir a face escolhida por meio de perguntas de sim ou não. Quem acertar primeiro, ganha.
As árvores de decisão funcionam exatamente assim, a ideia é construir um procedimento de perguntas de sim ou não a partir de certas características/atributos (no caso as features), para obter o target, que pode ser categórico ou numérico.
Como uma árvore pode representar um modelo de predição?
Podemos abstrair a estrutura de árvore por meio dos conceitos de ramos, nós, sub-árvores e folhas, como na imagem abaixo.
Os círculos roxos são chamados de nós e as linhas pretas que os ligam, de ramos. Os nós que não tem descendentes (com borda laranja na imagem) são chamados de folhas e o primeiro nó (com borda verde) é chamado de raiz. Juntos, os nós e ramos formam uma árvore.
Para transformar isso em uma árvore de decisão, imaginamos que a raiz representa o dataset inteiro e que cada ramo representa uma decisão. No exemplo dado na seção anterior, a raiz poderia representar todas as pessoas possíveis junto com a pergunta “Qual o gênero?”. A aresta saindo da raiz e indo para a esquerda poderia então representar a resposta “feminino” e o da direita, “masculino”, de modo que o nó da esquerda representaria o conjunto de mulheres e o da direita, o conjunto de homens. Os outros nós e ramos corresponderiam então a outras perguntas e as folhas dariam a classificação final (qual é a pessoa correta).
O número total de perguntas feitas nesse processo é chamado de profundidade (ou altura) dessa árvore. No caso da figura acima, temos uma árvore de profundidade 3: precisamos de 3 ramos (3 perguntas) para ir da raiz até as folhas. Note que isso corresponde a altura geométrica dessa árvore.
Ao longo desse processo, você pode ter percebido que uma árvore é formada de várias sub-árvores. Por exemplo, se olharmos apenas para o nó à direita da raiz e para os nós abaixo dele, temos uma sub-árvore, identificada pela circunferência tracejada. Do lado esquerdo, temos outro exemplo de sub-árvore.
Certo, mas como construo uma árvore de decisão?
Vamos pensar novamente no jogo que foi descrito, em que desejamos descobrir uma face. Se quisermos encontrar a solução da maneira mais rápida, as melhores perguntas a se fazer são aquelas que melhor dividem o seu conjunto de possibilidades de resposta, de forma a otimizar a eliminação das faces possíveis. Isso corresponderia a tentar separar o seu conjunto exatamente no meio.
Por exemplo, se metade dos indivíduos possuírem cabelo escuro, e a outra metade não, a melhor alternativa seria perguntar se a pessoa em questão tem cabelo escuro, para eliminar uma grande parte das respostas de uma só vez.
Tendo feito essa divisão, procuramos a pergunta ótima para o conjunto gerado, isto é, repetimos o processo, até descobrirmos a face.
Para um dataset, o processo é similar. As perguntas são feitas a respeito dos valores das features. E o processo é realizado para todo conjunto de dados gerado pelas divisões. Termina quando todos os caminhos fornecem classificação.
Note que as árvores crescem em tamanho máximo nesse processo. Para melhorar a capacidade de generalização de dados não vistos aplicamos um processo de poda (que será visto melhor no final do post).
O algoritmo pode ser representado pelo que segue:
1. Verifique qual atributo fornece o melhor corte
2. Crie um nó contendo esse atributo
3. Repita o mesmo para os subconjuntos até todos fornecerem um resultadoPerceba que o principal problema é saber quais perguntas fazer e quando fazê-las.
Os algoritmos que veremos a seguir fornecem diferentes respostas para esse problema.
ID3 — Interactive Dichotomiser 3 (Dicotomizador Iterativo 3)
Esse algoritmo é baseado na ideia de entropia. A entropia de um dataset é uma métrica da sua incerteza ou impureza, ou seja, representa a aleatoriedade em seus valores. O seu valor é zero quando não há aleatoriedade (todos os elementos do dataset tem a mesma classificação) e aumenta conforme o dataset fica mais impuro.
Considere, por exemplo, o caso da figura abaixo, em que há duas classes de elementos: as estrelas e os pentágonos. O dataset (a) é “impuro”, pois tem vários elementos de formas distintas. Já o dataset (b) é bem mais puro, pois quase todos os seus elementos têm a mesma forma (só há um pentágono). O caso extremo seria um dataset que só tivesse estrelas (ou, alternativamente, que só tivesse pentágonos). Nesse caso, o dataset seria completamente puro e sua entropia seria zero.
Em uma árvore de decisão, como vimos acima, um corte divide o dataset em dois subconjuntos. O algoritmo ID3 tenta fazer com que esses subconjuntos sejam tão puros quanto possível. Por exemplo, se tivermos duas classes, A e B, o corte ideal seria capaz de dividir o dataset em um subconjunto com elementos de classe A e outro com elementos de classe B. Um corte ruim dividiria o dataset em dois subconjuntos, cada um com vários elementos de classe A e B. Escolhendo apenas cortes do primeiro tipo, esperamos que as folhas da árvore representem subconjuntos completamente puros, permitindo que classifiquemos bem as observações.
Essa ideia é capturada pelo conceito de ganho de informação, que mede o quanto de entropia é removido a partir de um corte, ou seja, o quanto a pureza do dataset aumenta. Matematicamente é a diferença entre o valor da impureza antes de separar os dados e a média ponderada da impureza dos subconjuntos.
Para deixar isso um pouco mais claro, vamos analisar o exemplo abaixo, em que o objetivo é prever se o objeto é um pentágono ou uma estrela a partir de sua cor e transparência. Inicialmente, o dataset tem entropia alta. Para diminuir essa entropia, temos dois cortes possíveis (um para cada feature). Se dividirmos pela cor da figura (a), conseguimos dois subconjuntos com entropia baixa, pois cada um tem objetos de um único tipo. Logo, o ganho de informação é alto. Já separando por transparência (b), os subconjuntos ainda são “impuros”, ou seja, têm objetos de formas diferentes. Desse modo, o ganho de informação é baixo. Por esse motivo, o algoritmo escolheria o corte da esquerda.
CART — Classification and Regression Tree (Árvore de Classificação e Regressão)
Esse algoritmo é similar ao ID3, porém utiliza probabilidade para medir a impureza de um dataset, ao invés da entropia.
Imagine que você selecione duas observações aleatórias de um dataset. Qual é a probabilidade delas terem classes diferentes? Para que o nosso dataset seja puro, queremos que a probabilidade seja 0, ou seja, todas as observações têm a mesma classe. Por outro lado, conforme a impureza aumenta, esperamos que a probabilidade dos elementos terem a classes diferentes aumente.
Para aproveitar essa ideia, o CART define a impureza de Gini como a probabilidade de duas observações aleatórias de um dataset terem classificações diferentes. Ele segue um algoritmo semelhante ao do ID3, mas utiliza a impureza de Gini ao invés da entropia para escolher os melhores cortes.
Como o nome indica, esse algoritmo pode ser utilizado para predizer valores numéricos. Basicamente, nesse caso, a divisão consiste em encontrar grupos com resultados similares, e a média dos seus resultados é usada como predição para esse grupo. O algoritmo encontra a melhor divisão tentando minimizar a variância do grupo.
Árvore de decisão, na prática
Utilizaremos a maravilhosa biblioteca scikit learn de python para aplicar uma árvore de decisão. Se você ainda não a possui, veja o guia de instalação.
Após instalar, basta inserir o comando abaixo.
>>> from sklearn import treeE pronto, agora podemos implementar o algoritmo ID3 por meio da classe DecisionTreeClassifier. Para isso, é necessário alterar o parâmetro criterion para entropy, que por default é gini.
>>> tree.DecisionTreeClassifier(criterion="entropy")Vamos aplicar esse algoritmos no dataset Iris.
Já o CART pode ser utilizado pela classe DecisionTreeRegressor.
>>> tree.DecisionTreeRegressor()Vamos aplicar esse algoritmo no dataset Boston Housing.
Overfitting em Árvores de Decisão
Esse é o grande problema em todos os algoritmos de aprendizado! No caso de árvores de decisão ele surge quando a árvore se torna hiper específica para o dataset, perdendo portanto o poder de generalização em outros dados. Ou seja, conforme vamos aumentando demais o número de nós na árvore, a acurácia cresce na base de treino, mas piora na base de teste.
Para resolver esse problema recorremos as seguintes questões:
- Como detectar atributos (ou cortes) irrelevantes?
- Quais cortes valem a pena e quais têm maior probabilidade de causar overfitting?
Pruning
Pruning consiste em podar uma árvore de decisão já treinada, em uma tentativa de diminuir o número de nós e, portanto, o overfitting. A forma mais simples de fazer isso é pelo método do erro reduzido. Esse método passa por cada nó da árvore e:
- Transforma o nó em uma folha cuja classe é a mais comum no nó (dentre as observações da base de treinamento que se encaixam no nó). A sub-árvore abaixo desse nó é removida.
- Verifica a acurácia da nova árvore em um conjunto de validação.
- Se a acurácia do modelo não tiver diminuído, a nova árvore é mantida. Caso contrário, voltamos para a árvore antiga.
Hiperparâmetros
Quando a árvore está sendo treinada, é possível que alguma folha tenha apenas uma observação associada, o que pode levar a overfitting (a classe daquela folha é determinada por apenas uma observação).
No sklearn, podemos usar os hiperparâmetros min_samples_split e min_samples_leaf para controlar isso. O primeiro garante que um corte só seja feito em nós com no mínimo min_samples_split observações. No entanto, mesmo que esse número seja alto, é possível que alguma das folhas geradas por esse corte tenham um número muito baixo de observações.
Para resolver isso, podemos usar min_samples_leaf, que determina o número mínimo de observações que cada folha deve ter (se um corte fosse criar uma folha com menos observações, ele não será feito).
Além disso, podemos usar também max_depth para controlar a profundidade máxima da árvore.
C’est fini — Fim
Esperamos que tenha gostado desse Turing Talks. Nas próximas semanas voltaremos com mais tópicos nesse assunto amado por todos nós. Por isso, não deixe de seguir nossa página do Medium para não perder nada. Também, acompanhe nossa página do Facebook e Instagram, e fique ligado no que postamos por lá!
Abraços e até uma próxima!
