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 (representadas nas bifurcações) para conclusões sobre o valor alvo do item (representadas 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 as bifurcações 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 miniaturadaimagem| 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.

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:

A variável dependente, , é a variável de destino que estamos tentando entender, classificar ou generalizar. O vetor é composto pelas características, etc., que são usadas para essa tarefa. alt=Three different representations of a regression tree of kyphosis data|miniaturadaimagem|800x800px| 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.)

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.Friedman, J. H. (1999). Stochastic gradient boosting. Stanford University.Hastie, T., Tibshirani, R., Friedman, J. H. (2001). The elements of statistical learning : Data mining, inference, and prediction. New York: Springer Verlag. Á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), 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 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

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 de um item com etiqueta ser escolhido vezes a probabilidade 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 , 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 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 classes, suponha , e considere a fração de itens rotulados com classe no conjunto.

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:

em que 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.

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

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ó”.