Árboles de decisión¶
Un árbol de decisión es un árbol cuyos nodos representan valores de los rasgos de los datos; los hijos de los nodos responden a decisiones sobre estos valores y las hojas del árbol son clases a las que pueden pertenecer los datos.
Aquí presentamos una implementación del algoritmo para aprender árboles de decisión con base en ganancia de información.
In [1]:
import numpy as np
from collections import Counter
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import classification_report
Modelo para árboles de decisión¶
En primer lugar definimos una clase para crear objetos nodos que puedan usarse para construir el árbol de decisión.
In [2]:
class decisionnode:
"""
Clase para guardar nodos del árbol de decisión.
"""
def __init__(self,feat=-1,value=None,results=None,tb=None,fb=None):
#Columna
self.feat=feat
#Valor
self.value=value
#Resultados
self.results=results
#Rama positiva
self.tb=tb
#Rama negativa
self.fb=fb
def __str__(self):
if self.results != None:
return "Class: {}".format(self.results)
else:
return "Column {}: >={}?".format(self.feat, self.value)
También definimos funciones que utilizaremos con los árboles de decisión: una función que nos permitirá particionar los datos en base a si cumplen con cierto valor de un rasgo.
Una función para contar las apariciones de un valor a lo largo de los diferentes ejemplos en los datos.
Finalmente, definimos una función que nos permitirá visualizar el árbol de decisión y las decisiones que se hacen para llegar a una clase.
In [3]:
def divideSet(X,column,value):
"""
Función para separar el conjunto de datos bi-particionando.
Arguments
---------
rows : array
Renglones de los datos
column : array
Columnas de los datos
value : x
Valor actual de los datos.
Returns
-------
Bi-partición de los datos.
"""
split_function=None
#Si el valor es número
if isinstance(value,int) or isinstance(value,float):
#La partición se hace cuando se supera el valor
split_function = lambda row: row[column] >= value
else:
#Si no, la partición se hace si tiene el valor
split_function = lambda row: row[column] == value
#Conjunto uno cumple con el rasgo
set1 = [i for i,row in enumerate(X) if split_function(row)]
#Conjunto dos no cumple con el rasgo
set2 = [j for j,row in enumerate(X) if not split_function(row)]
return set1, set2
def uniqueCounts(rows):
"""
Función que cuenta las apariciones de un valor en los renglones.
Arguments
---------
rows : array
Renglones en los datos de entrada
Returns
-------
results : dict
Diccionario de valores y sus frecuencias
"""
#Guarda resultados
results = {}
for row in rows:
#revisa el valor anterior del renglón
r = row[len(row) - 1]
#print(r, len(row) - 1)
#Si no esta en resultados
if r not in results:
#Guarda el resultado actual
results[r] = 0
#Suma uno al resultado de r
results[r] += 1
return results
def print_tree(tree, indent = '\t'):
"""
Función para imprimir el árbol de forma jerárquica.
Arguments
---------
tree : object
Árbol que se desea visualizar
"""
# Imprime el resultado/clase
if tree.results != None:
print( list(tree.results.keys())[0] )
else:
#Imprime árbol
print(tree)
#Imprime ramas
print(indent + 'True->', end=" ")
print_tree(tree.tb, indent=indent+'\t')
print(indent + 'False->', end=" ")
print_tree(tree.fb, indent=indent+'\t')
Definimos además dos funciones que servirán para calcular la relevancia de las particiones realizadas:
- Entropía: $H(X_k) = \sum_{y\in X_k} p(y) \log p(y)$
- Gini Impurity: $G(X_k) = \sum_{y\in X_k} p(y)\big(1-p(y)\big)$
In [4]:
def entropy(classes):
"""
Función para cálculo de la entropía.
Arguments
---------
rows : array
Renglones de datos.
Returns
-------
Entropía total estimada.
"""
#Realiza conteos
results = Counter(classes)
#Guarda la entropía
H = 0.0
for r in results.keys():
#Calcula probabilidades
p = results[r]/len(classes)
#Calcula entropía
H -= p*np.log2(p)
return H
def giniimpurity(classes):
"""
Función para cálculo de la impureza de Gini.
Arguments
---------
rows : array
Renglones de datos.
Returns
-------
Impureza total estimada.
"""
#Total de clases en nodo
total = len(classes)
#Frecuencia de clases
counts = Counter(classes)
#Gini impurity
Gini = 0
for y, frec in counts.items():
#Probabilidad de clase
p = frec/total
#Suma valor de impureza
Gini += p*(1-p)
return Gini
Ahora definimos la clase para el modelo del árbol de decisión. Para construir el árbol de decisión se biparticionan los datos y se calcula la ganancia de información de esa bipartición:
$$IG(X,\phi) = H(X)-\mathbb{E}_{p\sim \phi}H(X|\phi)$$
Donde $\phi$ es un rasgo y $X$ son los datos actuales. En cada paso, se calcula la ganancia de información y se elige como nodo el rasgo $\phi$ que mayor ganancia aporte. Sus hijos responderán a los datos que tienen el valor del rasgo y aquellos que no. Se concluye el algoritmo hasta que todos los hijos pertenezcan a datos de una sola clase.
In [5]:
class DecisionTree():
"""
Clase para construcción del algoritmo de árbol de decisión.
"""
def __init__(self, score=entropy):
#El score con el que se calculará
#la ganancia
self.score = score
#El árbol que se ha obtenido
self.tree = None
def buildTree(self,X,Y):
"""
Función que construye el árbol de decisión en base a los datos.
Arguments
---------
X,Y : array
Dataset supervisado para entrenar y construir el árbol.
"""
#Tamaño y dimensión d de los datos
n,d = X.shape
#Calcula el valor de entropía o impureza
current_score = self.score(Y)
#Guarda ganancia
best_gain = 0.0
#Guarda mejor criterio
best_criteria = None
#Guarda conjuntos
best_sets = None
#Guarda las clases
best_classes = None
for feature in range(0, d):
#Guarda valores de columnas
feature_values = set([x[feature] for x in X])
for value in feature_values:
#Separa los conjuntos
set1, set2 = divideSet(X, feature, value)
#Calcula las probabilidades
p = float(len(set1))/len(X)
#Calcula la ganancia: Score - E[Score(sets)]
gain = current_score-p*self.score(Y[set1])-(1-p)*self.score(Y[set2])
#print(value, gain,self.score(Y[set1]), self.score(Y[set2]))
#Si la ganancia actual es mejor
if gain > best_gain and len(set1) > 0 and len(set2) > 0:
#La mejor ganancia es la actual
best_gain = gain
#Criterios son el valor de la columna
best_criteria = (feature, value)
#Guardas los mejores conjuntos
best_sets = (X[set1],X[set2])
#Clases
best_classes = (Y[set1],Y[set2])
#Revisa si la ganancia es mayor a 0
if best_gain > 0:
#Rama con valor 1 o T
trueBranch = self.buildTree(best_sets[0], best_classes[0])
#Rama con valor 0 o F
falseBranch = self.buildTree(best_sets[1], best_classes[1])
#Genera el nodo con los valores dados
return decisionnode(feat = best_criteria[0], value = best_criteria[1],
tb = trueBranch, fb = falseBranch)
#En otro caso
else:
return decisionnode(results = Counter(Y))
def fit(self,X,Y):
"""
Función para entrenar el árbol de decisión.
Arguments
---------
X,Y : array
Dataset supervisado para entrenar y construir el árbol.
"""
#Construye y guarda el árbol
self.tree = self.buildTree(X,Y)
def predict(self, observation, subtree=None):
"""
Función para predecir la clase según el árbol.
Arguments
---------
observation : array
Datos que se van a clasificar
Returns
-------
Clase predica por el árbol de decisión.
"""
#Revisa si el árbol no ha sido entrenado
if self.tree == None:
raise Exception('Debe entrenarse el árbol. Usar método fit(x,y)')
#Revisa cuál es el subárbol
if subtree == None:
tree = self.tree
else:
tree = subtree
if tree.results != None:
#Regresa la clase final
return list(tree.results.keys())[0]
else:
#Crea el ramaje para llegar a la clase
v = observation[tree.feat]
branch = None
if isinstance(v, int) or isinstance(v, float):
if v >= self.tree.value:
branch = tree.tb
else:
branch = tree.fb
else:
if v == tree.value:
branch = tree.tb
else:
branch = tree.fb
return self.predict(observation, branch)
def draw_tree(self):
#Imprime el árbol
print_tree(self.tree)
Aplicación del modelo¶
Podemos aplicar el modelo de árbol de decisión a datos simples donde tengamos valores categóricos.
In [6]:
#Datos de entrenamiento
x = np.array([['tos','fiebre', 'mareo'],
['no tos','fiebre','mareo'],
['tos','no fiebre','no mareo'],
['tos','fiebre','no mareo']])
#Clases de los datos
y = np.array(['gripe', 'no gripe', 'no gripe', 'gripe'])
#Creación del modelo
model = DecisionTree()
model.fit(x,y)
#Visualización del árbol
model.draw_tree()
Column 0: >=no tos? True-> no gripe False-> Column 1: >=fiebre? True-> gripe False-> no gripe
Un ejemplo más complejo¶
Tomamos los datos de iris de Sklearn que buscan predecir la clase de hojas. En este caso preparamos los datos y generamos el árbol de decisión.
In [7]:
#Separación de los datos
x_train, x_test, y_train, y_test = train_test_split(
load_iris().data, load_iris().target, test_size=0.3, random_state=540
)
#Creación y entrenamiento
tree = DecisionTree(score=entropy)
tree.fit(x_train, y_train)
#Visualización del árbol
tree.draw_tree()
Column 2: >=3.3? True-> Column 3: >=1.8? True-> 2 False-> Column 2: >=5.0? True-> Column 1: >=2.7? True-> 1 False-> 2 False-> 1 False-> 0
Finalmente, evaluamos el modelo:
In [8]:
#Predicción sobre dataset de evaluación
y_pred = [tree.predict(x) for x in x_test]
#Evaluación
print(classification_report(y_test, y_pred))
precision recall f1-score support
0 0.94 1.00 0.97 15
1 1.00 0.09 0.17 11
2 0.68 1.00 0.81 19
accuracy 0.78 45
macro avg 0.87 0.70 0.65 45
weighted avg 0.84 0.78 0.70 45