Un árbol de decisión es una estructura similar a un diagrama de flujo en la que cada nodo interno representa una prueba en una característica (por ejemplo, si una moneda se mueve hacia arriba o hacia abajo), cada nodo de hoja representa una etiqueta de clase (decisión tomada después de computar todas las características) y las ramas representan conjunciones de características que conducen a esas etiquetas de clase. Las rutas de la raíz a la hoja representan reglas de clasificación. El diagrama a continuación ilustra el flujo básico del árbol de decisión para la toma de decisiones con etiquetas (Lluvia (Sí), Sin Lluvia (No)).
El árbol de decisión es uno de los enfoques de modelado predictivo utilizados en estadística , minería de datos y aprendizaje automático.
Los árboles de decisión se construyen a través de un enfoque algorítmico que identifica formas de dividir un conjunto de datos según diferentes condiciones. Es uno de los métodos más utilizados y prácticos para el aprendizaje supervisado. Los árboles de decisión son un método supervisado supervisado supervisado supervisado y regresión modelos de árboles donde la variable objetivo puede tomar un conjunto discreto de valores se denomina árboles de clasificación . Los árboles de decisión donde la variable objetivo puede tomar valores continuos (generalmente números reales) se denominan árboles de regresión . El árbol de clasificación y regresión (CART) es un término general para esto.
A lo largo de este post intentaré explicar usando los ejemplos.
Formato de datos
Los datos vienen en registros de formularios.
(x, Y ) = (x1, x2, x3, ...., xk, Y)
La variable dependiente, Y, es la variable objetivo que estamos tratando de comprender, clasificar o generalizar. El vector x se compone de las características, x1, x2, x3, etc., que se utilizan para esa tarea.
Ejemplo
training_data = [
[& # 039; Green & # 039 ;, 3, & # 039; Apple & # 039;]
['Yellow', 3, 'Apple']
['Red', 1, 'Grape']
['Red', 1, 'Grape']
['Yellow', 3, 'Lemon']
]
# Header = ["Color", "diameter", "Label"]
# La última columna es la etiqueta.
# Las primeras dos columnas son características.
Enfoque para hacer un árbol de decisiones
Al hacer un árbol de decisiones, en cada nodo del árbol hacemos diferentes tipos de preguntas. Sobre la base de la pregunta formulada, calcularemos la ganancia de información correspondiente a ella.
Ganancia de información
La ganancia de información se utiliza para decidir qué característica dividir en cada paso en la construcción del árbol. La simplicidad es lo mejor, por eso queremos mantener nuestro árbol pequeño. Para hacerlo, en cada paso debemos elegir la división que resulta en los nodos hijos más puros. Una medida de pureza comúnmente utilizada se llama información. Para cada nodo del árbol, el valor de información mide cuánta información nos da una característica sobre la clase. La división con la ganancia de información más alta se tomará como la primera división y el proceso continuará hasta que todos los nodos secundarios estén puros, o hasta que la ganancia de información sea 0.
Pregunta Pregunta
clase Pregunta: "" "Se utiliza una pregunta para particionar un conjunto de datos.
Esta clase simplemente registra un & # 039; número de columna & # 039; (por ejemplo, 0 para Color) y un & # 039; valor de columna & # 039; (por ejemplo, , Verde). El método & # 039; match & # 039; se usa para comparar el valor de la característica en un ejemplo con el valor de la característica almacenada en la pregunta . Vea la demostración a continuación. "" "
def __init __ (self, column, value): self.column = column self.value = value
def match (self, example):
# Comparar el valor de la característica en una Ejemplo del valor de la característica
# en esta pregunta.
val = ejemplo [self.column]
si is_numeric (val):
devuelve val> = self.value
else:
devuelve val == self.value
def __repr __ (self): # Este es solo un método auxiliar para imprimir # la pregunta en un formato legible. condition = "==" if is_numeric (self.value): condition = "> =" return "Is% s% s% s?" % ( header [self.column]condition, str (self.value))
Permite probar preguntas y sus resultados.
Pregunta (1, 3) ## ¿Diámetro> = 3? Pregunta (0, "Verde") ## Is color == Green?
Ahora intentaremos particionar el conjunto de datos según la pregunta formulada. Los datos se dividirán en dos clases en cada paso.
def partición (filas, pregunta): "" "Particiona un conjunto de datos.
Para cada fila en el conjunto de datos, verifique si coincide con la pregunta. Si
entonces, agréguelo a & # 039; filas verdaderas & # 039; de lo contrario, agréguelo a & # 039; filas falsas & # 039;.
"" "
true_rows, false_rows = [][]
para fila en filas:
if question.match (fila):
true_rows.append (row)
else:
false_rows.append (row)
return true_rows, false_rows [19659038] # Vamos a dividir los datos de entrenamiento en función de si las filas son rojas.
true_rows, false_rows = partition (training_data, Question (0, & # 039; Red & # 039;))
# Esto contendrá todos los & # 039; Red & # 039; filas.
true_rows ## [['Red', 1, 'Grape']['Red', 1, 'Grape']]
false_rows ## [['Green', 3, 'Apple']['Yellow', 3, 'Apple']['Yellow', 3, 'Lemon']]
El algoritmo para construir un árbol de decisiones generalmente funciona de arriba a abajo, al elegir una variable en cada uno Paso que mejor divide el conjunto de elementos.
Gini Impurity
Primero entendamos el significado de Pure y Impure .
Pure
Puro significa, en una muestra seleccionada del conjunto de datos, todos los datos pertenecen a la misma clase (PURE).
Impure
Medias impuras, los datos son una mezcla de diferentes clases.
Definición de Gini Impurity
Gini Impurity es una medida de la probabilidad de una clasificación incorrecta de una nueva instancia de una variable aleatoria, si esa nueva instancia se clasificó de manera aleatoria de acuerdo con la distribución de las etiquetas de clase del conjunto de datos.
Si nuestro conjunto de datos es Puro, la probabilidad de clasificación incorrecta es 0. Si nuestra muestra es una mezcla de diferentes clases, entonces la probabilidad de clasificación incorrecta será alta.
Ejemplo
# Demo 1:
# Veamos algunos ejemplos para entender cómo Gini Impurity obras
#
# Primero, veremos un conjunto de datos sin mezclar.
no_mixing = [['Apple']
['Apple']]
# esto devolverá 0
gini (no_mixing) ## output = 0
## Demo 2:
# Now, we & # 039; miraremos en el conjunto de datos con una proporción de manzanas y naranjas 50:50
some_mixing = [['Apple']
['Orange']]
# esto devolverá 0.5 - lo que significa que existe un 50% de probabilidad de errores de clasificación
# a Ejemplo aleatorio que extraemos del conjunto de datos.
gini (some_mixing) ## output = 0.5
## Demo 3:
# Ahora, veremos un conjunto de datos con muchas etiquetas diferentes
lots_of_mixing = [['Apple']
['Orange'][19659056]
['Grapefruit']
['Blueberry']]
# Esto devolverá 0.8
gini (lots_of_mixing) ## output = 0.8
#######
Pasos para tomar el árbol de decisión [19659060] Obtenga la lista de filas (conjunto de datos) que se toman en consideración para tomar el árbol de decisión (recursivamente en cada nodo).
- Calcule la falta de certidumbre de nuestro conjunto de datos o impureza de Gini o cuánto se mezclan nuestros datos, etc.
- Generar lista de todas las preguntas que deben plantearse en ese nodo.
- Particiones de filas en filas verdaderas y filas falsas según cada pregunta formulada.
- Calcule la ganancia de información basándose en la impureza de Gini y la partición de datos del paso anterior. [19659061] Actualice la mayor ganancia de información en base a cada pregunta formulada.
- Actualice la mejor pregunta en base a la ganancia de información (mayor información ganancia
- Divide el nodo en la mejor pregunta. Repita otra vez desde el paso 1 hasta que obtengamos nodos puros (nodos de hoja).
Código para los pasos anteriores
def find_best_split (rows): "" "Encuentre la mejor pregunta para hacer iterando sobre cada característica / valor y calculando la ganancia de información. "" " best_gain = 0 # manténgase al tanto de la mejor ganancia de información best_question = None # mantenga el tren de la característica / valor que lo produjo current_uncertainty = gini (filas) n_features = len (filas [0]) - 1 # número de columnas
para col en rango (n_features): # para cada característica
valores = set ([row[col] para fila en filas]) # valores únicos en la columna
para val en valores: # para cada valor
pregunta = Pregunta (col, val)
# intente dividir el conjunto de datos true_rows, false_rows = partición (filas, pregunta)
# Salta esta división si no divide el # conjunto de datos si len (true_rows) == 0 o len (false_rows) == 0: continue
# Calcule la ganancia de información de esta división gain = info_gain (true_rows, false_rows, current_uncertainty)
# You en realidad puede usar & # 039;> & # 039; en lugar de & # 039;> = & # 039; aquí # pero quería que el árbol se viera de cierta manera para nuestro # juguete de datos. if gain> = best_gain: best_gain, best_question = gain, question
return best_gain, best_question
########
# Demo:
# Encuentra la mejor pregunta para hacer primero para nuestro conjunto de datos de juguetes.
best_gain, best_question = find_best_split (training_data)
best_question
## output - Is diámetro> = 3?
Ahora construya el árbol de decisiones basado en el paso descrito anteriormente de forma recursiva en cada nodo.
def build_tree (filas) ): "" "Construye el árbol.
Reglas de recursión: 1) Cree que funciona. 2) Empieza por verificar el caso base (no hay información adicional). 3) Prepárate para trazas de pila gigante. "" "
# Intente dividir el conjunto de datos en cada uno de los atributos únicos, # calcule la ganancia de información, # y devuelva la pregunta que produce la ganancia más alta. gain, question = find_best_split (rows)
# Caso base: no hay más información # Ya que no podemos hacer más preguntas, # we & # 039; devolveremos una hoja. if gain == 0: return Leaf (rows)
# Si llegamos aquí, hemos encontrado una característica / valor útil # para particionar. true_rows, false_rows = partición (filas, pregunta)
# Construye recursivamente la rama verdadera. true_branch = build_tree (true_rows)
# Construye recursivamente la rama falsa. false_branch = build_tree (false_rows)
# Devuelve un nodo de pregunta. # Esto registra la mejor característica / valor para preguntar en este punto, # así como las ramas a seguir # dependiendo de la respuesta. return Decision_Node (question, true_branch, false_branch)
Construyendo un árbol de decisiones
Construyamos un árbol de decisiones basado en los datos de entrenamiento.
training_data = [
[& # 039; Green & # 039 ;, 3 & & 039; Apple & # 039;]
['Yellow', 3, 'Apple']
['Red', 1, 'Grape']
['Red', 1, 'Grape']
['Yellow', 3, 'Lemon']
]
# Header = ["Color", "diameter", "Label"]
# La última columna es la etiqueta.
# Las primeras dos columnas son características.
my_tree = build_tree (training_data)
print_tree (my_tree)
Salida
Is diámetro> = 3?
-> Verdadero :
¿Es color == Amarillo?
-> Verdadero:
Predecir {& # 039; Limón & # 039 ;: 1, & # 039; Manzana & # 039 ;: 1}
- > Falso:
Predecir {& # 039; Manzana & # 039 ;: 1}
-> Falso:
Predecir {& # 039; Uva & # 039 ;: 2}
De la salida anterior Puede ver que en cada paso los datos se dividen en filas Verdadero y Falso. Este proceso se repite hasta que alcanzamos el nodo de hoja donde la ganancia de información es 0 y no es posible una mayor división de datos ya que los nodos son Puros.
Ventaja del árbol de decisión
- Fácil de usar y entender.
- Lata maneja datos tanto categóricos como numéricos.
- Resistente a los valores atípicos, por lo tanto, requiere poco procesamiento previo de los datos.
Desventaja del árbol de decisión
- Prone a sobreajuste.
- Requieren algún tipo de medida en cuanto a su desempeño.
- Debe tener cuidado con el ajuste de parámetros.
- Puede crear árboles aprendidos sesgados si dominan algunas clases.
Cómo evitar el ajuste excesivo del modelo del árbol de decisión
El ajuste excesivo es uno de los principales problemas para cada modelo en máquina aprendizaje. Si el modelo está sobre ajustado, se generalizará pobremente a nuevas muestras. Para evitar que el árbol de decisiones se adapte excesivamente eliminamos las ramas que hacen uso de características que tienen poca importancia. Este método se llama como Poda o post-poda. De esta manera, reduciremos la complejidad del árbol y, por lo tanto, mejoraremos la precisión predictiva mediante la reducción del sobreajuste.
La poda debe reducir el tamaño de un árbol de aprendizaje sin reducir la precisión predictiva medida por una validación cruzada establecido. Hay 2 técnicas principales de poda.
- Error mínimo: El árbol se recorta hasta el punto en que el error de validación cruzada es el mínimo.
- Árbol más pequeño: El árbol está podado Retroceder un poco más lejos que el error mínimo. Técnicamente, la poda crea un árbol de decisión con error de validación cruzada dentro de 1 error estándar del error mínimo.
Detención anticipada o Pre-poda
Un método alternativo para evitar el sobreajuste es intentar y detener el proceso de construcción de árboles temprano, antes de que produzca hojas con muestras muy pequeñas. Esta heurística se conoce como detención temprana pero a veces también se conoce como árboles de decisión previos a la poda.
En cada etapa de división del árbol, verificamos el error de validación cruzada. Si el error no disminuye lo suficiente, entonces nos detenemos. Las paradas tempranas pueden ser inadecuadas si se detienen demasiado pronto. La división actual puede ser de poco beneficio, pero una vez hecha, las divisiones posteriores reducen el error de manera más significativa.
La parada temprana y la poda se pueden usar juntas, por separado o en absoluto. Los árboles de decisión posteriores a la poda son más rigurosos desde el punto de vista matemático, por lo que encontrar un árbol es al menos tan bueno como detenerlo temprano. La parada temprana es una solución rápida heurística. Si se usa junto con la poda, una parada temprana puede ahorrar tiempo. Después de todo, ¿por qué construir un árbol solo para podarlo nuevamente?
Árbol de decisiones en la vida real
- Seleccionar un vuelo para viajar
Supongamos que necesita seleccionar un vuelo para su próximo viaje. ¿Cómo lo hacemos? Primero verificamos si el vuelo está disponible ese día o no. Si no está disponible, buscaremos otra fecha, pero si está disponible, buscaremos puede ser la duración del vuelo. Si queremos tener solo vuelos directos, veremos si el precio de ese vuelo se encuentra en su presupuesto predefinido o no. Si es demasiado costoso, nos fijamos en otros vuelos; de lo contrario, lo reservamos
- Manejo de los antojos nocturnos
Hay muchas más aplicaciones del árbol de decisiones en la vida real. Puede consultar este y este para obtener más aplicaciones del árbol de decisiones.
A partir de este artículo, traté de explicar los conceptos básicos del árbol de decisiones y cómo funciona básicamente. Puede encontrar el código fuente utilizado en este artículo en github .
Espero que le haya gustado este artículo. Para cualquier cambio, sugerencia, envíeme un mensaje directamente en este artículo o en LinkedIn . Happy Learning – Cheers:)