Implementação do algoritmo de classificação de árvore de decisão em Python

Este artigo compartilha o código específico de implementação do algoritmo de classificação de árvore de decisão em Python, para referência dos leitores, os detalhes são os seguintes

1

Árvore de decisão (decision tree) - é um algoritmo de classificação amplamente utilizado.

Em comparação com o algoritmo Bayes, a vantagem da árvore de decisão está no processo de construção, que não requer nenhum conhecimento de domínio ou configuração de parâmetros.

Em aplicações práticas, para descobertas de conhecimento exploratório, a árvore de decisão é mais aplicável.

2

Em termos simples, a ideia de classificação de árvore de decisão é semelhante a encontrar um parceiro. Imagine que a mãe de uma menina quer apresentar um namorado para ela, então surge a seguinte conversa:

　　　　　 Filha: Quanto tempo ela tem?

　　　　　 Mãe:26.

　　　　　 Filha: Ela é bonita?

　　　　　 Mãe: Ela é muito bonita.

　　　　　 Filha: Ela ganha bem?

　　　　　 Mãe: Não é muito alta, uma situação média.

　　　　　 Filha: Ela é funcionária pública?

　　　　　 Mãe: Sim, trabalha na Receita Federal.

　　　　　 Filha: Então, vou conhecê-lo.　

O processo de decisão da garota é um exemplo clássico de decisão de árvore de classificação.

Essência:Classificar os homens em duas categorias: vê ou não vê, com base em idade, aparência, renda e se é funcionário público

Supondo que os requisitos da garota para os homens sejam:3Menores de 20 anos, com aparência média ou acima e alta ou média renda de funcionários públicos, então pode ser representado pela lógica de decisão da garota na figura a seguir

A figura completa expressa a estratégia de decisão da garota para decidir se vê ou não um parceiro de encontro, onde:

◊Os nós verdes representam as condições de julgamento

◊Os nós amarelos representam o resultado da decisão

◊As setas representam o caminho de decisão sob diferentes condições de julgamento

As setas vermelhas na figura representam o processo de decisão da garota do exemplo acima.　

Essa figura pode ser considerada como uma árvore de decisão, dizendo que é 'basicamente uma árvore de decisão' porque as condições de julgamento na figura não são quantificadas, como alta, média e baixa renda, etc., ainda não pode ser considerada uma árvore de decisão no sentido rigoroso. Se todas as condições forem quantificadas, então se torna uma árvore de decisão real.　

A chave da algoritmo de classificação de árvore de decisão é construir uma árvore de decisão ótima com base em 'dados anteriores' para prever a classe de dados desconhecidos　

Árvore de decisão: é uma estrutura em forma de árvore (pode ser uma árvore binária ou não binária). Cada nó não folha representa um teste de atributo de característica, cada ramo representa a saída do atributo de característica em um intervalo de valores, e cada nó folha armazena uma classe. O processo de decisão usando árvore de decisão é começar pelo nó raiz, testar o atributo de característica correspondente do item a ser classificado e escolher o ramo de saída conforme o valor, até atingir o nó folha, onde a classe armazenada no nó folha é usada como resultado da decisão.

3、construção de árvore de decisão

Se tivermos os seguintes dados de amostra para julgar a qualidade da maçã:

amostra vermelha grande boa maçã

0　　　　　　　 　1　　　　　 1　　　　　　　　 1

1　　　　　　　 　1　　　　　 0　　　　　　　　 1

2　　　　　　　 　0　　　　　 1　　　　　　　　 0

3　　　　　　　 　0 0 0

amostras2características, A0 representa se é uma maçã vermelha. A1indica se é uma maçã grande. Se quiser usar esses dados de amostra para construir uma árvore de decisão automática para julgar se uma maçã é boa ou má.

Devido aos dados deste exemplo serem apenas2características, portanto, podemos percorrer todas as árvores de decisão possíveis, então2árvores, como mostrado na figura a seguir:

Claramente, a árvore de decisão que usa A0 (vermelho) como critério de divisão é superior à árvore de decisão que usa A1Árvore de decisão baseada no critério (tamanho):

Claro, isso é uma percepção intuitiva. No entanto, a intuição não é adequada para ser implementada em programas, então é necessário um método de avaliação quantitativa para avaliar o desempenho dessas duas árvores.

O método de avaliação quantitativa usado na avaliação da árvore de decisão éCalcular o ganho de entropia de cada situação de divisão:

Se a entropia cair mais após a divisão dos dados por um atributo selecionado, então esse atributo de divisão é a escolha ótima　

Critério de seleção de divisão de atributos (ou construção de árvores de decisão):

Em termos simples, a entropia é o grau de 'desordem' e 'confusão'.

Para entender por meio de cálculos:

1、entropia dos dados de amostra originais:

Número total de exemplos:4

maçã boa:2

maçã estragada:2

Entropia: -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1

A entropia é de1Representa o estado mais caótico e desorganizado atualmente.

2、calcular o ganho de entropia de divisão dos dois árvores de decisão

Árvore1Primeiro escolha A0 para fazer a divisão, e a entropia de cada nó subordinado é calculada conforme abaixo:

0,1nós folha têm2exemplos positivos, 0 exemplos negativos. A entropia é: e1 = -(2/2 * log(2/2) + 0/2 * log(0/2)) = 0。

2,3nós folha têm 0 exemplos positivos,2exemplos negativos. A entropia é: e2 = -(0/2 * log(0/2) + 2/2 * log(2/2)) = 0。

Portanto, a entropia da divisão A0 após a divisão é o peso ponderado da entropia de cada nó subordinado: E = e1*2/4 + e2*2/4 = 0.

O ganho de entropia da divisão A0 G (S, A0) = S - E = 1 - 0 = 1.

Na verdade, o nó folha da árvore de decisão representa que todos pertencem ao mesmo tipo de classe, portanto, a entropia é sempre 0.　

Árvore2Primeiro escolha A1faça a divisão, e a entropia de cada nó subordinado é calculada conforme abaixo:

0,2nós subordinados têm1exemplos positivos,1exemplos negativos. A entropia é: e1 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1.

1,3nós subordinados têm1exemplos positivos,1exemplos negativos. A entropia é: e2 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1.

Portanto, escolher A1A entropia da divisão após a divisão é o peso ponderado da entropia de cada nó subordinado: E = e1*2/4 + e2*2/4 = 1Isso significa que dividir é o mesmo que não dividir!

Escolher A1O ganho de entropia G (S, A1）=S - E = 1 - 1 = 0.　

Portanto, antes de cada divisão, precisamos calcular a divisão com o maior ganho de entropia da informação.

O ganho de entropia da divisão A0 é1>Fazendo A1o ganho de entropia da divisão no momento da divisão, então fazer a divisão A0 é a escolha óbvia!!!

4、orientação do algoritmo

Após a divisão do atributo de decisão, a desordem dos dados é cada vez menor, ou seja, a entropia da informação é cada vez menor　

5、algoritmo de implementação

Organizar as propriedades dos dados

Comparar o ganho de entropia da informação das informações divididas por um atributo específico, escolher o atributo com o maior ganho de entropia da informação como a primeira base de divisão, e continuar a escolher o segundo atributo, e assim por diante

Isso é o conteúdo completo deste artigo, esperamos que ajude no seu aprendizado e que você apóie o Tutorial Yell.

Declaração: O conteúdo deste artigo é extraído da internet, pertence ao respectivo detentor dos direitos autorais, o conteúdo é contribuído e carregado voluntariamente pelos usuários da internet, este site não possui direitos de propriedade, não foi editado manualmente e não assume responsabilidade legal. Se você encontrar conteúdo suspeito de violação de direitos autorais, bem-vindo a enviar e-mail para: notice#w, fornecendo provas relevantes.3Declaração: O conteúdo deste artigo é extraído da internet, pertence ao respectivo detentor dos direitos autorais, o conteúdo é contribuído e carregado voluntariamente pelos usuários da internet, este site não possui direitos de propriedade, não foi editado manualmente e não assume responsabilidade legal. Se você encontrar conteúdo suspeito de violação de direitos autorais, bem-vindo a enviar e-mail para: notice#w, fornecendo provas relevantes. Uma vez confirmado, o conteúdo suspeito de violação de direitos autorais será imediatamente removido.