Algoritmo de árboles de decisión en el aprendizaje automático de Python

1. Principio del árbol de decisión

El árbol de decisión es una estructura en forma de árbol donde se utilizan las propiedades de los ejemplos como nodos y los valores de las propiedades como ramas.
El nodo raíz del árbol de decisión es el atributo con la mayor información en todos los ejemplos. Los nodos intermedios del árbol de decisión son los atributos con la mayor información en los subconjuntos de ejemplos que forman el subárbol del nodo. Los nodos hoja del árbol de decisión son los valores de categoría de los ejemplos. El árbol de decisión es una forma de representación de conocimiento, que es una alta generalización de todos los datos de ejemplo. El árbol de decisión puede identificar con precisión la categoría de todos los ejemplos y también puede identificar eficazmente la categoría de nuevos ejemplos.　

Algoritmo de árbol de decisión ID3La idea básica es:

Primero, encontrar el atributo con la mayor capacidad de discriminación, dividir los ejemplos en varios subconjuntos, y luego seleccionar el atributo con la mayor capacidad de discriminación para dividir cada subconjunto, continuando así hasta que todos los subconjuntos solo contengan datos del mismo tipo. Finalmente, se obtiene un árbol de decisión.

El trabajo de J.R. Quinlan se centró en introducir el concepto de ganancia de información de la teoría de la información, que llamó ganancia de información (information gain), como una medida de la capacidad de discriminación del atributo, y diseñó un algoritmo recursivo para construir árboles de decisión.

El ejemplo es más fácil de entender:

Para el problema de clasificación climática, el atributo es:
El clima (A1Los valores son: soleado, nublado, lloviendo
La temperatura (A2Los valores son: frío, moderado, caliente
Humedad(A3) Valores: Alto, Normal
Viento (A4) Valores: Hay viento, Sin viento

Cada ejemplo pertenece a una categoría diferente, en este caso hay dos categorías, P y N. Los ejemplos de P y N se llaman respectivamente ejemplos positivos y ejemplos negativos. Combinar algunos ejemplos positivos y negativos conocidos para obtener el conjunto de entrenamiento.
Desde ID3El algoritmo obtiene un árbol de decisión que clasifica correctamente cada ejemplo en el conjunto de entrenamiento, como se muestra en la figura a continuación.

Las hojas del árbol de decisión son nombres de categorías, es decir, P o N. Los otros nodos están compuestos por atributos de ejemplos, y cada valor diferente del atributo corresponde a una rama;
Si se desea clasificar un ejemplo, comenzar desde la raíz del árbol y realizar pruebas en las ramas según los valores del atributo, continuar bajando hacia los nodos inferiores hasta llegar a los nodos hoja, y el ejemplo se clasificará como perteneciente a la categoría del nodo hoja.
Ahora use el gráfico para determinar un ejemplo específico,
La descripción del clima por la mañana de un día es:
Cielo: Nublado
Temperatura: Frío
Humedad: Normal
Viento: Sin viento

¿A qué tipo de clima pertenece?63;-------------Desde el gráfico se puede determinar que la categoría del ejemplo es P.　

ID3Es necesario construir un árbol de decisión de este tipo a partir del conjunto de entrenamiento de la tabla. En realidad, hay más de un árbol de decisión que puede clasificar correctamente el conjunto de entrenamiento.3El algoritmo puede obtener el árbol de decisión con el menor número de nodos.

ID3Algoritmo:

　　　　　1. Calcular la ganancia de información de cada atributo para la colección de ejemplos actual;
　　　　　2. Seleccionar el atributo Ak con la mayor ganancia de información;
　　　　　3. Agrupar ejemplos con valores iguales en Ak en el mismo subconjunto, el número de valores de Ak determina el número de subconjuntos;
　　　　 4. Para los subconjuntos que contienen tanto ejemplos positivos como negativos, se llama recursivamente al algoritmo de construcción de árboles;
　　　　　5. Si el subconjunto contiene solo ejemplos positivos o negativos, marcar la rama correspondiente con P o N y regresar al lugar de llamada.

Generalmente, cuando se trata de árboles, a menudo se utiliza la recursión.　

Para el problema específico de clasificación del clima, el cálculo específico es:
1Calculo de la entropía de información: donde S es la colección de ejemplos, P(ui) es la probabilidad de aparición de la categoría i:

|S| representa el número total de ejemplos en la colección de ejemplos S, |ui| representa el número de ejemplos de la categoría ui. Para9Tiene5Tiene
P(u1)=(9/14
P(u2)=(5/14
H(S)=(9/14)=log(14/9)+(5/14)=log(14/5)=0.94bit　

2Calculo de la ganancia de información:

Donde A es el atributo, Value(A) es la colección de valores del atributo A, v es un valor de atributo A, Sv es la colección de ejemplos en S donde el valor de A es v, | Sv | es el número de ejemplos en Sv.

Con el atributo A1Por ejemplo, según la fórmula de cálculo de la ganancia de información, el atributo A1La ganancia de información de

S=[9+,5-] //El conjunto de ejemplos originales contiene14Ejemplos,9Ejemplos positivos,5Ejemplos negativos
Sdespejado=[2+,3-]//Atributo A1Ejemplos con valores de cielo despejado, un total de5Un2Positivo,3Reverso
Snublado=[4+,0-] //Atributo A1Ejemplos con valores nublado, un total de4Un4Positivo, 0 negativo
Slluvia=[3+,2-] //Atributo A1Ejemplos con valores de cielo despejado, un total de5Un3Positivo,2Reverso
Por lo tanto　

3y el resultado es

Atributo A1La ganancia de información del atributo es la mayor, por lo que se selecciona como el nodo raíz.

4y construirá la raíz y las hojas de la decisión del árbol.

ID3El algoritmo seleccionará el atributo de ganancia de información más grande, clima, como la raíz del árbol, en14Examples of weather's3Branches are made for3 Branches correspond to3 Subsets are:

Among them, S2All examples in the branch are P class, so the corresponding branch is marked as P, and the other two subsets contain both positive and negative examples, so the recursive call is made to build the tree algorithm.

5Build the tree recursively

Respectively, for S1and S3Subset recursive call ID3The algorithm calculates the information gain of each attribute in each subset.
(1) For S1The humidity attribute has the largest information gain, so it is used as the root node of this branch, and further branching. High humidity examples are all N class, and this branch is marked as N. The normal value examples are all P class, and this branch is marked as P.
(2) For S3The wind attribute has the largest information gain, so it is used as the root node of this branch. Further branching, when there is wind, all are N class, and this branch is marked as N. When there is no wind, all are P class, and this branch is marked as P.

Two, Python implementation of decision tree algorithm classification

This code is an example in Chapter 3 of machine learning in action, tested and proven to be correct.
　1Calculate the shangnon value of the given data function:

def calcShannonEnt(dataSet): 
 #calculate the shannon value 
 numEntries = len(dataSet) 
 labelCounts = {} 
 for featVec in dataSet:  #create the dictionary for all of the data 
  currentLabel = featVec[-1] 
  if currentLabel not in labelCounts.keys(): 
   labelCounts[currentLabel] = 0 
  labelCounts[currentLabel] +)} 1 
 shannonEnt = 0.0 
 for key in labelCounts: 
  prob = float(labelCounts[key])/numEntries 
  shannonEnt -= prob*log(prob,2) #get the log value 
 return shannonEnt 

　2Create data function

def createDataSet(): 
 dataSet = [[1,1'], 
    [1,1, 'yes'], 
    [1,0,'no'], 
    [0,1'], 
    [0,1'], 
 labels = ['no surfacing','flippers'] 
 return dataSet, labels 

3.dividir el conjunto de datos, dividiendo el conjunto de datos según el característico dado

def splitDataSet(dataSet, axis, value): 
 retDataSet = [] 
 for featVec in dataSet: 
  if featVec[axis] == value:  #abstract the fature 
   reducedFeatVec = featVec[:axis] 
   reducedFeatVec.extend(featVec[axis+1:]) 
   retDataSet.append(reducedFeatVec) 
 return retDataSet 

4.elección del mejor método de división de conjuntos de datos

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 

5.creación recursiva del árbol

función para encontrar el nombre de la categoría que se repite más veces

def majorityCnt(classList): 
 classCount = {} 
 for vote in classList: 
  if vote not in classCount.keys(): classCount[vote] = 0 
  classCount[vote] +)} 1 
 sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1, reverse=True) 
 return sortedClassCount[0][0] 

función de código para crear árboles

def createTree(dataSet, labels): 
 classList = [example[-1] for example in dataSet] 
 # el tipo es el mismo, por lo que detener la clasificación 
 if classList.count(classList[0]) == len(classList): 
  return classList[0] 
 # recorrer todos los atributos y elegir el atributo más común 
 if (len(dataSet[0]) == 1) 
  return majorityCnt(classList) 
 bestFeat = chooseBestFeatureToSplit(dataSet) 
 bestFeatLabel = labels[bestFeat] 
 myTree = {bestFeatLabel:{}} 
 del(labels[bestFeat]) 
 # obtener la lista que tiene todas las propiedades 
 featValues = [example[bestFeat] for example in dataSet] 
 uniqueVals = set(featValues) 
 for value in uniqueVals: 
  subLabels = labels[:] 
  myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels) 
 return myTree 

Luego, en Python, ingrese el siguiente comando de símbolo de nombre:

myDat, labels = trees.createDataSet() 
myTree = trees.createTree(myDat, labels) 
print myTree 

Resultados:
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

6.función útil para clasificar árboles de decisión

def classify(inputTree, featLabels, testVec): 
 firstStr = inputTree.keys()[0] 
 secondDict = inputTree[firstStr] 
 featIndex = featLabels.index(firstStr) 
 for key in secondDict.keys(): 
  if testVec[featIndex] == key: 
   if type(secondDict[key]).__name__ == 'dict': 
    classLabel = classify(secondDict[key], featLabels, testVec) 
   else: classLabel = secondDict[key] 
 return classLabel 

En el símbolo del sistema de comandos de Python, ingrese:
trees.classify(myTree,labels,[1,0])　

Obtener resultado:
'no'
¡Felicidades. ¡Oh, sí. Lo has hecho.!!!

Esto es todo el contenido del artículo, esperamos que sea útil para su aprendizaje y que apoyen activamente el tutorial de alarido.

Declaración: El contenido de este artículo se ha obtenido de la red, y pertenece al autor original. El contenido ha sido contribuido y subido por los usuarios de Internet de manera autónoma. Este sitio no posee los derechos de propiedad, no ha sido editado por humanos y no asume ninguna responsabilidad legal. Si encuentra contenido sospechoso de copyright, le invitamos a enviar un correo electrónico a: notice#oldtoolbag.com (al enviar un correo electrónico, por favor reemplace # con @ para denunciar, y proporcione la evidencia relevante. Una vez verificada, este sitio eliminará inmediatamente el contenido sospechoso de infracción.)