Aprendizagem de árvore de decisão
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 para ir de observações sobre um item para conclusões sobre o valor alvo do item. 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 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.
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).
As árvores de decisão usadas na mineração de dados são de dois tipos principais: 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: 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 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 p i {\displaystyle p_{i}} de um item com etiqueta i {\displaystyle i} ser escolhido vezes a probabilidade ∑ k ≠ i p k = 1 − p i {\displaystyle \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.
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 p 1 , p 2 , . . . {\displaystyle 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. = − ∑ i = 1 J p i log 2 p i − ∑ i = 1 J − Pr ( i | a ) log 2 Pr ( i | a ) {\displaystyle =-\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 {\displaystyle A} , = − ∑ i = 1 J p i log 2 p i − ∑ a p ( a ) ∑ i = 1 J − Pr ( i | a ) log 2 Pr ( i | a ) {\displaystyle =-\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)}}}
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ó: em que S {\displaystyle S} , S t {\displaystyle S_{t}} , e S f {\displaystyle 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 ϕ ( s | t ) {\displaystyle \phi (s|t)} , em que s {\displaystyle s} é uma candidata a divisão no nó t {\displaystyle t} , é definida como abaixo em que t L {\displaystyle t_{L}} e t R {\displaystyle t_{R}} são os filhos esquerdo e direito do nó t {\displaystyle t} usando a divisão s {\displaystyle s} , respectivamente; P L {\displaystyle P_{L}} e P R {\displaystyle P_{R}} são as proporções de registros de t {\displaystyle t} em t L {\displaystyle t_{L}} e t R {\displaystyle t_{R}} , respectivamente; e P ( j | t L ) {\displaystyle P(j|t_{L})} e P ( j | t R ) {\displaystyle P(j|t_{R})} são as proporções de registros da classe j {\displaystyle j} em t L {\displaystyle t_{L}} e t R {\displaystyle t_{R}} , respectivamente.
Vantagens
Entre outros métodos de mineração de dados, as árvores de decisão têm várias vantagens:
Implementações
Muitos pacotes de software de mineração de dados fornecem implementações de um ou mais algoritmos de árvore de decisão.
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.
