\documentclass[serif]{beamer}
\usefonttheme{structurebold}
\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\begin{document}\bfseries\boldmath
\begin{frame}
  \title{$k$ vecinos más próximos}
  \author{MANADINE - Análisis de Datos 3}
  \titlepage
\end{frame}
\begin{frame}{Índice}
  \tableofcontents
\end{frame}
\section{Introducción}
\begin{frame}{Índice}
  \tableofcontents[currentsection]
\end{frame}
\begin{frame}{Aprendizaje perezoso \textit{vs.} ansioso}
  \begin{block}{Aprendizaje perezoso (\textit{lazy})}
      \begin{itemize}
      \item Aprendizaje basado en instancias\\(datos de entrenamiento).
      \item Se almacenan todas las instancias y se usan\\
        para clasificar una nueva observación.
      \item Propiedades:
        \begin{itemize}
        \item Poco tiempo de entrenamiento, \\pero mucho para la predicción.
        \item Aproximaciones locales a la función objetivo.
        \item Sencillo de entender y aplicar.
        \end{itemize}
      \end{itemize}
  \end{block}
\end{frame}
\begin{frame}{Aprendizaje perezoso \textit{vs.} ansioso}
  \begin{block}{Aprendizaje ansioso (\textit{eager})}
    \begin{itemize}
    \item Regresión logística, árboles de decisión,\\ bosques aleatorios,
      redes neuronales...
    \item Con los datos de entrenamiento se construye\\ un modelo
      (criterio de clasificación) aplicable\\ a observaciones nuevas.
    \item Ansioso: persigue una única hipótesis que cubra todo el espacio
      de instancias.
      \item Propiedades:
        \begin{itemize}
        \item Mucho tiempo de entrenamiento, \\ poco para la predicción.
        \item Aproximaciones más generales a la función objetivo.
        \item Más complicado de aplicar.
        \end{itemize}
      \end{itemize}
  \end{block}
\end{frame}
\section{kNN}
\begin{frame}{Índice}
  \tableofcontents[currentsection]
\end{frame}
\begin{frame}{kNN: los $k$ vecinos más próximos}
  \begin{block}{Esquema general}
    \begin{itemize}
    \item Se dispone de $n$ observaciones o instancias.
    \item Cada instancia contiene $p$ variables predictoras
      $\vec x_i=(x_{i1},...,x_{ip})$ y el valor
      $y_i$ de la función objetivo.
    \item Se calcula la cercanía entre las instancias mediante
      una distancia $d(\vec x_i,\vec x_j)$ o una medida de similaridad.
    \item De las $k$ instancias más cercanas a $\vec x_i$, que podemos
      denotar con índices $i_1,...,i_k$ (es decir, las instancias
      $\vec x_{i_1},...,\vec x_{i_k}$), kNN devuelve, según sea la
      función objetivo,
      \begin{itemize}
      \item discreta: la moda de $y_{i_1},...,y_{i_k}$.
      \item continua: el promedio de $y_{i_1},...,y_{i_k}$ (media
        aritmética, media ponderada, mediana...).
      \end{itemize}
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}{kNN: los $k$ vecinos más próximos}
  \begin{block}{Diagrama de Voronói o teselación de Thiessen}
    Subespacios de decisión inducidos al aplicar kNN con k=1 a
    un conjunto de instancias.\\[1ex]
    
    \begin{columns}[t]
      \begin{column}{0.5\textwidth}
        \includegraphics[width=.8\textwidth]
        {knn/Euclidean_Voronoi_diagram.svg.png}
        \centering Distancia euclídea
      \end{column}
      \begin{column}{0.5\textwidth}
        \includegraphics[width=.8\textwidth]
        {knn/Manhattan_Voronoi_diagram.svg.png}
        \centering Distancia de Manhattan
      \end{column}
    \end{columns}\vspace{2ex}
    
    Fuente: \url{https://en.wikipedia.org/wiki/Voronoi_diagram}
  \end{block}
\end{frame}
\definecolor{verde}{rgb}{0, 0.6836, 0}
\definecolor{azul}{rgb}{0, 0, 0.8125}
\definecolor{rojo}{rgb}{0.9922, 0, 0}
\begin{frame}{kNN: los $k$ vecinos más próximos}
  \begin{block}{Ejemplo}
    \begin{columns}
      \begin{column}{0.6\textwidth}
        \includegraphics[width=.9\textwidth]
        {knn/KnnClassification.svg.png}
      \end{column}
      \begin{column}{0.4\textwidth}
        \textcolor{verde}{\raisebox{-.6ex}{\scalebox{2.3}{$\bullet$}}}
        clasificado...\\[2ex]
       $k=3$ $\implies$ ...como \textcolor{rojo}{\Large$\blacktriangle$}\\[2ex]
       $k=5$ $\implies$ ...como \textcolor{azul}{$\blacksquare$}\\[2ex]
      \end{column}
    \end{columns}\vspace{1ex}
    
    Fuente:
    \url{https://es.wikipedia.org/wiki/K_vecinos_más_próximos}
    
  \end{block}
\end{frame}
\begin{frame}{kNN: los $k$ vecinos más próximos}
  \begin{block}{Algoritmo para clasificar}
    \begin{itemize}
    \item Considerar instancias de entrenamiento $(\vec x_i,y_i)$.
    \item Elegir el número $k$ de vecinos.
    \item Dada una nueva instancia, $\vec x_q$,\\
      encontrar los $k$ puntos $\vec x_{q_1}$, ..., $\vec x_{q_k}$\\
      más cercanos a $\vec x_q$ según la distancia $d(\cdot,\cdot)$.
    \item Clasificar $\vec x_q$ según la moda de  $y_{q_1}$, ..., $y_{q_k}$.
    \end{itemize}
  \end{block}
\end{frame}
\begin{frame}{kNN: los $k$ vecinos más próximos}
  \begin{block}{Algoritmo para regresión}
    \begin{itemize}
    \item Considerar instancias de entrenamiento $(\vec x_i,y_i)$.
    \item Elegir el número $k$ de vecinos.
    \item Dada una nueva instancia, $\vec x_q$,\\
      encontrar los $k$ puntos $\vec x_{q_1}$, ..., $\vec x_{q_k}$\\
      más cercanos a $\vec x_q$ según la distancia $d(\cdot,\cdot)$.
    \item La predicción para $\vec x_q$ será la media o mediana de  $y_{q_1}$, ..., $y_{q_k}$.
    \end{itemize}
  \end{block}
\end{frame}
\begin{frame}{kNN: los $k$ vecinos más próximos}
  \begin{block}{Regresión con distancia ponderada}
    \begin{itemize}
    \item Ponderar la contribución de cada uno de
      los $k$ vecinos de acuerdo a su distancia a $\vec x_q$.
    \item Peso mayor a los vecinos más próximos,
      $$y_q=\frac{\sum_i w_i y_i}{\sum_i w_i}\qquad
      w_i=e^{-\frac{d(x_i,x_q)}{2\sigma^2}}$$
    \end{itemize}
  \end{block}
\end{frame}
\begin{frame}{kNN: los $k$ vecinos más próximos}
  \begin{block}{Propiedades}
    \begin{itemize}
      \item Robusto a datos con ruido al promediar $k$ valores.
      \item Maldición de la dimensionalidad: \\ la distancia entre vecinos
        podría estar dominada por atributos irrelevantes. \\ Remedios:
        \begin{itemize}
        \item Tipificar.
        \item Eliminar atributos poco relevantes.
        \end{itemize}
    \end{itemize}
  \end{block}
\end{frame}
\begin{frame}{kNN: los $k$ vecinos más próximos}
  \begin{block}{Elección de $k$}
    \begin{itemize}
      \item $k$ pequeño: Sobreajuste \\ (varianza alta, error pequeño).
      \item $k$ grande: Se tiende a usar puntos irrelevantes
        (varianza pequeña, mucho error).
      \item Más criterios en
        \url{http://scott.fortmann-roe.com/} \url{docs/BiasVariance.html}
    \end{itemize}
  \end{block}
\end{frame}

\section{Similaridad y disimilaridad}
\begin{frame}{Índice}
  \tableofcontents[currentsection]
\end{frame}
\begin{frame}{Distancias y similaridades}
  \begin{block}{\texttt{dist}}
    La función \texttt{dist} de R dispone de varios métodos:
    \begin{itemize}
    \item euclidean
    \item maximum
    \item manhattan
    \item canberra
    \item binary
    \item minkowski
    \end{itemize}
  \end{block}
  \begin{block}{\texttt{class::knn}}
    Las funciones \texttt{knn} y \texttt{knn1} del paquete \texttt{class}
    emplean la distancia euclídea.
  \end{block}
\end{frame}
\section{Ejemplos en R}
\begin{frame}{Índice}
  \tableofcontents[currentsection]
\end{frame}

\begin{frame}[fragile]{Ejemplo 1}
\begin{block}{\texttt{iris} - enfoque habitual}\footnotesize
\begin{verbatim}  
library(class) # para knn
n <- dim(iris)[1]
entrena <- sample(1:n, n*0.75)   # datos de entrenamiento
valida  <- setdiff(1:n, entrena) # datos de validación
vecinos3 <- knn (iris[entrena,-5],
                 iris[valida, -5],
                 iris[entrena, 5],
                 k=3, prob=TRUE)
summary(vecinos3) # frecuencias 
table (iris$Species[valida], vecinos3) # matriz de confusión
\end{verbatim}
\end{block}
\end{frame}

\begin{frame}[fragile]{Ejemplo 1 bis}
  \begin{block}{\texttt{iris} - ejemplo de \texttt{?knn}}\footnotesize
\begin{verbatim}
library(class) # para knn
entrena <- rbind(iris[ 1:25,-5], iris[51: 75,-5], iris[101:125,-5])
valida  <- rbind(iris[26:50,-5], iris[76:100,-5], iris[126:150,-5])
cl <- factor(c(rep("s",25), rep("c",25), rep("v",25)))
vecinos3 <- knn (entrena, valida, cl, k = 3, prob=TRUE)
table (cl, vecinos3)
##    vecinos3
## cl   c  s  v
##   c 23  0  2
##   s  0 25  0
##   v  3  0 22

## proporciones de votos de la clase ganadora:
prob <- attr(vecinos3,"prob") 
\end{verbatim}
  \end{block}
\end{frame}

\begin{frame}[fragile]{Ejemplo 2}
\begin{block}{simulación de dos poblaciones normales bidimensionales}\footnotesize
\begin{verbatim}
library(mvtnorm)   # librería para generar datos normal multivariante
library(RcmdrMisc) # librería para numSummary
library(class)     # librería para knn
## Muestra población 1
mu1 <- c(11,12); S1 <- matrix(c(1.5, 0.2, 0.2, 1.5), nrow=2, ncol=2)
n1 <- 100
X1 <- rmvnorm(n1, mu1, S1)
X1 <- cbind(X1, rep(1, n1))
head(X1)
## Muestra población 2
mu2 <- c(12.5,10); S2 <- matrix(c(1.5,0.6,0.6,1.6), nrow=2, ncol=2)
n2 <- 100
X2 <- rmvnorm(n2, mu2, S2)
X2 <- cbind(X2, rep(2, n2))
cor(X2[, 1:2])
X <- rbind(X1, X2) # muestra global 
colnames(X) <- c("V1", "V2", "Y")
head(X)
\end{verbatim}
\end{block}
\end{frame}

\begin{frame}[fragile]{Ejemplo 2}
\begin{block}{simulación de dos poblaciones normales bidimensionales}\footnotesize
\begin{verbatim}
n <- dim(X)[1]
ext_v1 <- c(min(X[,1]), max(X[,1]))  # mínimo y máximo de V1
ext_v2 <- c(min(X[,2]), max(X[,2]))  # mínimo y máximo de V2
## gráfica conjunta de las dos muestras
plot(X[1:n1,1], X[1:n1,2], col="red", xlim=ext_v1, ylim=ext_v2,
     xlab="V1", ylab="V2")
points(X[(n1+1): (n1+n2),1], X[(n1+1):(n1+n2),2], col="blue")
## descripción de los dos grupos
numSummary(X[, 1:2], groups=X[,3])
boxplot(X[,1] ~ X[,3], xlab="Poblaciones", ylab="V1")
boxplot(X[,2] ~ X[,3], xlab="Poblaciones", ylab="V2")
## clasificación usando knn
n <- dim(X)[1]; n
entrena <- sample(1:n, n*0.75); valida <- setdiff(1:n, entrena)
vecinos3 <- knn(X[entrena,-3], X[valida,-3], factor(X[entrena,3]),
                k=3, prob=TRUE)
summary(vecinos3)
table (X[valida,3], vecinos3)
\end{verbatim}
  \end{block}
\end{frame}

\begin{frame}[fragile]{Ejemplo 3}
  \begin{block}{Simulación: efecto de la dimensión}
 \footnotesize
\begin{verbatim}
n <- 1000 ; d <- 1 # dimensiones
g <- rbinom (n, 1, 0.5) * 2 # * diferencia de medias ;
x1 <- rnorm (n, g) # primera variable importa ;
X <- cbind (x1, matrix(rnorm(d*n),n)) # resto, no ;
en <- sample (n, 0.8*n) # datos de entrenamiento ;
aciertos <- function (k) 
  mean (diag (table (g[-en], 
                     knn (X[en,], X[-en,], g[en], k))))
aciertos(1) ; aciertos(11) ; aciertos(111)
## dif=1 dim=1    -> 68% con k=11 
## dif=1 dim=100  -> 60% con k=111
## dif=1 dim=1000 -> 55% con k=111
## dif=2 dim=1    -> 80% con k=11
## dif=2 dim=100  -> 75% con k=111
## dif=2 dim=1000 -> 65% con k=111
\end{verbatim}
 \end{block}
\end{frame}

\begin{frame}{Ejemplo 4}
  \begin{block}{\texttt{MASS::Cushings}}
    \begin{itemize}
    \item El síndrome de Cushing es un desorden hipertensivo asociado
      con sobresecreción de cortisol por la glándula suprarrenal.
    \item Los datos recogen tasas (mg/24h) de secreción urinaria de
      dos hormonas esteroideas: tetrahidrocortisona y pregnanetriol.
    \item Type: tipo de síndrome subyacente:
      \begin{description}
      \item[a] adenoma.
      \item[b] hiperplasia bilateral.
      \item[c] carcinoma.
      \item[u] desconocido.
      \end{description}
    \end{itemize}
  \end{block}
\end{frame}

\begin{frame}[fragile]{Ejemplo 4}\footnotesize
\begin{verbatim}
## para gráficas del ejemplo; adaptado de
## https://rdrr.io/cran/MASS/src/inst/scripts/ch12.R
library(MASS) # para Cushings
library(nnet) # para class.ind
cushplot <- function(xp, yp, Z, m)
{
  plot(Cushings[,1], Cushings[,2], log="xy", type="n", main=m,
       xlab = "Tetrahydrocortisone", ylab = "Pregnanetriol")
  for(il in 1:4) {
      set <- Cushings$Type==levels(Cushings$Type)[il]
      text(Cushings[set, 1], Cushings[set, 2],
           labels = as.character(Cushings$Type[set]), col = 2 + il) }
  zp <- Z[, 3] - pmax(Z[, 2], Z[, 1])
  contour(exp(xp), exp(yp), matrix(zp, np),
          add = TRUE, levels = 0, labex = 0)
  zp <- Z[, 1] - pmax(Z[, 2], Z[, 3])
  contour(exp(xp), exp(yp), matrix(zp, np),
          add = TRUE, levels = 0, labex = 0)
  invisible()
}
\end{verbatim}
\end{frame}

\begin{frame}[fragile]{Ejemplo 4}
\begin{verbatim}
## hasta el 21 tienen Type conocido
cush <- log(as.matrix(Cushings[, -3]))
tp <- Cushings$Type[1:21]
xp <- seq(0.6, 4.0, length = 100); np <- length(xp)
yp <- seq(-3.25, 2.45, length = 100)
cushT <- expand.grid(Tetrahydrocortisone = xp,
                     Pregnanetriol = yp)
Z <- knn(scale(cush[1:21, ], FALSE, c(3.4, 5.7)),
         scale(cushT, FALSE, c(3.4, 5.7)), tp)
cushplot(xp, yp, class.ind(Z), "k=1")
Z <- knn(scale(cush[1:21, ], FALSE, c(3.4, 5.7)),
         scale(cushT, FALSE, c(3.4, 5.7)), tp, k = 3)
cushplot(xp, yp, class.ind(Z), "k=3")
\end{verbatim}
\end{frame}
\begin{frame}{Ejemplo 4}
  \begin{center}
    \includegraphics[width=.49\textwidth]{knn/venables1.png}
    \includegraphics[width=.49\textwidth]{knn/venables3.png}
  \end{center}
\end{frame}
\section{Bibliografía}
\begin{frame}{Índice}
  \tableofcontents[currentsection]
\end{frame}
\begin{frame}{Bibliografía}
\begin{block}{Yizhou Sun (2017)}
  CS145: INTRODUCTION TO DATA MINING\\
  7: Vector Data: K Nearest Neighbor\\
  \url{https://www.coursehero.com/file/112016329/KNNpdf/}
\end{block}
\begin{block}{Venables \& Ripley (2002)}
  MODERN APPLIED STATISTICS WITH S\\
  12.3 Non-Parametric Rules\\
  \url{https://link.springer.com/book/}\\
  \url{10.1007/978-0-387-21706-2}
\end{block}
\end{frame}
\end{document}
