Implementazione dell'albero decisionale in Python

Questo articolo condivide l'esempio di codice Python per implementare l'albero di decisione, per riferimento, il contenuto è il seguente

Vantaggi e svantaggi dell'algoritmo:

Vantaggio: bassa complessità di calcolo, risultati facili da comprendere, insensibili alla perdita di valori intermedi, può gestire dati di caratteristiche non correlati

Svantaggio: potrebbe verificarsi il problema di overfitting

Tipi di dati applicabili: numerici e nominali

L'idea dell'algoritmo:

1. L'idea generale della costruzione dell'albero di decisione:

In realtà, l'albero di decisione è come una struttura if-else, il cui risultato è un albero che può essere scelto continuamente dal nodo radice ai nodi foglia. Tuttavia, l'if-else qui non è quello che pensiamo di impostare. Quello che dobbiamo fare è fornire un metodo per cui il computer possa ottenere l'albero di decisione che ci serve. Il punto chiave di questo metodo è come selezionare le proprietà con valore e ordinarle dal nodo radice ai nodi foglia. Dopo aver completato questo, possiamo costruire ricorsivamente un albero di decisione

2. Guadagno di informazione

Il principio massimo della segmentazione del set di dati è quello di rendere i dati disordinati più ordinati. Poiché questo riguarda anche il problema dell'ordine e della disordine delle informazioni, naturalmente dobbiamo pensare all'entropia delle informazioni. Calcoliamo anche l'entropia delle informazioni qui (un altro metodo è l'impurità di Gini). La formula è come segue:

Requisiti dei dati:

1 I dati devono essere elenchi composti da elementi di lista, e tutti i elementi delle colonne devono avere la stessa lunghezza di dati
2 L'ultima colonna dei dati o l'ultimo elemento di ogni esempio dovrebbe essere il tag di categoria dell'esempio corrente

Funzione:

calcShannonEnt(dataSet)

Calcolare l'entropia di Shannon del set di dati, in due passaggi: primo passo calcolare la frequenza, secondo passo calcolare l'entropia di Shannon secondo la formula

splitDataSet(dataSet, aixs, value)

Dividere il set di dati, raggruppare tutti i valori che soddisfano X[aixs] == value in un insieme, e restituire un insieme segmentato (escludendo l'attributo aixs utilizzato per segmentare, perché non è necessario)

chooseBestFeature(dataSet)

Scegliere la migliore proprietà per la segmentazione, il pensiero è molto semplice: dividere ogni proprietà e vedere quale è la migliore. In questo caso viene utilizzato un set per selezionare l'elemento unico nella lista, che è un metodo molto veloce

majorityCnt(classList)

Poiché costruiamo ricorsivamente l'albero di decisione in base al consumo delle proprietà, potrebbe accadere che le proprietà siano esaurite ma la classificazione non sia ancora completata. In questo caso, utilizzeremo il metodo di voto della maggioranza per calcolare la classificazione del nodo

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 -= prob * 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 #因为数据集的最后一项是标签
  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 += prob * calcShannonEnt(subDataSet)
    infoGain = baseEntropy - newEntropy
    if infoGain > bestInfoGain:
      bestInfoGain = infoGain
      bestFeature = i
  return bestFeature
#因为我们递归构建决策树是根据属性的消耗进行计算的，所以可能会存在最后属性用完了，但是分类
#还是没有算完，这时候就会采用多数表决的方式计算节点分类
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[-1] for example in dataSet]
  if classList.count(classList[0]) == len(classList): #类别相同则停止划分
    return classList[0]
  if len(dataSet[0]) == 1: #所有特征已经用完
    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:
    
    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()

Questo è tutto il contenuto dell'articolo, speriamo che sia utile per la tua apprendimento, e speriamo che tu sostenga fortemente la guida a urlania.

Dichiarazione: il contenuto di questo articolo è stato raccolto da Internet, il copyright è di proprietà del rispettivo proprietario, il contenuto è stato contribuito e caricato autonomamente dagli utenti di Internet, questo sito non detiene il diritto di proprietà, non è stato editato manualmente e non assume alcuna responsabilità legale. Se trovi contenuti sospetti di violazione del copyright, ti preghiamo di inviare una e-mail a: notice#oldtoolbag.com (al momento dell'invio dell'e-mail, sostituisci # con @) per segnalare, fornendo prove pertinenti. Una volta verificata, questo sito eliminerà immediatamente il contenuto sospetto di violazione del copyright.