Funcionamento

Lê a base de dados e monta, literalmente, uma árvore de decisão.

Principais problemas:

• Overfitting, árvores muito grandes que são adaptadas demais aos dados
• Pequenas mudanças nos dados pode mudar toda a árvore
• Um algoritmo complexo e antigo, que está sendo adaptado para não ficar defasado
  • Random forest (usado pelo Kinect) é uma aplicação nova das árvores de decisão que bate de frente com KNN, redes neurais e SVM

Principais vantagens

• Fácil interpretação
• Não precisa de normalização e padronização de dados

Entendendo o algoritmo

Os atributos mais importantes ficam no topo da árvore, descendo conforme o grau de importância diminui.

Para fazer a construção da árvore, o algoritmo vai utilizar de duas formas matemáticas: Entropia(S) e Ganho de informação(S,A)

• Lista todos os valores de uma classe e contabiliza quantos registros existem em cada valor e aplica a fórmula da entropia para cada
  • Alto: 6/14
    • E(alto) = -(6/14) * log(6/14; 2)
  • Moderado: 3/14
    • E(moderado) = -(3/14) * log(3/14; 2)
  • Baixo: 5/14
    • E(baixo) = -(5/14) * log(5/14; 2)
• A fórmula da Entropia possui um somatório, então temos que juntar as três fórmulas em uma só: E(alto) + E(moderado) + E(baixo) = -(6/14) * log(6/14; 2) -(3/14) * log(3/14; 2) -(5/14) * log(5/14; 2) = 1,53
• Com o valor da Entropia Geral em mãos, vamos calcular o ganho de informação. O GI é feito para cada atributo da nossa base e, quanto maior o valor, maios a relevãncia (e mais no topo da árvore ficará)
  • O processo é parecido com o de entropia, vamos contabilizar os registros em relação ao total para cada atributo. Com esta info, vamos contabilizar a classe de cada atributo e seu valor.
  • G(historia)
    • G(historia<boa>): 5/14
      • G(historia<boa><alto>): 1/5
      • G(historia<boa><moderado>): 1/5
      • G(historia<boa><baixo>): 3/5
      • E(s) = -1/5 * log(1/5; 2) -1/5 * log(1/5; 2) -3/5 * log(3/5; 2) = 1,37
    • G(historia<desconhecida>): 5/14
      • G(historia<desconhecida><alto>): 2/5
      • G(historia<desconhecida><moderado>): 1/5
      • G(historia<desconhecida><baixo>): 2/5
      • E(s) = 1,52
    • G(historia<ruim>): 4/14
      • G(historia<ruim><alto>): 3/4
      • G(historia<ruim><moderado>): 1/4
      • G(historia<ruim><baixo>): 0/4
      • E(s) = 0,81
    • G(historia) = E(geral) - (Count(historia<boa>) * E(historia<boa>)) - (Count(historia<desconhecida>) * E(historia<desconhecida>)) - (Count(historia<ruim>) * E(historia<ruim>))
      • 1,53 - (5/14 * 1,37) - (5/14 * 1,52) - (4/14 * 0,81) = 0,26
  • G(dívida) = 0,06
  • G(garantia) = 0,20
  • G(renda) = 0,66
• Com os ganhos anotados, sabemos que o valor maior é o G(renda), logo, ele é o nodo principal da nossa árvore. A partir dele, vamos separar em 3 setas, pois temos 3 possibilidades de valores (<15; ≥ 15 < 35; > 35).
• Para cara seta (valor do atributo), vamos filtrar a nossa base de dados e refazer todos estes cálculos para descobrir qual é o atributo mais imporante agora (através do valor do ganho).

Outra forma de montar uma árvore de decisão

Outra forma de montar uma árvore de decisão é colocando a info em um gráfico, separando as classes, e fazendo split (linhas que separam duas partes do gráfico baseado em uma característica (um dos eixos do gráfico).