Árbol de decisión

El árbol de decisión es un método básico de clasificación y regresión. Su modelo tiene una estructura de árbol en problemas de clasificación, representa el proceso de clasificación de instancias en función de características. En esencia, el modelo de árbol de decisión es una distribución de probabilidad condicional definida en el espacio de características y el espacio de clases. El aprendizaje de árboles de decisión generalmente incluye tres pasos: selección de características, generación de árboles de decisión y poda de árboles de decisión.

El modelo de árbol de decisión de clasificación es una estructura de árbol que describe la clasificación de instancias. El árbol de decisión se compone de nodos y bordes dirigidos. Hay dos tipos de nodos: nodos internos y nodos hoja. Los nodos internos representan una característica o atributo y los nodos hoja representan una clase.

Utilice el árbol de decisión para la clasificación, comience desde el nodo raíz, pruebe una determinada característica de la instancia y asigne la instancia a sus nodos secundarios en función de los resultados de la prueba. En este momento, cada nodo secundario corresponde; al valor de la característica A. Las instancias se prueban y asignan de forma recursiva de esta manera hasta que se alcanza un nodo hoja. Finalmente, las instancias se dividen en clases de nodos hoja.

Un árbol de decisión es una distribución de probabilidad condicional de una clase bajo condiciones de característica dadas. Esta distribución de probabilidad condicional se define en una partición del intervalo de característica. Dividir el espacio de características en celdas o regiones separadas y definir una distribución de probabilidad de clase en cada celda constituye una distribución de probabilidad condicional. Una ruta del árbol de decisión corresponde a una unidad en la partición, y la distribución de probabilidad condicional representada por el árbol de decisión consiste en la distribución de probabilidad condicional de la clase bajo las condiciones dadas de cada unidad. Suponiendo que X es una variable aleatoria que representa una característica e Y es una variable aleatoria que representa una clase, entonces esta distribución de probabilidad condicional se puede expresar como P (Y | X). El valor de En este momento, las instancias del nodo se clasifican en la categoría con alta probabilidad condicional. Es decir, el proceso de aprendizaje del árbol de decisión es en realidad el proceso de estimar un modelo de probabilidad condicional a partir de un conjunto de datos. Hay infinitos modelos de probabilidad condicional basados ​​​​en clases divididas por intervalos de características. Se debe considerar la capacidad del modelo. También se debe considerar su capacidad de generalización.

Para que el modelo tenga en cuenta tanto las capacidades de ajuste como de generalización del modelo, el aprendizaje del árbol de decisión utiliza la función de máxima verosimilitud regularizada como función de pérdida, con el objetivo de minimizar la función de pérdida para encontrar el modelo óptimo. Obviamente, seleccionar el árbol de decisión óptimo entre todos los árboles de decisión posibles es un problema NP-completo, por lo que en la práctica, generalmente se usan métodos heurísticos para resolver aproximadamente este problema de optimización: seleccionando recursivamente las características óptimas y entrenando los datos en función de estas características. se divide hasta que cada conjunto de subdatos tiene la mejor clasificación y finalmente se genera un árbol de características. Por supuesto, el árbol de decisión obtenido de esta manera en realidad no es óptimo. Además, debido a las características algorítmicas del árbol de decisión, para evitar que el modelo se sobreajuste, el árbol de decisión generado debe podarse de abajo hacia arriba para simplificarlo y mejorar la capacidad de generalización del modelo. Específicamente, se trata de eliminar los nodos hoja que están demasiado subdivididos, devolverlos al nodo principal, o incluso a un nodo superior, y luego cambiar el nodo principal o el nodo superior a un nuevo nodo hoja. Si el conjunto de datos tiene muchas características, también puede filtrar las características del conjunto de datos antes de realizar el aprendizaje del árbol de decisiones.

Dado que el árbol de decisión es una distribución de probabilidad condicional, los árboles de decisión de diferentes profundidades corresponden a modelos de probabilidad de diferente complejidad. La generación del árbol de decisión corresponde a la selección local del modelo y la poda del mismo. El árbol de decisión corresponde al modelo de selección global.

El concepto de entropía se originó en la física. Inicialmente, los físicos utilizaban este concepto para medir el grado de desorden de un sistema termodinámico. En 1948, Claude Elwood Shannon introdujo la entropía termodinámica en la teoría de la información, por lo que también se la llama entropía de Shannon. En la teoría de la información, la entropía es una medida de incertidumbre. Cuanto mayor es la entropía de una información, más información se puede transmitir. Por el contrario, significa que se puede transmitir menos información.

Si existe una moneda ideal con las mismas posibilidades de salir cara y cruz, entonces la entropía de un evento de lanzamiento de moneda es igual al valor máximo que puede alcanzar.

No tenemos forma de saber cuál será el resultado del próximo lanzamiento de moneda, por lo que cada lanzamiento de moneda es impredecible. Por lo tanto, al lanzar una moneda normal varias veces, la entropía de este evento es de un bit, porque solo hay dos resultados: cara o cruz, que se pueden representar como códigos 0, 1, y los dos resultados son independientes entre sí. Si se realizan n experimentos independientes, la entropía es n porque puede representarse mediante un flujo de bits de longitud n. Pero si ambas caras de una moneda son exactamente iguales, la entropía de esta serie de lanzamientos de moneda es cero porque el resultado se puede predecir con precisión. En el mundo real, la entropía de los datos que recopilamos se encuentra entre los dos casos anteriores.

Otro ejemplo un poco más complicado es suponer que una variable aleatoria Su entropía es . Por lo tanto, la entropía es en realidad la expectativa matemática de multiplicar y sumar el número de bits de una variable aleatoria y la probabilidad de su aparición secuencial.

Según el teorema H de Boltzmann, Shannon define la entropía de la variable aleatoria X como:

¿Dónde está la cantidad de información de la variable aleatoria? Cuando se toman las variables de muestras finitas, la entropía se puede expresar como:

Si, entonces definido.

De la misma manera, la entropía condicional se puede definir:

Es fácil ver que la entropía condicional es la expectativa matemática de la entropía de la distribución de probabilidad condicional de Y bajo el dado condiciones de. Cuando las probabilidades en entropía y entropía condicional se obtienen mediante estimación de máxima verosimilitud, la entropía correspondiente y la entropía condicional se denominan entropía de prueba (entropía empírica) y entropía condicional empírica (entropía condicional empírica), respectivamente.

Cuanto mayor es. entropía, mayor es la incertidumbre de la variable aleatoria. Se puede verificar a partir de la definición:

Cuando la base es, la unidad de entropía es

Por ejemplo, hay 26. letras en inglés Si cada letra aparece con la misma frecuencia en el artículo, la cantidad de información de cada letra es:

Igual que Suponiendo que hay 2500 caracteres chinos de uso común. que cada carácter chino aparece un promedio de veces en el artículo, el contenido informativo de cada carácter chino es:

De hecho, el número de veces que aparece cada letra y carácter chino en el artículo no es en promedio, Las letras raras y los caracteres chinos raros tienen un contenido de información relativamente alto. Obviamente, según la definición de expectativa, la entropía es la cantidad promedio de mensajes de todo el sistema de mensajes.

La entropía se puede utilizar para representar la incertidumbre del conjunto de datos. Cuanto mayor es la entropía, mayor es la incertidumbre del conjunto de datos. Por lo tanto, la diferencia en la entropía del conjunto de datos antes y después de la partición se utiliza para medir el efecto del uso de las características actuales para dividir el conjunto de datos (similar a la función de costo del aprendizaje profundo). Para dividir el conjunto de datos, la entropía del conjunto de datos antes de la división es segura, pero la entropía después de la división es incierta. Cuanto más pequeña es, menor es la incertidumbre del subconjunto obtenido mediante esta división de características (es decir, la. más puro el subidón). Por lo tanto, cuanto mayor sea el valor, más rápido aumentará la pureza cuando se utilicen las características actuales para dividir el conjunto de datos. Cuando construimos el árbol de decisión óptimo, siempre esperamos alcanzar un subconjunto de datos de mayor pureza más rápidamente. Para este punto, podemos referirnos al algoritmo de descenso de gradiente en el algoritmo de optimización. La razón por la cual cada paso es minimizar la función de pérdida. el método del gradiente negativo Es decir, la dirección del gradiente negativo es la dirección en la que el valor de la función disminuye más rápido. De la misma manera: en el proceso de construcción de un árbol de decisión, siempre esperamos que el conjunto se desarrolle en la dirección del subconjunto con mayor pureza lo más rápido posible, por lo que siempre elegimos la característica que maximiza la ganancia de información para dividir el conjunto de datos actual.

Obviamente, este método de división tiene desventajas. Según el criterio de ganancia de información, cuando una determinada característica B del conjunto de datos tiene un valor grande, es más fácil obtener datos de mayor pureza dividiendo según esta característica. Si el subconjunto de datos es demasiado pequeño, la ganancia de información será demasiado grande, lo que en última instancia conducirá a que la ganancia de información se sesgue hacia características con más valores.

Sea un conjunto de muestras de datos, asumiendo que el atributo de categoría tiene valores diferentes: , sea el número de muestras en clase.

Para una muestra determinada, su entropía de información es:

Entre ellas, está la probabilidad de que cualquier muestra pertenezca a , que generalmente puede estimarse mediante .

Supongamos que un atributo A tiene diferentes valores, use el atributo A para dividir el conjunto en subconjuntos, que contiene muestras del atributo en el conjunto con valores. Si se selecciona el atributo A como atributo de prueba, estos subconjuntos son nuevos nodos de hoja que crecen a partir de los nodos del conjunto. Supongamos que es el número de muestras con categoría en el subconjunto, entonces la entropía de información de dividir muestras según el atributo A es:

Entre ellas, está la probabilidad de muestras con categoría en el subconjunto. Finalmente, la ganancia de información (Ganancia) obtenida después de dividir los subconjuntos de muestra por el atributo A es:

Es decir, La ganancia de información del atributo A = la entropía de los datos antes de la partición - el subconjunto de datos después de dividir por el atributo A Entropía de un conjunto. La ganancia de información (ganancia de información), también conocida como información mutua (información matual), representa el grado en que conocer la información de la característica X reduce la incertidumbre de la información de clase Y. La ganancia de información es obviamente menor y el valor de es mayor, lo que significa que la selección del atributo de prueba A proporciona más información para la clasificación y la incertidumbre de clasificación después de seleccionar A es menor.

El criterio de selección de características de ganancia de información utilizado por el algoritmo clásico ID3 hará que la división esté más sesgada hacia características con más valores, para evitar esta situación. J. Ross Quinlan, el proponente de ID3, propuso C4.5, que cambió el criterio de selección de características de ganancia de información a tasa de ganancia de información basada en ID3. Un parámetro de penalización se multiplica en función de la ganancia de información. Cuando la cantidad de características es grande, el parámetro de penalización es pequeño; cuando la cantidad de características es pequeña, el parámetro de penalización es grande (similar a la regularización). Este parámetro de penalización es el inverso de la métrica de información dividida.

A diferencia de ID3 y C4.5, CART utiliza la impureza Gini como criterio de selección de características. La impureza de Gini, también llamada índice de Gini, representa la probabilidad de que una muestra seleccionada al azar en el conjunto de muestras esté mal clasificada Índice de Gini (impureza de Gini) = probabilidad de que la muestra sea seleccionada * probabilidad de que la muestra esté mal clasificada. . Cuanto menor sea el índice de Gini, menor será la probabilidad de que la muestra seleccionada en el conjunto sea mal clasificada, es decir, mayor será la pureza del conjunto y, a la inversa, menos pura será el conjunto.

El índice de Gini del conjunto de muestra:

El conjunto de muestra tiene m categorías, lo que representa el número de muestras en la enésima categoría, entonces el índice de Gini es:

Basado en un cierto El índice de Gini después de dividir el conjunto de muestra S por una característica:

CART es un árbol binario, es decir, cuando se usa una determinada característica para dividir el conjunto de muestra, dos conjuntos se obtienen: a. Muestras iguales al conjunto de valores de característica dado; b. Un conjunto de muestra que no es igual a un valor de característica dado. En esencia, es un procesamiento binario de características con múltiples valores.

Para cada una de las divisiones anteriores, se puede calcular la pureza de dividir el conjunto de muestras en dos subconjuntos en función de un determinado valor de característica:

Por lo tanto, para una muestra con múltiples características con un valor (más de 2), debe calcular la pureza del subconjunto después de dividir el conjunto de muestra (que representa los posibles valores de la característica) usando cada valor como punto de división, y luego encontrar el índice de Gini de todos posibles divisiones. La división más pequeña, el punto de división de esta división, es el mejor punto de división que utiliza características para dividir el conjunto de muestras.

Referencias:

Árbol de decisiones: comprensión de la ganancia de información, índice de ganancia de información, índice Geni

Comprensión profunda del aprendizaje automático (entropía de la información)

Método de aprendizaje estadístico (Li Hang)

Para facilitar la comprensión, los siguientes conjuntos de datos se utilizan para la clasificación utilizando tres métodos:

Antes de realizar un análisis específico, considere Como el ingreso es de tipo numérico, para utilizar el algoritmo del árbol de decisión, primero se debe discretizar el atributo.

En los algoritmos de aprendizaje automático, algunos algoritmos de clasificación (ID3, Apriori, etc.) requieren que los datos estén en forma de atributos categóricos. Por lo tanto, cuando se trata de problemas de clasificación, a menudo es necesario transformar algunos continuos. atributos en atributos categóricos. En términos generales, la discretización de atributos continuos se realiza estableciendo una cantidad de puntos de división discretos dentro del rango de valores del conjunto de datos, dividiendo el rango de valores en varios intervalos y luego usando diferentes símbolos o valores enteros para representar cada sub- valor de los datos. Por lo tanto, las dos cuestiones centrales de la discretización son: cómo determinar el número de categorías y cómo asignar atributos continuos a estos valores de categoría. Los métodos de discretización comúnmente utilizados incluyen el método de igual ancho, el método de igual frecuencia y el método de agrupamiento unidimensional.

En el uso real, la función cut() de Pandas se usa a menudo para lograr una discretización de igual ancho:

Puede ver que los resultados de la discretización son los mismos que los calculados manualmente. Cabe señalar que El método de ancho igual es sensible a los valores atípicos y tiende a distribuir de manera desigual los valores de los atributos en varios intervalos, lo que resulta en más datos en algunos intervalos y menos datos en algunos intervalos. Esto obviamente no se aprovecha. el establecimiento de un modelo de toma de decisiones.

Utilice cuatro cuantiles como puntos límite para dividir el intervalo:

Aunque la discretización de igual frecuencia evita la distribución de datos de la discretización de igual ancho Problema desigual, pero es posible dividir los mismos valores de datos en diferentes intervalos para cumplir con el requisito de que cada intervalo tenga la misma cantidad de valores de atributos.

El conjunto de datos obtenido después de utilizar el método de discretización de agrupamiento unidimensional es:

En este ejemplo, el conjunto de datos obtenido después de elegir utilizar la discretización basada en agrupamiento método Conjunto de datos para el cálculo del indicador. Para predecir si un cliente puede pagar sus deudas, se utilizan atributos como A (propiedad de bienes raíces), B (estado civil), C (ingresos anuales) para dividir el conjunto de datos y finalmente construir un árbol de decisión.

Soltero:

Divorciado:

Casado:

Obviamente, los niños divididos por el valor del atributo B 'casados' El conjunto de datos pertenece al mismo nodo hoja y ya no se puede clasificar.

A continuación, realice la selección de características óptima en el subconjunto de datos dividido por el valor del atributo B 'único':

1) Calcule la entropía de información total del conjunto de datos, donde Entre los 4 datos, hay 3 datos 'sí' sobre si la deuda se puede pagar y 1 para datos 'no'. La entropía de información total es:

2) Para el atributo A (poseer bienes inmuebles), su valor de atributo Hay dos tipos de "sí" y "no". Entre ellos, si A es "sí", si la deuda se puede pagar es "sí", hay 1, y si es "no", hay 0 si A es "no", si la deuda se puede pagar; es 'sí' Hay 2, y hay 1 para 'No', entonces la entropía de información del atributo A es:

3) Para el atributo B (estado civil), ya que se ha determinado, el la entropía de información de este subconjunto de datos es 0

4) Para el atributo C (ingreso anual), sus valores de atributo incluyen 'ingreso medio' e 'ingreso bajo'. Bajo la premisa de que C es una persona de "ingresos medios", la respuesta a si se puede realizar el reembolso es "sí", y el número 0 es "no" bajo la premisa de que C es una persona de "ingresos bajos". la respuesta a si el reembolso es posible es "sí". Hay 2 para "No", entonces la entropía de información del atributo C es:

5) Finalmente, calcule el valor de ganancia de información de los dos atributos. respectivamente:

Valor de ganancia de información Lo mismo significa que la pureza del árbol de decisión aumenta después de dividir el subconjunto de datos en dos atributos. En este momento, cualquiera de ellos se puede seleccionar como nodo hoja.

De la misma manera, se realizó la selección de características óptimas en el subconjunto de datos y se encontró que la entropía de la información era 0:

Se compiló el árbol de decisión final: