\documentclass[mathserif]{beamer} % antiambiguo \usepackage[spanish]{babel}\spanishdecimal{\raisebox{1.2ex}{,}} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usetheme{Hannover} \usepackage{microtype}\DisableLigatures[f]{ encoding = *, family = * } \usepackage[scaled=.9]{heuristica} % antiambiguo y graso \usepackage[varqu,varl,scale=.9]{inconsolata} % comillas rectas, ele moderna \usepackage[heuristica]{newtxmath} \usepackage{amsmath, amssymb} % chatgpt para appendix \newcommand{\Prob}{\Pr} \newcommand{\Eta}{{\rm H}} \usepackage{tikz} \usetikzlibrary{decorations.pathreplacing,positioning} \begin{document} \title{Árboles de decisión} \author{N. Corral,\\B. Sinova,\\C. Carleos} \frame{\titlepage} \frame{\tableofcontents} \section{Ejemplo} <>= options (width = 55) options (digits = 4) options (OutDec = "'") setHook("before.plot.new", function() { par(family="serif", cex=1.3, reset=TRUE) }) @ \begin{frame}[fragile]\frametitle{} <<>>= summary (iris) @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= boxplot (Petal.Length ~ Species, iris) @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= boxplot (Petal.Width ~ Species, iris) @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= boxplot (Sepal.Length ~ Species, iris) @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= boxplot (Sepal.Width ~ Species, iris) @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= plot (Petal.Length ~ Petal.Width, iris, col=Species) legend ("bottomright", legend=levels(iris$Species), pch=1, col=1:3) @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= plot (Petal.Length ~ Petal.Width, iris, col=Species) abline (h=2.5, col=4) text (1.5, 1.5, "setosa") @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= plot (Petal.Length ~ Petal.Width, iris, col=Species) abline (h=2.5, col=4) segments (1.65, 2.5, , 99, col=4) text (1.5, 1.5, "setosa") text (2.2, 3.5, "virginica") text (0.5, 3.5, "versicolor") @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= plot (Petal.Length ~ Petal.Width, iris, col=Species) abline (h=2.5, col=4) segments (1.65, 2.5, , 99, col=4) segments (1.65, 4.95, -99, , col=4) text (1.5, 1.5, "setosa") text (2.2, 3.5, "virginica") text (0.5, 3.5, "versicolor") text (0.5, 6, "virginica") @ \end{frame} \begin{frame}[fragile]\frametitle{} <<>>= library (rpart.plot) # basta rpart para cálculos árbol <- rpart (Species ~ Petal.Length + Petal.Width, iris) árbol @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= plot (Petal.Length ~ Petal.Width, iris, col=Species) abline (h=2.5, col=4) segments (1.65, 2.5, , 99, col=4) text (1.5, 1.5, "setosa") text (2.2, 3.5, "virginica") text (0.5, 3.5, "versicolor") @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= prp (árbol) @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= prp (árbol, yes.text="verdadero", no.text="falso") @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= prp (árbol, type=3) @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= prp (árbol, type=4) @ \end{frame} \section{Generalidades} \begin{frame}\frametitle{Nomenclatura} \begin{itemize} \item predictores: \(X_1, \dots, X_p\) \item respuesta: \(Y\) \begin{itemize} \item cualitativa: árbol de clasificación \item cuantitativa: árbol de regresión \end{itemize} \item el árbol consta de \emph{ramas} \item cada rama nace de un \emph{nodo} o \emph{nudo} \begin{itemize} \item cada nodo representa un subconjunto de la muestra \item la muestra completa es el nodo \emph{raíz} \item los nodos finales se llaman \emph{hojas}; \\ representan una partición de la muestra \end{itemize} \item nodo \(t\): regla de decisión asociada a cierta \(X_i\) \begin{itemize} \item \(X_i\) cuantitativa: ¿ \(X_i\leq c_t\) ? \item \(X_i\) cualitativa: ¿ \(X_i\in A_{it}\) \(\subset\) \(\{a_1,...,a_m\}\) = \(\{\text{valores de }X_i\}\) ? \end{itemize} \end{itemize} \end{frame} \begin{frame}[fragile]\frametitle{Árbol con predictor cualitativo} <<>>= library (carData) rpart (vote ~ region + age, Chile) @ \end{frame} \begin{frame}\frametitle{Algoritmos} \begin{description} \item [CHAID] 1980. CHi\(^2\) Automatic Interaction Detection. Ramificaciones múltiples. Sólo clasificación. \item [CART] 1984. Classification And Regression Trees. Ramificaciones binarias. Base de bosques aleatorios. \item [ID3\(\rightarrow\)C4.5] 1986-93. El más popular en Weka (llamado J48). Ramificaciones múltiples. Sólo para clasificación. Existe C5.0 pero resultados similares a CART. \item [MARS] 1991. Multivariate Adaptive Regression Splines (lineal a trozos). Sólo regresión. \emph{Alisador} de CART. \item [CIT] 2006. Conditional Inference Trees. Basado en contrastes de independencia. Soslaya sobreajustes. \end{description} \end{frame} \begin{frame}\frametitle{Elementos para la construcción} \begin{itemize} \item método para elegir hoja candidata a división \begin{itemize} \item impureza \end{itemize} \item criterio de parada \begin{itemize} \item riesgo \item \texttt{cp} (parámetro de complejidad) \item poda \end{itemize} \item método para asignar a un nodo una predicción \begin{itemize} \item clasificación: moda \item regresión: media \end{itemize} \end{itemize} \end{frame} % \begin{frame}\frametitle{Notación de los nodos} % \begin{itemize} % \item \(t\) un cierto nodo % \item \(t_L\) nodo hijo izquierdo % \item \(t_R\) nodo hijo derecho % \item \(T\) conjunto de las hojas del árbol % \end{itemize} % \end{frame} \begin{frame}\frametitle{Notación de los nodos} \begin{columns} \begin{column}{0.6\textwidth} \begin{itemize} \item \(t\) un cierto nodo \item \(t_L\) nodo hijo izquierdo \item \(t_R\) nodo hijo derecho\vspace{4cm} \item \(T\) conjunto de las hojas del árbol \end{itemize} \end{column} \begin{column}{0.4\textwidth} \centering % Gráfico 1: notación padre-hijos (sin hojas) \begin{tikzpicture}[level distance=1.2cm, level 1/.style={sibling distance=2cm}, every node/.style={circle, draw, minimum size=0.7cm, inner sep=0pt}] \node (t) {\(t\)} child { node (tL) {\(t_L\)} } child { node (tR) {\(t_R\)} }; \end{tikzpicture} \bigskip % Gráfico 2: árbol con hojas \begin{tikzpicture}[level distance=1.2cm, level 1/.style={sibling distance=2cm}, level 2/.style={sibling distance=1cm}, every node/.style={circle, draw, minimum size=0.7cm, inner sep=0pt}] \node (t1) {\(t_1\)} child { node (t2) {\(t_2\)} } child { node (t3) {\(t_3\)} child { node (t6) {\(t_6\)} } child { node (t7) {\(t_7\)} } }; % Llave para el conjunto T (hojas) \end{tikzpicture} \bigskip \(T = \{t_2, t_6, t_7\}\) \end{column} \end{columns} \end{frame} \begin{frame}[fragile]\frametitle{} <>= prp (árbol, type=4) @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= árbol $ frame [, 1:5] # todos los nodos árbol $ where [c(1:5,145:150)] # hojas table (árbol$where) @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= prp (árbol, type=4, nn=TRUE) @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= prp (árbol, type=4, ni=TRUE) @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= prp (árbol, type=4, extra=1) @ \end{frame} \section{Árboles de clasificación} \begin{frame}\frametitle{Elegir siguiente corte:\\medidas de impureza} \begin{displaymath} \Phi \colon \begin{array}[t]{ccc} \mathbb P & \rightarrow & \mathbb R \\ (p_1,\dots,p_k) & \mapsto & \Phi(p_1,\dots,p_k) \end{array} \end{displaymath} donde \[ \mathbb P = \bigl\{ (p_1,\dots,p_k)\in[0,1]^k\;\bigm|\; p_1+\dots+p_k=1\bigr\} \] requisitos: \begin{itemize} \item alcanzar máximo en \(\bigl(\frac1k,\dots,\frac1k\bigr)\) \item alcanzar mínimo en conjuntos homogéneos como \(\bigl(0,\dots,0,1,0,\dots,0\bigr)\) \item invariancia frente a permutaciones de \((p_1,\dots,p_k)\) \end{itemize} \end{frame} \begin{frame}\frametitle{} \begin{itemize} \item impureza del nodo \(t\) \[\Phi(t) = \Phi(\Pr[1\mid t],\dots,\Pr[k\mid t])\] donde \(\Pr[j\mid t]\) es la probabilidad de la clase \(j\) en el nodo \(t\) \item reducción de la impureza al dividir \(t\) en \(\{t_L,t_R\}\) \[ \Delta \Phi(t\rightarrow t_L,t_R) = \Phi(t) - p_L\Phi(t_L) - p_R\Phi(t_R)\] donde \begin{itemize} \item \(p_L\)\hspace{.7em}es la proporción de \(t\) que se va a \(t_L\) \item \(p_R\) = \(1-p_L\)\quad es la proporción de \(t\) que se va a \(t_R\) \end{itemize} \item se busca la regla de decisión (variable \(X_i\) y umbral)\\ que maximice \(\Delta\Phi\) \[ \max_{\substack{i=1,\dots,p\\-\infty>= p1 <- seq (0, 1, 0.001) ; p2 <- 1 - p1 y1 <- - p1 * log(p1) - p2 * log(p2) # entropía y2 <- p1 * (1-p1) + p2 * (1-p2) # Gini plot (p1, y1, type="l", xlab=expression(p[1] == 1-p[2]), ylab="", axes=FALSE) legend("bottom", , c("info.","Gini"), 1:2) axis(1); axis(2); mtext("escala información", 2, -1.5) par (new = TRUE) plot (p1, y2, type="l", col=2, axes=FALSE,xlab="",ylab="", main="Forma de las medidas de impureza (2 clases)") axis(4); mtext("escala Gini", 4, -1.5) @ \end{frame} \begin{frame}\frametitle{Ejemplo: selección de corte con medidas de impureza} \textbf{Problema}: Predecir si un cliente comprará o no. Datos: \medskip \begin{tabular}{c|cccccccccc} Edad & 23 & 25 & 30 & 32 & 35 & 38 & 40 & 42 & 45 & 48 \\ \hline Compra & No & No & Sí & No & Sí & Sí & No & Sí & Sí & Sí \\ \end{tabular} \medskip \textbf{Nodo inicial \(t\)}: 10 casos (4 \texttt{No}, 6 \texttt{Sí}) Probabilidades: \(p_{\text{No}}=0.4\), \(p_{\text{Sí}}=0.6\) \[ \begin{aligned} \text{Entropía: } {\rm H}(t) &= -0.4\log_2 0.4 - 0.6\log_2 0.6 \approx 0.971 \\ \text{Gini: } G(t) &= 1 - (0.4^2+0.6^2) = 0.48 \end{aligned} \] \end{frame} \begin{frame}\frametitle{Ejemplo: selección de corte con medidas de impureza} \textbf{Posibles cortes} (ordenar edad, probar puntos medios): \medskip\scriptsize \begin{tabular}{ccc} Corte & \(t_L\) (Edad < corte) & \(t_R\) (Edad \(\ge\) corte) \\ \hline $27.5$ & [23,25]: (0\% Sí) & resto: (6/8=75\% Sí) \\ $33.5$ & [23,25,30,32]: (1/4=25\% Sí) & resto: (5/6=$83.3$\% Sí) \\ $41.5$ & hasta 40: (3/7=$42.9$\% Sí) & desde 42: (3/3=100\% Sí) \\ \hline\hline & \(p_L\) & \(p_R\) \\ \hline $27.5$ & $0.2$ & $0.8$ \\ $33.5$ & $0.4$ & $0.6$ \\ $41.5$ & $0.7$ & $0.3$ \\ \hline\hline & \(\Delta {\rm H}\) & \(\Delta G\) \\ \hline $27.5$ & $0.971 - 0.2\cdot 0 - 0.8\cdot 0.811 = 0.322$ & $0.48 - 0.2\cdot 0 - 0.8\cdot 0.375 = 0.18$ \\ $33.5$ & $0.971 - 0.4\cdot 0.811 - 0.6\cdot 0.650 = 0.081$ & $0.48 - 0.4\cdot 0.375 - 0.6\cdot 0.278 = 0.097$ \\ $41.5$ & $0.971 - 0.7\cdot 0.985 - 0.3\cdot 0 = 0.282$ & $0.48 - 0.7\cdot 0.490 - 0.3\cdot 0 = 0.137$ \\ \end{tabular} \end{frame} \begin{frame}\frametitle{Ejemplo: selección de corte con medidas de impureza} {conclusión} \begin{itemize} \item el corte en $27.5$ maximiza la reducción de entropía (\(\Delta \Eta = 0.322\)) \item también maximiza la reducción de Gini (\(\Delta G = 0.18\)) \item por tanto, se elegiría \texttt{Edad < 27.5} como primera división \end{itemize} {impureza \(\Phi(T)\)del árbol final} (si no seguimos dividiendo) \begin{itemize} \item entropía \[\Pr(t_L)\Phi(t_L) + \Pr(t_R)\Phi(t_R) = 0.2\cdot 0 + 0.8\cdot 0.811 = 0.649\] \item Gini \[0.2\cdot 0 + 0.8\cdot 0.375 = 0.3\] \end{itemize} \end{frame} \begin{frame}[fragile]\frametitle{} <<>>= ## por omisión se usa Gini a.gini <- rpart (Species ~ Petal.Length + Petal.Width, iris, parms = list(split="gini")) a.info <- rpart (Species ~ Petal.Length + Petal.Width, iris, parms = list(split="information")) @ \end{frame} \begin{frame}\frametitle{Criterio de parada: Riesgo} \begin{itemize} \item riesgo o pérdida de una hoja \begin{eqnarray*} R(t) &=& \Pr[\text{error de clasificación}\mid t] \\ &=& 1-\max_{j\in\text{clases}} \Pr[j\mid t] \end{eqnarray*} \item ejemplos: raíces \begin{itemize} \item clientes \begin{itemize} \item predicción: siempre \texttt{Sí} (moda, 6/10) \item errores: 4 casos \texttt{No} $\Rightarrow$ Riesgo $R = \frac{4}{10} = 0.40$ \end{itemize} \item iris \begin{itemize} \item predicción: siempre \texttt{setosa} \\(hay tres modas, 50/150; escogida por orden alfabético) \item errores: 50 \texttt{versicolor} y 50 \texttt{virginica} $\Rightarrow$ $R=100/150=0.67$ \end{itemize} \end{itemize} \end{itemize} \end{frame} \begin{frame}[fragile]\frametitle{} <>= prp (árbol, type=4, extra=1) @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= prp (árbol, type=4, extra=2) @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= prp (árbol, type=4, extra=3) @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= prp (árbol, type=4, extra=4) @ \end{frame} \begin{frame}[t]\frametitle{Criterio de parada: Riesgo} \begin{itemize} \item riesgo de una hoja \[R(t) =\Pr[\text{error clasif.}\mid t]=1-\max_{j\in\text{clases}} \Pr[j\mid t]\] \item riesgo del árbol \[R(T) =\Pr[\text{error clasif.}]= \sum_{t\in T} R(t)\Pr[t]\] \item ejemplo: $T$ = (árbol de clientes con un corte en Edad < $27.5$) \begin{itemize} \item nodo izquierdo $t_L$ (edad < $27.5$): casos \{23,25\}, ambos \texttt{No} ; \\predicción \texttt{No}, errores = 0 \item nodo derecho $t_R$ (edad $\ge$ $27.5$): 8 casos, 6 \texttt{Sí} y 2 \texttt{No} ; \\predicción \texttt{Sí}, errores = 2 \end{itemize} \[ R(T) = \frac{|t_L|}{N} \cdot R(t_L) + \frac{|t_R|}{N} \cdot R(t_R) = \frac{2}{10}\cdot 0 + \frac{8}{10}\cdot \frac{2}{8} = 0.20 \] \end{itemize} \end{frame} \begin{frame}[t]\frametitle{Criterio de parada: Riesgo} \begin{itemize} \item riesgo de una hoja \[R(t) =\Pr[\text{error clasif.}\mid t]=1-\max_{j\in\text{clases}} \Pr[j\mid t]\] \item riesgo del árbol \[R(T) =\Pr[\text{error clasif.}]= \sum_{t\in T} R(t)\Pr[t]\] \item disminución del riesgo si \(t\rightarrow\{t_L,t_R\}\) \[ \Delta R = R(t) - R(t_L,t_R) >0 \] \item ¿ criterio de corte: maximizar \(\Delta R\) ? \end{itemize} \end{frame} \begin{frame}\frametitle{¿Riesgo como criterio de corte?} \begin{itemize} \item ¿ maximizar \(\Delta R\) ? \item ejemplo 1: \begin{itemize} \item supóngase 80\% de individuos de clase 1 en la raíz \item supóngase corte candidato con hijos equiprobables \begin{itemize} \item 60\% de clase 1 en \(t_L\) \(\Rightarrow\) asignar clase 1 \item 100\% de clase 1 en \(t_R\) \(\Rightarrow\) asignar clase 1 \end{itemize} pero \(\Delta R = 0\) aunque la bifurcación es muy informativa \end{itemize} \item ejemplo 2: sean dos cortes candidatos con hojas equiprob. \begin{itemize} \item corte $A$ llevaría a 70\% y 70\% de clase 1 \item corte $B$ llevaría a 85\% y 50\% de clase 1 \item el $A$ tiene menos riesgo ; $R(A)=0.3 < R(B)=0.325$ \item el $B$ es preferible en la práctica, \\porque establece mejor cómo seguir dividiendo \item mediante impurezas, se prefiere $B$ \begin{itemize} \item Gini: \(G(A)= % 2\times\{0.5\cdot[1 - (0.7^2+0.3^2)]\}= 0.42\) ; \(G(B) = % 0.5\cdot0.255 + 0.5\cdot0.5 = 0.3775\) \item información: \({\rm H}(A) = % 0.5\cdot0.881 + 0.5\cdot0.881 = 0.881\) ; \({\rm H}(B) = % 0.5\cdot0.610 + 0.5\cdot1 = 0.805\) \end{itemize} \end{itemize} \end{itemize} \end{frame} \begin{frame}\frametitle{Criterios de parada en \texttt{rpart} de {\sf R}} \begin{description} \item[minsplit] Tamaño mínimo antes de cortar. \\ Por omisión, $20$. \item[minbucket] Tamaño mínimo de cada hoja. Por omisión, $7$. \item[cp] Parámetro de complejidad. \\ % Proporción mínima de mejora en el ajuste. \\ Coeficiente de penalización por número de hojas. \\ Por omisión, $1\%$. \item[maxdepth] Máxima profundidad de las hojas \\(0 = profundidad de la raíz). \\ Por omisión, $30$. \end{description} \end{frame} \begin{frame}[fragile]\frametitle{} <>= árbol$frame[,1:6] table (iris$Species, predict (árbol, iris, type="class")) @ \end{frame} \begin{frame}[fragile]\frametitle{} <<>>= rpart (Species~Petal.Length+Petal.Width, iris, control = rpart.control (cp = 0, minsplit = 2)) @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= prp (rpart (Species~Petal.Length+Petal.Width, iris, control = rpart.control (cp = 0, minsplit = 2)), yes.text="sí", no.text="no") @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= plot (Petal.Length ~ Petal.Width, iris, col=Species) abline (h=2.45, col=4) segments(1.75, 2.45, 1.75, 99, col=4) segments(-99, 4.95, 1.75, 4.95, col=4) segments(1.65, 2.45, 1.65, 4.95, col=4) segments(1.55, 4.95, 1.55, 99, col=4) segments(1.55, 5.45, 1.75, 5.45, col=4) @ \end{frame} \begin{frame}\frametitle{Criterio de parada \texttt{cp}} \begin{itemize} \item \(T_\infty\) árbol sin ramas, sólo raíz \item $\alpha>0$ parámetro de complejidad (\texttt{cp}) \item \(R_\alpha(T)=R(T)+\alpha\cdot|T|\cdot R(T_\infty)\) \item \(T_\alpha\) único árbol que minimiza \(R_\alpha\) \item \(T_0\) árbol completo \end{itemize} \end{frame} \begin{frame}[fragile]\frametitle{} <<>>= printcp (árbol) # árbol$cptable @ \end{frame} \begin{frame}\frametitle{Validación cruzada} \begin{columns} \begin{column}{0.4\textwidth} \begin{itemize} \item objetivo: estimar el error en datos nuevos \item dividir la muestra en \(K\) partes (pliegues) \item para cada \(k=1,\dots,K\): \begin{itemize} \item entrenar con \(K-1\) partes \item evaluar en la parte restante \end{itemize} \[ \text{Error}_{\text{VC}} = \frac{1}{K} \sum_{k=1}^K \text{Error}_k \] \item En \texttt{rpart}: argumento \texttt{xval} \end{itemize} \end{column} \begin{column}{0.4\textwidth} \centering \begin{tikzpicture} \foreach \i in {1,...,5} { \foreach \j in {1,...,5} { \draw[fill=gray!20] (\j, -\i) rectangle ++(0.6,0.6); } % marcar el pliegue de validación \draw[fill=blue!50] (\i, -\i) rectangle ++(0.6,0.6); } \end{tikzpicture} \vspace{0.5em} {\scriptsize cada fila: un pliegue usado como validación (azul) y cuatro como entrenamiento (gris)} \end{column} \end{columns} \end{frame} \begin{frame}[fragile]\frametitle{Validación cruzada} Cambiar número de cruzvalidaciones\\ para obtener resultados más estables:\\[3ex] <<>>= a100 <- rpart (Species~Petal.Length+Petal.Width, iris, control=rpart.control(cp=0, minsplit=2, xval=100)) a100$cptable @ \end{frame} \begin{frame}[fragile]\frametitle{} <>= plotcp (a100) # abscisas = medias geométricas @ \end{frame} \begin{frame}[fragile]\frametitle{Poda} \begin{itemize} \item si árbol demasiado ralo, \begin{itemize} \item obtener $T_0$ con \texttt{cp=0, minbucket=1} \item chequear \texttt{printcp} o \texttt{plotcp} y podar según \texttt{cp} óptimo \end{itemize} \end{itemize} <<>>= prune (a100, cp=0.09) # cualq. entre 0,02 y 0,44 @ \end{frame} \begin{frame}[fragile]\frametitle{Importancia de las variables} <>= prp (árbol, nn=TRUE, extra=1) @ \end{frame} \begin{frame}[fragile]\frametitle{Importancia de las variables} \begin{itemize} \item suma de calidad de la división en nodos cuyas reglas involucran la variable \(X_i\) : \(\displaystyle\sum_{t\text{ usa }X_i}\Delta\Phi(t)\) \item si dos variables están muy correladas, su importancia conjunta se dividirá entre las dos y puede que ninguna destaque \item como componente \texttt{variable.importance} del objeto \texttt{rpart} aparece en forma absoluta <<>>= árbol $ variable.importance @ \item en la salida de \verb+summary+ aparece en porcentajes \end{itemize} \end{frame} \begin{frame}[fragile]\frametitle{Importancia de las variables} <<>>= summary (árbol) @ \end{frame} \section{Árboles de regresión} \begin{frame}[fragile]\frametitle{Regresión} \begin{itemize} \item \(Y\) cuantitativa \item \verb|rpart| usa el método \verb|anova| \item predicción \(\hat y_t\): al nodo \(t\) se le asigna \(\bar y = \frac1{n_t}\sum_{i\in t} y_i\) \\ (en clasificación asignábamos la moda) \item criterio: maximizar \(\text{SC}_t-\text{SC}_L-\text{SC}_R\) donde \begin{itemize} \item \(\text{SC}_t\) = suma de cuadrados \(\sum (y_i-\bar y)^2\) en el nodo \(t\) \item \(\text{SC}_L\) = ídem en su nodo hijo \(L\) \item \(\text{SC}_R\) = ídem en su nodo hijo \(R\) \end{itemize} \item riesgo en el nodo \(t\): varianza \(\frac1{n_t}\sum_{i\in t} (y_i-\hat y_t)^2\) \\ (en clasificación era la tasa de incorrectos) \end{itemize} \end{frame} \section{Resumen} \begin{frame}[fragile]\frametitle{Protocolo para\\construir un \'arbol} \begin{enumerate} \item Determinar el n\'umero adecuado de permutaciones para validaci\'on cruzada, \texttt{xval} = ¿$10, 100, \dots$? \item Crear un \'arbol completo \begin{itemize} \item \texttt{cp} = 0 \item \texttt{minsplit} = 2 \'o \texttt{minbucket} = 1 \item ¿\texttt{xval}? \end{itemize} \item Fijarse en si \verb|xstd| (errores t\'\i picos obtenidos por cruzvalidaci\'on) son reducidos. Si no, aumentar \verb+xval+ \item Buscar el par\'ametro de complejidad (\texttt{cp}) adecuado \begin{verbatim} plotcp (árbol) # o printcp(árbol) \end{verbatim} \item Podar el \'arbol (o recalcularlo con \texttt{cp}) \begin{verbatim} árbol1 <- prune (árbol, cp=...) árbol1 <- rpart (..., control=rpart.control(cp=...)) \end{verbatim} \end{enumerate} \end{frame} \section{Ejercicios} \begin{frame}[fragile]\frametitle{Ejercicio 1: iris} \begin{itemize} \item Construye un árbol de clasificación para los datos \verb+iris+ a partir de todas sus variables (en la presentación usamos sólo las de los pétalos). \item ¿Se gana algo respecto a usar sólo los pétalos? \item Compáralo con el análisis discriminante. \end{itemize} \end{frame} \begin{frame}[fragile]\frametitle{Ejercicio 2: mtcars} \begin{itemize} \item Construir un modelo de regresión lineal para estimar \verb+mpg+ a partir del resto de variables. \item Construir un árbol de regresión con el mismo objetivo. \item Comparar ambos modelos: \begin{itemize} \item Con la información que producen las funciones de {\sf R}. \item Con validación cruzada. \end{itemize} \end{itemize} \end{frame} \begin{frame}[fragile]\frametitle{Ejercicio 3: solder} \begin{itemize} \item Construye un árbol a partir de los datos \verb+solder.balance+ para buscar variables que afecten al número de proyecciones (\verb|skips|). \end{itemize} \end{frame} \begin{frame}[fragile]\frametitle{Ejercicio 4: genotipos} \begin{itemize} \item Construye un árbol para los datos \url{http://bellman.ciencias.uniovi.es/~carleos/master/manadine/curso1/AnalisisDatos1/3-arboles/dat/geno.csv} para predecir \verb|genotipo|. \end{itemize} \end{frame} % \begin{frame}[fragile]\frametitle{Ejercicio 5: tejido mamario} % \begin{itemize} % \item Construye un árbol de clasificación para los datos % sobre tejido mamario % de la Hoja 2. Compáralo con el resultado obtenido con análisis discriminante. % \end{itemize} % \end{frame} \section{Bibliografía} \begin{frame}[fragile]\frametitle{Más detalles} \begin{itemize} \item \url{https://es.wikipedia.org/wiki/Aprendizaje_basado_en_%C3%A1rboles_de_decisi%C3%B3n} \item \url{https://cran.r-project.org/web/packages/rpart/vignettes/longintro.pdf} \item \url{https://www.researchgate.net/publication/263671703_Fifty_Years_of_Classification_and_Regression_Trees} \end{itemize} \end{frame} \section{Apéndice: Balanceo / Equilibrio} \begin{frame}{Apéndice} \begin{itemize} \item muestras desbalanceadas\\ o desequilibradas \item p.ej. prevalencia baja \end{itemize} \end{frame} %------------------------------------------------- \begin{frame}{Impureza de Gini (caso estándar)} Sea un nodo con probabilidades: \[ p_k = P(Y = k \mid \text{nodo}) \] \medskip \textbf{Índice de Gini:} \[ \Phi = \sum_k p_k (1 - p_k) = 1 - \sum_k p_k^2 \] \medskip \textbf{Interpretación:} \begin{itemize} \item Probabilidad de error al clasificar aleatoriamente según $p_k$ \item Equivalente a pérdida 0-1 simétrica (aproximación suave) \end{itemize} \end{frame} %------------------------------------------------- \begin{frame}{Riesgo bayesiano con pérdidas} Sea una matriz de pérdidas: \[ L(i,j) \] \medskip \textbf{Riesgo al predecir $j$:} \[ R(j) = \sum_k L(k,j)\, p_k \] \medskip \textbf{Riesgo óptimo en el nodo:} \[ \Phi = R^* = \min_j R(j) \] \medskip \textbf{Interpretación:} \begin{itemize} \item Generaliza la impureza \item Incorpora asimetría de costes \end{itemize} \end{frame} %------------------------------------------------- \begin{frame}{Gini como caso particular} Si: \[ L(i,j) = \mathbf{1}_{i \neq j} \] \medskip entonces: \[ R(j) = 1 - p_j \] \[ \Phi = R^* = 1 - \max_k p_k \] \medskip \textbf{Comparación:} \begin{itemize} \item $\Phi = 1 - \max_k p_k$: error Bayes óptimo \item $\Phi = 1 - \sum_k p_k^2$: Gini (versión suavizada) \end{itemize} \end{frame} \begin{frame}[fragile] <>= p <- seq(0,1,length=200) gini <- 2*p*(1-p) bayes <- 1 - pmax(p,1-p) cFN <- 5 cFP <- 1 cost <- pmin(cFN*p, cFP*(1-p)) plot(p, gini, type="l", lwd=2, ylim=c(0,1), ylab="Impureza", xlab="p = P(Y=1)") lines(p, bayes, lwd=2, lty=2) lines(p, cost, lwd=2, lty=3) legend("topright", legend=c("Gini","Error Bayes","Coste asimétrico"), lty=1:3, lwd=2) @ \end{frame} %------------------------------------------------- \begin{frame}{Impureza generalizada\\ (con pérdidas)} \[ \Phi = \min_j \sum_k L(k,j)\, p_k \] \medskip \textbf{Idea clave:} \begin{itemize} \item La impureza es el riesgo mínimo \item Depende de la decisión óptima \item Generaliza Gini y error de clasificación \end{itemize} \end{frame} %------------------------------------------------- \begin{frame}{Caso binario explícito} Clases: $\{0,1\}$ \medskip \[ L = \begin{pmatrix} 0 & c_{\mathrm{FP}} \\ c_{\mathrm{FN}} & 0 \end{pmatrix} \] \medskip Sea $p = P(Y=1)$: \[ R(0) = c_{\mathrm{FN}}\, p \quad R(1) = c_{\mathrm{FP}}\, (1-p) \] \medskip \[ \Phi(p) = \min \{ c_{\mathrm{FN}} p,\; c_{\mathrm{FP}} (1-p) \} \] \end{frame} %------------------------------------------------- \begin{frame}{Forma de la impureza} \[ \Phi(p) = \min \{ c_{\mathrm{FN}} p,\; c_{\mathrm{FP}} (1-p) \} \] \medskip \textbf{Propiedades:} \begin{itemize} \item Función cóncava a trozos \item No simétrica salvo $c_{\mathrm{FN}} = c_{\mathrm{FP}}$ \item Máximo en: \[ p = \frac{c_{\mathrm{FP}}}{c_{\mathrm{FP}} + c_{\mathrm{FN}}} \] \end{itemize} \medskip \textbf{Comparación:} \begin{itemize} \item Gini estándar: máximo en $p = 1/2$ \item $\Phi$: máximo desplazado \end{itemize} \end{frame} \begin{frame}[fragile] <>= p <- seq(0,1,length=200) cFN <- 5 cFP <- 1 R0 <- cFN * p R1 <- cFP * (1 - p) plot(p, R0, type="l", lwd=2, ylim=c(0, max(R0,R1)), ylab="Riesgo", xlab="p = P(Y=1)") lines(p, R1, lwd=2, lty=2) # punto de corte pstar <- cFP / (cFP + cFN) abline(v=pstar, lty=3) legend("topright", legend=c("R(0): predecir 0", "R(1): predecir 1"), lty=1:2, lwd=2, bg="white") @ \end{frame} \begin{frame}[fragile] <>= p <- seq(0,1,length=200) cFN <- 5 cFP <- 1 R0 <- cFN * p R1 <- cFP * (1 - p) plot(p, R0, type="l", lwd=2, ylim=c(0, max(R0,R1)), ylab="Riesgo", xlab="p = P(Y=1)") lines(p, R1, lwd=2, lty=2) # punto de corte pstar <- cFP / (cFP + cFN) abline(v=pstar,col=2)#, col="gray", lty=3) text(0.065, max(R0,R1)*0.5, "decidir 0", col=2) text(0.275, max(R0,R1)*0.5, "decidir 1", col=2) legend("topright", legend=c("R(0): predecir 0", "R(1): predecir 1"), lty=1:2, lwd=2, bg="white") @ \end{frame} %------------------------------------------------- \begin{frame}{Incorporación de \texttt{prior}} Sea $\pi_k$ el prior: \[ \tilde{p}_k \propto \pi_k\, \hat{p}_k \] \medskip \textbf{Impureza:} \[ \Phi = \min_j \sum_k L(k,j)\, \pi_k\, \hat{p}_k \] \medskip \textbf{Interpretación:} \begin{itemize} \item $\pi_k$ reescala las frecuencias \item Cambia la distribución efectiva \end{itemize} \end{frame} %------------------------------------------------- \begin{frame}{Criterio de división} Para un split: \[ \Delta = \Phi(\text{padre}) - \left( \frac{n_L}{n} \Phi(L) + \frac{n_R}{n} \Phi(R) \right) \] \medskip \textbf{Optimización:} \begin{itemize} \item Maximizar reducción de impureza \item Con impureza definida como riesgo \end{itemize} \medskip \textbf{Conclusión:} \[ \text{\texttt{rpart} implementa CART basado en riesgo bayesiano} \] \end{frame} %------------------------------------------------- \begin{frame}{Problema: \texttt{kyphosis}} \textbf{Contexto:} \begin{itemize} \item Pacientes pediátricos (edad $\leq 200$ meses) \item Variable respuesta: \texttt{Kyphosis} $\in \{\texttt{absent}, \texttt{present}\}$ \item Objetivo: predecir recurrencia tras cirugía \end{itemize} \medskip \textbf{Distribución de clases:} \[ n = 81, \quad n_{\texttt{absent}} = 64, \quad n_{\texttt{present}} = 17 \] \medskip \textbf{Desbalanceo:} \[ P(\texttt{absent}) \approx 0.79, \quad P(\texttt{present}) \approx 0.21 \] \end{frame} %------------------------------------------------- \begin{frame}{Clasificador trivial} \textbf{Regla:} predecir siempre \texttt{absent} \medskip \[ \hat{Y} = \texttt{absent} \quad \forall x \] \medskip \textbf{Error:} \[ \text{error} = P(Y = \texttt{present}) \approx 0.21 \] \[ \text{accuracy} \approx 79\% \] \medskip \textbf{Conclusión:} \begin{itemize} \item Alta accuracy sin usar variables \item No detecta ningún caso positivo \end{itemize} \end{frame} %------------------------------------------------- \begin{frame}{Limitaciones del enfoque estándar} \textbf{Problema:} \begin{itemize} \item La accuracy no refleja utilidad clínica \end{itemize} \medskip \textbf{Falso negativo:} \begin{itemize} \item No detectar cifosis \item Posible impacto clínico grave \end{itemize} \medskip \textbf{Falso positivo:} \begin{itemize} \item Intervención innecesaria \item Coste menor (relativo) \end{itemize} \medskip \[ c_{\mathrm{FN}} \gg c_{\mathrm{FP}} \] \end{frame} %------------------------------------------------- \begin{frame}{Motivación para \texttt{prior} y \texttt{loss}} \textbf{Objetivo:} optimizar riesgo, no accuracy \medskip \[ \Phi = \min_j \sum_k L(k,j)\, \pi_k\, \hat{p}_k \] \medskip \textbf{Estrategias:} \begin{itemize} \item Ajustar $\pi_k$ (prior) para corregir desbalanceo \item Ajustar $L(k,j)$ para reflejar costes \end{itemize} \medskip \textbf{Resultado esperado:} \begin{itemize} \item Mayor sensibilidad (detectar \texttt{present}) \item Menor dependencia de la mayoría \end{itemize} \end{frame} %------------------------------------------------- \begin{frame}{Clasificador trivial: matriz de confusión} \textbf{Regla:} predecir siempre \texttt{absent} \medskip \[ \hat{Y} = \texttt{absent} \quad \forall x \] \medskip \textbf{Matriz de confusión:} \[ \begin{array}{c|cc} & \text{Pred: absent} & \text{Pred: present} \\ \hline \text{Real: absent} & 64 & 0 \\ \text{Real: present} & 17 & 0 \\ \end{array} \] \medskip \textbf{Métricas:} \[ \text{accuracy} = \frac{64}{81} \approx 0.79 \qquad \text{sensibilidad} = 0 \] \end{frame} %------------------------------------------------- \begin{frame}{Comparación conceptual: accuracy vs riesgo} \textbf{Clasificador trivial:} \begin{itemize} \item Alta accuracy ($\approx 79\%$) \item Sensibilidad nula \end{itemize} \medskip \textbf{Problema:} \[ \text{Accuracy no incorpora costes asimétricos} \] \medskip \textbf{Enfoque con pérdidas:} \[ \Phi = \min_j \sum_k L(k,j)\, \pi_k\, \hat{p}_k \] \medskip \textbf{Efecto:} \begin{itemize} \item Penaliza fuertemente falsos negativos \item Fuerza modelos a detectar \texttt{present} \end{itemize} \end{frame} %------------------------------------------------- \begin{frame}[fragile]{Ejemplo base en R} \textbf{Dataset: \texttt{kyphosis}} \medskip \begin{verbatim} library(rpart) fit0 <- rpart(Kyphosis ~ ., data = kyphosis, method = "class") \end{verbatim} \medskip \textbf{Configuración implícita:} \begin{itemize} \item Prior empírico \item Pérdida 0-1 simétrica \end{itemize} \medskip \[ \Phi = 1 - \max_k p_k \quad (\text{aprox. Gini}) \] \end{frame} %------------------------------------------------- \begin{frame}[fragile]{Uso de prior uniforme} \textbf{Objetivo:} compensar desbalanceo \medskip \begin{verbatim} fit1 <- rpart(Kyphosis ~ ., data = kyphosis, method = "class", parms = list(prior = c(0.5, 0.5))) \end{verbatim} \medskip \textbf{Efecto:} \begin{itemize} \item Repondera clases: \[ \tilde{p}_k \propto \pi_k \hat{p}_k \] \item Mayor atención a \texttt{present} \end{itemize} \medskip \textbf{Consecuencia:} \begin{itemize} \item Splits más sensibles a la clase minoritaria \end{itemize} \end{frame} %------------------------------------------------- \begin{frame}[fragile]{Matriz de pérdidas asimétrica} \textbf{Objetivo:} penalizar falsos negativos \medskip \[ L = \begin{pmatrix} 0 & 1 \\ 5 & 0 \end{pmatrix} \] \medskip \begin{verbatim} L <- matrix(c(0,1, 5,0), nrow = 2, byrow = TRUE) fit2 <- rpart(Kyphosis ~ ., data = kyphosis, method = "class", parms = list(loss = L)) \end{verbatim} \medskip \textbf{Efecto:} \[ \Phi(p) = \min \{ 5p,\; (1-p) \} \] \end{frame} %------------------------------------------------- \begin{frame}[fragile]{Combinación: prior + loss} \textbf{Modelo más realista} \medskip \begin{verbatim} L <- matrix(c(0,1, 5,0), 2, byrow = TRUE) fit3 <- rpart(Kyphosis ~ ., data = kyphosis, method = "class", parms = list( prior = c(0.5, 0.5), loss = L)) \end{verbatim} \medskip \textbf{Impureza:} \[ \Phi = \min_j \sum_k L(k,j)\, \pi_k\, \hat{p}_k \] \medskip \textbf{Interpretación:} \begin{itemize} \item Prior: frecuencia esperada \item Loss: coste decisional \end{itemize} \end{frame} %------------------------------------------------- \begin{frame}[fragile]{Comparación de modelos} \begin{verbatim} rpart.plot::rpart.plot(fit0) rpart.plot::rpart.plot(fit2) \end{verbatim} \medskip \textbf{Observar:} \begin{itemize} \item Cambios en los splits \item Cambios en las hojas (clase predicha) \item Mayor sensibilidad en \texttt{fit2}, \texttt{fit3} \end{itemize} \medskip \textbf{Mensaje clave:} \[ \text{El árbol depende de } \Phi \text{, no solo de los datos} \] \end{frame} %------------------------------------------------- \end{document}