Aprender el algoritmo de clasificación de árboles de decisión en Python

A partir de este capítulo, comenzamos a aprender algoritmos formalmente.

Primero, aprendemos el algoritmo de clasificación clásico y efectivo: algoritmo de clasificación de árboles de decisiones.

1、algoritmo de árboles de decisiones

El árbol de decisiones clasifica las propiedades de los ejemplos utilizando una estructura de árbol, es el algoritmo de clasificación más intuitivo, y también se puede usar para regresión. Sin embargo, tiene dificultades para resolver algunas clasificaciones lógicas especiales. Ejemplo típico como XOR lógico, el árbol de decisiones no es bueno para resolver este tipo de problemas.
La construcción del árbol de decisiones no es única, desafortunadamente, la construcción del árbol de decisiones óptimo es un problema NP. Por lo tanto, cómo construir un buen árbol de decisiones es el punto de investigación clave.
J. Ross Quinlan en1975introdujo la noción de entropía de información en la construcción del árbol de decisiones, que es el famoso ID3algoritmo. Posteriormente, C4.5, C5.0, CART, etc. son mejoras de este método.

La entropía es el grado de 'desorden' y 'confusión'. Puede ser confuso al principio de este concepto. Para entender rápidamente cómo dividir atributos utilizando el ganancia de entropía de información, puedes referirte al artículo de este hermano: Python Machine Learning Decision Tree Algorithm

Si aún no entiendes, consulta el siguiente ejemplo.

Supongamos que queremos construir un árbol de decisiones automático para seleccionar buenas manzanas, por simplicidad, solo lo dejo aprender lo siguiente:4ejemplos:
Ejemplo　　　 Rojo　　　　 Grande　　　　　 Buena manzana　
0　　　　　　　 　1　　　　　　　 1　　　　　　　　 1　
1　　　　　　　 　1　　　　　　 　0　　　　　　　　 1　
2　　　　　　 　 0　　　　　 　 1　　　　　　　　 0　
3　　　　　　 　 0　　　　　　 　0　　　　　　　　 0　

El ejemplo tiene2propiedades, A0 representa si es una manzana roja. A1representa si es una manzana grande.

Por lo tanto, la entropía de información de este ejemplo antes de la clasificación es S = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1.

La entropía es1representa el estado más caótico y desordenado actual.

Este ejemplo solo2propiedades. Por lo tanto, naturalmente, solo puede haber2árboles de decisiones, como se muestra en la siguiente figura:

Obviamente, el árbol de decisiones que utiliza A0 (rojo) como base para la división en la izquierda es mejor que el uso de A1Decision Tree basado en la división de (tamaño)
Por supuesto, esto es una percepción intuitiva. Para una evaluación cuantitativa,则需要计算每种划分情况的信息熵增益。
Primero, seleccione A0 como la división, y calcule la entropía de cada nodo subyacente de la siguiente manera:
0,1Los nodos hoja tienen2ejemplos positivos, 0 ejemplos negativos. La entropía es: e1 = -(2/2 * log(2/2) + 0/2 * log(0/2)) = 0。
2,3Los nodos hoja tienen 0 ejemplos positivos,2ejemplos negativos. La entropía es: e2 = -(0/2 * log(0/2) + 2/2 * log(2/2)) = 0。

Por lo tanto, se elige la información de entropía de A0 después de la división como el peso promedio de la proporción de la información de entropía de cada nodo subyacente: E = e1*2/4 + e2*2/4 = 0。
elegir A0 para dividir la ganancia de entropía de información G(S, A0) = S - E = 1 - 0 = 1.

De hecho, los nodos hoja del árbol de decisión representan que todos pertenecen al mismo tipo de categoría, por lo que la entropía es ciertamente 0.

Del mismo modo, si se elige A1hacer la división, el cálculo de la entropía de cada nodo subyacente es como sigue:
0,2los nodos subyacentes tienen1ejemplos positivos,1ejemplos negativos. La entropía es: e1 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1.
1,3los nodos subyacentes tienen1ejemplos positivos,1ejemplos negativos. La entropía es: e2 = -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1.
Por lo tanto, elegir A1La entropía de la división después de la división es el peso de la entropía de cada nodo subyacente en la suma ponderada: E = e1*2/4 + e2*2/4 = 1. Esto es, ¡no es diferente de no dividir!
elegir A1G(S, A) = S1）=S - E = 1 - 1 = 0.
Por lo tanto, antes de cada división, solo necesitamos calcular la división que tiene la mayor ganancia de entropía de información.

2、Conjunto de datos

Para facilitar la explicación y comprensión, utilizamos un conjunto de datos de prueba extremadamente simple:
1.5 50 delgado　
1.5 60 gordo　
1.6 40 delgado　
1.6 60 gordo　
1.7 60 delgado　
1.7 80 gordo　
1.8 60 delgado　
1.8 90 gordo　
1.9 70 delgado　
1.9 80 gordo　

Este conjunto de datos tiene un total de10ejemplos, cada ejemplo tiene2características,分别为 altura y peso, la tercera columna es la etiqueta de categoría, que representa 'gordo' o 'delgado'. Los datos se almacenan en1.txt.

Nuestra tarea es entrenar un clasificador de árboles de decisión, que, al ingresar altura y peso, pueda decir si la persona es gorda o delgada.
(Los datos son una especulación subjetiva del autor, tienen cierta lógica, pero ignora su razonabilidad)

El árbol de decisión es bastante natural en la rama lógica binaria de 'sí' o 'no'. ¿Y qué pasa con los valores continuos de altura y peso en este conjunto de datos?

Aunque es un poco más complicado, no es un problema. Solo hay que encontrar los puntos intermedios que dividen estos valores continuos en diferentes intervalos y se convierte en un problema lógico binario.
La tarea del árbol de decisión en este ejemplo es encontrar algunos puntos críticos de altura y peso, clasificar los ejemplos en pares en función de si son mayores o menores que estos puntos críticos, y construir el árbol de decisión de arriba a abajo.

Implementar utilizando las bibliotecas de aprendizaje automático de Python es bastante simple y elegante.

3、Implementación en Python

La implementación en Python es la siguiente:

# -*- coding: utf-8 -*- 
import numpy as np 
import scipy as sp 
from sklearn import tree 
from sklearn.metrics import precision_recall_curve 
from sklearn.metrics import classification_report 
from sklearn.cross_validation import train_test_split 
''''' 数据读入 ''' 
data  = [] 
labels = [] 
with open("data\\1.txt) como ifile: 
    for line in ifile: 
      tokens = line.strip().split(' ') 
      data.append([float(tk) for tk in tokens[:-1]) 
      labels.append(tokens[-1]) 
x = np.array(data) 
labels = np.array(labels) 
y = np.zeros(labels.shape) 
''''' 标签转换为0 '''/1 ''' 
y[labels=='gordo'] =1 
''''' 拆分训练数据与测试数据 ''' 
x_train, x_test, y_train, y_test = train_test_split(x, y, test_size = 0.2) 
''''' 使用信息熵作为划分标准，对决策树进行训练 ''' 
clf = tree.DecisionTreeClassifier(criterion='entropy') 
print(clf) 
clf.fit(x_train, y_train) 
''''' 把决策树结构写入文件 ''' 
with open("tree.dot", 'w') as f: 
  f = tree.export_graphviz(clf, out_file=f) 
''''' 系数反映每个特征的影响力。越大表示该特征在分类中起到的作用越大 ''' 
print(clf.feature_importances_) 
'''''测试结果的打印''' 
answer = clf.predict(x_train) 
print(x_train) 
print(answer) 
print(y_train) 
print(np.mean( answer == y_train)) 
'''''准确率与召回率''' 
precision, recall, thresholds = precision_recall_curve(y_train, clf.predict(x_train)) 
answer = clf.predict_proba(x)[:,1] 
print(classification_report(y, answer, target_names = ['delgado', 'gordo'])) 

Los resultados de salida son similares a los siguientes:}
[ 0.2488562　 0.7511438]
array([[　 1.6,　 60. ],
　　　　　　 [　 1.7,　 60. ],
　　　　　　 [　 1.9,　 80. ],
　　　　　　 [　 1.5,　 50. ],
　　　　　　 [　 1.6,　 40. ],
　　　　　　 [　 1.7,　 80. ],
　　　　　　 [　 1.8,　 90. ],
　　　　　　 [　 1.5,　 60. ])
array([ 1, 0.,　 1, 0., 0.,　 1,　 1,　 1.])
array([ 1, 0.,　 1, 0., 0.,　 1,　 1,　 1.])
1.0
　　　　　　　　　　　　 precision　　　 recall　 f1-score　　 soporte
　　　　　　 thin　　　　　　 0.83　　　　　 1.00　　　　　 0.91　　　　　　　　 5
　　　　　　　 fat　　　　　　　 1.00　　　　　 0.80　　　　　 0.89　　　　　　　　 5
avg / total　　　　　　 1.00　　　　　 1.00　　　　　 1.00　　　　　　　　 8
array([ 0.,　 1, 0.,　 1, 0.,　 1, 0.,　 1. 0., 0.])
array([ 0.,　 1, 0.,　 1, 0.,　 1, 0.,　 1, 0.,　 1.])

Puede ver que la precisión de probar los datos entrenados es100%. Pero al probar todos los datos al final, aparecerá1Muestras de prueba clasificadas incorrectamente.
Explica que el árbol de decisión de este ejemplo absorbe bien las reglas del conjunto de entrenamiento, pero la predictividad es un poco peor.
Aquí hay3Puntos que necesitan ser explicados, esto se utilizará en el aprendizaje automático en el futuro.

1、 división de datos de entrenamiento y prueba.

Esto se hace para facilitar la validación cruzada. La validación cruzada es para probar la estabilidad del clasificador.
En el código, 0.2Representa la elección aleatoria20% de los datos se utilizan como prueba. El resto80% se utiliza para entrenar el árbol de decisión.
Es decir10Muestras se seleccionan aleatoriamente8Entrenamientos. El conjunto de datos de este artículo es pequeño, y el propósito aquí es ver que debido a la elección aleatoria de los datos de entrenamiento, cada árbol de decisión construido es diferente.

2、 diferentes factores de influencia de las características.

La influencia de las diferentes características de los muestras en el peso de la clasificación puede variar mucho. Ver la influencia de cada muestra en la clasificación después de la clasificación también es muy importante.
En este caso, el peso de la altura es 0.25El peso es 0.75Puede ver que la importancia del peso es mucho mayor que la de la altura. Para la determinación de la obesidad, esto es bastante lógico.

3、 precisión y tasa de recuperación.

Este2Es un estándar importante para evaluar la precisión de la clasificación. Por ejemplo, en el código final se combinan todos10Especifica los resultados de prueba de
Resultados de prueba: array([ 0.,　 1, 0.,　 1, 0.,　 1, 0.,　 1. 0., 0.])
Resultados reales: array([ 0.,　 1, 0.,　 1, 0.,　 1, 0.,　 1, 0.,　 1.])
La tasa de precisión de clasificación como thin es 0.83. Porque el clasificador clasificó6Un thin, de los cuales los correctos son5Un thin, de los cuales5/6=0.83.
La tasa de recuperación de clasificación como thin es1.00. Porque en el conjunto de datos hay5Un thin, mientras que el clasificador los clasificó todos correctamente (¡incluso dividió un fat en thin!), tasa de recuperación5/5=1.
La tasa de precisión de clasificación como fat es1.00. No se repetirá.
La tasa de recuperación de clasificación como fat es 0.80. Porque en el conjunto de datos hay5fat, mientras que el clasificador solo clasificó4¡Un (¡Dividió un fat en thin!)!, tasa de recuperación4/5=0.80。
A menudo, especialmente en situaciones de clasificación de datos de gran dificultad, la precisión y el recall suelen estar en conflicto. Puede necesitar encontrar el mejor punto de equilibrio según sus necesidades.
Por ejemplo, en este ejemplo, su objetivo es garantizar que los graciosos que encuentre sean verdaderamente graciosos (precisión) o garantizar que encuentre a más graciosos (recall).

El código también escribe la estructura del árbol de decisiones en el archivo tree.dot. Abriendo este archivo, es fácil dibujar el árbol de decisiones y还可以看到更多关于决策树的分类信息。
El archivo tree.dot de este artículo se muestra a continuación:

digraph Tree { 
0 [label="X[1] <= 55.0000\nentropy = 0.954434002925
samples = 8", shape="box"] ; 
1 [label="entropy = 0.0000\nsamples = 2
value = [ 2. 0.]", shape="box"] ; 
0 -> 1 ; 
2 [label="X[1] <= 70.0000\nentropy = 0.650022421648
samples = 6", shape="box"] ; 
0 -> 2 ; 
3 [label="X[0] <= 1.6500\nentropy = 0.918295834054
samples = 3", shape="box"] ; 
2 -> 3 ; 
4 [label="entropy = 0.0000\nsamples = 2
value = [ 0. 2[shape="box"] ; 
3 -> 4 ; 
5 [label="entropy = 0.0000\nsamples = 1
value = [ 1. 0.]", shape="box"] ; 
3 -> 5 ; 
6 [label="entropy = 0.0000\nsamples = 3
value = [ 0. 3[shape="box"] ; 
2 -> 6 ; 
} 

Basándose en esta información, el árbol de decisiones debería tener el siguiente aspecto:

Este es el contenido completo del artículo, esperamos que sea útil para su aprendizaje y que todos apoyen el tutorial de alarido.

Declaración: el contenido de este artículo se ha obtenido de la red, es propiedad del autor original, el contenido se ha contribuido y subido por los usuarios de Internet de manera autónoma. Este sitio no posee los derechos de propiedad, no ha sido editado artificialmente 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 proporcionar evidencia relevante. Una vez verificada, este sitio eliminará inmediatamente el contenido sospechoso de infracción.