Métodos de Aprendizagem Supervisionada Baseados em Árvore
Introdução
Neste artigo falaremos de alguns métodos baseados em árvores, conceituando desde o que são árvores de decisão, como são utilizadas para regressão e classificação e como o algoritmo age, o que é ensemble e alguns modelos modelos dessa metodologia como bagging, random forest, boosting e BART.
1 Decision Trees
Decision Tree ou árvores de decisão são métodos de regressão e classificação não paramétricos de aprendizado supervisionado. Nele, o objetivo é criar um modelo que prediz o valor de uma variável dependente a partir do aprendizado de regras de decisão inferidas a partir das features. Esse método possui diversas vantagens em relação aos demais, mas também algumas desvantagens.
Possui como vantagem a simplicidade de se entender e interpretar e as árvores podem ser visualizadas graficamente. Requerem pouca preparação de dados. Outras ténicas por exemplo quererem normalização de dados, criação de variáveis dummy e valores nulos/em branco precisam ser removidos. (A implementação do scikit-learn ainda não lida com valores nulos). O custo de usar a árvore (ou seja, prever dados) é logarítmico no número de pontos de dados usados para treinar a árvore. São capazes de lidar com dados numéricos e categóricos (sua implementação do scikit-learn não suporta variáveis categóricas por enquanto) e com problemas de várias saídas. Usam um modelo “caixa branca”, significa que explica facilmente as situações observadas pelo modelo através de lógica booleana. É possível validar um modelo usando testes estatísticos. Isso torna possível explicar a confiabilidade do modelo. E funcionam bem, mesmo que suas suposições sejam um pouco violadas pelo modelo verdadeiro a partir do qual os dados foram gerados.
Algumas desvantagens dizem respeito ao processo de decision tree, que pode criar modelos complexos demais, não generalizendo bem nos dados. Ou seja overfittando, mas alguns mecanismos como prunning, definir um número mínimo de amostras por nós ou definir um maximum depth ou profundade máxima da árvore são necessários para que esse problema não aconteça. As árvores de decisão podem ser instáveis porque pequenas variações nos dados podem resultar na geração de uma árvore completamente diferente, mas esse problema pode ser mitigado usando árvores de decisão dentro de um ensemble. As previsões de árvores de decisão não são suaves nem contínuas, mas aproximações constantes por partes. Portanto, eles não são bons em extrapolação. Os algoritmos de aprendizado de árvore de decisão são baseados em algoritmos heurísticos, como o algoritmo greedy, onde as decisões localmente ótimas são tomadas em cada nó. Esses algoritmos não podem garantir o retorno da árvore de decisão globalmente ótima, mas isso pode ser mitigado treinando várias árvores em um ensemble learner, onde as features e as amostras são amostrados aleatoriamente com substituição. Existem conceitos difíceis de aprender porque as árvores de decisão não os expressam facilmente, como problemas de XOR, paridade ou multiplexador. Os learners da árvore de decisão criam árvores tendenciosas se algumas classes dominarem, se os dados não forem balanceados. Portanto, é recomendado balancear o conjunto de dados antes de ajustar com a árvore de decisão.
1.1 Regressão
O processo de construção de uma árvore de regressão é dividido em duas etapas. Primeiro, as variáveis preditoras são divididas em J regiões distintas e não sobrepostas, R1, R2, …, Rj. E para cada observação que está na região Rj, é feito uma predição em que o valor dela é a média (geralmente) do valor da variável dependente de treinamento na região Rj.
Imagine que está fazendo uma regressão de salário de trabalhadores baseado em anos de experiência e anos de estudo.
A figura acima mostra uma árvore de regressão ajustada à esses dados. Ela consiste em um conjunto de regras de divisão (splits), começando no topo da árvore. A primeira divisão no topo da árvore atribui o primeiro ramo (branch) a esquerda a quem tem menos de 10 anos de experiência. O salário predito para esses trabalhadores é dado pelo valor médio salarial para trabalhadores os trabalhadores com menos de 10 anos de experiência. Para trabalhadores com dez anos ou mais de experiência é atribuído o ramo a direita, e depois são subdivididos em anos de estudo.
No geral a árvore estratificaria ou segmentaria os trabalhadores em três regiões do espaço para previsão. A primeira em que pessoas tem menos de 10 anos de experiência, trabalhadores com dez ou mais anos de experiência sem ensino superior (<12), e trabalhadores com mais de 10 anos de experiência com ensino superior (>12)
Essas três regiões podem ser escritas como
R1 = {X | Experiência < 10},
R2 = {X | Experiência >= 10, Estudo <12} e
R2 = {X | Experiência >= 10, Estudo >12}
Essas três regiões R1, R2 e R3 são chamadas de nós terminais (terminal nodes) ou folhas (leaves) da árvore. Os pontos ao longo da divisão dos ramos são chamados de nós internos (internal nodes). Nesse exemplo fictícia acima na figura 1.1 dois nós internos são indicados como Experiência < 10 e Estudos < 12. Os segmentos das árvores que conectam os nós são chamados de ramos (branches). Uma interpretação que pode ser feita a partir do gráfico na figura 1.1 é que Experiência é o fator mais importante para determinar o salário, e os trabalhadores com menos anos de estudo ganham menos que os que possuem mais.
O objetivo nas partições e no número delas é achar um número de partições que minimise o RSS. O RSS, ou “Residual Sum of Squares” (Soma Residual dos Quadrados), é uma métrica estatística frequentemente utilizada para avaliar a qualidade de ajuste de um modelo estatístico aos dados observados. É calculada como a soma dos quadrados das diferenças entre os valores observados e os valores previstos pelo modelo. Essa estatística é usada pra mensurar a variância nos resíduos dos dados que não são explicados pelo modelo de regressão. Quanto menor o valor de RSS, melhor o ajuste do modelo aos dados. É dado por:
em que ŷrj é a resposta média para a observação de treino na j-ésima partição.
É inviável computacionalmente considerar todos os números de partições possíveis, por isso é feito uma abordagem top-down e greedy chamada de recursive binary splitting. Ela é top-down porquê começa no topo da árvore, em que todos os pontos de observação pertencem a uma mesma região e depois divide sucesivamente os espaços preditores. Cada divisão é feita através de dois novos ramos abaixo da árvore. E também é greedy porquê para cada passo da construção da árvore, a melhor divisão é feita em cada passo, no passo atual.
Para que possamos performar o recursive binary splitting, primeiro é selecionado o preditor Xj e o ponto de corte s em que a divisão do espaço do preditor nas regiões {X | Xj < s} e {X | Xj >= s} leve a maior redução possível do RSS. São considerados todos os preditores X1, X2, …, Xp e todos os possíveis valores de corte s para cada preditor, e depois é escolhido o preditor e o ponto de corte que resulta na árvore que tem menor RSS. Para cada j e s, são definidos pares de semiplanos e é buscado um valor de j e s que minimize a equação onde ŷrj1 é a resposta média para as observações de treino em R1(j, s), e ŷr2 é a resposta média para as observações de treino em R2(j, s). Assim, encontramos os valores de j e s que minimizam o RSS.
R1 (j, s) = {X|Xj < s} e
R2 (j, s) = {X|Xj ≥ s}
Em seguida o processo é repetido, buscando o melhor preditor e o melhor ponto de corte para dividir os dados buscando minimizar o RSS em cada região. Mas em vez de dividir o espaço da variável preditora completo, é dividido uma das duas regiões identificadas anteriormente, resultando em três regiões. E novamente uma das três regiões é dividida buscando minimizar o RSS. Esse processo continua até que algum critério seja alcancado, por exemplo, continuar o processoa té atingir no máximo dez, cinquenta ou mil regiões.
Uma vez que as regiões R1, R2, …, Rj são criadas, predizemos a resposta baseado nas observações de teste utilizando a média das observações de treinamento da região j em a observação de teste pertence.
Esse processo descrito até agora pode produzir bons resultados no dataset de treino, mas provavelmente irá overfittar os dados, resultando em uma performace ruim no dataset de teste. Isso ocorre porquê a árvore final é muito complexa. Uma árvore com poucas partições e regiões leva a uma baixa variância e melhor interpretação, ao custo de ter pouco viés.
Uma alternativa é construir a árvore somente até o ponto em que a minimização do RSS a partir da partição atinja algum critério, como exceder algum limite. Assim, resultando em árvores menores.
Através do cost complexity pruning ou weakest link pruning podemos fazer fazer essa poda (prune) até esse ponto. Em vez de considerar todas as subárvores possíveis que minimizam o RSS até atingir um critério, podemos considerar uma sequência de árvores indexadas por um parâmetro de tunning alfa α não negativo. Cada valor de alfa corresponde a subárvores T ⊂ T0 tal que é a menor possível.
Aqui |T| indica o número de nós terminais da árvore T, Rm é o subset do espaço preditor (os retangulos da figura 1.2) correspondente ao m-ésimo nó terminal, e ŷrm é a resposta prevista associada ao Rm, sendo a resposta prevista a média das observações de treino em Rm. O parâmetro de tunning alfa controle o trade-off entre a complexidade de uma subárvore e seu ajusta nos dados de treino. Quando o alfa = 0, então a subárvore T será igual a T0, porquê apenas estará mensurando o erro do treinamento. Mas quanto maior o alfa, mais minimizado e menor será a subárvore. Quanto mais aumentamos o alfa, mais os ramos são podados, de modo que fica fácil obter uma sequência de subárvores em função do alfa. Assim, podemos selecionar um valor do alfa usando um conjunto de dados de validação ou validação cruzada e depois retornamos ao dataset completo e obtermos a subárvore correspondente ao alfa. O processo de construção de árvore de regressão pode ser resumido em:
1. Usar recursive binary splitting para crescer uma árvore grande nos dados de treino, parar apenas quando os nós terminais tiverem menos que um número mínimo de observações.
2. Aplicar a cost complexity prunning à árvore para obter a sequência das melhores subárvores como uma função de alfa.
3. Usar K-fold cross validation para escolher o alfa. Assim, dividindo as observações de treino em K partes em que cada parte k = 1,…K:
3.1. Repetir os passos 1 e 2 em tudo, excetona k-ésima parte dos dados de treinamento
3.2. Validar o mean squared prediction error nos dados na k-ésima parte a esquerda, como uma função de alfa.
Faça a média dos resultados para cada valor de alfa, e escolha o alfa que minimiza o erro médio
4. Volta para a subárvore do passo 2 que corresponde ao valor escolhido de alfa.
1.2 Classificação
As árvores de classificação são bem similares as de regressão, mas são usadas para prever resultados qualitativos. Nas árvores de classificação, o valor predito é classe mais comum nas observações de treinamento na região em que ela pertence.
Assim como nas árvores de regressão utilizamos recusrive binary splitting para construir a árvore, mas não podemos utilizar o RSS como critério para fazer as partições das regiões, então como alternativa podemos utilizar o classification error rate, gini index ou entropy.
Como vamos atribuir a uma observação em uma determinada região à classe mais comum de observações de treinamento daquela região, o classification error rate é a fração de observações de treinamento daquela região que não pertencem à classe mais comum.
Nela, representamos com p̂mk a proporção das observações de treino na m-ésima região que são da k-ésima classe. Mas o erro não é sensível ao crescimento da árvore, sendo preferível utilizar gini index ou entropy.
O gini index é a mensuração do total da variância ao longo das K classes. É a mensuração da pureza dos nós, quando tem um valor pequeno indica que o nó contêm predominantemente observações de uma única classe.
Na teoria da informação, entropia é uma mensuração de impureza ou incerteza num grupo de observaçoes, na classification tree determina a escolha da partição dos dados a partir do ganho de informação da entropia. Quanto maior a aleatóriedade nos dados, maior a entropia e menor o ganho de informação.
Assim como o gini index, a entropia terá um valor pequeno se o m-ésimo nó for puro.
Ao construir uma árvore de classificação, gini e entropia são geralmente usados para validar a qualidade da partição, já que essas duas abordagens são mais sensíveis em relação a pureza do nó que o classification error rate. Qualquer uma das três abordagens pode ser usada ao fazer o prunning da árvore, mas caso a precisão da árvore final for o objetivo, é preferível usar o classification error rate.
2 Ensemble
Os métodos abordados a seguir são métodos de ensemble. Ensemble é uma abordagem que combina vários weak learners, modelos que trariam uma previsão mediana e fraca, com o objetivo de obter uma única previsão muito mais poderosa.
2.1 Bagging
Boostrap aggregation ou bagging é um procedimento de propósito geral para reduzir a variância de métodos de aprendizado estatístico.
Num dataset com n observações independentes Z1, …,Zn, cada observação possui variância σ², a variância da média das observações é dada por σ²/n. Isso significa que realizar a média do conjunto de observações reduz a variância. Logo, uma forma de aumentar a acurácia do teste diminuindo a variância é realizar vários treinamentos com subsets da população, construir predições separadas e realizar a média delas. Aqui, utilizamos B para gerar os subsets de treino, e realizamos a média para obter um único modelo de aprendizagem estatística com baixa variância.
Aqui entra o “boostrap” do bootstrapping aggregation. O procedimento de bagging utiliza amostragem por bootstrapping, gerando diferentes subsets do treinamento, selecionando os dados aleatoriamente com reposição. Após gerar B diferentes subsets, é feito o treinamento no b-ésimo subset, e ao final realizamos a média das predições.
Os weak learners são treinados em cada subsample em paralelo de forma independente e ao final, é feito uma média ou a maioria dos resultados são tomados para calcular uma estimativa mais precisa. Nos problemas de regressão, é feito uma média de todas as saídas previstas pelos classificados individuais, esse processo é chamado de soft voting. Já nos problemas de classificação, a classe com a maioria dos votos é aceita, processo chamado de hard voting ou majority votting.
2.2 Random Forests
Random forest é uma melhoria do bagging com uma diferença na forma em que as árvores de decisão são criadas, descorrelacionando elas. Assim como no bagging, são construídas um número de árvores de decisão em subsets amostrados a partir do bootstrapping. Mas para construir essas árvores, cada vez que uma partição é realizada é considerado apenas um número m aleatório de preditores como candidatos do total de preditores p. Essa partição ou split da árvore é feito apenas com m preditores e a cada split um novo número m de preditores é escolhido e geralmente são usados m≈√p, ou seja, o número de preditores aleatórios considerados para o próxima partição é aproximadamente igual a raíz quadrada do total de preditores.
Ao considerar somente esse pequeno número de preditores como candidatos é eliminado a possibilidade de um preditor muito forte ser selecionado no topo, criando várias árvores em paralelo parecidas e correlacionadas. A média dessas árvores correlacionadas não diminui a variância quanto a média de um conjunto de árvores não correlacionadas. Random forest resolve esse problema a partir dessa limitação no número de preditores em cada partição das árvores de decisão. Usar esse pequeno subset de preditores é útil quando temos um grande número de preditores correlacionados.
2.3 Boosting
Boosting é outra forma de melhorar as predições a partir de árvores de decisão. Assim como bagging, boosting é uma abordagem de propósito geral que pode ser aplicada em vários métodos de aprendizagem estatística para problemas de regressão e classificação.
O processo de boosting é parecido com o de bagging, porém, o treino é feito de forma sequêncial, diferente do bagging que é em paralelo. Cada árvore cresce utilizando informação da árvore anterior. Boosting não utiliza amostragem por bootstrapping, em vez disso as árvores são ajustadas em uma versão modificada do dataset original.
No boosting a árvore de decisão atual utiliza o resídio do modelo anterior como variável a ser prevista, em vez da variável Y. Depois é adicionado uma nova árvore de decisão na função ajustada para obter o resíduo atualizado. Cada árvore pode ser pequena e com apenas alguns nós terminais, determinados pelo parâmetro d no algoritmo. Ao ajustar árvores pequenas aos resíduos, a melhoria na predição é feita de forma lenta nas áreas em que não performa tão bem. O parâmetro de encolhimento da árvore lambda λ retarda o processo, permitindo que mais árvores de formas diferentes ataquem os resíduos. De modo geral, métodos de aprendizagem estatística que “aprendem devagar” performam bem.
Boosting possui três parâmetros de tunning: O número de árvores B, o parâmetro de escolhimento lambda λ e o número de partições d de cada árvore que controla a complexidade do ensemble.
Diferente do bagging, boosting pode overfittar se o parâmetro de número de árvores B for muito grande, mesmo que lentamente. Para evitar isto, podemos utilizar validação cruzada para selecionar o número de árvores B. O fator de encolhimento lambda λ é um valor pequeno e positivo, ele controla a taxa em que o boosting aprende. Os valores tipicamente utilizados são 0.01 ou 0.001, e a escolha correta depende muito do problema. Um número muito pequeno de λ requer um número muito grande de B para atingir uma boa performace.
2.4 Bayesian Additive Regression Trees (BART)
Bayesian additive regression trees ou BART é outro método de ensemble e bayesiano que usa árvores de decisão. Assim como bagging e random forest, cada árvore é construída aleatóriamente, e também cada árvore tenta capturar um sinal ainda não ainda não contabilizado pelo modelo atual, semelhante ao boosting. Ele utiliza uma abordagem bayesiana para ajustar as árvores do ensemble, cada vez que pertubamos aleatóriamente uma árvore para ajustar os resíduos, estamos desenhando uma nova árvore a partir de uma distribuição posterior.
Para utilizar o BART devemos selecioanr o número de árvores K, o número de iterações B e o número de iterações “burn-in” L. As primeiras predições das primeiras iterações geralmente são descartadas já que não provêm um bom resultado, é o chamados período de “burn-in”. Geralmente é utilizado um grande valor para B e K e um valor moderado para L.
A notação fˆb_k(x) representa a predição em x para a k-ésima árvore de regressão usada na b-ésima iteração. Ao final de cada iteração, as árvores K dessa interação serão somadas.
Na primeira iteração do BART, todas as árvores são inicializadas para ter uma única raíz, em que a média da resposta é dividida pelo número total de árvores. Nas iterações subsequêntes o BART atualiza cada uma das árvores K, uma de cada vez. Na b-ésima iteração, para atualizar a k-ésima árvore, é subtraído de cada valor de resposta as previões de todas as árvores, exceto da k-ésima árvore, para que seja obtido o resíduo parcial para a i-ésima observação..
Em vez de ajustar uma árvore nova pra esse resíduo parcial, o BART aleatóriamente escolhe a pertubação para a árvore da iteração anterior de um conjunto de pertubações, priorizando as que melhoram o ajuste para o resíduo parcial. O output do BART é uma coleção de modelos preditivos:
3 Conclusão
Neste artigo busquei trazer a teoria e intuição por trás dos métodos baseados em árvore mas sem a pretenção de esgotar o assunto. Busquei manter no escopo deste artigo explicações simples e intuitivas sem aprofundar os detalhes, por isso recomendo que busquem aprendê-los também. Cada método abordado possuem diversas implementações para o uso em machine learning, desde as mais básicas do scikit-learn as de gradiente boosting. Ao entender a lógica de cada método, sua implementação é mais robusta dado que se sabe o que o modelo está realizando. Mas além disso é importante estudar os parâmetros de cada implementação e seu impacto no modelo para se ter um melhor resultado.
Siga o meu perfil e se inscreva para receber por email os próximos posts relacionados a data science, machine learning e estatística.
Como Citar
Guimarães, Alysson. (Sep 2022). Métodos de Aprendizagem Supervisionada Baseados em Árvore. https://k3ybladewielder.medium.com/. https://k3ybladewielder.medium.com/p-2c0580fe8f10
ou
@miscellaneous{guimaraes2022tree,
title = {Métodos de Aprendizagem Supervisionada Baseados em Árvore},
author = {Guimarães, Alysson},
journal = {https://k3ybladewielder.medium.com},
year = {2022},
month = {Sep},
url = {https://k3ybladewielder.medium.com/p-2c0580fe8f10}
}7 Referencias
G. James et al., An Introduction to Statistical Learning, Springer Texts in Statistics, https://doi.org/10.1007/978-1-0716-1418-1_1
Decision Trees. Scikit-learn, 2022. Disponível em <https://scikit-learn.org/stable/modules/tree.html>, Acesso em 24/08/2022
What is Bagging?. IBM, 2021. Disponível em <https://www.ibm.com/cloud/learn/bagging>, acesso em 29/08/2022.
