Implementação da árvore de decisão em Python

Este artigo compartilha o código específico de implementação do árvore de decisão em python para referência, o conteúdo específico é o seguinte

Vantagens e desvantagens do algoritmo:

Vantagem: baixa complexidade de cálculo, resultados fáceis de entender, insensível a valores ausentes no meio, pode lidar com dados de características irrelevantes

Desvantagem: pode gerar o problema de overfitting

Tipos de dados aplicáveis: numéricos e nominais

Ideia do algoritmo:

1.Ideia geral da construção da árvore de decisão:

A árvore de decisão, em termos simples, é como um if-A estrutura do else é a mesma, seu resultado é gerar uma árvore que pode ser julgada e escolhida continuamente de raiz a folha, mas aqui o if-else não pode ser o que queremos configurar, o que precisamos fazer é fornecer um método pelo qual o computador pode obter a árvore de decisão que precisamos. O ponto chave deste método está em como escolher características valiosas entre muitas e escolher a melhor ordem de raiz a folha. Completamos isso, podemos também construir recursivamente uma árvore de decisão

2.Ganho de Informação

O princípio máximo de dividir o conjunto de dados é tornar os dados desorganizados mais organizados. Since isso envolve a questão da ordem e desordem da informação, naturalmente, devemos pensar em entropia de informação. Aqui também calculamos a entropia de informação (outro método é a impureza de Gini). A fórmula é a seguinte:

Os requisitos que os dados precisam atender:

1 Os dados devem ser listas compostas por elementos de lista, e todos os elementos das colunas devem ter a mesma comprimento de dados
2 A última coluna dos dados ou o último elemento de cada exemplo deve ser o rótulo de classe do exemplo atual

Função:

calcShannonEnt(dataSet)

Calcular a entropia de Shannon do conjunto de dados, em duas etapas, a primeira etapa é calcular a frequência, e a segunda etapa é calcular a entropia de Shannon com base na fórmula

splitDataSet(dataSet, aixs, value)

Dividir o conjunto de dados, reunir todos os valores que satisfazem X[aixs] == value em um conjunto, retornar um conjunto dividido (não inclui a propriedade aixs usada para dividir, porque não é necessário)

chooseBestFeature(dataSet)

Escolher as melhores propriedades para a divisão, a ideia é很简单，é dividir cada propriedade, ver qual é melhor. Aqui é usado um conjunto para escolher os elementos únicos da lista, isso é um método muito rápido

majorityCnt(classList)

因為我們遞歸構建決策樹是根據屬性的消耗進行計算的，所以可能會存在最後屬性用完了，但是分類還沒有算完，這時候就會採用多數表決的方式計算節點分類

createTree(dataSet, labels)

基於遞歸構建決策樹。這裡的label更多是對於分類特徵的名稱，為了更好看和後面的理解。

#coding=utf-8
import operator
from math import log
import time
def createDataSet():
  dataSet=[[1,1,'yes'],
      [1,1,'yes'],
      [1,0,'no'],
      [0,1,'no'],
      [0,1,'no']]
  labels = ['no surfaceing','flippers']
  return dataSet, labels
#计算香农熵
def calcShannonEnt(dataSet):
  numEntries = len(dataSet)
  labelCounts = {}
  for feaVec in dataSet:
    currentLabel = feaVec[-1]
    if currentLabel not in labelCounts:
      labelCounts[currentLabel] = 0
    labelCounts[currentLabel] += 1
  shannonEnt = 0.0
  for key in labelCounts:
    prob = float(labelCounts[key])/numEntries
    shannonEnt -= * log(prob, 2)
  return shannonEnt
def splitDataSet(dataSet, axis, value):
  retDataSet = []
  for featVec in dataSet:
    if featVec[axis] == value:
      reducedFeatVec = featVec[:axis]
      reducedFeatVec.extend(featVec[axis+1:])
      retDataSet.append(reducedFeatVec)
  return retDataSet
def chooseBestFeatureToSplit(dataSet):
  numFeatures = len(dataSet[0]) - 1#porque o último item do conjunto de dados é a etiqueta
  baseEntropy = calcShannonEnt(dataSet)
  bestInfoGain = 0.0
  bestFeature = -1
  for i in range(numFeatures):
    featList = [example[i] for example in dataSet]
    uniqueVals = set(featList)
    newEntropy = 0.0
    for value in uniqueVals:
      subDataSet = splitDataSet(dataSet, i, value)
      prob = len(subDataSet) / float(len(dataSet))
      newEntropy += * calcShannonEnt(subDataSet)
    infoGain = baseEntropy -newEntropy
    if infoGain > bestInfoGain:
      bestInfoGain = infoGain
      bestFeature = i
  return bestFeature
#porque construímos recursivamente a árvore de decisão com base no consumo de atributos, pode haver casos em que todos os atributos forem usados, mas a classificação
#se ainda não tivermos calculado, neste caso usaremos o método de maioria para calcular a classificação do nó
def majorityCnt(classList):
  classCount = {}
  for vote in classList:
    if vote not in classCount.keys():
      classCount[vote] = 0
    classCount[vote] += 1
  return max(classCount)     
def createTree(dataSet, labels):
  classList = [example[-1for example in dataSet]
  if classList.count(classList[0]) == len(classList):#se as classes forem as mesmas, para parar a divisão
    return classList[0]
  se len(dataSet[0]) == 1:#Todas as características foram usadas
    return majorityCnt(classList)
  bestFeat = chooseBestFeatureToSplit(dataSet)
  bestFeatLabel = labels[bestFeat]
  myTree = {bestFeatLabel:{}}
  del(labels[bestFeat])
  featValues = [example[bestFeat] for example in dataSet]
  uniqueVals = set(featValues)
  for value in uniqueVals:
    subLabels = labels[:]#Para não alterar o conteúdo original da lista, foi feito uma cópia
    myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet," ")) 
                    (bestFeat, value),subLabels)
  return myTree
def main():
  data,label = createDataSet()
  t1 = time.clock()
  myTree = createTree(data,label)
  t2 = time.clock()
  print myTree
  print 'execute for ',t2-t1
if __name__=='__main__':
  main()

Isso é tudo o que há no artigo, esperamos que ajude na aprendizagem de todos e que todos apoiem o tutorial Yell.

Declaração: O conteúdo deste artigo é de propriedade da Internet, pertence ao respectivo autor, 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 responsabilidades legais relacionadas. Se você encontrar conteúdo suspeito de violação de direitos autorais, por favor, envie um e-mail para: notice#w3Aviso: O conteúdo deste artigo foi extraído da Internet, pertence ao respectivo autor, o conteúdo foi 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 responsabilidades legais relacionadas. Se você encontrar conteúdo suspeito de violação de direitos autorais, por favor, envie um e-mail para: notice#w