As Árvores de Decisão e Regressão são algoritmos supervisionados. O objetivo principal é induzir um modelo que seja capaz de predizer uma classe/rótulo/valor de uma variável resposta por meio do aprendizado de regras simples inferidas do conjunto de treinamento. Essas regras são geradas por meio da estratégia de divisão e conquista que recursivamente tende a diminuir a complexidade do problema, tornando-o mais simples. A combinação dessas regras produz uma árvore capaz de gerar uma solução para o problema complexo. Os modelos em árvore são designados Árvores de Decisão (AD) para problemas de classificação e Árvores de Regressão (AR) para problemas de regressão.
Formalmente uma AD é um grafo acíclico direcionado em que cada nó é um nó de divisão ou um nó folha:
-
Nó de divisão: Possui dois ou mais sucessores. Ele contém um teste condicional baseado nos valores dos atributos. Normalmente o teste é univariado, ou seja, em um único atributo. Exemplo: Idade > 18, Profissão ∈ {professor, estudante}.
-
Nó folha: É rotulado com uma função que considera valores da variável alvo dos exemplos que chegam na folha. Em uma AD de classificação podemos usar uma função de minimização de custo 0-1 como a moda. Em AR de regressão podemos usar uma função de minimização do erro médio quadrático ou desvio absoluto. Exemplo: média/mediana
A Figura a seguir representa uma AD e sua divisão no espaço para uma base de dados com dois atributos preditivos (x1 e x2). Cada nó da árvore corresponde a uma região nesse espaço. Os nós folhas são mutualmente excludentes e a junção de todas as regiões cobre todo o espaço definido pelos atributos. Os hiperplanos gerados são ortogonais aos eixos dos atributos testados e paralelo a todos os outros eixos. Todas as regiões são hiper-retângulos.
Exemplo de uma Árvore de Decisão. Adaptado de Katti Faceli et al., (2011)
O algoritmo de AD é mostrado na Figura a seguir. A entrada para a função é o conjunto de treinamento D e sua saída é uma AD. Na sequência o critério de parada é avaliado. Se mais divisões do conjunto de treinamento são necessárias, é escolhido um atributo que maximiza alguma medida de impureza. Na sequência a função de geração da árvore é chamada recursivamente e aplicada a uma partição do conjunto de treinamento D.
Algoritmo de uma Árvore de Decisão. Adaptado de Katti Faceli et al., (2011)
É ressaltar que a geração de uma árvore minimal é um problema NP-completo. Os algoritmos exploram heurísticas que localmente executam pesquisa um passo a frente. Uma vez que uma decisão é tomada ela nunca é desfeita. Isso pode gerar uma solução ótima localmente, o que pode estar longe do ótimo global.
Considere um nó t de divisão de uma AD em que a probabilidade de observar exemplos de classe ci é dado por pi. Portanto a probabilidade de observar todas as classes é p1,p2,...pn então a impureza sobre um nó t é uma função sobre a proporção da classe daquele nó . Portanto a redução de impureza gerado pela divisão S de um conjuntos de treinamento em dois subconjuntos L e R pode ser medida como:
Nessa equação PL e PR representam a probabilidade de um exemplo quando aplicado a regra de divisão pertencer ao subconjunto L ou R, respectivamente.
A função de impureza apresenta características gerais como: simetria, ter máximo quando e ter um mínimo quando
. Logo, a proposta natural de uma AD deve tentar maximizar a divisão dos subconjuntos que geram menor erro. Portanto, uma divisão que mantém a proporção de classes em todo o subconjunto não tem utilidade e uma divisão em que cada subconjunto contém somente exemplos de uma classe tem utilidade máxima. Casos intermediários são tratados de forma diferente por cada medida de impureza.
Existem diversas medidas de impureza como ganho de informação, entropia, distância, ângulo, qui-quadrado e etc. Nessa seção vamos abordar a entropia e ganho de informação, medidas base para o entendimento do algoritmo C4.5 proposto por Ross Quinlan em 1993.
A entropia mede a aleatoriedade de uma variável aleatória em bits. Suponha uma variável aleatória A com domínio . Suponha que a probabilidade de observar os valores são
. A entropia de A é calculada como:
Em uma AD, entropia é usada para medir a aleatoriedade do atributo alvo. A cada nó de decisão da árvore, o atributo que mais reduz a aleatoriedade da variável alvo será escolhido para dividir os dados. O ganho de informação é medido em cada atributo para verificar o quanto eles reduzem a entropia do sistema. Portanto o ganho de informação é medido como a diferença da entropia do conjunto de dados e a soma ponderada da entropia das partições.
Assumindo que temos um problema de classificação binária, ou seja, duas classes e que cada uma delas tenha p e q exemplos no conjunto de treinamento, respectivamente. Dessa forma podemos calcular a entropia das classes da seguinte forma:
Alem disso, essa base tem um atributo A com v categorias. Para calcular a entropia desse atributo precisamos considerar a entropia das partições, ou seja, a entropia de cada uma das v categorias. A seguinte equação representa a entropia das partições p e q do atributo A:
Uma vez que sabemos a entropia do conjunto de dados e a entropia do atributo A, podemos calcular o ganho de informação por meio da diferença entre a entropia da base e a entropia das partições. A equação a seguir representa esse conceito:
A heurística apresentada deve ser aplicada para todos atributos da base com o objetivo de selecionar aquele que maximiza o ganho de informação para aquele conjunto de dados. Como mencionado, normalmente os testes são realizados em atributos nominais e irá dividir os dados em tantos subconjuntos quantos os valores do atributo.
O conjunto de dados Jogar Tênis é um problema de classificação binária em que pretende-se classificar se uma pessoa deve ou não, dado certas condições climáticas, jogar tênis. Os atributos de entrada são o Tempo, Temperatura, Umidade e Vento. O conjunto tem 14 amostras de treinamento e a última coluna denominada Joga representa os rótulos jogar ou não tênis. Os atributos Tempo e Vento são categóricos e os atributos Temperatura e Umidade são contínuos.
Base de dados Jogar Tênis. Adaptado de Katti Faceli et al., (2011)
Para construir uma AD precisamos descobrir o atributo que melhor discrimina as classes. Para isso, precisamos calcular as probabilidades associadas de cada classe, a entropia do conjunto de treinamento, a entropia das partições e então estimar o ganho de informação de cada atributo. A seguir iremos calcular o ganho de informação do atributo Tempo.
1⁰ Passo:
Probabilidade associada de cada classe:
Entropia da classe para todo o conjunto de treinamento:
2⁰ Passo:
Estimar a probabilidades de observar as classes dado cada categoria do atributo Tempo:
3⁰ Passo: Calcular a entropia ponderada para o atributo Tempo:
4⁰ Passo: Calcular o ganho de informação em dividir o conjunto de acordo com os valores do atributo Tempo:
Uma vez que foi calculado o ganho de informação gerado pelo atributo Tempo, o mesmo precisa ser feito para o atributo Vento, Temperatura e Umidade. No caso dos dois últimos, como eles são atributos contínuos, alguma estratégia precisa ser utilizada para permitir a divisão desse atributo em partições.
As estratégias mais utilizadas é a discretização ou a escolha de um ponto de corte binário. A discretização está relacionada a transformação dos dados contínuos em categóricos por meio de estratégias como o histograma enquanto a escolha de um ponto de corte define um valor do conjunto de treinamento (normalmente utilizando uma função de mérito) que permite a construção de uma partição binária. Usualmente utiliza-se a segunda estratégia.
No exemplo da base Jogar Tênis, um ponto de corte interessante para o atributo Temperatura é o valor 70.5. Esse valor permite separar as amostrar em partições interessantes. A seguir os passos 2, 3 e 4 são repetidos:
2⁰ Passo:
Estimar a probabilidades de observar as classes dado cada categoria do atributo Temperatura:
3⁰ Passo: Calcular a entropia ponderada para o atributo Temperatura:
4⁰ Passo: Calcular o ganho de informação em dividir o conjunto de acordo com os valores do atributo Temperatura:
Sumarizando o ganho de informação para todos os atributos temos os seguintes valores:
Portanto podemos concluir que o atributo Tempo é que gera maior redução no ganho de informação. Logo o nó raiz da AD é composta pelo nó Tempo com 3 ramos, cada um relacionado a uma categoria desse atributo categórico (ensolarado, chuvoso e nublado). Como o algoritmo é baseado em dividir para conquistar, cada nó filho da árvore precisa ser construído baseado em sua partição dos dados. O processo se repete até que todos os nós sejam puros ou uma estratégia de poda seja aplicada.
As estatísticas calculadas em nós mais rasos em uma AD costumam ser os mais importantes enquanto estatísticas de nós mais profundos costumam ter níveis de importância menores. Isso se dá porque os nós mais rasos refletem os conceitos mais gerais enquanto os mais profundos, os conceitos mais específicos e normalmente relacionados ao superajustamento. O superajustamento está diretamente relacionado ao tamanho da árvore. Quanto maior, mais superajustada e mais difícil de ser interpretada. Portanto, podar uma árvore, que é trocar nós profundos por nós folhas, pode ajudar a minimizar esse problema.
A troca dos nós mais profundos por folhas pode causar a classificação errônea de alguns exemplos do conjunto de treinamento. Apensar de parecer contra-intuitivo, isso pode melhorar o desempenho para exemplos novos nunca antes vistos. Os métodos de poda mais conhecidos são: pré-poda e pós-poda. Enquanto a pré-poda é realizada durante a construção da árvore, a pós-poda é realizada depois da construção da árvore.