Implementación del algoritmo de clasificación de árboles de decisión en Python

Este artículo comparte el código específico de implementación del algoritmo de clasificación de árboles de decisión en Python, a modo de ejemplo, y el contenido específico es el siguiente

1、resumen

Árbol de decisión (decision tree) - es un algoritmo de clasificación ampliamente utilizado.

En comparación con el algoritmo de Bayes, la ventaja del árbol de decisión radica en que su proceso de construcción no requiere ningún conocimiento del dominio ni configuración de parámetros.

En la práctica, para la discovery de conocimiento exploratorio, el árbol de decisión es más aplicable.

2、algoritmo de pensamiento

En términos coloquiales, la idea de clasificación de árboles de decisión es similar a buscar una pareja. Imaginemos que la madre de una chica quiere presentarle a su hija un novio, y así se tiene la siguiente conversación:

　　　　　 Hija: ¿Cuántos años tiene?

　　　　　 Madre:26.

　　　　　 Hija: ¿Es guapo?

　　　　　 Madre: Es bastante atractivo.

　　　　　 Hija: ¿Tiene buen ingreso?

　　　　　 Madre: No es muy alto, una situación media.

　　　　　 Hija: ¿Es funcionario público?

　　　　　 Madre: Sí, trabaja en la administración fiscal.

　　　　　 Hija: Bueno, voy a verlo.　

El proceso de toma de decisiones de esta niña es un proceso de toma de decisiones de árbol de clasificación típico.

Esencia:Clasifica a los hombres en dos categorías: ver y no ver, según la edad, apariencia, ingresos y si es funcionario público

Supongamos que los requisitos de esta niña para los hombres son:3Bajo 20 años, apariencia media o superior y es alto ingreso o funcionario público de ingresos medios o superiores, luego esta niña puede representar su lógica de toma de decisiones en la siguiente figura

La imagen completa expresa la estrategia de toma de decisiones de la niña para decidir si ve a un compañero de cita, entre ellas:

◊Los nodos verdes representan las condiciones de juicio

◊Los nodos naranja representan el resultado de la decisión

◊Las flechas indican la ruta de decisión bajo diferentes condiciones de juicio

Las flechas rojas en la imagen indican el proceso de toma de decisiones de la niña en el ejemplo anterior.　

Esta imagen básicamente puede considerarse como un árbol de decisiones, se dice que 'básicamente puede considerarse' porque las condiciones de juicio en la imagen no están cuantificadas, como ingresos altos, medianos y bajos, etc., no se puede considerar un árbol de decisiones en el sentido estricto, si se cuantifican todas las condiciones, se convierte en un verdadero árbol de decisiones.　

La clave del algoritmo de clasificación de árboles de decisiones es construir un árbol de decisiones óptimo basado en 'datos previos' para predecir la categoría de datos desconocidos　

Árbol de decisiones: es una estructura en forma de árbol (puede ser un árbol binario o no binario). Cada nodo no hoja representa una prueba de atributo de característica, cada rama representa la salida del atributo de característica en un rango de valores, y cada nodo hoja almacena una categoría. El proceso de toma de decisiones con un árbol de decisiones es comenzar desde el nodo raíz, probar el atributo de característica correspondiente del elemento a clasificar y elegir la rama de salida según su valor, hasta llegar al nodo hoja, y tomar la categoría almacenada en el nodo hoja como el resultado de la decisión.

3、construcción de árboles de decisiones

Supongamos que hay los siguientes datos de muestra para juzgar si las manzanas son buenas o malas:

Muestra            Roja                              Grande                      Manzana buena

0　　　　　　　 　1　　　　　 1　　　　　　　　 1

1　　　　　　　 　1　　　　　 0　　　　　　　　 1

2　　　　　　　 　0　　　　　 1　　　　　　　　 0

3　　　　　　　 　0                   0                              0

La muestra de datos tiene2Un atributo, A0 indica si es una manzana roja. A1Indica si es una manzana grande. Si se debe construir un árbol de decisiones automático para juzgar si las manzanas son buenas o malas basado en este conjunto de datos de muestra:

Debido a que los datos de este ejemplo solo tienen2Un atributo, por lo que podemos exhaustionar todos los árboles de decisiones posibles que se pueden construir, es2Árboles, como se muestra en la siguiente figura:

Claramente, el árbol de decisiones que primero utiliza A0 (rojo) como base de división es mejor que el lado derecho que utiliza A1(Tamaño) como base de división del árbol de decisiones.

Por supuesto, esto es un conocimiento intuitivo. Y la intuición obviamente no es adecuada para la implementación de programas, por lo que se necesita una evaluación cuantitativa para evaluar el rendimiento de estos dos árboles.

El método de evaluación cuantitativa utilizado para evaluar el árbol de decisiones esCalcular el aumento de entropía de cada situación de división:

Si después de dividir los datos mediante un atributo seleccionado, la entropía disminuye más, entonces este atributo de división es la elección óptima　

La base de la elección de la división de atributos (es decir, la construcción de un árbol de decisiones):

En términos simples, la entropía es el grado de 'desorden y caos'.

A través del cálculo para entender:

1、la entropía de los datos de muestra originales:

Número total de ejemplos:4

Manzanas buenas:2

Manzanas malas:2

Entropía: -(1/2 * log(1/2) + 1/2 * log(1/2)) = 1

El entropía es1Se encuentra en el estado más caótico y desordenado.

2、cálculo de la ganancia de entropía de división de dos árboles de decisión

árbol1Primero elegir A0 para hacer la división, la entropía de información de cada nodo subyacente se calcula como sigue:

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, la entropía de información después de la división A0 es el peso ponderado de la proporción de la entropía de información de cada nodo subyacente: E = e1*2/4 + e2*2/4 = 0.

La ganancia de entropía de información de la división A0 es G（S, A0）=S - E = 1 - 0 = 1.

De hecho, los nodos hoja del árbol de decisión representan que todos pertenecen a la misma categoría, por lo que la entropía debe ser 0.　

árbol2Primero elegir A1hacer la división, la entropía de información de cada nodo subyacente se calcula 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 información después de la división es el peso ponderado de la proporción de la entropía de información de cada nodo subyacente: E = e1*2/4 + e2*2/4 = 1. Esto significa que dividir es lo mismo que no dividir!

Elegir A1Hacer la división de la entropía de información G（S, A1）=S - E = 1 - 1 = 0.　

Por lo tanto, antes de cada división, solo necesitamos calcular la división con la mayor ganancia de entropía de información.

La ganancia de entropía de información de la división A0 primero es1>Hacer A1la ganancia de entropía de información en la división, por lo que hacer la división A0 primero es la elección óptima！！！

4、guía de pensamiento del algoritmo

Después de la división de las propiedades de la decisión, la desorden de los datos se vuelve cada vez más bajo, es decir, la entropía de información se vuelve cada vez más pequeña　

5、implementación del algoritmo

Organizar las propiedades de los datos

Comparar la ganancia de entropía de información de la información dividida según una propiedad específica, elegir la propiedad con la mayor ganancia de entropía de información como la primera base de división, luego continuar seleccionando la segunda propiedad, y así sucesivamente

Esto es todo el contenido de este artículo, espero que sea útil para su aprendizaje y que todos nos apoyemos más en el tutorial de grito.

Declaración: el contenido de este artículo se obtiene de la red, es propiedad del autor original, el contenido se contribuye y carga de manera autónoma por los usuarios de Internet, este sitio no posee los derechos de propiedad, no se ha procesado editorialmente y no asume ninguna responsabilidad legal relacionada. Si encuentra contenido sospechoso de infracción de derechos de autor, por favor envíe un correo electrónico a: notice#oldtoolbag.com (al enviar un correo electrónico, reemplace # con @ para denunciar y proporcione evidencia. Una vez verificada, este sitio eliminará inmediatamente el contenido sospechoso de infracción de derechos de autor.)