**IAIC** Solución Práctica Semana 10 Introducción al Aprendizaje Automático !!!warn: Descargas 1. [Aquí puedes descargar un ZIP con los ficheros necesarios para realizar esta práctica](P10.zip). # K-Vecinos más Cercanos (KNN) **Problema 1**.- Aplica **KNN** (con $k=1, 2, 3$) para clasificar $P_1=(0,0,0)$, $P_2=(0.75,\ 0,\ 0)$ y $P_3=(1,1,1)$, a partir del conjunto de entrenamiento siguiente y usando la distancia de Manhattan: | | $E_1$ | $E_2$ | $E_3$ | $E_4$ | $E_5$ | |-------|:---------:|:---------:|:--------:|:-------:|:---------------:| |Punto |$(1,0.5,0)$|$(-1,-1,0)$|$(1,0,-1)$|$(0,0,1)$|$(1,-0.5,-0.5)$ | |Clasif.|NO |SI |SI |NO |NO | !!!Alg:

**Solución**

Calculamos las distancias entre los puntos $P_i$ y los puntos del conjunto de entrenamiento: | | $P_1$ | $P_2$ | $P_3$ | |-----|:------:|:------:|:------:| |$E_1$|1.5 |0.75 |1.5 | |$E_2$|2 |2.75 |5 | |$E_3$|2 |1.25 |3 | |$E_4$|1 |1.75 |2 | |$E_5$|2 |1.25 |3 | De donde podemos sacar los vecinos para cada valor de $K$: | | $P_1$ | $P_2$ | $P_3$ | |-----|:-------------------:|:-----------:|:---------------:| |$K=1$|$E_4$ |$E_1$ |$E_1$ | |$K=2$|$E_1,E_4$ |$E_1,E_3/E_5$|$E_1,E_4$ | |$K=3$|$E_1,E_4,E_2/E_3/E_5$|$E_1,E_3,E_5$|$E_1,E_4,E_3/E_5$| Las clasificaciones asociadas: | | $P_1$ | $P_2$ | $P_3$ | |-----|:--------------:|:---------:|:------------:| |$K=1$|$NO$ |$NO$ |$NO$ | |$K=2$|$NO,NO$ |$NO,SI/NO$ |$NO,NO$ | |$K=3$|$SI,NO,NO/SI/NO$|$NO,SI,NO$ |$NO,NO,SI/NO$ | Las clasificaciones resultantes: | | $P_1$ | $P_2$ | $P_3$ | |-----|:--------------:|:---------:|:---------:| |$K=1$|$NO$ |$NO$ |$NO$ | |$K=2$|$NO$ |? |$NO$ | |$K=3$|? |$NO$ |$NO$ |

**Problema 2**.- 1. Aplica **KNN** (con $k = 1, 3, 5$) para clasificar $P_1 = (0.5, 1)$, $P_2=(0,0)$ y $P_3=(0.5,0.5)$, a partir del siguiente conjunto de entrenamiento, y usando la distancia euclídea: | | $E_1$ | $E_2$ | $E_3$ | $E_4$ | $E_5$ | $E_6$ | |-------|:------:|:------:|:------:|:------:|:------:|:------:| |Punto |$(1, 2)$|$(3, 1)$|$(2, 1)$|$(0, 1)$|$(1, 1)$|$(0, 0)$| |Clasif.|$1$ |$1$ |$1$ |$0$ |$0$ |$1$ | **Problema 3**.- Implementa el algoritmo de **K vecinos más cercanos** (KNN) para que acepte puntos de cualquier dimensión. Implementa una modificación del algoritmo KNN, **KNN ponderado** en el que se pondera la importancia de los vecinos más cercanos en función de la distancia a la que se encuentren (los más cercanos pesan más). !!!Alg:

**Solución**

Primero vamos a definir algunas funciones auxiliares que nos harán falta: *distancias*, y *secciones iniciales de listas*. ~~~~C to-report dist [p1 p2] report d-m p1 p2 end to-report toma [n l] report sublist l 0 n end to-report d-m [p1 p2] report sum map abs (map - p1 p2) end to-report d-e [p1 p2] report sum map [x -> x ^ 2] (map - p1 p2) end ~~~~ **Nota**: Observa que la distancia euclídea se ha calculado sin la raíz cuadrada, ya que solo nos interesa como medida comparativa, no el valor exacto. Para lo siguiente, vamos a suponer que los ejemplos nos los dan como una lista de pares `[coor clas]`, donde `coor` es el vector de coordenadas del punto, y `clas` es la clasificación del ejemplo. Por ejemplo: ~~~~C [ [[1 2] 1] [[3 1] 1] [[2 1] 1] [[0 1] 0] [[1 1] 0] [[0 0] 1] ] ~~~~ La función KNN recibe como dato de entrada: `k-par` (el número de vecinos a considerar), los `ejemplos` conocidos, y las coordenadas del punto, `P`, a clasificar. Los pasos a seguir son claros: 1. Calcular las distancias de `P` a los ejemplos (se añade la distancia a la estructura de cada ejemplo): `[coor clas dist]`. 2. Ordenar la lista de ejemplos según las distancias a `P`. 3. Tomar los `k-par` primeros ejemplos de la lista ordenada. 4. Extraer las clases de esos primeros ejemplos. 5. Calcular la moda (el elemento que más se repite) de las clases anteriores. El código en NetLogo quedaría como: ~~~~ to-report KNN [k-par ejemplos P] let ejemplos-con-distancias map [ P1 -> lput (dist (first P1) P) P1] ejemplos set ejemplos-ordenados sort-by [ [x y] -> last x < last y ] ejemplos-con-distancias report modes map [x -> item 1 x] (toma k-par ejemplos-ordenados) end ~~~~ Un ejemplo de uso sería: ~~~~ let ejemplos [ [[1 2] 1] [[3 1] 1] [[2 1] 1] [[0 1] 0] [[1 1] 0] [[0 0] 1] ] print KNN k ejemplos [0 0] ~~~~ En la versión ponderada hemos de quedarnos con todas las clases (no solo la más frecuente) para poder calcular la suma de los inversos de las distancias de los ejemplos de cada clase (como la distancia podría ser $0$, creamos una función inversa que permita un valor mínimo para calcular el inverso). Calculamos las sumas ponderadas para cada clase presente, que se ordenan decrecientemente en función de la suma acumulada, y la primera clase corresponde con la que ha obtenido el valor máximo: ~~~~ to-report KNN-ponderado [k-par ejemplos P] let ejemplos-con-distancias map [ P1 -> lput (dist (first P1) P) P1] ejemplos let ejemplos-ordenados sort-by [ [x y] -> last x < last y ] ejemplos-con-distancias let k-ejemplos (toma k-par ejemplos-ordenados) let clases remove-duplicates map [x -> item 1 x] k-ejemplos let pesos map [c -> (list c sum (map [x -> inverso (last x)] (filter [x -> item 1 x = c] k-ejemplos)))] clases set pesos sort-by [ [x y] -> last x > last y] pesos report first first pesos end to-report inverso [x] report 1 / max (list x 0.001) end ~~~~

**Problema 4**.- En el algoritmo KNN existe el problema de que requiere de mucha memoria y tiempo de ejecución porque hay que almacenar continuamente todos los datos que definen el espacio de ejemplos de entrenamiento. Sin embargo, es muy probable que muchas de las muestras no sean necesarias para clasificar las demás, ya que su información es redundante con otras existentes en el mismo conjunto. Implementa las siguientes variantes de **KNN** que intentan reducir este problema: 1. **KNN Condensado** (observa que depende del orden dado a los datos y, además, tiene el problema de conservar los datos que introducen ruido al sistema): Dado un orden en los datos de entrada, para cada ejemplo se clasifica por medio de KNN haciendo uso únicamente de los datos anteriores; si la clasificación obtenida por ellos coincide con la asignada al ejemplo, ese ejemplo se elimina de los datos, si no, permanece. 2. **KNN Reducido**: es similar a la variante anterior, pero se comienza con el conjunto completo de datos, y se eliminan aquellos que no afectan a la clasificación del resto de datos de entrada (en contra de la condensación anterior, es capaz de eliminar las muestras que producen ruido, y guarda aquellas que son críticas para la clasificación). !!!Alg:

**Solución**

Haciendo uso de las funciones definidas en los ejercicios anteriores, y con alguna auxiliar para facilitar la tarea, podemos escribir: ~~~~C to-report quita [n l] report sublist l n (length l) end to-report KNN-condensado [k-par ejemplos] let rep toma k-par ejemplos foreach (quita k-par ejemplos) [ ej -> if KNN-ponderado k-par rep (first ej) != last ej [set rep lput ej rep] ] report rep end ~~~~ Ten en cuenta que si usamos un valor de `k-par`, hemos de disponer de esa cantidad de elementos iniciales para poder comenzar a calcular K-NN. El procedimiento anterior devuelve el conjunto de ejemplos tras haber quitado los elementos *redundantes* según la definición de condensación. Algo similar se podría hacer para el KNN reducido.

# Métricas de Rendimiento Notaremos, para cualquier conjunto $A$, $A^n=A\times\dots\times A$ ($n$ veces), y si $n < m$, notamos: $(n:m)=\{n, n+1, \dots, m\}$. **Problema 5**.- Calcula la matriz de confusión y las métricas de rendimiento asociadas de los modelos extraídos del problema $2$ sobre el conjunto $(0:5)^2$ considerando la clasificación real: $Clas(x,y)=1\Leftrightarrow x < 3$. **Problema 6**.- Calcula la matriz de confusión y las métricas de rendimiento asociadas de los modelos extraídos del problema $1$ sobre el conjunto $\{(\frac{x}{10},\frac{y}{10},\frac{z}{10}):\ (x,y,z)\in (-10:10)^3\}$ considerando la clasificación real: $Clas(a,b,c)=SI\Leftrightarrow a^2 + b^2 +c^2 < 0.25$. !!!Alg:

**Solución**

Vamos a hacer las funciones necesarias para poder resolver simultáneamente los ejercicios 5 y 6. La función que devuelve las métricas se basa por completo en el cálculo previo de la matriz de confusión. Téngase presente que hace uso de la extensión `matrix` para manipular matrices mutables. Además, recibe dos procedimientos anónimos: `model` y `Obs` que calculan, respectivamente, la salida predicha por el modelo y la observación real, así como el conjunto de datos de test sobre los que se calculará la matriz. Una vez calculada la matriz de confusión, extrae los valores de TN, FP, FN y TP y calcula directamente las métricas asociadas: ~~~~C extensions [matrix] to-report metricas [model Obs test] let M matrix:make-constant 2 2 0 foreach test [ P -> let observed (run-result Obs P) let predicted (run-result model P) matrix:set M observed predicted (matrix:get M observed predicted) + 1 ] let TN matrix:get M 0 0 let FP matrix:get M 0 1 let FN matrix:get M 1 0 let TP matrix:get M 1 1 let Accuracy (TN + FP) / (TN + TP + FN + FP) print (word "Accuracy = " Accuracy) let Prec TP / (TP + FP) print (word "Precision = " Prec) let Sensitivity TP / (TP + FN) print (word "Sensitivity = " Sensitivity) let TPR Sensitivity let Specificity TN / (TN + FP) print (word "Specificity = " Specificity) let FPR 1 - Specificity let F1 (TPR * FPR) / (TPR + FPR) print (word "F1 = " F1) report M end ~~~~ Tras esto, para realizar los ejercicios 5 y 6 basta definir adecuadamente cada uno de los datos de entrada. Se añaden, para facilitar la escritura, un par de funciones para calcular productos cartesianos de conjuntos: ~~~~ to-report ej5 [k-par] ca let ejemplos [ [[1 2] 1] [[3 1] 1] [[2 1] 1] [[0 1] 0] [[1 1] 0] [[0 0] 1] ] let model [ P -> first (KNN k-par ejemplos P)] let Obs [P -> ifelse-value (first P) < 3 [1][0]] let test prod-cart2 (range 6) (range 6) report metricas model Obs test end to-report ej6 [k-par] ca let ejemplos [ [[1 0.5 0] 0] [[-1 -1 0] 1] [[1 0 -1] 1] [[0 0 1] 0] [[1 -0.5 -0.5] 0] ] let model [ P -> first (KNN k-par ejemplos P)] let Obs [P -> ifelse-value (sum map [x -> x ^ 2] P) < 0.25 [1][0]] let A map [x -> x / 10] (range -10 11) let test (prod-cart3 A A A) report metricas model Obs test end to-report prod-cart2 [A B] report reduce sentence map [x -> map [y -> (list x y)] B] A end to-report prod-cart3 [A B C] report map [x -> reduce sentence x] prod-cart2 (prod-cart2 A B) C end ~~~~

# Dataframes !!!Tip

Librería para trabajar con DataFrames

`DF:load`, `DF:save, DF:header, DF:data`, `DF:first`, `DF:last`, `DF:n-of`, `DF:shape`, `DF:pp`, `DF:ren-col`, `DF:add-col`, `DF:move-col`, `DF:add-calc-col`, `DF:col`, `DF:value`, `DF:sort-col`, `DF:filter`, `DF:map`, `DF:foreach`, `DF:col-values`, `DF:filter-col`, `DF:rem-col`, `DF:shuffle`, `DF:split`, `DF:sort-by`, `DF:enum`, `DF:Cat2NumDep`, `DF:Cat2NumIndep`, `DF:Bin2NumDep`, `DF:Bin2NumIndep`, `DF:scale`, `DF:normalize`, `DF:summary` El formato que se sigue es: `(Tipo-Salida) DF:Funcion Tipo-Entrada-1 ... Tipo-Entrada-N`, donde los tipos son: `Df` (Dataframe), `L` (Lista), `S` (Cadena), `N` (Número), `X` (Genérico) * Carga un CSV en un DF: `(Df) DF:load f` * Graba un DF en un CSV: `() DF:save Df f` * Muestra el DF en el Centro de Comandos: `DF:show Df` * Pretty Print de un DF (cadena para imprimir): `(S) DF:pp Df` * Resumen del DF: `() DF:summary Df` * Recuperación: (`cn`: column name) * Cabecera: `(L) DF:header Df` * Datos: `(L) DF:data Df` * `N` primeras filas: `(L) DF:first N Df` * `N` últimas filas: `(L) DF:last N Df` * `N` filas al azar: `(L) DF:n-of N Df` * Una columna (datos): `(L) DF:col cn Df` * Valores (sin duplicados) de `cn`: `(L) DF:col-values cn Df` * Valor de una columna en una fila: `(X) DF:value cn row Df` * Forma (`N1` filas x `N2` columnas): `([N1 N2]) DF:shape Df` * Modificación Columnas: * Cambia nombre de una columna: `(Df) DF:ren-col old-cn new-cn Df` * Añade nueva columna con contenido: `(Df) DF:add-col cn cont Df` * Añade nueva columna calculada: `(Df) DF:add-calc-col cn f Df` * Elimina columna: `(Df) DF:rem-col cn Df` * Filtra filas con valor `val` en `cn`: `(Df) DF:filter-col cn val Df` * Ordena las filas según `cn`: `(Df) DF:sort-col cn Df` * Cambia una columna de posición (`pos` se calcula sin `cn`): `(DF) DF:move-col cn pos Df` * Modificación Dataframe: * Filtra las filas verificando `f`: `(Df) DF:filter f Df` * Aplica `f` a todas las filas: `(L) DF:map f Df` * Ejecuta una acción `f` a cada fila: `() DF:foreach Df f` * Reordena al azar las filas: `(Df) DF:shuffle Df` * Split aleatorio (`r` $\in [0,1]$), `r|(1-r)`: `([Df1 Df2]) DF:split r Df` * Ordena las filas usando una función `f`: `(Df) DF:sort-by f Df` * Añade una columna con enumeración: `(Df) DF:enum Df` * Categórica a Numérica: * `(DF) DF:Cat2NumDep cn Df` * `(DF) DF:Cat2NumIndep cn Df` * Binaria a Numérica: * `(DF) DF:Bin2NumDep cn Df` * `(DF) DF:Bin2NumIndep cn Df` * Normalización (no comprueba que los datos sean numéricos, ni maneja datos faltantes): * Escala lineal: escala los valores de `cn` para que tomen los valores en $[a,b]$: `(DF) DF:scale cn a b Df` * Normal: escala los valores de `cn` para seguir una normal $N(0,1)$: `(DF) DF:normalize cn Df`

**Problema 7**.- Analiza el funcionamiento de las siguientes funciones de test de la librería DF:

Test Titanic

~~~~C to DF:titanic-test ca let dftest DF:n-of 10 DF:load "titanic.csv" DF:print dftest DF:print (DF:scale "Age" 0 1 dftest) DF:print (DF:scale "Fare" -1 1 dftest) DF:print (DF:normalize "Fare" dftest) let df2 (DF:enum dftest) DF:print df2 let df3 (DF:move-col "#-row" 0 df2) DF:print df3 let df4 (DF:move-col "Survived" 8 df3) DF:print df4 end ~~~~

Test PlayGolf

~~~~C to DF:PlayGolf-test ca let dftest DF:load "PlayGolf.txt" print "Complete DF: dftest" DF:print dftest DF:summary dftest print "DF:Cat2NumIndep \"Outlook\" dftest" DF:print DF:Cat2NumIndep "Outlook" dftest print "DF:Cat2NumDep \"Outlook\" dftest" DF:print DF:Cat2NumDep "Outlook" dftest print "DF:Bin2NumDep \"Windy\" dftest" DF:print DF:Bin2NumDep "Windy" dftest print "DF:Bin2NumIndep \"Windy\" dftest" DF:print DF:Bin2NumIndep "Windy" dftest print "DF:filter [r -> (DF:value \"Windy\" r dftest) and (DF:value \"PlayGolf\" r dftest)] dftest" let dftest2 DF:filter [r -> (DF:value "Windy" r dftest) and (DF:value "PlayGolf" r dftest)] dftest DF:print dftest2 print "DF:col-values \"Outlook\" dftest" print (DF:col-values "Outlook" dftest) print "" print "DF:rem-col \"Outlook\" dftest" DF:print (DF:rem-col "Outlook" dftest) print "Separate DFs by every value in every attribute:" print "" foreach DF:header dftest [ h -> foreach (DF:col-values h dftest)[ v -> print (word h " = " v) let f [r -> DF:value h r dftest = v] DF:print (DF:filter f dftest) ] ] end ~~~~

Test Iris

~~~~C to DF:iris-test ca let dftest DF:n-of 10 DF:load "iris.txt" print "DF:sort-col \"pw\" dftest" DF:print DF:sort-col "pw" dftest print "DF:enum dftest" DF:print DF:enum dftest print "DF:sort-by [[r1 r2] -> ((first r1) < (first r2)) or ((first r1) = (first r2) and (item 1 r1) < (item 1 r2))] dftest" DF:print DF:sort-by [[r1 r2] -> ((first r1) < (first r2)) or ((first r1) = (first r2) and (item 1 r1) < (item 1 r2))] dftest print "DF:header dftest" print DF:header dftest print "DF:first 3 dftest" DF:print (DF:first 3 dftest) print "DF:last 3 dftest" DF:print (DF:last 3 dftest) print "DF:n-of 3 dftest" DF:print (DF:n-of 3 dftest) print "DF:add-col \"Random\" (n-values (first DF:shape dftest) [random 10]) dftest" DF:print (DF:add-col "Random" (n-values (first DF:shape dftest) [random 10]) dftest) print "DF:add-calc-col \"Join\" [r -> (word (item 0 r) \" \" (item 1 r))] dftest" let dftest1 DF:add-calc-col "Join" [r -> (word (item 0 r) " " (item 1 r))] dftest DF:print dftest1 DF:foreach dftest [r -> print r] print DF:map [x -> first x] dftest end ~~~~

**Problema 8**.- Experimento con Iris: haciendo uso de la última columna de Iris como clasificación de cada ejemplo (habrá entonces 3 clases), y por medio de las funciones que proporciona la librería DF, divide el conjunto de datos en dos secciones al azar (de 100 y 50, respectivamente), y usa la primera de ellas como conjunto de entrenamiento para KNN, y la segunda como conjunto de test para calcular la matriz de confusión. Establece para qué valor de $k$ se obtienen los mejores resultados y qué clases son las que se confunden más entre sí. ¿Es robusto el valor de $k$ frente a posibles cambios en las configuraciones de los conjuntos de Entrenamiento Test? **Nota**: Ten en cuenta que ahora la clasificación no es binaria, por lo que muchas de las métricas de rendimiento no se pueden calcular, pero podemos considerar una métrica *Accuracy* generalizada que se calcularía como: $$Accuracy = \frac{Nº\ Aciertos}{Tamaño\ Test}$$ !!!Alg:

**Solución**

Blabla: ~~~~C to-report matriz-confusion [model Obs test] let M matrix:make-constant 3 3 0 foreach test [ P -> let observed (run-result Obs P) let predicted (run-result model P) matrix:set M observed predicted (matrix:get M observed predicted) + 1 ] print (sum map [i -> matrix:get M i i] [0 1 2]) report M end to DF:iris-test2 ca ; Cargamos el dataset let dfIris DF:load "iris.txt" let df1 dfIris ; Para cada columna pw,pl,sw,sl foreach bl (DF:header df1) [ at -> ; Normalizamos esa columna set df1 DF:normalize at df1 ; Y eliminamos la columna original set df1 DF:rem-col at df1 ] ; Añadimos una columna con la unión de las 4 numéricas set df1 DF:add-calc-col "v" [r -> (bf r)] df1 ; eliminamos las individuales foreach bf bl (DF:header df1) [ at -> set df1 DF:rem-col at df1 ] ; movemos la columna class al final set df1 DF:move-col "class" 1 df1 ; Extraemos los valores de las clases let classes DF:col-values "class" df1 ; Cambiamos cada clase por un valor numérico [0 1 2] set df1 DF:add-calc-col "c" [r -> position (last r) classes] df1 set df1 DF:rem-col "class" df1 ; Dividimos el dataset en (1/3)/(2/3) (solo nos quedamos con los datos) let df1-df2 DF:split (1 / 3) df1 let ejemplos DF:data first df1-df2 let test DF:data last df1-df2 ; Definimos cómo funciona el modelo sobre los datos de test let model [ P -> (KNN-ponderado 2 ejemplos (first P))] ; y cómo obtenemos la observación real de los datos de test let Obs [P -> last P] ; Calculamos la matriz de confusión show matriz-confusion model Obs test end ~~~~

# Práctica Entregable Las condiciones para la entrega son: 1. Utiliza los ejercicios que se han realizado en clase para escribir la solución al problema propuesto. 3. **Pon tu nombre al fichero**, con el siguiente formato: `Apellido1_Apellido2_Nombre.nlogo` 4. **Envíalo por la plataforma de EV** en la tarea de la práctica correspondiente. !!!Alg

**Enunciado**

Calcula la matriz de confusión (y las métricas de rendimiento asociadas) del siguiente problema de modelado: 1. El conjunto de entrenamiento es $(-5:5)^2$, y con la clasificación $Clas(x,y)=1\Leftrightarrow |x|+|y|< 2$. 2. Aplicamos el modelo KNN ponderado, con $k=3$ y la distancia de manhattan, . 3. El conjunto de test es una malla en $[-5,5]^2$ espaciada en secciones de $\frac{1}{20}$ en cada eje, y con la misma función de clasificación que la dada para el conjunto de entrenamiento.