O que é uma Decision Tree?

Como você pode ver no diagrama abaixo, uma Decision Tree começa com um nó raiz, que não possui nenhuma ramificação de entrada. Os ramos de saída do nó raiz então alimentam os nós internos, também conhecidos como nós de decisão. Com base nos recursos disponíveis, ambos os tipos de nós conduzem avaliações para formar subconjuntos homogêneos denotados por nós folha ou nós terminais. Os nós folha representam todos os resultados possíveis dentro do conjunto de dados.

Como exemplo, vamos imaginar que você estivesse tentando avaliar se deveria ou não surfar. Você pode usar as seguintes regras de decisão para fazer uma escolha:

Esse tipo de estrutura de fluxograma também cria uma representação fácil de digerir da tomada de decisões, possibilitando que diversos grupos em uma organização entendam melhor por que uma decisão foi tomada.

O aprendizado de Decision Tree emprega a estratégia dividir para conquistar, conduzindo uma pesquisa ambiciosa para identificar os pontos de divisão ideais em uma árvore. Esse processo de divisão é então repetido de maneira descendente e recursiva até que todos, ou a maioria dos registros tenham sido classificados em rótulos de classe específicos.

A classificação ou não de todos os pontos de dados como conjuntos homogêneos depende em grande parte da complexidade da decision tree. Árvores menores atingem com maior facilidade nós de folha puros, ou sejam, pontos de dados em uma única classe. No entanto, à medida que uma árvore cresce, torna-se cada vez mais difícil manter essa pureza, e isso geralmente resulta em poucos dados dentro de uma determinada subárvore. Quando isso ocorre, é conhecido como fragmentação de dados e, muitas vezes, pode levar ao sobreajuste.

Como resultado, as Decision Trees têm preferência por árvores pequenas, o que é consistente com o princípio da parcimônia na Navalha de Occam; ou seja, "as entidades não devem ser multiplicadas além do necessário". Dito de outra forma, as Decision Trees devem adicionar complexidade apenas se necessário, já que a explicação mais simples geralmente é a melhor. Para reduzir a complexidade e evitar o sobreajuste, a poda geralmente é empregada; este é um processo que remove ramificações que se dividem em recursos com baixa importância. O ajuste do modelo pode então ser avaliado por meio do processo de validação cruzada.

Outra maneira pela qual as decision trees podem manter a precisão é formando um conjunto por meio de um algoritmo de floresta aleatória; esse classificador prevê resultados mais precisos, especialmente quando as árvores individuais não estão correlacionadas entre si.

O algoritmo de Hunt, desenvolvido na década de 1960 para modelar o aprendizado humano em psicologia, é a base de muitos algoritmos populares de decision tree, como os seguintes:

- ID3: Ross Quinlan é creditado no desenvolvimento do ID3, abreviação de "Iterative Dichotomiser 3". Esse algoritmo utiliza a entropia e o ganho de informações como métricas para avaliar as divisões de candidatos. Há algumas das pesquisas de Quinlan sobre esse algoritmo de 1986 disponíveis aqui.

- C4.5: Esse algoritmo é considerado uma iteração posterior do ID3, que também foi desenvolvido por Quinlan. Pode utilizar ganho de informação ou taxas de ganho para avaliar pontos de divisão dentro das decision trees.

- CART: O termo CART é uma abreviação de "árvores de classificação e regressão" e foi introduzido por Leo Breiman. Este algoritmo normalmente utiliza impureza de Gini para identificar o atributo ideal para divisão. A impureza Gini mede a frequência com que um atributo escolhido aleatoriamente é classificado incorretamente. Ao avaliar usando a impureza de Gini, um valor menor é mais ideal.

Embora haja várias maneiras de selecionar o melhor atributo em cada nó, dois métodos, ganho de informação e impureza de Gini, atuam como critério de divisão popular para modelos de decision tree. Eles ajudam a avaliar a qualidade de cada condição de teste e quão bem ela será capaz de classificar as amostras em uma classe.

É difícil explicar o ganho de informação sem antes discutir entropia. Entropia é um conceito que deriva da teoria da informação, que mede a impureza dos valores da amostra. É definido pela seguinte fórmula, onde:

• S representa o conjunto de dados em que a entropia é calculada 
• c representa as classes no conjunto, S
• p(c) representa a proporção de pontos de dados que pertencem à classe c em relação ao número total de pontos de dados no conjunto, S

Os valores de entropia podem cair entre 0 e 1. Se todas as amostras no conjunto de dados, S, pertencerem a uma classe, a entropia será igual a zero. Se metade das amostras for classificada como uma classe e a outra metade estiver em outra classe, a entropia será mais alta em 1. Para selecionar o melhor recurso para dividir e encontrar a Decision Tree ideal, o atributo com a menor quantidade de entropia deve ser usado.

Ganho de informação representa a diferença na entropia antes e depois de uma divisão em um determinado atributo. O atributo com o maior ganho de informações produzirá a melhor divisão, pois está fazendo o melhor trabalho na classificação dos dados de treinamento de acordo com sua classificação de destino. O ganho de informação é geralmente representado com a seguinte fórmula,

onde

• a representa um atributo específico ou rótulo de classe
• Entropia(S) é a entropia do conjunto de dados, S
• |Sv|/|S| representa a proporção dos valores em S_v para o número de valores no conjunto de dados, S.

Vamos dar um exemplo para consolidar esses conceitos. Imagine que temos o seguinte conjunto de dados arbitrário:

Para esse conjunto de dados, a entropia é 0,94. Isso pode ser calculado encontrando-se a proporção de dias em que “Jogar tênis” é “Sim”, que é 9/14, e a proporção de dias em que “Jogar tênis” é “Não”, que é 5/14. Em seguida, esses valores podem ser inseridos na fórmula de entropia acima.

Entropia (Tênis) = -(9/14) log2(9/14) – (5/14) log2 (5/14) = 0,94

Podemos então calcular o ganho de informação para cada um dos atributos individualmente. Por exemplo, o ganho de informação para o atributo "Umidade" seria o seguinte:

Ganho (Tênis, Umidade) = (0,94)-(7/14)*(0,985) - (7/14)*(0.592) = 0.151

Recapitulando,

- 7/14 representa a proporção de valores em que a umidade é igual a "alta" em relação ao número total de valores de umidade. Nesse caso, o número de valores em que a umidade é igual a "alta" é o mesmo que o número de valores em que a umidade é igual a "normal".

- 0,985 é a entropia quando umidade = "alta"

- 0,59 é a entropia quando a umidade = "normal"

Em seguida, repete o cálculo do ganho de informações para cada atributo na tabela acima e seleciona o atributo com o maior ganho de informações para ser o primeiro ponto de divisão na decision tree. Nesse caso, o Outlook produz o maior ganho de informações. A partir daí, o processo é repetido para cada subárvore.

A impureza do Gini é a probabilidade de classificar incorretamente o ponto de dados aleatório no conjunto de dados se ele for rotulado com base na distribuição de classe do conjunto de dados. Semelhante à entropia, se definido, S é puro, ou seja, pertencente a uma classe), então sua impureza é zero. Isso é denotado pela seguinte fórmula:

Embora as decision trees possam ser utilizadas em uma variedade de casos de uso, outros algoritmos normalmente superam os algoritmos de decision tree. Dito isso, as decision trees são particularmente úteis para tarefas de mineração de dados e descoberta de conhecimento. Vamos explorar os principais benefícios e desafios da utilização de decision trees mais abaixo:

• Fácil de interpretar: A lógica booliana e as representações visuais das decision trees facilitam a sua compreensão e consumo. A natureza hierárquica de uma decision tree também facilita a visualização de quais atributos são mais importantes, o que nem sempre fica claro com outros algoritmos, como redes neurais.
  
  
• É necessária pouca ou nenhuma preparação de dados: As decision trees têm várias características que as tornam mais flexíveis do que outros classificadores. Ele pode lidar com vários tipos de dados, ou sejam, valores discretos ou contínuos, e valores contínuos podem ser convertidos em valores categóricos por meio do uso de limites. Além disso, ele também pode lidar com valores com valores ausentes, o que pode ser problemático para outros classificadores, como Naïve Bayes.
  
  
• Mais flexível: as decision trees podem ser aproveitadas para tarefas de classificação e regressão, tornando-as mais flexíveis do que alguns outros algoritmos. Também é insensível às relações subjacentes entre atributos; isso significa que, se duas variáveis estiverem altamente correlacionadas, o algoritmo escolherá apenas um dos recursos para dividir.

• Propenso a overfitting: decision trees complexas tendem a overfitting e não generalizam bem com novos dados. Esse cenário pode ser evitado através dos processos de pré-poda ou pós-poda. A pré-poda interrompe o crescimento da árvore quando não há dados suficientes, enquanto a pós-poda remove subárvores com dados inadequados após a construção da árvore.
  
  
• Estimadores de alta variância: pequenas variações nos dados podem produzir uma árvore de decisão muito diferente. O ensacamento, ou a média das estimativas, pode ser um método para reduzir a variância das decision trees. No entanto, essa abordagem é limitada, pois pode levar a preditores altamente correlacionados.
  
  
• Mais caro: como as decision trees adotam uma abordagem de busca ambiciosa durante a construção, o treinamento delas pode ser mais caro do que o de outros algoritmos.