¿Qué criterios debe utilizar un algoritmo de árbol de decisiones para dividir variables/columnas?

Antes de crear un algoritmo de árbol de decisiones, el primer paso es responder a esta pregunta. Echemos un vistazo a una de las formas de responder a esta pregunta. Para hacerlo, necesitaremos entender un uso de algunos conceptos clave de la teoría de la información.

Examinemos este método siguiendo los siguientes pasos:

1. Eche un vistazo muy breve a lo que es un Árbol de decisiones.
2. Defina y examine la fórmula para la Entropía.
3. Discuta qué es un Poco en teoría de la información.
4. Defina la ganancia de información y utilice la entropía para calcularla.
5. Escriba algunas funciones básicas de Python utilizando los conceptos anteriores.

En ciencia de datos, el algoritmo de árbol de decisión es un algoritmo de aprendizaje supervisado para problemas de clasificación o regresión. Nuestro objetivo final es utilizar datos históricos para predecir un resultado. A diferencia de la regresión lineal, los árboles de decisión pueden captar interacciones no lineales entre variables en los datos.

Veamos un árbol de decisiones muy simple. A continuación se muestra un flujo de trabajo que se puede usar para tomar una decisión sobre si comer o no una galleta de mantequilla de maní.

En este ejemplo, un árbol de decisión puede recoger en el hecho de que sólo se debe comer la galleta si se cumplen ciertos criterios. Este es el objetivo final de un árbol de decisiones. Queremos seguir tomando decisiones (escisiones) hasta que se cumplan ciertos criterios. Una vez que nos encontramos podemos usarlo para clasificar o hacer una predicción. Este ejemplo es muy básico usando solo dos variables (alergia, arruinar la cena). Pero, si tiene un conjunto de datos con miles de variables/columnas, ¿cómo decide qué variables/columnas son las más eficientes para dividir? Una forma popular de resolver este problema, especialmente si se usa un algoritmo ID3, es usar entropía y ganancia de información.

La Tarea

digamos que tenemos algunos datos y queremos usar para hacer un cuestionario en línea que predice algo sobre el tomador de prueba. Después de observar las relaciones en los datos, hemos decidido usar un algoritmo de árbol de decisiones. Si nunca has sido absorbido por un cuestionario en línea, puedes ver cientos de ejemplos aquí. El objetivo del cuestionario será adivinar si el participante es de uno de los estados del medio oeste de Estados Unidos. Las preguntas del cuestionario girarán en torno a si les gusta un determinado tipo de comida o no. A continuación tiene un pequeño conjunto de datos ficticios con quince entradas. Cada entrada tiene respuestas a una serie de preguntas. La mayoría de las preguntas son sobre si les gustó un determinado tipo de comida, en la que el participante respondió (1) por sí o (0) por ahora. La última columna(«midwest?») es nuestra columna de destino, lo que significa que una vez que se construye el árbol de decisiones, esta es la clasificación que estamos tratando de adivinar.

la Entropía

Para que podamos empezar vamos a utilizar una teoría de la información métrica llamada entropía. En ciencia de datos, la entropía se utiliza como una forma de medir cuán «mixta» es una columna. Específicamente, la entropía se usa para medir el trastorno. Comencemos por encontrar la entropía de nuestra columna objetivo, » ¿medio oeste?”.

Hay diez personas que viven en el medio oeste y cinco personas que no. Si alguien te preguntara qué tan mezclada está la columna, podrías decir que era una especie de mezcla, con una mayoría (2/3) de las personas del medio oeste. La entropía nos da una forma de cuantificar la respuesta «algo mixta». Cuanto más mezclados estén los (1)s y (0) s en la columna, mayor será la entropía. Si «midwest»?»si tuviéramos cantidades iguales de (1)s y (0) s, nuestra entropía sería 1. Si «midwest»?»consistido solamente en (1) s la entropía sería 0.

podemos utilizar la siguiente fórmula para calcular la entropía:

Vamos a ir a través de cada paso de la fórmula y calcular la entropía para el «midwest?” columna.

1. Necesitamos iterar a través de cada valor único en una sola columna y asignarlo a i. Para este ejemplo, tenemos 2 casos (c) en el «midwest?»columna (0) o (1).
2. Luego calculamos la probabilidad de que ese valor ocurra en los datos. Para el caso de (1), la probabilidad es 10/15. Para el caso de (0), la probabilidad es 5/15.
3. Tomamos la probabilidad de cada caso y la multiplicamos por el logaritmo base 2 de la probabilidad. 2 es la base más común porque la entropía se mide en bits (más sobre esto más adelante). La explicación completa de por qué se usa 2 está fuera del alcance de esta publicación, pero un usuario en stack Exchange ofrece una buena explicación. Para el caso de(1), obtenemos 10/15*log2(10/15). Para el caso de (0), obtenemos 5/15*log2(5/15).
4. A continuación, tomamos nuestro producto de cada caso anterior y lo sumamos. Para este ejemplo, 10/15*log2(10/15) + 5/15*log2(5/15).
5. Finalmente, negamos la suma total de arriba — – (10/15*log2(10/15) + 5/15 * log2 (5/15)).

una Vez que pongo los pasos a seguir todos juntos podemos obtener el siguiente:

el final de la entropía es .918278. Entonces, ¿qué significa eso realmente?

Teoría de la Información y un poco de Información

En el futuro, será importante comprender el concepto de bit. En teoría de la información, un bit es considerado como un número binario que representa 0 para ninguna información y 1 para un bit completo de información. Podemos representar un poco de información como un número binario porque tiene el valor (1) o (0). Supongamos que hay la misma probabilidad de que llueva mañana (1) o no llueva(0). Si te digo que mañana lloverá, te he dado un poco de información.

también podemos pensar en la entropía como información. Supongamos que tenemos un dado de seis lados cargado que siempre aterriza en (3). Cada vez que hacemos rodar el dado, sabemos por adelantado que el resultado será (3). No obtenemos nueva información rodando el dado, por lo que la entropía es 0. Por otro lado, si el dado está lejos y lanzamos un (3), había una probabilidad de 1/6 en rodar el (3). Ahora hemos obtenido información. Por lo tanto, rodar el dado nos da un poco de información: de qué lado aterrizó el número.

Para profundizar en el concepto de un poco de información, puede leer más aquí.

Obtenemos menos de un «bit» de solo información .918278-porque hay más (1) s en el «midwest?»columna que (0)s. Esto significa que si estuviéramos prediciendo un nuevo valor, podríamos adivinar que la respuesta es (1) y estar en lo correcto más a menudo que en lo incorrecto (porque hay una probabilidad de 2/3 de que la respuesta sea 1). Debido a este conocimiento previo, obtenemos menos de un «bit» completo de información cuando observamos un nuevo valor.

Usando Entropía para Tomar Decisiones

Nuestro objetivo es encontrar la(s) mejor(s) variable (s)/columna (s) para dividir al construir un árbol de decisiones. Finalmente, queremos seguir dividiendo las variables / columnas hasta que nuestra columna de destino mixta ya no esté mezclada.

Por ejemplo, veamos la entropía del » midwest?»columna después de dividir nuestro conjunto de datos en el» potato_salad?” columna.

Arriba, nuestro conjunto de datos se divide en dos secciones. A la izquierda, a todos los que les guste la ensalada de patatas. En el lado derecho, todos los que no lo hacen. Llenamos el foco en el lado izquierdo, que ahora tiene siete personas del medio oeste y dos personas que no lo son. Al usar la fórmula para la entropía en la columna dividida a la izquierda del medio oeste, la nueva entropía es.764204. Esto es genial! Nuestro objetivo es bajar la entropía y nos fuimos .918278 a .764204. Pero, no podemos detenernos ahí, si miramos la columna derecha, nuestra entropía subió, ya que hay una cantidad igual de (1)s y (0) s. Lo que necesitamos es una forma de ver cómo cambia la entropía en ambos lados de la división. La fórmula para obtener información hará eso. Nos da un número para cuantificar cuántos bits de información hemos ganado cada vez que dividimos nuestros datos.

Ganancia de información

Anteriormente establecimos que queremos divisiones que bajen la entropía de nuestra columna de destino. Cuando nos separamos en » potato_salad?»vimos esa entropía en el medio oeste?»bajó por el lado izquierdo. Ahora necesitamos entender la entropía total bajada cuando miramos a ambos lados de la división. Echemos un vistazo a la ganancia de información.

La ganancia de información utilizará la siguiente fórmula:

Deje que el desglose de lo que está pasando aquí.

Volveremos a nuestro » potato_salad?” ejemplo. Las variables de la fórmula anterior representarán lo siguiente:

• T = Target, nuestro » midwest?»column
• A = la variable (columna) que estamos probando, «potato_salad?»
• v = cada valor en A, cada valor en el » potato_salad?»columna

1. Primero, calcularemos la entropía original para (T) antes de la división , .918278
2. Luego, para cada valor único (v) en la variable (A), calculamos el número de filas en las que (A) toma el valor (v) y lo dividimos por el número total de filas. Para el «potato_salad?»columna obtenemos 9/15 para el valor único de (1) y 6/15 para el valor único de (0).
3. A continuación, multiplicamos los resultados por la entropía de las filas donde (A) es (v). Para la división izquierda (dividir en 1 para » potato_salad?») obtenemos 9/15 * .764204. Para el lado derecho de la división ( dividir en 0 para » potato_salad?») obtenemos 6/15 * 1.
4. Agregamos todos estos subconjuntos de productos juntos, 9/14*.764204 + 6/15 = .8585224.

5. Luego restamos de la entropía general para obtener ganancia de información, .918278 -.8585224 = .059754

Nuestra ganancia de información es .059754. ¿Qué nos dice eso?

Aquí hay una explicación alternativa. Estamos encontrando la entropía de cada conjunto después de la división, ponderándola por el número de elementos en cada división, y luego restando de la entropía actual. Si el resultado es positivo, hemos bajado la entropía con nuestra división. Cuanto más alto es el resultado, más hemos bajado la entropía.

Terminamos con .059754, lo que significa que ganamos .059754 bits de información dividiendo nuestro conjunto de datos en » potato_salad?»variable/columna. Nuestra ganancia de información es baja, pero sigue siendo positiva, lo que se debe a que bajamos la entropía en el lado izquierdo de la división.

Ahora tenemos que repetir este proceso para cada columna que estemos usando. En lugar de hacer esto a mano, escribamos código Python.

Envolviéndolo Todo Con Python

Ahora que entendemos la ganancia de información, necesitamos una forma de repetir este proceso para encontrar la variable / columna con la mayor ganancia de información. Para hacer esto, podemos crear algunas funciones simples en Python.

Importar los datos

Vamos a convertir nuestra tabla de arriba en un DataFrame usando la biblioteca de pandas de Python. Importaremos pandas y usaremos la función read_csv () para crear un DataFrame llamado «midwest».

import pandas as pd
midwest = pd.read_csv('midwes.csv')

Una función Python para Entropía

Para esta función, necesitaremos la biblioteca NumPy para usar la función bincount () y el módulo math para usar la función log ().

import numpy
import math

A continuación, definiremos nuestra función con un parámetro. El argumento dado será la serie, lista o matriz NumPy en la que estamos tratando de calcular la entropía.

def calc_entropy(column):

Necesitaremos encontrar el porcentaje de cada caso en la columna. Podemos usar el numpy.función bincount() para esto. El valor devuelto es una matriz NumPy que almacenará el recuento de cada valor único de la columna que se pasó como argumento.

counts = numpy.bincount(column)

Almacenaremos las probabilidades de cada valor único dividiendo el array «counts» por la longitud de la columna.

probabilities = counts / len(column)

Luego podemos inicializar una variable llamada «entropía» y establecerla en 0.

entropy = 0

A continuación, podemos usar un «bucle for» para recorrer cada probabilidad en nuestro array de probabilidades y multiplicarlo por el logaritmo base 2 de probabilidad utilizando las matemáticas.función log (). Luego, agregue cada caso a nuestra variable de entropía almacenada. * asegúrese de comprobar que su probabilidad es mayor que 0, de lo contrario log(0) devolverá indefinido

for prob in probabilities:
if prob > 0:
endtropy += prob * math.log(prob,2)

Finalmente, devolveremos nuestra variable de entropía negada.

return -entropy

ahora Todos juntos:

Genial! Ahora podemos construir una función para calcular la ganancia de información.

Una función de Python para Obtener información

Necesitaremos definir una función que tenga tres parámetros, uno para todo el conjunto de datos, uno para el nombre de la columna en la que queremos dividir y uno para el nombre de nuestra columna de destino.

def calc_information_gain(data, split_name, target_name):

A continuación, podemos usar la función de entropía de antes para calcular la entropía original de nuestra columna de destino.

orginal_entropy = calc_entropy(data)

Ahora necesitamos dividir nuestra columna.

*Para este ejemplo, solo usaremos las variables / columnas con dos únicas. Si desea dividir en una variable / columna como «edad», hay varias formas de hacerlo. Una forma es dividir en cada valor único. Otra forma es simplificar el cálculo de la ganancia de información y simplificar las divisiones al no dividir para cada valor único. En su lugar, la mediana se encuentra para la variable/coumn que se está dividiendo. Cualquier fila donde el valor de la variable esté por debajo de la mediana irá a la rama izquierda, y el resto de las filas irá a la rama derecha. Para calcular la ganancia de información, sólo tendremos que calcular entropías para dos subconjuntos. No caminaremos a través de este método, pero una vez que se realice la división en la mediana, el resto de pasos serían los mismos que se describen a continuación.

Dado que las columnas con las que estamos trabajando solo tienen dos valores únicos, haremos una división a la izquierda y una división a la derecha.

Comenzaremos usando los pandas.Serie.unique () para darnos una matriz de los valores únicos en la columna

values = data.unique()

A continuación, crearemos una división izquierda y derecha usando «valores».

left_split = data == values]
right_split = data == values]

Ahora podemos iniciar una variable para restar de nuestra entropía original.

to_subtract = 0

Luego iteraremos a través de cada subconjunto creado por nuestra división, calcularemos la probabilidad del subconjunto y luego agregaremos el producto de la probabilidad y la entropía de la columna de destino de los subconjuntos.

for subset in :
prob = (subset.shape / data.shape)
to_subtract += prob * calc_entropy(subset)

Finalmente, podemos devolver la diferencia de to_ubract restada de la entropía original.

return original_entropy - to_subtract

La función completa está a continuación.

Una función de Python para la mayor ganancia de información

Nuestra función final será una que devolverá el nombre de la variable/columna con la mayor ganancia de información.

Como se mencionó anteriormente, solo estamos utilizando las columnas con dos valores únicos para este ejemplo. Almacenaremos esos nombres de columna en una lista para usar en la función. Para llegar al punto en que codificaremos esto para este ejemplo, pero en un conjunto de datos grande, sería mejor escribir código para construir esta lista dinámicamente en función de los criterios que usamos para elegir las columnas.

columns = 

Envolvamos el paso final en una función para que podamos reutilizarla según sea necesario. Tendrá un parámetro, la lista de columnas para las que queremos encontrar la mayor ganancia de información.

def highest_info_gain(columns):

Inicializaremos un diccionario vacío para almacenar nuestras ganancias de información.

information_gains = {}

Y luego podemos recorrer la lista de columnas y almacenar el resultado en nuestro diccionario information_gains.

for col in columns:
information_gain = calc_information_gain(midwest, col, 'midwest?)
information_gains = information_gain

Finalmente, podemos devolver la clave del valor más alto en nuestro diccionario.

return max(information_gains, key=information_gains.get)

ahora Todos juntos:

una Vez que ejecutamos nuestra última función

print(highest_info_gain(midwest, columns, 'midwest?'))
//sushi

podemos ver que la variable/columna con la mayor ganancia de información es » sushi?’.

Podemos visualizar una división en sushi a continuación:

Nuestra división izquierda tiene dos de cada seis personas del medio oeste. La división derecha tiene a ocho de las nueve personas del medio oeste. Esta fue una división eficiente y redujo nuestra entropía en ambos lados. Si continuamos usaríamos la recursividad para seguir dividiendo cada división con el objetivo de terminar cada rama con una entropía de cero.

Conclusión

Los árboles de decisión pueden ser un algoritmo de aprendizaje automático útil para detectar interacciones no lineales entre variables en los datos. En este ejemplo, observamos las etapas iniciales de un algoritmo de clasificación de árbol de decisión. Luego analizamos tres conceptos de teoría de la información, entropía, bit y ganancia de información. Mediante el uso de estos conceptos, pudimos construir algunas funciones en Python para decidir qué variables/columnas eran las más eficientes para dividir. Con un firme entendimiento de estos conceptos, podemos avanzar para construir un árbol de decisiones.