Exemplos de algoritmos de árvore de decisão em mineração de dados

decision tree algorithm examples data mining

Este tutorial detalhado explica tudo sobre o algoritmo de árvore de decisão em mineração de dados. Você aprenderá sobre os exemplos de árvore de decisão, algoritmo e classificação:

Nós demos uma olhada em alguns Exemplos de mineração de dados em nosso tutorial anterior em Série gratuita de treinamento de mineração de dados .

A mineração de árvore de decisão é um tipo de técnica de mineração de dados usada para construir modelos de classificação. Ele constrói modelos de classificação na forma de uma estrutura semelhante a uma árvore, assim como seu nome. Este tipo de mineração pertence ao aprendizado supervisionado em classe.

Na aprendizagem supervisionada, o resultado alvo já é conhecido. As árvores de decisão podem ser usadas para dados categóricos e numéricos. Os dados categóricos representam sexo, estado civil, etc., enquanto os dados numéricos representam idade, temperatura, etc.

perguntas e respostas da entrevista do engenheiro de rede na cisco

Um exemplo de árvore de decisão com o conjunto de dados é mostrado abaixo.

(imagem fonte )

O que você aprenderá:

• Qual é a utilidade de uma árvore de decisão?
• Análise de Classificação
• Análise de regressão
• Como funciona uma árvore de decisão?
• Algoritmo de indução de árvore de decisão
• Indução de árvore de decisão
• CARRINHO
• Indução de árvore de decisão para aprendizado de máquina: ID3
• O que é divisão binária gananciosa recursiva?
• Como selecionar atributos para criar uma árvore?
  • # 1) Ganho de informações
  • # 2) Taxa de ganho
  • # 3) Índice de Gini
• Overfitting em árvores de decisão
• O que é poda de árvore?
• O que é modelagem preditiva?
• Vantagens da classificação da árvore de decisão
• Desvantagens da classificação da árvore de decisão
• Conclusão
• Leitura recomendada

Qual é a utilidade de uma árvore de decisão?

A árvore de decisão é usada para construir modelos de classificação e regressão. É usado para criar modelos de dados que irão prever rótulos de classe ou valores para o processo de tomada de decisão. Os modelos são construídos a partir do conjunto de dados de treinamento alimentado ao sistema (aprendizado supervisionado).

Usando uma árvore de decisão, podemos visualizar as decisões que facilitam o entendimento e, portanto, é uma técnica de mineração de dados popular.

Análise de Classificação

A classificação de dados é uma forma de análise que constrói um modelo que descreve importantes variáveis ​​de classe.Por exemplo, um modelo criado para categorizar os pedidos de empréstimos bancários como seguros ou arriscados. Métodos de classificação são usados ​​em aprendizado de máquina e reconhecimento de padrões.

A aplicação da classificação inclui detecção de fraude, diagnóstico médico, marketing direcionado, etc. A saída do problema de classificação é considerada como “Modo” de todos os valores observados do nó terminal.

Um processo de duas etapas é seguido para construir um modelo de classificação.

1. Na primeira etapa, ou seja, aprendizagem: Um modelo de classificação com base nos dados de treinamento é construído.
2. Na segunda etapa, ou seja, classificação, a precisão do modelo é verificada e, em seguida, o modelo é usado para classificar novos dados. Os rótulos de classe apresentados aqui estão na forma de valores discretos, como “sim” ou “não”, “seguro” ou “arriscado”.

A abordagem geral para construir modelos de classificação é fornecida abaixo:

(imagem fonte )

Análise de regressão

A análise de regressão é usada para a previsão de atributos numéricos.

Os atributos numéricos também são chamados de valores contínuos. Um modelo construído para prever os valores contínuos em vez de rótulos de classe é chamado de modelo de regressão. A saída da análise de regressão é a “Média” de todos os valores observados do nó.

Como funciona uma árvore de decisão?

Uma árvore de decisão é um algoritmo de aprendizado supervisionado que funciona para variáveis ​​discretas e contínuas. Ele divide o conjunto de dados em subconjuntos com base no atributo mais significativo do conjunto de dados. Como a árvore de decisão identifica esse atributo e como essa divisão é feita é decidida pelos algoritmos.

O preditor mais significativo é designado como o nó raiz, a divisão é feita para formar subnós chamados nós de decisão e os nós que não se dividem mais são nós terminais ou nós folha.

Na árvore de decisão, o conjunto de dados é dividido em regiões homogêneas e não sobrepostas. Ele segue uma abordagem de cima para baixo, pois a região do topo apresenta todas as observações em um único lugar que se divide em dois ou mais ramos que se dividem posteriormente. Esta abordagem também é chamada de abordagem gananciosa pois considera apenas o nó atual entre os trabalhados sem focar nos nós futuros.

Os algoritmos da árvore de decisão continuarão em execução até que um critério de parada, como o número mínimo de observações, etc. seja alcançado.

Depois que uma árvore de decisão é construída, muitos nós podem representar dados discrepantes ou com ruído. O método de poda de árvore é aplicado para remover dados indesejados. Isso, por sua vez, melhora a precisão do modelo de classificação.

Para encontrar a precisão do modelo, um conjunto de teste consistindo em tuplas de teste e rótulos de classe é usado. As porcentagens das tuplas do conjunto de teste são classificadas corretamente pelo modelo para identificar a precisão do modelo. Se o modelo for considerado preciso, ele será usado para classificar as tuplas de dados para as quais os rótulos de classe não são conhecidos.

Alguns dos algoritmos da árvore de decisão incluem Algoritmo de Hunt, ID3, CD4.5 e CART.

Exemplo de criação de uma árvore de decisão

(O exemplo é retirado de Conceitos de mineração de dados: Han e Kimber)

# 1) Etapa de aprendizagem: Os dados de treinamento são alimentados no sistema para serem analisados ​​por um algoritmo de classificação. Neste exemplo, o rótulo da classe é o atributo, ou seja, “decisão de empréstimo”. O modelo construído a partir desses dados de treinamento é representado na forma de regras de decisão.

# 2) Classificação: O conjunto de dados de teste é alimentado ao modelo para verificar a precisão da regra de classificação. Se o modelo fornecer resultados aceitáveis, ele será aplicado a um novo conjunto de dados com variáveis ​​de classe desconhecidas.

Algoritmo de indução de árvore de decisão

Indução de árvore de decisão

A indução da árvore de decisão é o método de aprendizado das árvores de decisão do conjunto de treinamento. O conjunto de treinamento consiste em atributos e rótulos de classe. As aplicações da indução da árvore de decisão incluem astronomia, análise financeira, diagnóstico médico, manufatura e produção.

Uma árvore de decisão é uma estrutura semelhante a uma árvore de fluxograma feita a partir de tuplas do conjunto de treinamento. O conjunto de dados é dividido em subconjuntos menores e está presente na forma de nós de uma árvore. A estrutura em árvore possui um nó raiz, nós internos ou nós de decisão, nó folha e ramos.

O nó raiz é o nó superior. Ele representa o melhor atributo selecionado para classificação. Os nós internos dos nós de decisão representam um teste de um atributo do nó folha do conjunto de dados ou nó terminal que representa a classificação ou rótulo de decisão. Os ramos mostram o resultado do teste realizado.

Algumas árvores de decisão têm apenas nós binários , isso significa exatamente dois ramos de um nó, enquanto algumas árvores de decisão são não binárias.

A imagem abaixo mostra a árvore de decisão do conjunto de dados do Titanic para prever se o passageiro sobreviverá ou não.

(imagem fonte )

CARRINHO

O modelo CART, ou seja, Modelos de Classificação e Regressão, é um algoritmo de árvore de decisão para construir modelos. O modelo de árvore de decisão em que os valores de destino têm uma natureza discreta é chamado de modelos de classificação.

Um valor discreto é um conjunto finito ou infinito contável de valores, Por exemplo, idade, tamanho, etc. Os modelos em que os valores alvo são representados por valores contínuos são geralmente números chamados de Modelos de Regressão. Variáveis ​​contínuas são variáveis ​​de ponto flutuante. Esses dois modelos juntos são chamados de CART.

A CART usa o Índice de Gini como matriz de classificação.

Indução de árvore de decisão para aprendizado de máquina: ID3

No final dos anos 1970 e início dos 1980, J.Ross Quinlan foi um pesquisador que construiu um algoritmo de árvore de decisão para aprendizado de máquina. Este algoritmo é conhecido como ID3, dicotomizador iterativo . Este algoritmo foi uma extensão dos sistemas de aprendizagem de conceito descritos por E.B Hunt, J e Marin.

Mais tarde, ID3 veio a ser conhecido como C4.5. ID3 e C4.5 seguem uma abordagem gananciosa de cima para baixo para construir árvores de decisão. O algoritmo começa com um conjunto de dados de treinamento com rótulos de classe que são divididos em subconjuntos menores conforme a árvore é construída.

# 1) Inicialmente, existem três parâmetros, ou seja, lista de atributos, método de seleção de atributos e partição de dados . A lista de atributos descreve os atributos das tuplas do conjunto de treinamento.

#dois) O método de seleção de atributos descreve o método para selecionar o melhor atributo para discriminação entre tuplas. Os métodos usados ​​para seleção de atributos podem ser Ganho de Informação ou Índice de Gini.

# 3) A estrutura da árvore (binária ou não binária) é decidida pelo método de seleção de atributos.

# 4) Ao construir uma árvore de decisão, ela começa como um único nó que representa as tuplas.

# 5) Se as tuplas do nó raiz representam rótulos de classe diferentes, ele chama um método de seleção de atributo para dividir ou particionar as tuplas. A etapa levará à formação de ramos e nós de decisão.

# 6) O método de divisão determinará qual atributo deve ser selecionado para particionar as tuplas de dados. Ele também determina os ramos a crescer a partir do nó de acordo com o resultado do teste. O principal motivo dos critérios de divisão é que a partição em cada ramificação da árvore de decisão deve representar o mesmo rótulo de classe.

Um exemplo de atributo de divisão é mostrado abaixo:

uma. O parcelamento acima é de valor discreto.

b. O parcelamento acima é para valor contínuo.

# 7) As etapas de particionamento acima são seguidas recursivamente para formar uma árvore de decisão para as tuplas do conjunto de dados de treinamento.

# 8) O porcionamento para apenas quando todas as partições são feitas ou quando as tuplas restantes não podem ser particionadas mais.

# 9) A complexidade do algoritmo é descrita por n * | D | * log | D | onde n é o número de atributos no conjunto de dados de treinamento D e | D | é o número de tuplas.

O que é divisão binária gananciosa recursiva?

No método de divisão binária, as tuplas são divididas e cada função de custo de divisão é calculada. A divisão de custo mais baixa é selecionada. O método de divisão é binário, formado por 2 ramos. É recursivo por natureza, pois o mesmo método (cálculo do custo) é usado para dividir as outras tuplas do conjunto de dados.

Esse algoritmo é chamado de ganancioso, pois se concentra apenas no nó atual. Ele se concentra em reduzir seu custo, enquanto os outros nós são ignorados.

Como selecionar atributos para criar uma árvore?

As medidas de seleção de atributos também são chamadas de regras de divisão para decidir como as tuplas serão divididas. Os critérios de divisão são usados ​​para melhor particionar o conjunto de dados. Essas medidas fornecem uma classificação para os atributos para particionar as tuplas de treinamento.

Os métodos mais populares de seleção do atributo são o ganho de informações e o índice de Gini.

# 1) Ganho de informações

Este método é o principal método usado para construir árvores de decisão. Ele reduz as informações necessárias para classificar as tuplas. Isso reduz o número de testes necessários para classificar a tupla fornecida. O atributo com o maior ganho de informação é selecionado.

A informação original necessária para a classificação de uma tupla no conjunto de dados D é dada por:

Onde p é a probabilidade de a tupla pertencer à classe C. A informação é codificada em bits, portanto, log para a base 2 é usado. E (s) representa a quantidade média de informações necessárias para descobrir o rótulo da classe do conjunto de dados D. Este ganho de informação também é chamado Entropia .

A informação necessária para a classificação exata após o porcionamento é dada pela fórmula:

Onde P (c) é o peso da partição. Esta informação representa a informação necessária para classificar o conjunto de dados D no porcionamento por X.

O ganho de informação é a diferença entre a informação original e a esperada, necessária para classificar as tuplas do conjunto de dados D.

Ganho é a redução da informação exigida pelo conhecimento do valor de X. O atributo com o maior ganho de informação é escolhido como “melhor”.

# 2) Taxa de ganho

O ganho de informações pode às vezes resultar em porções inúteis para classificação. No entanto, a taxa de ganho divide o conjunto de dados de treinamento em partições e considera o número de tuplas do resultado em relação ao total de tuplas. O atributo com a razão de ganho máximo é usado como um atributo de divisão.

servidor privado de topo do mundo de warcraft

# 3) Índice de Gini

O índice de Gini é calculado apenas para variáveis ​​binárias. Ele mede a impureza nas tuplas de treinamento do conjunto de dados D, como

P é a probabilidade de a tupla pertencer à classe C. O índice de Gini que é calculado para o conjunto de dados binário dividido D pelo atributo A é dado por:

Onde n é a enésima partição do conjunto de dados D.

A redução na impureza é dada pela diferença do índice de Gini do conjunto de dados original D e o índice de Gini após a partição pelo atributo A.

A redução máxima na impureza ou índice Gini máximo é selecionado como o melhor atributo para divisão.

Overfitting em árvores de decisão

O overfitting ocorre quando uma árvore de decisão tenta ser a mais perfeita possível, aumentando a profundidade dos testes e, assim, reduzindo o erro. Isso resulta em árvores muito complexas e leva ao sobreajuste.

O overfitting reduz a natureza preditiva da árvore de decisão. As abordagens para evitar o sobreajuste das árvores incluem a pré-poda e a pós-poda.

O que é poda de árvore?

A poda é o método de remover os ramos não utilizados da árvore de decisão. Alguns ramos da árvore de decisão podem representar outliers ou dados ruidosos.

A poda de árvores é o método para reduzir os galhos indesejados da árvore. Isso reduzirá a complexidade da árvore e ajudará na análise preditiva eficaz. Ele reduz o sobreajuste, pois remove os galhos sem importância das árvores.

Existem duas maneiras de podar a árvore:

# 1) Pré-poda : Nesta abordagem, a construção da árvore de decisão é interrompida mais cedo. Isso significa que foi decidido não particionar ainda mais os ramos. O último nó construído torna-se o nó folha e este nó folha pode conter a classe mais frequente entre as tuplas.

As medidas de seleção de atributos são usadas para descobrir o peso da divisão. Os valores limite são prescritos para decidir quais divisões são consideradas úteis. Se o porcionamento do nó resultar em divisão caindo abaixo do limite, o processo é interrompido.

# 2) Postpruning : Este método remove os galhos atípicos de uma árvore totalmente crescida. Os ramos indesejados são removidos e substituídos por um nó folha denotando o rótulo de classe mais frequente. Essa técnica requer mais computação do que pré-poda, no entanto, é mais confiável.

As árvores podadas são mais precisas e compactas quando comparadas às árvores não podadas, mas apresentam uma desvantagem de replicação e repetição.

A repetição ocorre quando o mesmo atributo é testado repetidamente ao longo de um galho de uma árvore. Replicação ocorre quando as subárvores duplicadas estão presentes na árvore. Esses problemas podem ser resolvidos por divisões multivariadas.

A imagem abaixo mostra uma árvore não podada e podada.

Exemplo de algoritmo de árvore de decisão

Exemplo Fonte

Construindo uma Árvore de Decisão

Vamos dar um exemplo do conjunto de dados meteorológicos dos últimos 10 dias com os atributos perspectiva, temperatura, vento e umidade. A variável de resultado será jogar críquete ou não. Usaremos o algoritmo ID3 para construir a árvore de decisão.

Passo 1: A primeira etapa será criar um nó raiz.

Passo 2: Se todos os resultados forem sim, então o nó folha “sim” será retornado, caso contrário, o nó folha “não” será retornado.

Etapa 3: Descubra a entropia de todas as observações e a entropia com o atributo “x” que é E (S) e E (S, x).

Passo 4: Descubra o ganho de informação e selecione o atributo com alto ganho de informação.

Passo 5: Repita as etapas acima até que todos os atributos sejam cobertos.

Cálculo da entropia:

sim não

9 5

Se a entropia for zero, significa que todos os membros pertencem à mesma classe e se a entropia for um, significa que metade das tuplas pertence a uma classe e uma delas pertence a outra classe. 0,94 significa distribuição justa.

Encontre o atributo de ganho de informação que dá o ganho máximo de informação.

Por exemplo “Vento”, leva dois valores: Forte e Fraco, portanto, x = {Forte, Fraco}.

Encontre H (x), P (x) para x = fraco e x = forte. H (S) já foi calculado acima.

Fraco = 8

Forte = 8

Para vento “fraco”, 6 deles dizem “Sim” para jogar críquete e 2 deles dizem “Não”. Então a entropia será:

Para vento “forte”, 3 disseram “Não” para jogar críquete e 3 disseram “Sim”.

Isso mostra uma aleatoriedade perfeita, já que metade dos itens pertence a uma classe e a outra metade pertence a outras.

Calcule o ganho de informação,

Da mesma forma, o ganho de informação para outros atributos é:

O atributo outlook tem o maior ganho de informação de 0,246, portanto, é escolhido como raiz.

Nublado tem 3 valores: Ensolarado, Nublado e Chuva. Nublado com jogo de críquete é sempre “Sim”. Então termina com um nó folha, “sim”. Para os outros valores “Ensolarado” e “Chuva”.

A tabela para Outlook como “Sunny” será:

Entropia para “Outlook” “Sunny” é:

O ganho de informação para atributos em relação ao Sunny é:

O ganho de informação para umidade é maior, portanto, é escolhido como o próximo nó. Da mesma forma, a entropia é calculada para a chuva. O vento dá o maior ganho de informação .

A árvore de decisão seria semelhante a abaixo:

O que é modelagem preditiva?

Os modelos de classificação podem ser usados ​​para prever os resultados de um conjunto desconhecido de atributos.

Quando um conjunto de dados com rótulos de classe desconhecidos é alimentado no modelo, ele atribui automaticamente o rótulo de classe a ele. Este método de aplicação de probabilidade para prever resultados é chamado de modelagem preditiva.

melhor software para criar fluxogramas

Vantagens da classificação da árvore de decisão

Listados abaixo estão os vários méritos da Classificação da Árvore de Decisão:

1. A classificação da árvore de decisão não requer nenhum conhecimento de domínio, portanto, é apropriada para o processo de descoberta de conhecimento.
2. A representação dos dados na forma de árvore é facilmente compreendida pelo homem e é intuitiva.
3. Ele pode lidar com dados multidimensionais.
4. É um processo rápido e com grande precisão.

Desvantagens da classificação da árvore de decisão

A seguir estão os vários deméritos da Classificação da Árvore de Decisão:

1. Às vezes, as árvores de decisão se tornam muito complexas e são chamadas de árvores superdimensionadas.
2. O algoritmo da árvore de decisão pode não ser uma solução ótima.
3. As árvores de decisão podem retornar uma solução tendenciosa se algum rótulo de classe a dominar.

Conclusão

Árvores de decisão são técnicas de mineração de dados para classificação e análise de regressão.

Essa técnica agora está abrangendo muitas áreas como diagnóstico médico, marketing direcionado, etc. Essas árvores são construídas seguindo um algoritmo como ID3, CART. Esses algoritmos encontram maneiras diferentes de dividir os dados em partições.

É a técnica de aprendizado supervisionado mais conhecida, usada em aprendizado de máquina e análise de padrões. As árvores de decisão prevêem os valores da variável de destino, construindo modelos por meio do aprendizado do conjunto de treinamento fornecido ao sistema.

Esperamos que você tenha aprendido tudo sobre a mineração de árvores de decisão com este tutorial informativo !!

PREV Tutorial | PRÓXIMO Tutorial

Leitura recomendada

• Exemplos de mineração de dados: aplicações mais comuns de mineração de dados 2021
• Técnicas de Data Mining: Algoritmo, Métodos e Principais Ferramentas de Data Mining
• Mineração de dados: processo, técnicas e questões importantes na análise de dados
• Estrutura de dados da árvore B e da árvore B + em C ++
• Estrutura de dados de árvore binária em C ++
• Processo de mineração de dados: modelos, etapas do processo e desafios envolvidos
• Árvore AVL e estrutura de dados heap em C ++
• Data Mining Vs Machine Learning Vs Artificial Intelligence Vs Deep Learning