Comprender mediante la implementación: árbol de decisiones

Imagen del autor

Muchos modelos avanzados de aprendizaje automático, como bosques aleatorios o algoritmos de aumento de gradiente, como XGBoost, CatBoost o LightGBM (e incluso codificadores automáticos!) se basan en un ingrediente común fundamental: la árbol de decisión!

Sin comprender los árboles de decisión, es imposible comprender cualquiera de los algoritmos avanzados de embolsado o aumento de gradiente mencionados anteriormente, ¡lo cual es una desgracia para cualquier científico de datos! Entonces, desmitifiquemos el funcionamiento interno de un árbol de decisiones implementando uno en Python.

En este artículo, aprenderás

• por qué y cómo un árbol de decisiones divide los datos,
• la ganancia de información, y
• cómo implementar árboles de decisión en Python usando NumPy.

Puedes encontrar el código en mi Github.

Para hacer predicciones, los árboles de decisión se basan en terrible el conjunto de datos en partes más pequeñas de forma recursiva.

Imagen del autor

En la imagen de arriba, puede ver un ejemplo de una división: el conjunto de datos original se separa en dos partes. En el siguiente paso, ambas partes se vuelven a dividir, y así sucesivamente. Esto continúa hasta que se cumple algún tipo de criterio de parada, por ejemplo,

• si la división da como resultado que una parte esté vacía
• si se alcanzó una cierta profundidad de recursión
• si (después de las divisiones anteriores) el conjunto de datos solo consta de unos pocos elementos, lo que hace innecesarias más divisiones.

¿Cómo encontramos estas divisiones? ¿Y por qué nos importa? Vamos a averiguar.

Motivación

Supongamos que queremos resolver un binario problema de clasificación que nos creamos ahora:

import numpy as np
np.random.seed(0) X = np.random.randn(100, 2) # features
y = ((X[:, 0] > 0) * (X[:, 1] < 0)) # labels (0 and 1)

Los datos bidimensionales se ven así:

Imagen del autor

Podemos ver que hay dos clases diferentes: púrpura en aproximadamente el 75 % y amarillo en aproximadamente el 25 % de los casos. Si alimenta estos datos a un árbol de decisión clasificador, este árbol tiene los siguientes pensamientos inicialmente:

“Hay dos etiquetas diferentes, lo cual es demasiado complicado para mí. Quiero limpiar este lío dividiendo los datos en dos partes; estas partes deberían estar más limpias que los datos completos anteriores”. - árbol que ganó conciencia

Y así lo hace el árbol.

Imagen del autor

El árbol decide hacer una división aproximadamente a lo largo del x-eje. Esto tiene el efecto de que la parte superior de los datos ahora es perfectamente limpiar, lo que significa que solo encuentras una sola clase (púrpura en este caso) allí.

Sin embargo, la parte inferior sigue siendo confuso, incluso más desordenado que antes en cierto sentido. La relación de clase solía ser de alrededor de 75:25 en el conjunto de datos completo, pero en esta parte más pequeña es de aproximadamente 50:50, que es lo más confuso posible.

 Nota:  Aquí, no importa que el morado y el amarillo estén bien separados en la imagen. Solo el cantidad bruta de diferentes etiquetas en la cuenta de dos partes.

Imagen del autor

Aún así, esto es lo suficientemente bueno como un primer paso para el árbol, y así continúa. Si bien no crearía otra división en la parte superior, limpia parte más, puede crear otra división en la parte inferior para limpiarla.

Imagen del autor

Et voilà, cada una de las tres partes separadas está completamente limpia, ya que solo encontramos un solo color (etiqueta) por parte.

Es realmente fácil hacer predicciones ahora: si llega un nuevo punto de datos, simplemente verifique cuál de los tres partes miente y darle el color correspondiente. Esto funciona tan bien ahora porque cada parte es limpia. Fácil, ¿verdad?

Imagen del autor

Muy bien, estábamos hablando de limpia y confuso datos pero hasta ahora estas palabras solo representan una vaga idea. Para implementar cualquier cosa, tenemos que encontrar una manera de definir limpieza.

Medidas de limpieza

Supongamos que tenemos algunas etiquetas, por ejemplo

y_1 = [0, 0, 0, 0, 0, 0, 0, 0] y_2 = [1, 0, 0, 0, 0, 0, 1, 0]
y_3 = [1, 0, 1, 1, 0, 0, 1, 0]

Intuitivamente y₁ es el conjunto de etiquetas más limpio, seguido de y₂ y luego y₃. Hasta aquí todo bien, pero ¿cómo podemos ponerle números a este comportamiento? Quizá lo más fácil que se te ocurra sea lo siguiente:

Solo cuenta la cantidad de ceros y la cantidad de unos. Calcular su diferencia absoluta. Para hacerlo más agradable, normalícelo dividiéndolo por la longitud de las matrices.

Por ejemplo,  y₂ tiene 8 entradas en total: 6 ceros y 2 unos. Por lo tanto, nuestro personalizado definido puntaje de limpieza sería |6 – 2| / 8 = 0.5. Es fácil calcular que las puntuaciones de limpieza de y₁ y y₃ son 1.0 y 0.0 respectivamente. Aquí, podemos ver la fórmula general:

Imagen del autor

Aquí, norte₀ y norte₁ son los números de ceros y unos respectivamente, norte = norte₀ + norte₁ es la longitud de la matriz y pag₁ = norte₁ / norte es la parte de las 1 etiquetas.

El problema con esta fórmula es que es adaptado específicamente al caso de dos clases, pero muy a menudo estamos interesados ​​en la clasificación multiclase. Una fórmula que funciona bastante bien es la Medida de impureza de Gini:

Imagen del autor

o el caso general:

Imagen del autor

Funciona tan bien que scikit-learn lo adoptó como medida por defecto por su DecisionTreeClassifier clase.

Imagen del autor

 Nota:  Medidas de Gini desorden en lugar de limpieza. Ejemplo: si una lista solo contiene una sola clase (=¡datos muy claros!), entonces todos los términos de la suma son cero, por lo tanto, la suma es cero. El peor caso es si todas las clases aparecen el número exacto de veces, en cuyo caso el Gini es 1–1/C donde C es el número de clases.

Ahora que tenemos una medida de limpieza/desorden, veamos cómo se puede usar para encontrar buenas divisiones.

Encontrar divisiones

Hay muchas divisiones entre las que elegimos, pero ¿cuál es buena? Usemos de nuevo nuestro conjunto de datos inicial, junto con la medida de impureza de Gini.

Imagen del autor

No contaremos los puntos ahora, pero supongamos que el 75% son morados y el 25% son amarillos. Usando la definición de Gini, la impureza del conjunto de datos completo es

Imagen del autor

Si dividimos el conjunto de datos a lo largo de la x-eje, como se hizo antes:

Imagen del autor

La la parte superior tiene una impureza de Gini de 0.0 y la parte de abajo

Imagen del autor

En promedio, las dos partes tienen una impureza de Gini de (0.0 + 0.5) / 2 = 0.25, que es mejor que el 0.375 de todo el conjunto de datos anterior. También podemos expresarlo en términos de los llamados ganancia de información:

La ganancia de información de esta división es 0.375 – 0.25 = 0.125.

Tan fácil como eso. Cuanto mayor sea la ganancia de información (es decir, cuanto menor sea la impureza de Gini), mejor.

Nota:  Otra división inicial igualmente buena sería a lo largo del eje y.

Una cosa importante a tener en cuenta es que es útil para pesar las impurezas de Gini de las partes por el tamaño de las partes. Por ejemplo, supongamos que

• la parte 1 consta de 50 puntos de datos y tiene una impureza de Gini de 0.0 y
• la parte 2 consta de 450 puntos de datos y tiene una impureza de Gini de 0.5,

entonces la impureza de Gini promedio no debería ser (0.0 + 0.5) / 2 = 0.25 sino 50 / (50 + 450) * 0.0 + 450 / (50 + 450) * 0.5 = 0.45.

Bien, ¿y cómo encontramos la mejor división? La respuesta simple pero aleccionadora es:

Simplemente pruebe todas las divisiones y elija la que tenga la mayor ganancia de información. Es básicamente un enfoque de fuerza bruta.

Para ser más precisos, los árboles de decisión estándar utilizan se divide a lo largo de los ejes de coordenadas, Es decir, xᵢ = c por alguna característica i y umbral c. Esto significa que

• una parte de los datos divididos consta de todos los puntos de datos x   xᵢcy
• la otra parte de todos los puntos x  xᵢ ≥ c.

Estas sencillas reglas de división han demostrado ser lo suficientemente buenas en la práctica, pero, por supuesto, también puede ampliar esta lógica para crear otras divisiones (es decir, líneas diagonales como xᵢ + 2xⱼ = 3, por ejemplo).

¡Genial, estos son todos los ingredientes que necesitamos para comenzar ahora!

Implementaremos el árbol de decisiones ahora. Dado que consta de nodos, definamos un Node primera clase.

from dataclasses import dataclass @dataclass
class Node: feature: int = None # feature for the split value: float = None # split threshold OR final prediction left: np.array = None # store one part of the data right: np.array = None # store the other part of the data

Un nodo conoce la función que utiliza para dividir (feature) así como el valor de división (value). value también se utiliza como almacenamiento para la predicción final del árbol de decisión. Dado que construiremos un árbol binario, cada nodo necesita conocer sus hijos izquierdo y derecho, tal como están almacenados en left y right .

Ahora, hagamos la implementación real del árbol de decisión. Lo estoy haciendo compatible con scikit-learn, por lo tanto, uso algunas clases de sklearn.base . Si no está familiarizado con eso, consulte mi artículo sobre cómo construir modelos compatibles con scikit-learn.

¡A implementar!

import numpy as np
from sklearn.base import BaseEstimator, ClassifierMixin class DecisionTreeClassifier(BaseEstimator, ClassifierMixin): def __init__(self): self.root = Node() @staticmethod def _gini(y): """Gini impurity.""" counts = np.bincount(y) p = counts / counts.sum() return (p * (1 - p)).sum() def _split(self, X, y): """Bruteforce search over all features and splitting points.""" best_information_gain = float("-inf") best_feature = None best_split = None for feature in range(X.shape[1]): split_candidates = np.unique(X[:, feature]) for split in split_candidates: left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] information_gain = self._gini(y) - ( len(X_left) / len(X) * self._gini(y_left) + len(X_right) / len(X) * self._gini(y_right) ) if information_gain > best_information_gain: best_information_gain = information_gain best_feature = feature best_split = split return best_feature, best_split def _build_tree(self, X, y): """The heavy lifting.""" feature, split = self._split(X, y) left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] if len(X_left) == 0 or len(X_right) == 0: return Node(value=np.argmax(np.bincount(y))) else: return Node( feature, split, self._build_tree(X_left, y_left), self._build_tree(X_right, y_right), ) def _find_path(self, x, node): """Given a data point x, walk from the root to the corresponding leaf node. Output its value.""" if node.feature == None: return node.value else: if x[node.feature] node.value: return self._find_path(x, node.left) else: return self._find_path(x, node.right) def fit(self, X, y): self.root = self._build_tree(X, y) return self def predict(self, X): return np.array([self._find_path(x, self.root) for x in X])

¡Y eso es! Puede hacer todas las cosas que le gustan de scikit-learn ahora:

dt = DecisionTreeClassifier().fit(X, y)
print(dt.score(X, y)) # accuracy # Output
# 1.0

Dado que el árbol no está regularizado, se sobreajusta mucho, de ahí la puntuación perfecta del tren. La precisión sería peor en datos no vistos. También podemos comprobar cómo se ve el árbol a través de

print(dt.root) # Output (prettified manually):
# Node(
# feature=1,
# value=-0.14963454032767076,
# left=Node(
# feature=0,
# value=0.04575851730144607,
# left=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# ),
# right=Node(
# feature=None,
# value=1,
# left=None,
# right=None
# )
# ),
# right=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# )
# )

Como imagen, sería esta:

Imagen del autor

En este artículo, hemos visto cómo funcionan los árboles de decisión en detalle. Empezamos con algunas ideas vagas pero intuitivas y las convertimos en fórmulas y algoritmos. Al final, pudimos implementar un árbol de decisiones desde cero.

Sin embargo, una advertencia: nuestro árbol de decisiones aún no se puede regularizar. Por lo general, nos gustaría especificar parámetros como

• máxima profundidad
• tamaño de la hoja
• y mínima ganancia de información

Entre muchos otros. Afortunadamente, estas cosas no son tan difíciles de implementar, lo que hace que esta sea una tarea perfecta para ti. Por ejemplo, si especifica leaf_size=10 como parámetro, los nodos que contengan más de 10 muestras ya no deberían dividirse. Además, esta implementación es no eficiente. Por lo general, no querrá almacenar partes de los conjuntos de datos en nodos, sino solo los índices. Entonces, su conjunto de datos (potencialmente grande) está en la memoria solo una vez.

Lo bueno es que ahora puedes volverte loco con esta plantilla de árbol de decisiones. Puede:

• implementar divisiones diagonales, es decir xᵢ + 2xⱼ = 3 en lugar de solo xᵢ = 3,
• cambie la lógica que ocurre dentro de las hojas, es decir, puede ejecutar una regresión logística dentro de cada hoja en lugar de simplemente hacer un voto mayoritario, lo que le da una árbol lineal
• cambie el procedimiento de división, es decir, en lugar de usar la fuerza bruta, pruebe algunas combinaciones aleatorias y elija la mejor, lo que le dará una clasificador de árbol extra
• y más.

 
 
Dr. Robert Kübler es científico de datos en Publicis Media y autor en Towards Data Science.

 
Original. Publicado de nuevo con permiso.
 

• Distribución de relaciones públicas y contenido potenciado por SEO. Consiga amplificado hoy.
• Platoblockchain. Inteligencia del Metaverso Web3. Conocimiento amplificado. Accede Aquí.
• Fuente: https://www.kdnuggets.com/2023/02/understanding-implementing-decision-tree.html?utm_source=rss&utm_medium=rss&utm_campaign=understanding-by-implementing-decision-tree