Poda da árvore de decisão - Decision tree pruning

Antes e depois da poda

A poda é uma técnica de compressão de dados em aprendizado de máquina e algoritmos de pesquisa que reduz o tamanho das árvores de decisão , removendo seções da árvore que não são críticas e redundantes para classificar instâncias. A poda reduz a complexidade do classificador final e, portanto, melhora a precisão preditiva pela redução do sobreajuste .

Uma das questões que surge em um algoritmo de árvore de decisão é o tamanho ideal da árvore final. Uma árvore muito grande corre o risco de sobrecarregar os dados de treinamento e de generalizar insuficientemente para novas amostras. Uma pequena árvore pode não capturar informações estruturais importantes sobre o espaço de amostra. No entanto, é difícil dizer quando um algoritmo de árvore deve parar porque é impossível dizer se a adição de um único nó extra diminuirá drasticamente o erro. Esse problema é conhecido como efeito horizonte . Uma estratégia comum é fazer a árvore crescer até que cada nó contenha um pequeno número de instâncias e, em seguida, usar a poda para remover os nós que não fornecem informações adicionais.

A poda deve reduzir o tamanho de uma árvore de aprendizagem sem reduzir a precisão preditiva medida por um conjunto de validação cruzada . Existem muitas técnicas de poda de árvores que diferem na medida usada para otimizar o desempenho.

Técnicas

Os processos de poda podem ser divididos em dois tipos (pré e pós-poda).

Os procedimentos de pré-poda evitam uma indução completa do conjunto de treinamento, substituindo um critério stop () no algoritmo de indução (por exemplo, profundidade máxima da árvore ou ganho de informação (Attr)> minGain). Os métodos de pré-poda são considerados mais eficientes porque não induzem um conjunto inteiro, mas sim as árvores permanecem pequenas desde o início. Os métodos de pré-poda compartilham um problema comum, o efeito horizonte. Isso deve ser entendido como o término prematuro indesejado da indução pelo critério stop ().

A pós-poda (ou apenas a poda) é a maneira mais comum de simplificar as árvores. Aqui, nós e subárvores são substituídos por folhas para reduzir a complexidade. A poda pode não apenas reduzir significativamente o tamanho, mas também melhorar a precisão da classificação de objetos invisíveis. Pode ser que a precisão da atribuição no conjunto de trens se deteriore, mas a precisão das propriedades de classificação da árvore aumenta em geral.

Os procedimentos são diferenciados com base em sua abordagem na árvore (de cima para baixo ou de baixo para cima).

Poda de baixo para cima

Esses procedimentos começam no último nó da árvore (o ponto mais baixo). Seguindo recursivamente para cima, eles determinam a relevância de cada nó individual. Se a relevância para a classificação não for fornecida, o nó será eliminado ou substituído por uma folha. A vantagem é que nenhuma subárvore relevante pode ser perdida com este método. Esses métodos incluem poda de erro reduzido (REP), poda de complexidade de custo mínimo (MCCP) ou poda de erro mínimo (MEP).

Poda de cima para baixo

Em contraste com o método ascendente, este método começa na raiz da árvore. Seguindo a estrutura abaixo, é realizada uma verificação de relevância que decide se um nó é relevante para a classificação de todos os n itens ou não. Ao podar a árvore em um nó interno, pode acontecer que uma subárvore inteira (independentemente de sua relevância) seja eliminada. Um desses representantes é a poda de erro pessimista (PEP), que traz resultados bastante bons com itens não vistos.

Algoritmos de poda

Remoção de erros reduzida

Uma das formas mais simples de poda é a poda com erro reduzido. Começando nas folhas, cada nó é substituído por sua classe mais popular. Se a precisão da previsão não for afetada, a alteração será mantida. Embora um tanto ingênua, a remoção de erros reduzida tem a vantagem de simplicidade e velocidade .

Remoção de complexidade de custo

A poda de complexidade de custo gera uma série de árvores onde é a árvore inicial e é apenas a raiz. Na etapa , a árvore é criada removendo uma subárvore da árvore e substituindo-a por um nó folha com valor escolhido como no algoritmo de construção da árvore. A subárvore removida é escolhida da seguinte maneira: ${\ displaystyle T_ {0} \ dots T_ {m}}$ ${\ displaystyle T_ {0}}$ ${\ displaystyle T_ {m}}$ ${\ displaystyle i}$ ${\ displaystyle i-1}$

Defina a taxa de erro da árvore sobre o conjunto de dados como . ${\ displaystyle T}$ ${\ displaystyle S}$ ${\ displaystyle \ operatorname {err} (T, S)}$
A subárvore que minimiza é escolhida para remoção. ${\ displaystyle {\ frac {\ operatorname {err} (\ operatorname {prune} (T, t), S) - \ operatorname {err} (T, S)} {\ left \ vert \ operatorname {folhas} (T ) \ right \ vert - \ left \ vert \ operatorname {folhas} (\ operatorname {ameixa} (T, t)) \ right \ vert}}}$

A função define a árvore obtida pela poda das subárvores da árvore . Uma vez que a série de árvores foi criada, a melhor árvore é escolhida pela precisão generalizada medida por um conjunto de treinamento ou validação cruzada. ${\ displaystyle \ operatorname {ameixa} (T, t)}$ ${\ displaystyle t}$ ${\ displaystyle T}$

Veja também

Referências

Pearl, Judea (1984). Heurísticas . Addison-Wesley.
Mansour, Y. (1997). "Poda de árvore de decisão pessimista com base no tamanho da árvore" . Proc. 14ª Conferência Internacional sobre Aprendizado de Máquina . pp. 195–201.
Breslow, LA; Aha, DW (1997). "Simplificando Árvores de Decisão: Um Levantamento". A Revisão da Engenharia do Conhecimento . 12 (1): 1-47. doi : 10.1017 / S0269888997000015 .
Quinlan, JR (1986). "Indução de Árvores de Decisão" . Aprendizado de máquina . Kluwer Academic Publishers. 1 : 81–106. doi : 10.1007 / BF00116251 .

Languages

In other projects