Aprendizagem de árvore de decisão

Parte de uma série sobre
Aprendizado de máquina e mineração de dados
Problemas Classificação Agrupamento Regressão Detecção de anomalias AutoML Regras de associação Aprendizagem por reforço Predição estruturada Engenharia de características Aprendizagem de características Aprendizagem online Aprendizagem semissupervisionada Aprendizagem não supervisionada Aprendizagem de ordenação Aprendizado de ontologias Indução de gramática
Aprendizagem supervisionada (classificação • regressão) Árvores de decisão Ensembles Bagging Boosting Floresta aleatória k-NN Regressão linear Naive Bayes Redes neurais artificiais Regressão logística Máquina de vetores de relevância (RVM) Máquina de vetores de suporte (SVM) Otimização de Política Proximal Perceptron
Clustering BIRCH CURE Hierarchical Difuso k-means Maximização de expectativa (EM) DBSCAN OPTICS Mean-shift
Redução de dimensionalidade Análise fatorial CCA ICA LDA NMF PCA PGD t-SNE SDL
Predição estruturada Modelos gráficos Rede bayesiana Campo aleatório condicional Markov oculto
Detecção de anomalias RANSAC k-NN LOF Isolation Forest
Rede neural artificial Autoencoder Computação cognitiva Aprendizagem profunda DeepDream Perceptron multicamadas RNN LSTM GRU ESN Máquina de Boltzmann restrita GAN SOM Rede neural convolucional U-Net Transformer Spiking neural network Memtransistor RAM eletroquímica (ECRAM)
Aprendizagem por reforço Aprendizagem Q SARSA Diferença temporal (TD)
Teoria Equilíbrio entre viés e variância Teoria da aprendizagem computacional Minimização de risco empírico Aprendizagem Occam Aprendizagem PAC Aprendizagem estatística Teoria VC
Locais de aprendizado de máquina NeurIPS ICML ML JMLR ArXiv
Artigos relacionados Glossário de inteligência artificial Lista de conjuntos de dados para pesquisa em aprendizagem de máquina Visão geral da aprendizagem de máquina Função softmax

O aprendizado de árvore de decisão ou indução de árvores de decisão é uma das abordagens de modelagem preditiva usadas em estatística, mineração de dados e aprendizado de máquina. Ele usa uma árvore de decisão (como um modelo preditivo) para ir de observações sobre um item (representado nos ramos) para conclusões sobre o valor alvo do item (representado nas folhas). Os modelos de árvore em que a variável de destino pode assumir um conjunto discreto de valores são chamados de árvores de classificação; nessas estruturas de árvore, as folhas representam rótulos de classe e os ramos representam conjunções de características que levam a esses rótulos de classe. As árvores de decisão em que a variável de destino pode assumir valores contínuos (normalmente números reais) são chamadas de árvores de regressão. As árvores de decisão estão entre os algoritmo de aprendizado de máquina mais populares devido à sua inteligibilidade e simplicidade.

Na análise de decisão, uma árvore de decisão pode ser usada para representar visualmente e explicitamente as decisões e a tomada de decisão. Na mineração de dados, uma árvore de decisão descreve os dados (mas a árvore de classificação resultante pode ser uma entrada para a tomada de decisão). Esta página trata das árvores de decisão na mineração de dados.

Visão geral

Uma árvore que mostra a sobrevivência dos passageiros do Titanic ("sibsp" é o número de cônjuges ou irmãos a bordo). Os valores sob as folhas mostram a probabilidade de sobrevivência e a porcentagem de observações na folha. Resumindo: Suas chances de sobrevivência eram boas se você fosse (i) uma mulher ou (ii) um homem com menos de 9,5 anos e com um número de irmãos estritamente menor do que 3.

A aprendizagem de árvore de decisão é um método comumente usado na mineração de dados. O objetivo é criar um modelo que preveja o valor de uma variável de destino com base em várias variáveis de entrada.

Uma árvore de decisão é uma representação simples para classificar exemplos. Para esta seção, suponha que todas as características de entrada tenham domínios discretos finitos e que haja uma única característica alvo denominada "classificação". Cada elemento do domínio da classificação é denominado classe. Uma árvore de decisão ou uma árvore de classificação é uma árvore na qual cada nó interno (não folha) é rotulado com uma característica de entrada. Os arcos vindos de um nó rotulado com um recurso de entrada são rotulados com cada um dos valores possíveis da característica de destino ou o arco leva a um nó de decisão subordinado em uma característica de entrada diferente. Cada folha da árvore é rotulada com uma classe ou distribuição de probabilidade sobre as classes, o que significa que o conjunto de dados foi classificado pela árvore em uma classe específica ou em uma distribuição de probabilidade específica (que, se a árvore de decisão estiver bem construída, é inclinada para certos subconjuntos de classes).

Uma árvore é construída dividindo o conjunto de origem, que constitui o nó raiz da árvore, em subconjuntos - que constituem os filhos sucessores. A divisão é baseada em um conjunto de regras de divisão que levam em conta características de classificação. Esse processo é repetido em cada subconjunto derivado de uma maneira recursiva chamada de particionamento recursivo. A recursão é concluída quando o subconjunto em um nó tem todos os mesmos valores da variável de destino ou quando a divisão não agrega mais valor às previsões. Este processo de indução de cima para baixo de árvores de decisão (TDIDT) é um exemplo de algoritmo guloso e é de longe a estratégia mais comum para aprender árvores de decisão a partir de dados.^{[carece de fontes]}

Na mineração de dados, as árvores de decisão também podem ser descritas como a combinação de técnicas matemáticas e computacionais para auxiliar na descrição, categorização e generalização de um determinado conjunto de dados.

Os dados vêm em registros da forma:

$({\textbf {x}},Y)=(x_{1},x_{2},x_{3},...,x_{k},Y)$

A variável dependente, $Y$, é a variável de destino que estamos tentando entender, classificar ou generalizar. O vetor ${\textbf {x}}$ é composto pelas características, $x_{1},x_{2},x_{3}$ etc., que são usadas para essa tarefa.

Um exemplo de árvore que estima a probabilidade de cifose após cirurgia espinhal, dada a idade do paciente e a vértebra em que a cirurgia foi iniciada. A mesma árvore é mostrada de três maneiras diferentes. À esquerda, as folhas coloridas mostram a probabilidade de cifose após cirurgia espinhal e a porcentagem de pacientes na folha. No centro, a árvore é vista como um gráfico em perspectiva. À direita, vista aérea do gráfico do centro. A probabilidade de cifose após a cirurgia é maior nas áreas mais escuras. (Nota: O tratamento da cifose avançou consideravelmente desde que este pequeno conjunto de dados foi coletado.^{[carece de fontes]})

Tipos de árvore de decisão

As árvores de decisão usadas na mineração de dados são de dois tipos principais:

• A análise de árvore de classificação é quando o resultado previsto é a classe (discreta) à qual os dados pertencem.
• A análise de árvore de regressão ocorre quando o resultado previsto pode ser considerado um número real (por exemplo, o preço de uma casa ou o tempo de permanência de um paciente em um hospital).

A expressão análise de árvore de classificação e regressão (CART) é um termo abrangente usado para se referir a ambos os procedimentos acima, introduzido pela primeira vez por Breiman et al. em 1984. As árvores usadas para regressão e árvores usadas para classificação têm algumas semelhanças - mas também algumas diferenças, como o procedimento usado para determinar onde dividir.

Algumas técnicas, muitas vezes chamadas de métodos de conjunto, constroem mais de uma árvore de decisão:

• Árvores aumentadas: construindo incrementalmente um conjunto, treinando cada nova instância para enfatizar as instâncias de treinamento previamente modeladas incorretamente. Um exemplo típico é AdaBoostAdaBoost. Elas podem ser usadas para problemas do tipo regressão e do tipo classificação.
• Árvores de decisão agregadas por bootstrap, um método de conjunto antigo, constrói várias árvores de decisão reamostrando repetidamente os dados de treinamento com substituição e votando nas árvores para uma previsão de consenso.
  • Um classificador de floresta aleatória é um tipo específico de agregação por bootstrap.
• Floresta de rotação - na qual cada árvore de decisão é treinada aplicando primeiro a análise de componente principal (PCA) em um subconjunto aleatório das características de entrada.

Um caso especial de árvore de decisão é uma lista de decisão, que é uma árvore de decisão unilateral, de modo que cada nó interno tem exatamente 1 nó folha e exatamente 1 nó interno como filho (exceto para o nó inferior, cujo único filho é um único nó folha). Embora menos expressivas, as listas de decisão são indiscutivelmente mais fáceis de entender do que as árvores de decisão gerais devido à sua dispersão adicional, permitem métodos de aprendizagem não gananciosos e a imposição de restrições monotônicas.

Os algoritmos de árvore de decisão notáveis incluem:

• ID3 (dicotomizador iterativo 3)
• C4.5 (sucessor de ID3)
• CART (árvore de classificação e regressão)
• Detecção de interação automática qui-quadrado (CHAID). Executa divisões de vários níveis ao calcular árvores de classificação.
• MARS: estende as árvores de decisão para lidar melhor com os dados numéricos.
• Árvores de inferência condicional. Abordagem baseada em estatísticas que usa testes não paramétricos como critérios de divisão, corrigidos para testes múltiplos para evitar sobreajuste. Esta abordagem resulta em seleção de preditor imparcial e não requer poda.

ID3 e CART foram inventados de forma independente na mesma época (entre 1970 e 1980),^{[carece de fontes]} mas seguem uma abordagem semelhante para aprender uma árvore de decisão a partir de tuplas de treinamento.

Também foi proposto tirar vantagem de conceitos da teoria de conjuntos fuzzy para a definição de uma versão especial de árvore de decisão, conhecida como Fuzzy Decision Tree (FDT). Neste tipo de classificação difusa, geralmente um vetor de entrada ${\textbf {x}}$ está associado a várias classes, cada uma com um valor de confiança diferente. Conjuntos impulsionados de FDTs também foram recentemente investigados e mostraram desempenhos comparáveis aos de outros classificadores fuzzy muito eficientes.

Métricas

Os algoritmos para construir árvores de decisão geralmente funcionam de cima para baixo, escolhendo em cada etapa uma variável que melhor divide o conjunto de itens. Diferentes algoritmos usam diferentes métricas para medir o "melhor". Geralmente medem a homogeneidade da variável de destino dentro dos subconjuntos. Alguns exemplos são fornecidos a seguir. Essas métricas são aplicadas a cada subconjunto candidato e os valores resultantes são combinados (por exemplo, média) para fornecer uma medida da qualidade da divisão.

Impureza de Gini

 Nota: Não confundir com Coeficiente de Gini.

Usado pelo algoritmo CART (árvore de classificação e regressão) para árvores de classificação, a impureza de Gini (em homenagem ao matemático italiano Corrado Gini) é uma medida de quantas vezes um elemento escolhido aleatoriamente do conjunto seria rotulado incorretamente se fosse rotulado aleatoriamente de acordo com o distribuição de rótulos no subconjunto. A impureza Gini pode ser calculada somando a probabilidade $p_{i}$ de um item com etiqueta $i$ ser escolhido vezes a probabilidade $\sum _{k\neq i}p_{k}=1-p_{i}$ de um erro na categorização desse item. Ele atinge seu mínimo (zero) quando todos os casos no nó caem em uma única categoria de destino.

A impureza de Gini também é uma medida da teoria da informação e corresponde à entropia de Tsallis com coeficiente de deformação $q=2$, que em física está associada à falta de informação em sistemas fora do equilíbrio, não expansíveis, dissipativos e quânticos. Para o limite $q\to 1$ recupera-se a entropia usual de Boltzmann-Gibbs ou Shannon. Nesse sentido, a impureza de Gini é apenas uma variação da medida usual de entropia para árvores de decisão.

Para calcular a impureza Gini para um conjunto de itens com $J$ classes, suponha $i\in \{1,2,...,J\}$, e considere a fração $p_{i}$ de itens rotulados com classe $i$ no conjunto.

$\operatorname {I} _{G}(p)=\sum _{i=1}^{J}\left(p_{i}\sum _{k\neq i}p_{k}\right)=\sum _{i=1}^{J}p_{i}(1-p_{i})=\sum _{i=1}^{J}(p_{i}-{p_{i}}^{2})=\sum _{i=1}^{J}p_{i}-\sum _{i=1}^{J}{p_{i}}^{2}=1-\sum _{i=1}^{J}{p_{i}}^{2}$

Ganho de informação

Usada pelos algoritmos de geração de árvore ID3, C4.5 e C5.0. O ganho de informação é baseado no conceito de entropia e conteúdo da informação na teoria da informação.

A entropia é definida da seguinte forma:

$\mathrm {H} (T)=\operatorname {I} _{E}\left(p_{1},p_{2},...,p_{J}\right)=-\sum _{i=1}^{J}{p_{i}\log _{2}p_{i}}$

em que $p_{1},p_{2},...$ são frações que somam 1 e representam a porcentagem de cada classe presente no nó filho que resulta de uma divisão na árvore.

$$\overbrace {IG(T,a)} ^{\text{Ganho de informação}}=\overbrace {\mathrm {H} (T)} ^{\text{Entropia (pai)}}-\overbrace {\mathrm {H} (T|a)} ^{\text{Soma das entropias (filhos)}}$$

$=-\sum _{i=1}^{J}p_{i}\log _{2}{p_{i}}-\sum _{i=1}^{J}-\Pr(i|a)\log _{2}{\Pr(i|a)}$

Calculando a média sobre os valores possíveis de $A$ ,

$$\overbrace {E_{A}\left(IG(T,a)\right)} ^{\text{Ganho de Informação Esperado}}=\overbrace {I(T;A)} ^{\text{Informação mútua entre T e A}}=\overbrace {\mathrm {H} (T)} ^{\text{Entropia (pai)}}-\overbrace {\mathrm {H} (T|A)} ^{\text{Soma ponderada das entropias (filhos)}}$$

$=-\sum _{i=1}^{J}p_{i}\log _{2}{p_{i}}-\sum _{a}{p(a)\sum _{i=1}^{J}-\Pr(i|a)\log _{2}{\Pr(i|a)}}$

isto é, o ganho de informação esperado é a informação mútua, ou seja, em média, a redução na entropia de T é a informação mútua.

O ganho de informação é usado para decidir em que característica dividir em cada etapa da construção da árvore. Simplicidade é o melhor, então queremos manter nossa árvore pequena. Para fazer isso, em cada etapa devemos escolher a divisão que resulta nos nós filhos mais consistentes. Uma medida comumente usada de consistência é chamada de informação que é medida em bits. Para cada nó da árvore, o valor da informação “representa a quantidade esperada de informação que seria necessária para especificar se uma nova instância deveria ser classificada como sim ou não, visto que o exemplo atingiu aquele nó”.

Considere um exemplo de conjunto de dados com quatro atributos: clima (ensolarado, nublado, chuvoso), temperatura (quente, ameno, frio), umidade (alta, normal) e ventoso (verdadeiro, falso), com uma variável alvo binária (sim ou não), jogar, e 14 pontos de dados. Para construir uma árvore de decisão com base nesses dados, precisamos comparar o ganho de informação de cada uma de quatro árvores, cada uma dividida em uma dos quatro características. A divisão com o maior ganho de informação será considerada a primeira divisão e o processo continuará até que todos os nós filhos tenham dados consistentes ou até que o ganho de informação seja 0.

Para encontrar o ganho de informação da divisão usando windy, devemos primeiro calcular a informação nos dados antes da divisão. Os dados originais continham nove sim e cinco não.

$I_{E}([9,5])=-{\frac {9}{14}}\log _{2}^{}{\frac {9}{14}}-{\frac {5}{14}}\log _{2}{\frac {5}{14}}=0.94$

A divisão usando a característica ventoso resulta em dois nós filhos, um para um valor ventoso verdadeiro e um para um valor ventoso falso. Neste conjunto de dados, existem seis pontos de dados com um valor ventoso verdadeiro, três dos quais têm um valor de jogar (onde o jogar é a variável alvo) sim e três com um valor de jogo de não. Os oito pontos de dados restantes com um valor de ventoso falso contêm dois não e seis sim. A informação do nó ventoso = verdadeiro é calculada usando a equação de entropia acima. Uma vez que há um número igual de sim e não neste nó, temos

$I_{E}([3,3])=-{\frac {3}{6}}\log _{2}^{}{\frac {3}{6}}-{\frac {3}{6}}\log _{2}^{}{\frac {3}{6}}=-{\frac {1}{2}}\log _{2}^{}{\frac {1}{2}}-{\frac {1}{2}}\log _{2}^{}{\frac {1}{2}}=1$

Para o nó em que ventoso = falso, havia oito pontos de dados, seis sim e dois não. Assim, tem-se

$I_{E}([6,2])=-{\frac {6}{8}}\log _{2}^{}{\frac {6}{8}}-{\frac {2}{8}}\log _{2}^{}{\frac {2}{8}}=-{\frac {3}{4}}\log _{2}^{}{\frac {3}{4}}-{\frac {1}{4}}\log _{2}^{}{\frac {1}{4}}=0.81$

Para encontrar a informação da divisão, pega-se a média ponderada desses dois números com base em quantas observações caíram em cada nó.

$I_{E}([3,3],[6,2])=I_{E}({\text{ventoso ou não}})={\frac {6}{14}}\cdot 1+{\frac {8}{14}}\cdot 0.81=0.89$

Agora pode-se calcular o ganho de informação obtido pela divisão na característica ventoso.

$IG({\text{ventoso}})=I_{E}([9,5])-I_{E}([3,3],[6,2])=0.94-0.89=0.05$

Para construir a árvore, o ganho de informação de cada possível primeira divisão precisaria ser calculado. A melhor primeira divisão é aquela que fornece o maior ganho de informação. Este processo é repetido para cada nó impuro até que a árvore seja concluída. Este exemplo é adaptado do exemplo que aparece em Witten et al.

Redução da variância

Introduzida no CART, a redução da variância é frequentemente empregada em casos em que a variável alvo é contínua (árvore de regressão), o que significa que o uso de muitas outras métricas exigiria primeiro uma discretização antes de ser aplicada. A redução da variância de um nó N é definida como a redução total da variância da variável de destino Y devido à divisão neste nó:

$I_{V}(N)={\frac {1}{|S|^{2}}}\sum _{i\in S}\sum _{j\in S}{\frac {1}{2}}(y_{i}-y_{j})^{2}-\left({\frac {|S_{t}|^{2}}{|S|^{2}}}{\frac {1}{|S_{t}|^{2}}}\sum _{i\in S_{t}}\sum _{j\in S_{t}}{\frac {1}{2}}(y_{i}-y_{j})^{2}+{\frac {|S_{f}|^{2}}{|S|^{2}}}{\frac {1}{|S_{f}|^{2}}}\sum _{i\in S_{f}}\sum _{j\in S_{f}}{\frac {1}{2}}(y_{i}-y_{j})^{2}\right)$

em que $S$, $S_{t}$, e $S_{f}$ são o conjunto de índices da amostra antes da divisão, o conjunto de índices da amostra para os quais o teste da divisão é verdadeiro e o conjunto de índices da amostra para os quais o teste da divisão é falso, respectivamente. Cada uma das somas acima são de fato estimativas de variância, porém, escritas de uma forma que não faz referência à média diretamente.

Medida de "bondade"

Usada pela CART em 1984, a medida de "bondade" é uma função que busca otimizar o equilíbrio da capacidade de uma candidata a divisão de criar filhos puros com sua capacidade de criar filhos de tamanhos iguais. Este processo é repetido para cada nó impuro até que a árvore seja concluída. A função $\phi (s|t)$, em que $s$ é uma candidata a divisão no nó $t$, é definida como abaixo

$\phi (s|t)=2P_{L}P_{R}\sum _{j=1}^{\text{Número de classes}}|P(j|t_{L})-P(j|t_{R})|$

em que $t_{L}$ e $t_{R}$ são os filhos esquerdo e direito do nó $t$ usando a divisão $s$, respectivamente; $P_{L}$ e $P_{R}$ são as proporções de registros de $t$ em $t_{L}$ e $t_{R}$, respectivamente; e $P(j|t_{L})$ e $P(j|t_{R})$ são as proporções de registros da classe $j$ em $t_{L}$ e $t_{R}$, respectivamente.

Considere um exemplo de conjunto de dados com três atributos: poupança (baixo, médio, alto), ativos (baixo, médio, alto), renda (valor numérico) e um risco de crédito de variável alvo binário (bom, ruim) e 8 pontos de dados. Os dados completos são apresentados na tabela abaixo. Para iniciar uma árvore de decisão, vamos calcular o valor máximo de $\phi (s|t)$ usando cada característica para descobrir qual irá dividir o nó raiz. Este processo continuará até que todos os filhos sejam puros ou todos os valores $\phi (s|t)$ estejam abaixo de um limite definido.

Cliente	Poupança	Ativos	Renda ($ 1000s)	Risco de crédito
1	Médio	Alto	75	Bom
2	Baixo	Baixo	50	Ruim
3	Alto	Médio	25	Ruim
4	Médio	Médio	50	Bom
5	Baixo	Médio	100	Bom
6	Alto	Alto	25	Bom
7	Baixo	Baixo	25	Ruim
8	Médio	Médio	75	Bom

Para encontrar $\phi (s|t)$ da característica economia, é preciso observar a quantidade de cada valor. Os dados originais continham três baixos, três médios e dois altos. Dos baixos, um tinha um bom risco de crédito, enquanto que entre os médios e altos, 4 tinham um bom risco de crédito. Suponha uma candidata a divisão $s$ de forma que os registros com uma poupança baixa sejam colocados no filho da esquerda e todos os outros registros sejam colocados no filho da direita.

$\phi (s|root)=2{\frac {3}{8}}*{\frac {5}{8}}*(|({\frac {1}{3}}-{\frac {4}{5}})|+|({\frac {2}{3}}-{\frac {1}{5}})|)=0.44$

Para construir a árvore, é preciso calcular a "bondade" de todas as divisões candidatas para o nó raiz. A candidata com o valor máximo dividirá o nó raiz e o processo continuará para cada nó impuro até que a árvore seja concluída.

Em comparação com outras métricas, como ganho de informação, a medida de "bondade" tentará criar uma árvore mais equilibrada, levando a um tempo de decisão mais consistente. No entanto, ele sacrifica alguma prioridade para a criação de filhos puros, o que pode levar a divisões adicionais que não estão presentes com outras métricas.

Usos

Vantagens

Entre outros métodos de mineração de dados, as árvores de decisão têm várias vantagens:

• Simples de entender e interpretar. As pessoas são capazes de entender os modelos de árvore de decisão após uma breve explicação. As árvores também podem ser exibidas graficamente de uma maneira que não especialistas podem interpretar com facilidade.
• Capaz de lidar com dados numéricos e categóricos. Outras técnicas geralmente são especializadas na análise de conjuntos de dados que possuem apenas um tipo de variável. (Por exemplo, as regras de relação podem ser usadas apenas com variáveis nominais, enquanto as redes neurais podem ser usadas apenas com variáveis numéricas ou categóricas convertidas para valores 0-1.) As árvores de decisão iniciais eram capazes de lidar apenas com variáveis categóricas, mas as versões mais recentes, como C4.5, não têm essa limitação.
• Requer pouca preparação de dados. Outras técnicas geralmente requerem normalização de dados. Uma vez que as árvores podem lidar com preditores qualitativos, não há necessidade de criar variáveis fictícias.
• Usa um modelo de caixa branca ou caixa-aberta. Se uma dada situação é observável em um modelo, a justificativa para a condição é facilmente explicada por lógica booleana. Por outro lado, em um modelo de caixa preta, a justificativa para os resultados é normalmente difícil de entender, por exemplo, com uma rede neural artificial.
• Possível validar um modelo por meio de testes estatísticos. Isso torna possível contabilizar a confiabilidade do modelo.
• Abordagem não paramétrica que não faz suposições sobre os dados de treinamento ou resíduos de predição; por exemplo, nenhuma suposição de distribuição, independência ou variância constante
• Apresenta bom desempenho com grandes conjuntos de dados. Grandes quantidades de dados podem ser analisados usando recursos de computação padrão em um tempo razoável.
• Espelha a tomada de decisão humana mais de perto do que outras abordagens. Isso pode ser útil ao modelar decisões/comportamento humano.
• Robusto contra colinearidade, especialmente impulsionando
• Seleção de características integrada. Características irrelevantes adicionais serão menos usadas então podem ser removidas em execuções subsequentes. A hierarquia de atributos em uma árvore de decisão reflete a importância dos atributos. Isso significa que as característica na parte superior são as mais informativas.
• As árvores de decisão podem aproximar de qualquer função booleana, por exemplo XOR.

Limitações

• As árvores podem ser muito não robustas. Uma pequena mudança nos dados de treinamento pode resultar em uma grande mudança na árvore e, consequentemente, nas previsões finais.
• O problema de aprender uma árvore de decisão ótima é conhecido como NP-completo sob vários aspectos da otimidade e até mesmo para conceitos simples. Consequentemente, algoritmos de aprendizagem de árvore de decisão práticos são baseados em heurísticas, como o algoritmo guloso, no qual decisões ótimas localmente são feitas em cada nó. Esses algoritmos não podem garantir o retorno da árvore de decisão globalmente ótima. Para reduzir o efeito guloso da otimização local, foram propostos alguns métodos, como a árvore de distâncias duplas de informações (DID).
• Os aprendizes da árvore de decisão podem criar árvores excessivamente complexas que não generalizam bem a partir dos dados de treinamento. (Isso é conhecido como sobreajuste.) Mecanismos como a poda são necessários para evitar esse problema (com exceção de alguns algoritmos, como a abordagem de inferência condicional, que não requer a poda).
• A profundidade média da árvore, que é definida pelo número de nós ou testes até a classificação, não é garantida como mínima ou pequena sob vários critérios de divisão.
• Para dados que incluem variáveis categóricas com diferentes números de níveis, o ganho de informação nas árvores de decisão é tendencioso em favor de atributos com mais níveis. No entanto, a questão da seleção de preditor com viés é evitada pela abordagem de inferência condicional, uma abordagem de dois estágios ou uma seleção adaptativa de características do tipo "deixar um de fora".

Implementações

Muitos pacotes de software de mineração de dados fornecem implementações de um ou mais algoritmos de árvore de decisão.

Exemplos incluem:

• Salford Systems CART (que licenciou o código proprietário dos autores originais de CART),
• IBM SPSS Modeler,
• RapidMiner,
• SAS Enterprise Miner,
• Matlab,
• R (um ambiente de software de código aberto para computação estatística, que inclui várias implementações CART, como as dos pacotes rpart, party e randomForest),
• Weka (um pacote de mineração de dados gratuito e de código aberto, contém muitos algoritmos de árvore de decisão),
• Orange,
• KNIME,
• Microsoft SQL Server, e
• Scikit-learn (uma biblioteca de aprendizado de máquina gratuita e de código aberto para a linguagem de programação Python).

Extensões

Grafos de decisão

Em uma árvore de decisão, todos os caminhos do nó raiz ao nó folha prosseguem por meio de conjunções, ou E. Em um grafo de decisão, é possível usar disjunções (OUs) para unir dois ou mais caminhos usando comprimento mínimo de mensagem (MML). Os grafos de decisão foram estendidos ainda mais para permitir que novos atributos não declarados anteriormente sejam aprendidos dinamicamente e usados em diferentes locais do grafo. O esquema de codificação mais geral resulta em melhor precisão preditiva e pontuação probabilística de perda de log.^{[carece de fontes]} Em geral, os grafos de decisão inferem modelos com menos folhas do que as árvores de decisão.

Métodos de busca alternativos

Algoritmos evolutivos têm sido usados para evitar decisões ótimas locais e pesquisar o espaço das árvores de decisão com pouco viés a priori.

Também é possível amostrar uma árvore usando MCMC.

A árvore pode ser pesquisada de baixo para cima. Ou várias árvores podem ser construídas paralelamente para reduzir o número esperado de testes até a classificação.

Ver também

• Poda de árvores de decisão
• Algoritmo C4.5
• AdaBoost

Leitura complementar

• James, Gareth; Witten, Daniela; Hastie, Trevor; Tibshirani, Robert (2017). «Tree-Based Methods». An Introduction to Statistical Learning: with Applications in R. New York: Springer. pp. 303–336. ISBN 978-1-4614-7137-0 

Ligações externas

• Aprendizagem evolutiva de árvores de decisão em C++
• Uma explicação muito detalhada do ganho de informação como critério de divisão