Árbol de decisión - Clasificación

Antes de empezar a estudiar árboles de decisión es importante conocer algunos conceptos importantes relacionados con el tema:

Aprendizaje Supervisado vs Aprendizaje no supervisado.

La mayoría de problemas de aprendizaje estadístico pueden ser clasificados dos categorías: Aprendizaje Supervisado y Aprendizaje No Supervisado.

Aprendizaje supervisado.

Para cada observación de las variables predictoras \(x_i~;~i=1,..,n\) existe una variable respuesta \(y_i\). Se desea ajustar un modelo de datos que relacione la variable respuesta \(y_i\) con las variables predictoras.

• Predicción: para futuras observaciones de individuos tratar de pronosticar con exactitud la respuesta.

• Inferencia: comprender mejor la relación entre la respuesta y las predictoras.

Algunos ejemplos de métodos de solución de problemas asociados con aprendizaje supervisado:

• Regresión lineal
• Regresión polinómica.
• Regresión Ridge.
• Regresión Lasso.
• Regresión logística.
• Árboles de decisión.
• Máquinas de soporte vectorial.
• Random Forest.
• K-Nearest Neighbors (KNN).
• Naive Bayes. …

Aprendizaje no supervisado.

Para cada observación \(i=1,..., n\), se tiene un vector \(x_i\), sin embargo, no se tiene asociado una variable respuesta \(y_i\) que permita supervisar algún ajuste.

Cuando se utiliza aprendizaje no supervisado se puede tratar de entender las relaciones entre variables o las relaciones entre las observaciones. Una herramienta de aprendizaje estadístico que podemos utilizar en este contexto es el análisis de conglomerados, o clustering. El objetivo del análisis de conglomerados es determinar, a partir del análisis de x1, . , xn , si las observaciones pertenecen a grupos relativamente distintos. Por ejemplo, en un estudio de segmentación de mercado podríamos observar múltiples características (variables) de los clientes potenciales, como el código postal, los ingresos familiares y los hábitos de compra. Podríamos pensar que los clientes pertenecen a grupos diferentes, como los que gastan mucho o los que gastan poco. Si se dispusiera de información sobre los patrones de gasto de cada cliente, sería posible realizar un análisis supervisado. Sin embargo, esta información no está disponible, es decir, no sabemos si cada cliente potencial es un gran gastador o no. En este caso, podemos intentar agrupar a los clientes en función de las variables medidas, con el fin de identificar distintos grupos de clientes potenciales. La identificación de estos grupos puede ser interesante porque es posible que difieran en alguna propiedad de interés, como los hábitos de gasto. Algunos métodos de aprendizaje no supervisado:

• K-means
• Clustering jerárquico.
• Análisis de componentes principales.
• Análisis discriminante no supervizado. …

Problemas de regresión vs Problemas de clasificación

Las variables pueden ser clasificadas como cuantitativas o cualitativas. Las variables cuantitativas toman valores numéricos: edad, estatura, ingreso, precio de una materia prima, costo de una vivienda. En contraste, las variables cualitativas toman valores en una de \(k\) clases o categorías diferentes: estado civil, marca de producto comprado, tipo de diagnóstico de una enfermedad.

En análisis de datos suele referirse a los problemas con variables respuesta cuantitativas como problemas de regresión, mientras que, a los problemas con variable respuesta cualitativa se consideran problemas de clasificaicón

Introducción a árboles de decisión

Los métodos basados en árboles consiste en segmentar el espacio (conjunto de posibles valores) de variables predictoras en una serie de espacios más simples .Dado que el conjunto de reglas de división usadas para segmentar el espacio de las variables predictoras puede resumirse y representarse en una árbol, este tipo de enfoque se conoce cómo métodos basados en árboles.

Los métodos basados en árboles son simples y útiles para interpretación, sin embargo, suelen no ser competitivos comparándose con otros métodos o enfoques de aprendizaje supervisado.

Árbol de decisión CART (Clasification and regression trees) para clasificación.

Funcionamiento del método.

Consideremos la siguiente muestra de datos de aprendizaje, Tabla 1:

Tabla 1: Datos ejemplo

Individuo	Reembolso de impuesto	Estado civil	Ingresos	¿Fraude?
1	si	soltero	125	no
2	no	casado	100	no
3	no	soltero	70	no
4	si	casado	120	no
5	no	divorciado	95	si
6	no	casado	60	no
7	si	divorciado	220	no
8	no	soltero	85	si
9	no	casado	75	no
10	no	soltero	90	si

Un modelo de árbol de decisión encontrado para los datos de la Tabla 1 es el mostrado en Figura 1

flowchart TD
  A[Reembolso] --> |Sí| B(No)
  A[Reembolso] --> |No| C[Estado civil]
  C[Estado civil] --> |Soltero-Divorciado| D[Ingresos]
  C[Estado civil] --> |Casado| E(No)
  D[Ingresos]  --> |<80| F(No)
  D[Ingresos]  --> |>80| G(Sí)
  
  style A fill:#f4b6f6
  style B fill:#b6daf6
  style C fill:#f4b6f6
  style D fill:#f4b6f6
  style E fill:#b6daf6
  style F fill:#b6daf6
  style G fill:#b6daf6

Figura 1: Modelo: árbol de decisión

El modelo de la Figura 1 anterior se puede usar para predecir la clase, valor de la variable respuesta, para una nueva observación.

¿Qué diría el modelo de la Figura 1 de un individuo que no se le ha realizado reembolso, casado y con ingresos mayores a 80? A la variable fraude se le asigna un “NO”.

Algunas preguntas que surgen del modelo de árbol de decisión observado en la Figura 1:

• ¿Por qué el nodo inicial corresponde a la variable reembolso?
• ¿Por qué el siguiente nodo de decisión corresponde a la variable estados civil?
• ¿Por qué la agrupación soltero - divorciado en la bifurcación del estado civil?
• ¿Por qué el punto de división de la variable ingresos es 80 si no corresponde a un valor estipulado en la tabla?

¿Cómo se puede construir un árbol de decisión? Algoritmo básico de HUNT.

Sea \(D_t\) el conjunto de registros de entrenamiento en un nodo \(t\) dado. Sea \(y_t = \{y_1,y_2,...,y_c \}\) el conjunto de etiquetas de las clases de la variable respuesta, entonces el algoritmo de Hunt propone:

• Si todos los registros \(D_t\) pertenecen a la misma clase \(y_t\) entonces \(t\) entonces \(t\) es un nodo hoja o nodos puros que se etiqueta como \(y_t\). Los nodos puros en donde todos los individuos pertenecen a una misma clase.

• Si \(D_t\) contiene registros que pertenecen a mas de una clase, se escoge una variable para dividir los datos en subconjuntos más pequeños.

• Se aplica de manera recursiva el procedimiento en cada subconjunto.

Un ejemplo de algoritmo de Hunt.

Paso 1:

Asumamos que la variable que inicia el árbol y se convierte en nodo inicial es el reembolso.

Observe en la Tabla 1 que las personas que si le han realizado reembolso no han cometido fraude. Por lo que se genera de esa manera un nodo hoja o nodo puro. La situación anterior se muestra en la Tabla 2 y en la Figura 2. Los individuos que cumplen la anterior condición serán excluidos de lo que sigue del análisis: individuos 1,4 y 7.

Tabla 2: Paso 1

Individuo	Reembolso de impuesto	Estado civil	Ingresos	¿Fraude?
1	si	soltero	125	no
2	no	casado	100	no
3	no	soltero	70	no
4	si	casado	120	no
5	no	divorciado	95	si
6	no	casado	60	no
7	si	divorciado	220	no
8	no	soltero	85	si
9	no	casado	75	no
10	no	soltero	90	si

flowchart TD
  A[Reembolso] --> |Sí| B[No fraude]
  A[Reembolso] --> |No| C[Fraude]
  
style B fill:#b6daf6

Figura 2: Árbol de decisión: paso 1

Paso 2:

Asumamos que la variable que sigue corresponde al estado civil. Observe que todos los individuos que tienen como estado civil casado tienen un no en el fraude. Por lo que se genera de esa manera un nodo hoja o nodo puro. La situación anterior se muestra en la Tabla 3 y en la Figura 3. Los individuos que cumplen la anterior condición serán excluidos de lo que sigue del análisis: individuos 2,6 y 9.

Tabla 3: Paso 2

Individuo	Reembolso de impuesto	Estado civil	Ingresos	¿Fraude?
1	si	soltero	125	no
2	no	casado	100	no
3	no	soltero	70	no
4	si	casado	120	no
5	no	divorciado	95	si
6	no	casado	60	no
7	si	divorciado	220	no
8	no	soltero	85	si
9	no	casado	75	no
10	no	soltero	90	si

flowchart TD
  A[Reembolso] --> |Sí| B[No fraude]
  A[Reembolso] --> |No| C[Estado civil]
  C[Estado civil] --> |Casado| D[No fraude]
  C[Estado civil] --> |Soltero, divorciado| E[Fraude]
  
style B fill:#b6daf6
style D fill:#b6daf6

Figura 3: Árbol de decisión: paso 2

Paso 3:

Asumamos que la variable que sigue corresponde a los ingresos anuales. Observe que todos los individuos que tienen ingresos mayores a 80, si hacen fraude. Los individuos con ingresos menores a 80, no hacen fraude. Por lo que se genera de esa manera dos nodos hoja o nodos puros. La situación anterior se muestra en la Tabla 4 y en la Figura 4.

Tabla 4: Paso 3

Individuo	Reembolso de impuesto	Estado civil	Ingresos	¿Fraude?
1	si	soltero	125	no
2	no	casado	100	no
3	no	soltero	70	no
4	si	casado	120	no
5	no	divorciado	95	si
6	no	casado	60	no
7	si	divorciado	220	no
8	no	soltero	85	si
9	no	casado	75	no
10	no	soltero	90	si

flowchart TD
  A[Reembolso] --> |Sí| B[No fraude]
  A[Reembolso] --> |No| C[Estado civil]
  C[Estado civil] --> |Casado| D[No fraude]
  C[Estado civil] --> |Soltero, divorciado| E[Ingresos]
  E[Ingresos] --> |<80| F[No fraude]
  E[Ingresos] --> |>80| G[Fraude]
  
style B fill:#b6daf6
style D fill:#b6daf6
style F fill:#b6daf6
style G fill:#b6daf6

Figura 4: Árbol de decisión: paso 3

¿Cómo aplicar el algoritmo de Hunt?

Se deben responder las siguientes preguntas:

1. ¿Cómo se dividen las variables?

Usando el método CART, se tendrán en cuenta solo divisiones binarias, tanto para predictores numéricos como para predictores categóricos.

Si las variables cualitativas nominales, Figura 5:

flowchart TD
  A[Tipo de carro] -->  B[Deportivo, Lujo]
  A[Tipo de carro] -->  C[Familiar]

Figura 5: Nominales

Si las variables cualitativas ordinales, no se viola el orden Figura 6:

flowchart TD
  A[Tamaño] -->  B[Pequeño]
  A[Tamaño] -->  C[Mediano, Grande]

Figura 6: Ordinales

Si las variables son cuantitativas suele usarse el punto medio, Figura 7:

flowchart TD
  A[Ingresos > 80k] -->  B[Si]
  A[Ingresos > 80k] -->  C[No]

Figura 7: Numérica

2. ¿Qué variables utilizar y en qué orden?

Cálculo de medidas de impureza.

Se puede considerar alguna de las siguientes medidas de impureza:

• Error de clasificación
• Índice de Gini
• Entropía

Para las 3 medidas de impureza normalmente usadas se defina \(p(j|t)\) como la probabilidad de pertenecer a la clase \(j\) estando en el nodo \(t\).

Para el error de clasificación se usa la ecuación Ecuación 1

\[\begin{align} Error(t) = 1- \max_{j}~[p~(j|t)] \end{align} \tag{1}\]

El índice de gini se calcula de la siguiente manera, Ecuación 2:

\[\begin{align} GINI (t)= 1- \sum_{j} [p~(j|t)] ^2 \end{align} \tag{2}\]

Y para la entropía se utiliza la Ecuación 3

\[\begin{align} Entropía (t)= - \sum_{j} p~(j|t) \log_2 p(j|t) \end{align} \tag{3}\]

Ejemplo cálculo de medidas de impureza.

Según la representación que se encuentra en el Figura 8. Calcule el error de clasificación, el índice de GINI y la entropía.

flowchart TD
  A[Padre] -->  B[Nodo N1]
  A[Padre] -->  c[Nodo N2]
  A[Padre] -->  D[Nodo N3]

Figura 8: Ejemplo cálculo medidas de impureza

La cantidad de individuos por nodo, \(N1, N2\) y \(N3\) así como la clase de la variable respuesta \(C1\) y \(C2\) se muestran en la Tabla 5

Tabla 5: Cálculo de medidas de impureza

	Nodo N1	Nodo N2	Nodo N3
C1	0	1	2
C2	6	5	4

Para el cálculo del error de clasificación por nodo, se tiene (recordar que \(j\) se refiere a la clase de la variable respuesta y \(t\) al nodo):

Para el nodo 1:

\[\begin{align} Error (N1) &= 1-\max \{ p(C1|N1),~P(C2|N1) \}\\ \\ Error (N1) &= 1-\max \left[ \frac{0}{6}, \frac{6}{6} \right] \\ \\ Error (N1) &= 1- \frac{6}{6} \\ \\ Error (N1) &= 0 \end{align}\]

Para el nodo 2:

\[\begin{align} Error (N2) &= 1-\max \{ p(C1|N2),~P(C2|N2) \}\\ \\ Error (N2) &= 1-\max \left[ \frac{1}{6}, \frac{5}{6} \right] \\ \\ Error (N2) &= 1- \frac{5}{6} \\ \\ Error (N2) &= \frac{1}{6} \\ \\ Error (N2) &= 0.1667 \end{align}\]

Para el nodo 3:

\[\begin{align} Error (N3) &= 1-\max \{ p(C1|N3),~P(C2|N3) \}\\ \\ Error (N3) &= 1-\max \left[ \frac{2}{6}, \frac{4}{6} \right] \\ \\ Error (N3) &= 1- \frac{2}{6} \\ \\ Error (N3) &= \frac{2}{6} \\ \\ Error (N3) &= 0.33334 \end{align}\]

Teniendo en cuenta el Error de clasificación el nodo con mayor pureza corresponde \(N1\), seguido por \(N2\) y \(N3\) respectivamente.

Para el cálculo del Coeficiente de GINI por nodo, se tiene

Para el nodo 1:

\[\begin{align} GINI (N1) &= 1-\sum_{j=1}^2 \left[ ~p(j|N1)~ \right]^2 \\ \\ GINI (N1) &= 1- p(C1|N1)^2 - P(C2|N1)^2 \\ \\ GINI (N1) &= 1 - \left( \frac{0}{6} \right)^2 - \left( \frac{6}{6} \right)^2 \\ \\ GINI (N1) &=0 \end{align}\]

Para el nodo 2:

\[\begin{align} GINI (N2) &= 1-\sum_{j=1}^2 \left[ ~p(j|N2)~ \right]^2 \\ \\ GINI (N2) &= 1- p(C1|N2)^2 - P(C2|N2)^2 \\ \\ GINI (N2) &= 1 - \left( \frac{1}{6} \right)^2 - \left( \frac{5}{6} \right)^2 \\ \\ GINI (N2) &= \frac{5}{18}\\ \\ GINI (N2) &= 0.277 \end{align}\]

Para el nodo 3:

\[\begin{align} GINI (N3) &= 1-\sum_{j=1}^2 \left[ ~p(j|N3)~ \right]^2 \\ \\ GINI (N3) &= 1- p(C1|N3)^2 - P(C2|N3)^2 \\ \\ GINI (N3) &= 1 - \left( \frac{2}{6} \right)^2 - \left( \frac{4}{6} \right)^2 \\ \\ GINI (N3) &= \frac{4}{9}\\ \\ GINI (N3) &= 0.444445 \end{align}\]

Teniendo en cuenta el Coeficiente de GINI el nodo con mayor pureza corresponde \(N1\), seguido por \(N2\) y \(N3\) respectivamente.

Para el cálculo de la entropía por nodo, se tiene

Para el nodo 1:

\[\begin{align} Entropía (N1) &= -\sum_{j=1}^2 p(j|N1)~ \log_2 (p(j|N1)) \\ \\ Entropía (N1) &= - \left[ p(C1|N1)\log_2 (p(C1|N1)) + p(C2|N1)\log_2 (p(C2|N1) \right]\\ \\ Entropía (N1) &= - \left[ \frac{0}{6} \log_2 \left( \frac{0}{6} \right)+ \frac{6}{6} \log_2 \left( \frac{6}{6} \right) \right]\\ \\ Entropía (N1) &= 0 \end{align}\]

Para el nodo 2:

\[\begin{align} Entropía (N2) &= -\sum_{j=1}^2 p(j|N2)~ \log_2 (p(j|N2)) \\ \\ Entropía (N2) &= - \left[ p(C1|N2)\log_2 (p(C1|N2)) + p(C2|N2)\log_2 (p(C2|N2) \right]\\ \\ Entropía (N2) &= - \left[ \frac{1}{6} \log_2 \left( \frac{1}{6} \right)+ \frac{5}{6} \log_2 \left( \frac{5}{6} \right) \right]\\ \\ Entropía (N2) &= 0.65002242 \end{align}\]

Para el nodo 3:

\[\begin{align} Entropía (N3) &= -\sum_{j=1}^2 p(j|N3)~ \log_2 (p(j|N3)) \\ \\ Entropía (N3) &= - \left[ p(C1|N3)\log_2 (p(C1|N3)) + p(C2|N3)\log_2 (p(C2|N3) \right]\\ \\ Entropía (N3) &= - \left[ \frac{2}{6} \log_2 \left( \frac{2}{6} \right)+ \frac{4}{6} \log_2 \left( \frac{4}{6} \right) \right]\\ \\ Entropía (N3) &= 0.91829583 \end{align}\]

Teniendo en cuenta la entropía el nodo con mayor pureza corresponde \(N1\), seguido por \(N2\) y \(N3\) respectivamente.

Cálculo de medidas split.

Posterior al cálculo de la medida de impureza seleccionada, ya sea Error de Clasificación, Coeficiente de GINI O Entropía. Se procede a calcular el Split para la medida de impureza usada. El split corresponde a un promedio ponderado de la medida de impureza por nodo.

El Error de Clasificación Split \(EC_{split}\) se calcula según la Ecuación 4

\[\begin{align} EC_{split} = \sum_{i=1}^k \frac{n_i}{n} EC(i) \end{align} \tag{4}\]

Donde:

• \(EC (i)\): error de clasificación para el nodo \(i\).
• \(n_i\): cantidad de individuos en el nodo \(i\).
• \(n\): total de individuos en todos los \(i\) nodos.

El *GINI split** \(GINI_{split}\) se calcula según la Ecuación 5

\[\begin{align} GINI_{split} = \sum_{i=1}^k \frac{n_i}{n} GINI(i) \end{align} \tag{5}\]

Donde:

• \(EC (i)\): coeficiente de GINI para el nodo \(i\).
• \(n_i\): cantidad de individuos en el nodo \(i\).
• \(n\): total de individuos en todos los \(i\) nodos.

La *Entropía split** \(Entropía_{split}\) se calcula según la Ecuación 6

\[\begin{align} Entropía_{split} = \sum_{i=1}^k \frac{n_i}{n} Entropía(i) \end{align} \tag{6}\]

Donde:

• \(EC (i)\): coeficiente de GINI para el nodo \(i\).
• \(n_i\): cantidad de individuos en el nodo \(i\).
• \(n\): total de individuos en todos los \(i\) nodos.

Ejemplo cálculo de \(GINI_{split}\).

Atendiendo a la Ecuación 5 el cálculo de \(GINI_{split}\) teniendo en cuenta los datos de la Tabla 5 y de la Figura 8. Y los cálculos de los Coeficientes de GINI que se resumen a continuación:

• \(GINI(1) = 0\)
• \(GINI(2) = \frac{5}{18}\)
• \(GINI(3) = \frac{4}{9}\)

La cantidad de individuos \(n_i\) por nodo \(i\) se resumen a continuación:

• \(n_1 = 6\)
• \(n_2 = 6\)
• \(n_3 = 6\)

Por lo que la cantidad total de individuos \(n=n_1+n_2+n_3=18\), por lo que el \(GINI_{split}\) se puede calcular de la siguiente manera:

\[\begin{align} GINI_{split} &= \left( \frac{6}{18}*0 \right) + \left( \frac{6}{18}*\frac{5}{18} \right) + \left( \frac{6}{18}*\frac{4}{9} \right)\\ \\ GINI_{split} &= 0,24074074 \end{align}\]

Cálculo de Información Ganada \(IG_{split}\).

Cada vez que se va a hacer una nueva división del árbol (split the tree) se debe comparar el grado de impureza del nodo padre respecto al grado de impureza de los nodos hijos. LO anterior se calcula con el Índice de Información Ganada \(IG_{split}\) que se muestra en la Ecuación 7

\[\begin{align} IG_{split} = I(padre) - \sum_{i=1}^k \frac{n_i}{n} I(i) \end{align} \tag{7}\]

Donde:

\(I\): indice de impureza utilizado: error de clasificación, GINI o entropía.

La idea es que el \(IG_{split}\) sea máximo y esto se logra si el promedio ponderado de las impurezas de los nodos hijos es mínimo.

Ejemplo cálculo de \(IG_{split}\).

Supongamos los siguientes datos para un nodo padre (Tabla 6):

Tabla 6: datos nodo padre ejemplo

	Nodo Padre
C1	7
C2	3

Supongamos igualmente la información de los nodos hijos son los siguientes, Tabla 7:

Tabla 7: datos nodos hijos ejemplo

	Nodo 1 - N1	Nodo 2 - N2
C1	3	4
C2	0	3

Gráficamente, Figura 9:

flowchart TD
  A[Padre] --> |Sí| B[Nodo N1]
  A[Padre] --> |No| c[Nodo N2]
 

Figura 9: Ejemplo cálculo medidas de impureza

Con los datos de la Tabla 6 se puede calcular el coeficiente de GINI para el nodo padre usando la Ecuación 2. Para luego poder calcular el \(IG_{split}\)

\[\begin{align} GINI(padre) &= 1- \left( \frac{7}{10} \right)^2 - \left( \frac{3}{10} \right)^2\\ \\ GINI(padre) &= 0.42 \end{align}\]

Se calcula el coeficiente de GINI para el Nodo 1

\[\begin{align} GINI(N1) &= 1- \left( \frac{3}{3} \right)^2 - \left( \frac{0}{3} \right)^2\\ \\ GINI(N1) &= 0 \end{align}\]

y el Nodo 2.

\[\begin{align} GINI(N2) &= 1- \left( \frac{4}{7} \right)^2 - \left( \frac{3}{7} \right)^2\\ \\ GINI(N2) &= \frac{24}{49} = 0.489795 \end{align}\]

Con el coeficiente de GINI de los nodos 1 y 2, podemos calcular el \(IG_{split}\) usando la Ecuación 7.

\[\begin{align} IG_{split} &= 0.42 - \frac{3}{10}*0 - \frac{7}{10}*0.49\\ \\ IG_{split} &= 0.077 \end{align}\]

La información ganada medida a partir del \(G_{split}\) es de \(0.077\). El propósito dentro del árbol es que la información ganada sea máxima. Lo anterior es equivalente a que el \(GINI_{split}\) sea mínimo.

¿Cómo escoger la mejor división?

Supongamos que se tiene que realizar la división de un nodo relacionado con la variable “Tipo de vehículo”, la variable es cuantitativa nominal con tres clases: Familiar, Deportivo, Lujo. Dos de las opciones de división de se muestran en la Figura 10 y la Figura 11

flowchart TD
  A[Tipo de vehículo] --> B[Deportivo - Lujoso]
  A[Tipo de vehículo] --> c[Familiar]

Figura 10: Posibles divisiones variable tipo de auto 1

flowchart TD
  A[Tipo de vehículo] --> B[Deportivo]
  A[Tipo de vehículo] --> c[Familiar - Lujoso]

Figura 11: Posibles divisiones variable tipo de auto 2

La información sobre las clases de la variable respuesta en las posibles divisiones consideradas se muestran en la Tabla 8 y la Tabla 9

Tabla 8: Datos de clase división 1

	Tipo de Vehículo
	Deportivo-Lujoso	Familiar
C1	9	7
C2	7	3

Tabla 9: Datos de clase división 2

	Tipo de vehículo
	Deportivo	Familiar - Lujoso
C1	8	2
C2	0	10

Con la información de Figura 10, Figura 11, Tabla 8 y Tabla 9 se pueden calcular los coeficientes de \(GINI\) y los \(GINI_{split}\) según la división 1 y la división 2 respectivamente, para la división 1 se tiene que:

\[\begin{align} GINI(N1-opción1) &= 1- \left( \frac{9}{16} \right)^2 - \left( \frac{7}{16} \right)^2\\ \\ GINI(N1-opción1) &= 0.4921875\\ \\ GINI(N2-opción1) &= 1- \left( \frac{1}{4} \right)^2 - \left( \frac{3}{4} \right)^2\\ \\ GINI(N2-opción1) &= 0.375\\ \\ GINI_{split} &= \left( \frac{16}{26}*\frac{126}{256} \right) + \left( \frac{10}{26}*\frac{3}{8} \right)\\ \\ GINI_{split} &= 0.4594278 \end{align}\]

Para la división 2, se tiene que:

\[\begin{align} GINI(N1-opción2) &= 1- \left( \frac{8}{8} \right)^2 - \left( \frac{0}{8} \right)^2\\ \\ GINI(N1-opción2) &= 0\\ \\ GINI(N2-opción2) &= 1- \left( \frac{2}{12} \right)^2 - \left( \frac{10}{12} \right)^2\\ \\ GINI(N2-opción2) &= 0.277777\\ \\ GINI_{split} &= \left( \frac{8}{20}*0 \right) + \left( \frac{12}{20}*\frac{40}{144} \right)\\ \\ GINI_{split} &= 0.16666 \end{align}\]

Al analizar las divisiones propuestas se escoge la división que bifurca el nodo Tipo de vehículo en un nodo para Vehículos deportivos y otro para Vehículos familiares y lujosos.

¿Por qué se escoge reembolso como variable inicial?

Calculemos los coeficientes de \(GINI\) como medida de impureza y los \(GINI_{split}\) para cada uno de las variables predictoras mostradas en Tabla 1. Empecemos con la variable Reembolso.

La variable predictora Reembolso se puede bifurcar en Sí y en No. Produciendo las siguientes clases por nodo para la variable respuesta, Tabla 10 y Tabla 11.

Tabla 10: Datos de clase variable reembolso - Rama Sí

¿Fraude?	Cantidad individuos
Sí	0
No	3

Tabla 11: Datos de clase variable reembolso - Rama No

¿Fraude?	Cantidad individuos
Sí	3
No	4

De las Tabla 10 y Tabla 11 se puede calcular el coeficiente de \(GINI\) para el nodo Si y para el nodo No así como el \(GINI_{split}\), como se muestra a continuación:

\[\begin{align} GINI(Sí) &= 1 - \left( \frac{0}{3} \right)^2 - \left( \frac{3}{3} \right)^2\\ \\ GINI(Sí) &= 0 \end{align}\]

\[\begin{align} GINI(No) &= 1 - \left( \frac{3}{7} \right)^2 - \left( \frac{4}{7} \right)^2\\ \\ GINI(No) &= 0,489795 \end{align}\] \[\begin{align} GINI_{split} &= \left( \frac{3}{10} * 0 \right) + \left( \frac{7}{10} * 0,489795 \right) \\ \\ GINI_{split} &=0,3428571 \end{align}\]

Pasemos a la variable Estado civil. La variable predictora estado civil se puede bifurcar de distintas maneras, vamos a agrupar en Soltero-Dirvorciado en un nodo y Casado en otro nodo, ya se estudió la forma de escoger una división para los nodos. Produciendo las siguientes clases por nodo para la variable respuesta, Tabla 12 y Tabla 13.

Tabla 12: Datos de clase variable estado civil - Rama Soltero - Divorciado

¿Fraude?	Cantidad de individuos
Sí	3
No	3

Tabla 13: Datos de clase variable estado civil - Rama casado

¿Fraude?	Cantidad de individuos
Sí	0
No	4

De las Tabla 12 y Tabla 13 se puede calcular el coeficiente de \(GINI\) para el nodo Soltero - Divorciado y para el nodo Casado así como el \(GINI_{split}\), como se muestra a continuación:

\[\begin{align} GINI(Soltero - Divorciado) &= 1 - \left( \frac{3}{6} \right)^2 - \left( \frac{3}{6} \right)^2\\ \\ GINI(Soltero - Divorciado) &= 0.5 \end{align}\]

\[\begin{align} GINI(Casado) &= 1 - \left( \frac{0}{4} \right)^2 - \left( \frac{4}{4} \right)^2\\ \\ GINI(Casado) &= 0 \end{align}\]

\[\begin{align} GINI_{split} &= \left( \frac{6}{10} * 0.5 \right) + \left( \frac{4}{10} * 0 \right) \\ \\ GINI_{split} &=0,3 \end{align}\]

Entre las dos nodos anteriores se debe escoger la variable Estado Civil como el nodo a dividir. El árbol mostrado al inicio para explicar el funcionamiento presenta dicho error

3. ¿Cuándo dejar de dividir? Es decir, ¿Cuándo termina el algoritmo?

Es una respuesta muy complicada, implica la selección del modelo. Se suele extender el algoritmo hasta que todos los nodos se conviertan en nodos puros.

Una idea es controlar la medida de impureza de manera que se pueda detener la división cuando el índice escogido comience a aumentar

Los autores de los árboles CART sugieren utilizar un enfoque de poda o pruning este enfoque suele ser el más usado.

La poda funciona de la siguiente manera.

Para cada nodo \(v\) del árbol hacer los pasos \(1\) y \(2\)

Paso1: para \(j=1,2,...,p\) \(p=~número~de~variables\)

• Calcular todas las divisiones binarias correspondientes a \(y\)

• Calcular la división binaria óptima \(d(j)\) correspondiente a la variable \(y\), es decir, la división binaria que maximiza el descenso de la impureza.

Paso 2: recursivamente calcular la mejor división binaria para \(d(1), d(2),..., d(p)\).

Árbol de decisión usando RStudio

Se usará para el ejemplo una base de datos de tipo de vino de un productor interesado en clasificar entre tres tipos de vino de acuerdo con características físico-químicas.

Lectura de datos

Leeremos los datos desde un archivo \(*.txt\) separado por comas y con separación de decimales separados por puntos. Guardaremos dicha información en un data frame llamado “datos”:

datos <- read.csv(file = "data_wine.csv",sep=";", dec=".", header=TRUE)

Generalidades de los datos

Observemos la generalidades de la base de datos:

datos <- read.csv(file = "data_wine.csv",sep=";", dec=".", header=TRUE)
summary(datos)

      tipo          alcohol      acido_malico      cenizas     
 Min.   :1.000   Min.   :  12   Min.   :0.740   Min.   :  2.0  
 1st Qu.:1.000   1st Qu.:1210   1st Qu.:1.603   1st Qu.:192.0  
 Median :2.000   Median :1285   Median :1.865   Median :228.0  
 Mean   :1.938   Mean   :1172   Mean   :2.336   Mean   :190.3  
 3rd Qu.:3.000   3rd Qu.:1358   3rd Qu.:3.083   3rd Qu.:248.0  
 Max.   :3.000   Max.   :1483   Max.   :5.800   Max.   :323.0  
 alcalinidad_ceniza    magnesio      fenoles_totales  flavonoides   
 Min.   : 12.0      Min.   : 70.00   Min.   :0.980   Min.   :0.340  
 1st Qu.: 20.0      1st Qu.: 88.00   1st Qu.:1.742   1st Qu.:1.205  
 Median :113.0      Median : 98.00   Median :2.355   Median :2.135  
 Mean   :107.5      Mean   : 99.74   Mean   :2.295   Mean   :2.029  
 3rd Qu.:188.0      3rd Qu.:107.00   3rd Qu.:2.800   3rd Qu.:2.875  
 Max.   :285.0      Max.   :162.00   Max.   :3.880   Max.   :5.080  
 fenoles_no_flavonoides proactocianinas intensidad_color    tonalidad     
 Min.   :0.1300         Min.   :0.410   Min.   :      2   Min.   :0.4800  
 1st Qu.:0.2700         1st Qu.:1.250   1st Qu.:     45   1st Qu.:0.7825  
 Median :0.3400         Median :1.555   Median :     90   Median :0.9650  
 Mean   :0.3619         Mean   :1.591   Mean   :  55872   Mean   :0.9574  
 3rd Qu.:0.4375         3rd Qu.:1.950   3rd Qu.:    427   3rd Qu.:1.1200  
 Max.   :0.6600         Max.   :3.580   Max.   :9899999   Max.   :1.7100  
 DO280_OD315_de_vinos_diluidos    prolina      
 Min.   :  2.0                 Min.   : 278.0  
 1st Qu.:167.2                 1st Qu.: 500.5  
 Median :260.0                 Median : 673.5  
 Mean   :230.0                 Mean   : 746.9  
 3rd Qu.:312.0                 3rd Qu.: 985.0  
 Max.   :392.0                 Max.   :1680.0  

Determinación de variable respuesta como factor

La variable respuesta “Tipo” le cambiamos el tipo de objeto a factor.

datos <- read.csv(file = "data_wine.csv",sep=";", dec=".", header=TRUE)
datos$tipo <- as.factor(datos$tipo)

Entrenamiento del modelo

Cargamos las librerías necesarias

library(tidyverse)
library(rpart)
library(rpart.plot)
library(caret)

Dividimos la base de datos en entrenamiento y prueba para poder evaluar la calidad de la clasificación. Usamos la función \(sample_frac\) de \(dplyr\) para obtener un conjunto de datos aleatorio de la base de datos origina. Usamos la función \(set.seed()\) para que la semilla sea la misma y el ejemplo reproducible. El \(70\%\) de los datos conformarán la base de datos para el entrenamiento del árbol.

set.seed(1649)
datos_entrenamiento <- sample_frac(datos, .7)

Para obtener la base de datos de prueba usamos la función \(setdiff\) de \(dplyr\), con esta función se obtiene el conjunto de datos complementario a los datos del entrenamiento.

datos_prueba <- setdiff(datos,datos_entrenamiento)

Procedemos al entrenamiento del modelo usando la biblioteca \(rpart\), el modelo entrenado lo guardaremos en un objeto llamado \(arbol1\). El argumento \(formula\) enxige que coloquemos nuestra variable respuesta en términos de las variables que deseamos utilizar para el árbol

arbol1 <- rpart(formula =tipo~ ., data=datos_entrenamiento)

Podemos imprimir el modelo entrenado.

arbol1 <- rpart(formula =tipo~ ., data=datos_entrenamiento)
arbol1

n= 125 

node), split, n, loss, yval, (yprob)
      * denotes terminal node

1) root 125 75 2 (0.35200000 0.40000000 0.24800000)  
  2) prolina>=755 48  6 1 (0.87500000 0.04166667 0.08333333)  
    4) flavonoides>=2.35 41  1 1 (0.97560976 0.02439024 0.00000000) *
    5) flavonoides< 2.35 7  3 3 (0.28571429 0.14285714 0.57142857) *
  3) prolina< 755 77 29 2 (0.02597403 0.62337662 0.35064935)  
    6) flavonoides>=1.265 51  4 2 (0.03921569 0.92156863 0.03921569) *
    7) flavonoides< 1.265 26  1 3 (0.00000000 0.03846154 0.96153846) *

Lo anterior muestra el esquema de nuestro árbol de clasificación. Cada inciso nos indica un nodo y la regla de clasificación que le corresponde. Siguiendo estos nodos, podemos llegar a las hojas del árbol, que corresponde a la clasificación de nuestros datos.

Todo lo anterior resulta mucho más claro si lo visualizamos, así que creamos una gráfica usando nuestro modelo con la función \(rpart.plot()\) de \(rpart.plot\).

arbol1 <- rpart(formula =tipo~ ., data=datos_entrenamiento)
rpart.plot(arbol1)

En estos gráficos, cada uno de los rectángulos representa un nodo de nuestro árbol, con su regla de clasificación.

Cada nodo está coloreado de acuerdo a la categoría mayoritaria entre los datos que agrupa. Esta es la categoría que ha predicho el modelo para ese grupo.

Dentro del rectángulo de cada nodo se nos muestra qué proporción de casos pertenecen a cada categoría y la proporción del total de datos que han sido agrupados allí. Por ejemplo, el rectángulo en el extremo inferior izquierdo de la gráfica tiene \(98\%\) de casos en el \(tipo~1\), \(2\%\) en los \(tipo~2\) y \(0\%\) en \(tipo~3\), que representan \(33\%\) de todos los datos.

Estas proporciones nos dan una idea de la precisión de nuestro modelo al hacer predicciones. De este modo, las reglas que conducen al rectángulo que acabamos de mencionar nos dan un \(98\%\) de clasificaciones correctas. En contraste, el segundo rectángulo, de izquierda a derecha, tuvo sólo \(57\%\) de clasificaciones correctas.

Evaluación del modelo

Usamos la función \(predict()\) con nuestro set de prueba para generar un vector con los valores predichos por el modelo que hemos entrenado, especificamos el parámetro \(type = "class"\) entendiendo que estamos en un modelo de clasificación. Guardamos el vector de predicciones en un objeto llamado \(predeccion1\)

prediccion1 <- predict(arbol1, newdata=datos_prueba, type="class")

Construimos la matriz de confusión usando \(confusionMatrix()\) de \(caret\).

datos_prueba$tipo <- as.factor(datos_prueba$tipo)
confusionMatrix(data = prediccion1, reference = datos_prueba$tipo)

Confusion Matrix and Statistics

          Reference
Prediction  1  2  3
         1 15  0  0
         2  0 15  3
         3  0  6 14

Overall Statistics
                                         
               Accuracy : 0.8302         
                 95% CI : (0.702, 0.9193)
    No Information Rate : 0.3962         
    P-Value [Acc > NIR] : 1.106e-10      
                                         
                  Kappa : 0.7444         
                                         
 Mcnemar's Test P-Value : NA             

Statistics by Class:

                     Class: 1 Class: 2 Class: 3
Sensitivity             1.000   0.7143   0.8235
Specificity             1.000   0.9062   0.8333
Pos Pred Value          1.000   0.8333   0.7000
Neg Pred Value          1.000   0.8286   0.9091
Prevalence              0.283   0.3962   0.3208
Detection Rate          0.283   0.2830   0.2642
Detection Prevalence    0.283   0.3396   0.3774
Balanced Accuracy       1.000   0.8103   0.8284

Matriz de confusión \(3\text{x}3\) para el ejemplo

La matriz de confusión del ejemplo corresponde a una matriz \(3x3\) organizada de la siguiente manera, Tabla 14:

Tabla 14: Ejemplo matriz de confusión \(3\text{x}3\)

Predicción	Real A	Real B	Real C
Predicción A	VP (A,A)	FP (A,B)	FP (A,C)
Predicción B	FN (B,A)	VP (B,B)	FP (B,C)
Predicción C	FN (C,A)	FN (C,B)	VP (C,C)

Miremos las métricas

Accuracy (exattitud)

La exactitud (o accuracy) es una métrica que mide qué tan bien un modelo clasifica correctamente. Esto refleja el porcentaje total de predicciones correctas para todas las clases.

\[\begin{align} Global~Accuracy= \frac{\sum TP}{Total~casos} \end{align}\]

Para el ejemplo usado el \(Global~Accuracy\) se calcula de la siguiente forma

\[\begin{align} Global~Accuracy= \frac{15+15+14}{15+15+14+6+3} = \frac{44}{53} = 0.8302 \end{align}\]

Sensitivity (Recall)

La sensibilidad o recall indica qué tan bien el modelo captura o detecta los casos positivos. Es particularmente útil cuando los falsos negativos son costosos o peligrosos. Un valor alto de sensibilidad significa que el modelo comete pocos falsos negativos.

Para una matriz de confusión con más de dos clases, calculamos la sensibilidad de cada clase individualmente. La sensibilidad se calcula para cada clase en función de cuántos casos de esa clase se identificaron correctamente entre todos los casos que realmente pertenecen a esa clase.

\[\begin{align} Sensitivity_i= \frac{TP_i}{TP_i+FN_i} \end{align}\]

• \(TP_i\): Verdaderos Positivos de la \(clase~i\), es decir, los casos donde el modelo predijo correctamente la \(clase~i\).
• \(FN_i\): Falsos Negativos de la \(clase~i\), es decir, los casos donde la clase real era \(i\), pero fueron clasificados incorrectamente.

El cálculo de la sensitivity para las tres clases del ejemplo es la siguiente

Para clase vino tipo 1

\(TP_1 = 15\)

\(FN_1= 0\)

Por lo tanto:

\[\begin{align} Sensitivity_1= \frac{15}{15+0} = 1 \end{align}\]

Para clase vino tipo 2

$TP_2 = 15 $

\(FN_2= 6\)

\[\begin{align} Sensitivity_2= \frac{15}{15+6} = 0.7143 \end{align}\]

Para clase vino tipo 3

\(TP_3 = 14\)

\(FN_3= 3\)

\[\begin{align} Sensitivity_3= \frac{14}{14+3} = 0.8231 \end{align}\]

Specificity

Es una métrica que mide la capacidad de un modelo para identificar correctamente los casos negativos entre todos los casos que son realmente negativos. En otras palabras, mide la proporción de verdaderos negativos que el modelo clasifica correctamente como negativos.

Mide la capacidad de un modelo para identificar correctamente las instancias que no pertenecen a una clase específica. Es decir, la especificidad evalúa cuántos de los negativos fueron correctamente clasificados como negativos.

Para una matriz de confusión con más de dos clases, calculamos la especificidad de cada clase individualmente. La especificidad se calcula para cada clase considerando como “negativo” todos los casos que no pertenecen a esa clase en particular.

\[\begin{align} Specificity_i= \frac{TN_i}{TN_i+FP_i} \end{align}\]

• \(TN_i\): Verdaderos Negativos de la \(clase~i\), es decir,casos que pertenecen a otras clases y fueron correctamente clasificados como tales.

• \(FP_i\): Falsos Positivos de la \(clase~i\), es decir, los casos que pertenecen a las otras clases, pero fueron incorrectamente clasificados como de la \(clase~i\).

El cálculo de la specificity para las tres clases del ejemplo es la siguiente

Para clase vino tipo 1

\(TN_1 = 15+3+6+14\)

\(FP_1= 0\)

Por lo tanto:

\[\begin{align} Specificity_1= \frac{15+3+6+14}{15+3+6+14+0} = 1 \end{align}\]

Para clase vino tipo 2

\(TN_2 = 15+14\)

\(FP_2= 3\)

Por lo tanto:

\[\begin{align} Specificity_2= \frac{15+14}{15+14+3} = \frac{29}{32} = 0.9062 \end{align}\]

Para clase vino tipo 3

\(TN_3 = 15+15\)

\(FP_3= 6\)

\[\begin{align} Specificity_3= \frac{15+15}{6} = 0.833 \end{align}\]

Sin embargo, no hemos terminado. Este árbol ha predicciones a partir de los datos de entrenamiento que hemos proporcionado. ¿Recuerdas que el algoritmo busca la mejor separación para crear grupos? Si nuestros datos cambian, la variable que hace la mejore separación también puede cambiar. Y por lo tanto, los grupos que resulten de esta separación, serán distintos, resultando en un modelo que puede ser muy distinto al que hemos obtenido.

Generamos un segundo árbol, usando sets de entrenamiento y prueba diferentes.

library(tidyverse)
library(rpart)
library(rpart.plot)
library(caret)

datos <- read.csv(file = "data_wine.csv",sep=";", dec=".", header=TRUE)
datos$tipo <- as.factor(datos$tipo)

set.seed(5985)
datos_entrenamiento_2 <- sample_frac(datos, .7)
datos_prueba_2 <- setdiff(datos,datos_entrenamiento_2)
arbol_2 <- rpart(formula =tipo~ ., data=datos_entrenamiento_2)
rpart.plot(arbol_2)

prediccion_2 <- predict(arbol_2, newdata=datos_prueba_2, type="class")
datos_prueba_2$tipo <- as.factor(datos_prueba_2$tipo)
confusionMatrix(data = prediccion_2, reference = datos_prueba_2$tipo)

Confusion Matrix and Statistics

          Reference
Prediction  1  2  3
         1 19  0  0
         2  0 20  1
         3  0  2 11

Overall Statistics
                                          
               Accuracy : 0.9434          
                 95% CI : (0.8434, 0.9882)
    No Information Rate : 0.4151          
    P-Value [Acc > NIR] : 3.949e-16       
                                          
                  Kappa : 0.9131          
                                          
 Mcnemar's Test P-Value : NA              

Statistics by Class:

                     Class: 1 Class: 2 Class: 3
Sensitivity            1.0000   0.9091   0.9167
Specificity            1.0000   0.9677   0.9512
Pos Pred Value         1.0000   0.9524   0.8462
Neg Pred Value         1.0000   0.9375   0.9750
Prevalence             0.3585   0.4151   0.2264
Detection Rate         0.3585   0.3774   0.2075
Detection Prevalence   0.3585   0.3962   0.2453
Balanced Accuracy      1.0000   0.9384   0.9339

Esta vez hemos obtenido un accuracy mejor.Nótese que es un modelo distinto. Si cambiamos los datos de entrenamiento y prueba, seguiremos obteniendo árboles distintos.

library(tidyverse)
library(rpart)
library(rpart.plot)
library(caret)

datos <- read.csv(file = "data_wine.csv",sep=";", dec=".", header=TRUE)
datos$tipo <- as.factor(datos$tipo)

set.seed(6875)
datos_entrenamiento_3 <- sample_frac(datos, .7)
datos_prueba_3 <- setdiff(datos,datos_entrenamiento_3)
arbol_3 <- rpart(formula =tipo~ ., data=datos_entrenamiento_3)
rpart.plot(arbol_3)

prediccion_3 <- predict(arbol_3, newdata=datos_prueba_3, type="class")
datos_prueba_3$tipo <- as.factor(datos_prueba_3$tipo)
confusionMatrix(data = prediccion_3, reference = datos_prueba_3$tipo)

Confusion Matrix and Statistics

          Reference
Prediction  1  2  3
         1 15  1  0
         2  0 19  2
         3  1  3 12

Overall Statistics
                                          
               Accuracy : 0.8679          
                 95% CI : (0.7466, 0.9452)
    No Information Rate : 0.434           
    P-Value [Acc > NIR] : 6.795e-11       
                                          
                  Kappa : 0.799           
                                          
 Mcnemar's Test P-Value : 0.5319          

Statistics by Class:

                     Class: 1 Class: 2 Class: 3
Sensitivity            0.9375   0.8261   0.8571
Specificity            0.9730   0.9333   0.8974
Pos Pred Value         0.9375   0.9048   0.7500
Neg Pred Value         0.9730   0.8750   0.9459
Prevalence             0.3019   0.4340   0.2642
Detection Rate         0.2830   0.3585   0.2264
Detection Prevalence   0.3019   0.3962   0.3019
Balanced Accuracy      0.9552   0.8797   0.8773

Función \(rpart\)

La función rpart en R es utilizada para construir árboles de decisión. Esta función forma parte del paquete \(rpart\) y ofrece una amplia gama de opciones para controlar el crecimiento, la complejidad y los criterios de división del árbol. A continuación, te mostraré las opciones más importantes.

rpart(formula, data, method = "class", control = rpart.control(...))

Argumentos principales:

1. formula: La fórmula que define la variable dependiente (respuesta) y las variables independientes (predictoras). La fórmula se especifica como respuesta ~ predictor1 + predictor2 + ... + predictor~k

2. data: El conjunto de datos que contiene las variables en la fórmula.

3. method: Especifica el tipo de árbol que se va a construir. Las opciones son:

• "class": Para clasificación (cuando la variable de respuesta es categórica).

• "anova: Para regresión (cuando la variable de respuesta es continua).

4. control: Este argumento permite controlar varios aspectos del ajuste del árbol a través de la función rpart.control(). Estos son algunos de los parámetros más importantes dentro de rpart.control():

• minsplit: El número mínimo de observaciones que debe tener un nodo antes de dividirse. Valor por defecto: 20.

• minbucket: El tamaño mínimo que puede tener un nodo terminal. Valor por defecto: un tercio de minsplit.

• cp: El parámetro de complejidad. Se utiliza para controlar el tamaño del árbol, podando los nodos que no mejoran el error lo suficiente. Valor por defecto: 0.01.

• maxcompete: El número de variables competidoras que se mostrarán en cada nodo.

• maxsurrogate: El número de variables sustitutas a utilizar.

• usesurrogate: Controla el uso de variables sustitutas en las divisiones.

Valores: 0: Solo divide si no hay valores perdidos. 1: Se usan las sustitutas cuando faltan valores en la variable de división. 2: Se usan las sustitutas siempre que sea posible.

• xval: El número de validaciones cruzadas a realizar. Valor por defecto: 10.

• surrogatestyle: Controla cómo se eligen las variables sustitutas:

0: Minimiza la tasa de error. 1: Maximiza la coincidencia con la variable original.

• maxdepth: La profundidad máxima del árbol. Valor por defecto: 30.

5. Otros argumentos:

parms: Parámetros adicionales dependiendo del tipo de árbol (clasificación, regresión, etc.). Por ejemplo, en clasificación se puede especificar la matriz de pérdida. weights: Ponderaciones para las observaciones en los datos.