Aprendizado por Árvores de Decisão

Afluentes: Inteligência Artificial

Definiçã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.

Imagine um fluxograma, por exemplo a figura abaixo. Isso pode ser considerado uma árvore de decisão (caso não tenha loop).

Se você extender todos os caminhos, estará montando uma árvore, em que cada nó pode ter de zero à n filhos. Cada nó armazena informações que, por meio de escolhas baseadas nelas, pode ir para diferentes nós. O nó inicial, de maior nível hierárquico, ou ponto de partida, é chamado de nó raiz, os nós provenientes de um nó são os nós filhos deste nó, que também podem possuir seus próprios nós filhos. Um nó que não possui filho é chamado de nó folha ou terminal.

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.

Contudo, uma árvore de decisão não é, por si só, aprendizado de máquina, mas seu o processo de construção automático, a partir de um conjunto de dados, sim. Existem algoritmos que fazem isso de forma não-paramétrica (não assume nada dos dados previamente) e supervisionada (possui um conjunto de dados e suas respectivas respostas).

• Uma vez construída uma árvore de decisão, seu uso é imediato e muito rápido computacionalmente. Além disso, a interpretabilidade da árvore de decisão é um de

seus pontos fortes.

• No entanto, a construção de uma árvore de decisão, chamado de processo de indução, pode ser uma tarefa de alta demanda computacional.
• Há muitas maneiras de uma árvore de decisão ser estruturada a partir de um conjunto de atributos. De forma exaustiva, o número de árvores de decisão possíveis cresce fatorialmente à medida que o número de atributos aumenta.
• Logo, torna-se impraticável definir a estrutura da árvore de decisão ótima para um determinado problema, devido ao elevado custo computacional envolvido nessa busca.
• Nesse sentido, algoritmos baseados em heurísticas têm sido desenvolvidos para a indução de árvores de decisão. Mesmo que eles não garantam uma solução ótima, apresentam resultados satisfatórios em tempo factível.

Vantagens

Árvores de decisões são conceitualmente simples, mas poderosas. Sua popularidade se dá por certas características:

• 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.

Problemas

As árvores de decisão possuem certos problemas que podem prejudicar seu poder preditivo:

• Á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).
• 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).