Aprendizagem da árvore de decisão - Decision tree learning

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 recursos 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 algoritmos 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 lida com árvores de decisão em mineração de dados .

Em geral

Uma árvore que mostra a sobrevivência dos passageiros no Titanic ("sibsp" é o número de cônjuges ou irmãos a bordo). As figuras 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 estritamente com menos de 3 irmãos.

O aprendizado da árvore de decisão é um método comumente usado em 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 todos os recursos de entrada tenham domínios discretos finitos e que haja um único recurso de destino denominado "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 um recurso de entrada. Os arcos vindos de um nó rotulado com um recurso de entrada são rotulados com cada um dos valores possíveis do recurso de destino ou o arco leva a um nó de decisão subordinado em um recurso 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 , constituindo o nó raiz da árvore, em subconjuntos - que constituem os filhos sucessores. A divisão é baseada em um conjunto de regras de divisão com base em recursos de classificação. Este processo é repetido em cada subconjunto derivado de uma maneira recursiva chamada 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 ganancioso 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 do formulário:

A variável dependente,, é a variável alvo que estamos tentando entender, classificar ou generalizar. O vetor é composto de recursos, etc., que são usados ​​para essa tarefa.

Três representações diferentes de uma árvore de regressão de dados de cifose
Um exemplo de árvore que estima a probabilidade de cifose após a cirurgia da coluna, 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. Meio A árvore como um gráfico em perspectiva. Vista aérea direita da parcela do meio. A probabilidade de cifose após a cirurgia é maior nas áreas mais escuras. (Nota: O tratamento da cifose avançou consideravelmente desde que este conjunto bastante pequeno 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 da árvore de classificação é quando o resultado previsto é a classe (discreta) à qual os dados pertencem.
  • A análise da á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).

O termo análise de árvore de classificação e regressão (CART) é um termo abrangente usado para se referir a qualquer um dos procedimentos acima, introduzido pela primeira vez por Breiman et al. em 1984. Á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 impulsionadas Construindo incrementalmente um conjunto treinando cada nova instância para enfatizar as instâncias de treinamento previamente modeladas incorretamente. Um exemplo típico é AdaBoost . Eles podem ser usados ​​para problemas do tipo regressão e do tipo classificação.
  • Árvores de decisão agregadas (ou ensacadas) de bootstrap, um método de conjunto inicial, constrói várias árvores de decisão ao reamostrar repetidamente os dados de treinamento com substituição e votar nas árvores para uma previsão de consenso. agregação de 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 dos recursos 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ó mais 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, permitindo que métodos de aprendizagem não gananciosos e restrições monotônicas sejam impostas.

    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 independentemente 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 alavancar 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). Nesse 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 uma variável em cada etapa que melhor divide o conjunto de itens. Algoritmos diferentes usam métricas diferentes para medir o "melhor". Geralmente medem a homogeneidade da variável de destino dentro dos subconjuntos. Alguns exemplos são dados 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 de Gini pode ser calculada somando a probabilidade de um item com rótulo ser escolhido vezes a probabilidade de um erro ao categorizar esse 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 teórica 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 desequilibrados, não extensos, 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 de Gini para um conjunto de itens com classes, suponha e deixe ser a fração de itens rotulados com classe no conjunto.

    Ganho de informação

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

    Entropia é definida como abaixo

    onde estão as 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 dos valores possíveis de ,

    Ou seja, 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 qual recurso dividir em cada etapa da construção da árvore. Simplicidade é o melhor, por isso 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 de consistência comumente usada é 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 deve ser classificada como sim ou não, visto que o exemplo atingiu aquele nó”.

    Considere um exemplo de conjunto de dados com quatro atributos: perspectiva (ensolarado, nublado, chuvoso), temperatura (quente, ameno, frio), umidade (alta, normal) e ventoso (verdadeiro, falso), com um binário (sim ou não) variável de destino, jogo 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 das quatro árvores, cada uma dividida em um dos quatro recursos. 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 as informações nos dados antes da divisão. Os dados originais continham nove sim e cinco não.

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

    Para o nó em que windy = false, havia oito pontos de dados, seis sim e dois não. Assim nós temos

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

    Agora podemos calcular o ganho de informação obtido pela divisão no recurso ventoso .

    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 de variância

    Introduzida no CART, a redução de variância é frequentemente empregada em casos em que a variável de destino é contínua (árvore de regressão), o que significa que o uso de muitas outras métricas exigiria primeiro a 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ó:

    onde , e são o conjunto de índices de amostra pré-divididos, conjunto de índices de amostra para os quais o teste de divisão é verdadeiro e o conjunto de índices de amostra para os quais o teste de divisão é falso, respectivamente. Cada uma das somas acima são de fato estimativas de variância , porém, escritas de uma forma sem referir-se diretamente à média.

    Medida de "bondade"

    Usada pela CART em 1984, a medida de "bondade" é uma função que busca otimizar o equilíbrio entre a capacidade de uma divisão candidata de criar filhos puros com sua capacidade de criar filhos do mesmo tamanho. Este processo é repetido para cada nó impuro até que a árvore seja concluída. A função , onde é uma divisão candidata no nó , é definida como abaixo

    onde e são os filhos esquerdo e direito do nó usando divisão , respectivamente; e são as proporções dos registros em e , respectivamente; e e são as proporções dos registros de classe em e , respectivamente.

    Considere um exemplo de conjunto de dados com três atributos: economia (baixo, médio, alto), ativos (baixo, médio, alto), renda (valor numérico) e um risco de crédito de variável de destino 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, calcularemos o valor máximo de uso de cada recurso para encontrar qual dividirá o nó raiz. Este processo continuará até que todos os filhos sejam puros ou todos os valores estejam abaixo de um limite definido.

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

    Para encontrar a economia de recursos , precisamos anotar a quantidade de cada valor. Os dados originais continham três graves, três médios e dois agudos. Das baixas, um tinha um bom risco de crédito, enquanto fora das médias e altas, 4 tinha um bom risco de crédito . Suponha que um candidato seja dividido de forma que os registros com uma economia baixa sejam colocados no filho da esquerda e todos os outros registros sejam colocados no filho da direita.

    Para construir a árvore, a "bondade" de todas as divisões candidatas para o nó raiz precisa ser calculada. O candidato 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 fácil de interpretar por não especialistas.
    • 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.) Árvores de decisão iniciais eram capazes apenas de lidar com variáveis ​​categóricas, mas versões mais recentes, como como C4.5, não tem essa limitação.
    • Requer pouca preparação de dados. Outras técnicas geralmente requerem normalização de dados. Como 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 explicação para a condição é facilmente explicada pela lógica booleana. Por outro lado, em um modelo de caixa preta , a explicação 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
    • Na seleção de recursos integrados . O recurso irrelevante adicional será menos usado para que possa ser removido em execuções subsequentes. A hierarquia de atributos em uma árvore de decisão reflete a importância dos atributos. Isso significa que os recursos na parte superior são os mais informativos.
    • As árvores de decisão podem se 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 por ser NP-completo sob vários aspectos de otimização 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, em que 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, alguns métodos, como a árvore de distâncias duplas de informações (DID), foram propostos.
    • Os alunos da árvore de decisão podem criar árvores excessivamente complexas que não generalizam bem a partir dos dados de treinamento. (Isso é conhecido como overfitting .) Mecanismos como 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 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 tendenciosa é evitada pela abordagem de Inferência Condicional, uma abordagem de dois estágios ou seleção de recurso de deixar um de fora adaptativo.

    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

    Extensões

    Gráficos de decisão

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

    Métodos de pesquisa alternativos

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

    Também é possível que uma árvore seja amostrada 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.

    Veja também

    Referências

    Leitura adicional

    links externos