**Aprendizaje Supervisado y No Supervisado** En el campo del aprendizaje automático, los Algoritmos de Aprendizaje Supervisado y No Supervisado han sido pilares fundamentales en el análisis y comprensión de conjuntos de datos. El aprendizaje supervisado, representado aquí por el Algoritmo k-Vecinos más Cercanos (kNN), busca encontrar patrones y realizar predicciones basadas en datos de entrenamiento previamente etiquetados. Por otro lado, el aprendizaje no supervisado, ejemplificado por el Algoritmo de K-Medias, se centra en la agrupación y segmentación de datos sin etiquetar, revelando estructuras y relaciones ocultas. En esta exploración, comenzaremos con una introducción a los fundamentos del aprendizaje automático, para luego sumergirnos en estos dos pilares esenciales: el Algoritmo de Aprendizaje Supervisado kNN y el Algoritmo de Aprendizaje No Supervisado K-Medias, explorando sus aplicaciones y funcionamiento. # Introducción !!!side:1 Normalmente, un espacio como $\mathbb{R}$ o $\mathbb{R}^n$. Como se ha comentado brevemente en la entrada de [Introducción al Aprendizaje Automático](Fundamentos_Matematicos_ML.md.html), los modelos de **aprendizaje supervisado** son aquellos en los que se aprenden funciones, relaciones que asocian _entradas_ con _salidas_, por lo que se ajustan a un conjunto de ejemplos de los que conocemos la relación entre la entrada y la salida deseada. Este hecho incluso llega a proporcionar una de las clasificaciones más habituales en el tipo de algoritmos que se desarrollan, así, dependiendo del tipo de salida, suele darse una subcategoría que diferencia entre modelos de **clasificación**, si la salida es un valor categórico (por ejemplo, una enumeración, o un conjunto finito de clases), y modelos de **regresión**, si la salida es un valor de un espacio continuo [1]. Adicionalmente, los modelos de **aprendizaje no supervisado** son aquellos en los que no estamos interesados en ajustar pares _(entrada, salida)_, sino en aumentar el _conocimiento estructural_ de los datos disponibles (y posibles datos futuros que provengan del mismo fenómeno), por ejemplo, dando una agrupación de los datos según su similaridad (**clustering**), simplificando las estructura de los mismos manteniendo sus características fundamentales (**reducción de la dimensionalidad**), codificando los datos en algún espacio con mejores propiedades (**embedding vectorial**), o extrayendo la estructura interna con la que se distribuyen los datos en su espacio original (**aprendizaje topológico**). Normalmente, la mayor parte de las definiciones, resultados teóricos, y algoritmos clásicos más importantes, se clasifican como algoritmos supervisados y, sobre todo en el pasado, muchos de los algoritmos no supervisados se reservaban para tareas de preprocesamiento de datos integrados en metodologías más amplias. Este hecho se debe, principalmente, a una cadena de factores. Por una parte, el objetivo que dirige el **aprendizaje supervisado está mucho más claramente definido**, mientras que el no supervisado resulta más etéreo y difuso. Lo que no solo afecta a un desarrollo más amplio al disponer de aplicaciones mejor definidas, sino que también permite disponer de métricas que permiten evaluar con mucha más claridad la bondad del aprendizaje realizado (el **rendimiento del algoritmo**). Por otra parte, y quizás como resultado de lo anterior, los algoritmos no supervisados resultan ser muy costosos porque requieren de más pruebas de ensayo y error, haciendo que haya que desarrollar un aparataje teórico y computacional mucho más elaborado. !!!side:2 De esta forma, muchas de las tareas de Aprendizaje Supervisado pasan a considerarse tareas de un campo menor, como es la **Ciencia de Datos**, mientras que las tareas de Aprendizaje no Supervisado siguen engrosando las filas de tareas de más envergadura, como es el desarrollo de una IA General. Sin embargo, sobre todo recientemente, han ido surgiendo nuevos algoritmos no supervisados relacionados con lo que se conoce como **Aprendizaje de la Representación**, que ha demostrado ser el núcleo del Aprendizaje Automático, y donde líneas de trabajo como el ya famoso **Deep Learning** están tomando el peso de los avances más interesantes que se están produciendo, hasta el punto de considerarse que el futuro de la Inteligencia Artificial se encuentra más cerca del aprendizaje no supervisado que del supervisado [2]. En esta entrada no profundizaremos en estas últimas líneas de trabajo, para lo que dedicaremos entradas futuras, y a modo de ejemplo y para fijar las ideas principales vamos a centrarnos en dos algoritmos concretos, uno de cada tipo, que pueden servir de representantes sencillos y claros para entender sus objetivos y comportamiento más general. Además, junto con otros algoritmos paradigmáticos que iremos viendo en otras entradas, los utilizaremos más adelante para introducir los conceptos generales de **matriz de confusión**, **error**, **sobre-aprendizaje**, **métricas de rendimiento**, etc. # Algoritmo de Aprendizaje Supervisado: kNN !!!side:3 Obsérvese el parecido que tiene kNN con los algoritmos de interpolación para espacios continuos: el valor de los puntos conocidos cercanos determina el valor del punto a interpolar. El algoritmo de los **k vecinos más cercanos** (**kNN** por sus siglas en inglés, **k Nearest Neighbour**) es un algoritmo de clasificación supervisado basado en criterios de vecindad. En particular, kNN se basa en la idea de que los nuevos ejemplos serán clasificados con la misma clase que tengan la mayor cantidad de vecinos más parecidos a ellos del conjunto de entrenamiento. Así pues, este algoritmo sigue un procedimiento que seguimos cada uno de nosotros al ver un ejemplo nuevo: vemos a qué se parece más (de lo que conocemos), y lo clasificamos de la misma forma [3]. Obviamente, este algoritmo introduce ya una condición que debe cumplirse entre los datos que tengamos, y es que hemos de ser capaces de medir la similaridad entre dos cualesquiera de ellos, por eso se considera que el espacio de datos de entrada debe ser algo parecido a un espacio métrico (es decir, un espacio donde haya una distancia definida), por lo que muchas veces será común pensar en los datos de entrada como si vinieran dados por medio de vectores de un espacio vectorial numérico estándar. !!!side:4 Que asigna a una nueva muestra la clasificación de la muestra más parecida. Su versión más simple, el **algoritmo de EL vecino más cercano** [4] explora todo el conocimiento almacenado en el conjunto de entrenamiento para determinar cuál será la clase a la que pertenece una nueva muestra, pero únicamente tiene en cuenta el vecino más próximo (más similar) a ella, por lo que es lógico pensar que es posible que no se esté aprovechando de forma eficiente toda la información que se podría extraer del conjunto de entrenamiento. Con el objetivo de resolver esta posible deficiencia surge la generalización de los $k$ vecinos más cercanos (kNN), en la que se utiliza la información suministrada por los $k$ ejemplos del conjunto de entrenamiento más cercanos al que queremos clasificar. !!!side:5 Aunque esta decisión solo resuelve el problema en clasificaciones binarias, y hay que ajustarla cuando tenemos un número superior de clases. En problemas prácticos donde se aplica esta regla de clasificación se acostumbra tomar un número, $k$, de vecinos impar para evitar posibles empates [5]. En otras ocasiones, en caso de empate, se selecciona la clase que verifique que sus representantes tengan la menor distancia media al nuevo ejemplo que se está clasificando. En última instancia, si también así se produce un empate, siempre se puede decidir aleatoriamente entre las clases con mayor representación. A partir de una idea tan simple es fácil introducir variantes que se espera funcionen mejor, aunque suele ser a cambio de introducir complejidad computacional. Una posible variante consiste en **ponderar la contribución de cada vecino** de acuerdo a la distancia entre él y la muestra a ser clasificada, dando mayor peso a los vecinos más cercanos frente a los que puedan estar más alejados. Por ejemplo, podemos ponderar el voto de cada vecino de acuerdo al cuadrado inverso de sus distancias: Si $x$ es el ejemplo que queremos clasificar, $V$ son las posibles clases de clasificación, y $\{x_1,\dots,x_k\}$ es el conjunto de los $k$ ejemplos de entrenamiento más cercanos, definimos el peso de $x_i$ respecto a $x$ como: $$w_i = \frac{1}{d(x,x_i)^2}$$ y entonces la clase asignada a $x$ es aquella que verifique que la suma de los pesos de sus representantes sea máxima, es decir: $$argmax_{v \in V} \sum_{i=1}^k w_i$$ Esta mejora es muy efectiva en muchos problemas prácticos. Es robusto ante el ruido de los datos y suficientemente efectivo en conjuntos de datos grandes.  Un problema que presenta kNN es que requiere de mucha memoria y tiempo de ejecución porque hay que almacenar continuamente todos los datos que definen el espacio de ejemplos inicial y hay que calcular las distancias de todos ellos a la nueva muestra que se quiere clasificar. Sin embargo, es muy probable que muchas de las muestras iniciales no sean necesarias para clasificar las demás, ya que su información es redundante con las otras existentes. Algunas variantes interesantes que intentan mitigar este problema son: !!!side:6 Observa que depende del orden dado a los datos y, además, tiene el problema de conservar los datos que introducen ruido al sistema. 1. **kNN Condensado**: Dado un orden en los datos de entrada, cada ejemplo $x_k$ del conjunto de entrada se clasifica por medio de kNN haciendo uso únicamente de los datos anteriores según ese orden $\{x_1,\dots, x_{k-1}\}$. Si la clasificación obtenida para $x_k$ coincide con la real, ese ejemplo se elimina de los datos (ya que los demás elementos pueden reproducirlo), si no, permanece [6]. 2. **kNN Reducido**: es similar a la 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. Al revés de lo que ocurre con la condensación, este método es capaz de eliminar las muestras que producen ruido, y guarda aquellas que son críticas para la clasificación. A pesar de estas variantes, un problema fundamental que presentan estos algoritmos es que no proporcionan un mecanismo independiente de los datos, sino que precisa del conjunto de entrenamiento completo (o los reducidos) para poder evaluar cualquier nuevo ejemplo. Lo que significa que el algoritmo debe acompañarse de los datos de aprendizaje para poder ser aplicado. Si el conjunto de datos es muy grande, el algoritmo puede llegar a ser muy ineficiente. Aunque hemos visto que hay variantes que permiten reducir el coste de este proceso, en ningún caso se proporciona como resultado un algoritmo libre de datos (en este sentido, se dice que este modelo es **no paramétrico**). Así que, en resumen, el clasificador kNN es un algoritmo de aprendizaje **no paramétrico** y **basado en instancias:** !!!side:7 Por ejemplo, supongamos que nuestros datos son altamente no gausianos, pero el modelo de aprendizaje que elegimos asume una forma gaussiana. En ese caso, nuestro algoritmo haría predicciones extremadamente pobres. * **No paramétrico** significa que no hace suposiciones explícitas sobre la forma funcional de la relación que está intentando aproximar, evitando los peligros de modelar mal la distribución subyacente de los datos [7]. * **Basado en instancias** significa que nuestro algoritmo no aprende explícitamente un modelo. En su lugar, elige memorizar las instancias de entrenamiento que posteriormente se utilizan como *conocimiento* para la fase de predicción. Concretamente, esto significa que solo cuando se hace una consulta a nuestra base de datos (es decir, cuando le pedimos que prediga una etiqueta a la que se le ha dado una entrada), el algoritmo utilizará las instancias de entrenamiento para devolver una respuesta. En este punto, probablemente la pregunta esencial es cómo elegir la variable $k$ y cuáles son sus efectos en el clasificador. Como la mayoría de los algoritmos de aprendizaje, la $k$ en kNN es lo que se denomina un **hiperparámetro** que el diseñador debe elegir para obtener el mejor ajuste posible para el conjunto de datos. Intuitivamente, se puede pensar que $k$ controla la forma de la frontera entre las distintas clases del problema (los **límites de decisión**): * Cuando $k$ es pequeño, estamos restringiendo la región de una predicción dada y forzando al clasificador a ser *más ciego* a la distribución general. Un valor pequeño para $k$ proporciona el ajuste más flexible, que tendrá un **sesgo bajo** pero una **alta varianza**. Gráficamente, el límite de decisión será más dentado. * Por otro lado, un valor $k$ más alto promedia más votantes en cada predicción y por lo tanto es más resistente a valores atípicos. Los valores más grandes de $k$ tendrán límites de decisión más suaves, lo que significa **menor varianza**, pero **mayor sesgo**.  A pesar de todo lo anterior, es un algoritmo que está en la caja de herramientas de cualquier profesional del análisis de datos, ya que es tremendamente sencillo de aplicar y proporciona unos primeros resultados que permiten medir la eficiencia comparada de otros modelos más elaborados. kNN se utiliza a menudo en **aplicaciones** de búsqueda en las que se buscan elementos *similares*; es decir, cuando la tarea es de alguna forma la de *encontrar elementos similares a uno dado* (a veces, a esto se le llama una **búsqueda kNN**). La forma de medir la similitud es creando una representación vectorial de los elementos, y luego comparando los vectores utilizando una métrica de distancia apropiada (como la distancia euclídea, por ejemplo). Algunos ejemplos concretos de búsqueda de kNN podrían ser: * **Búsqueda por Conceptos**: Búsqueda de documentos semánticamente similares (es decir, documentos que contienen temas similares). Se utiliza, por ejemplo, para ayudar a las empresas a encontrar todos los correos electrónicos, contratos, etc. que son relevantes para una demanda. * **Sistemas de Recomendación**: Posiblemente, el mayor caso de uso de la búsqueda kNN. Si sabe que a un usuario le gusta un artículo en particular, entonces el objetivo es recomendarle artículos similares. Para encontrar artículos similares, se compara el conjunto de usuarios a los que les gusta cada artículo; si a un conjunto similar de usuarios les gustan dos artículos diferentes, entonces los artículos en sí son probablemente similares. Esto se aplica a la recomendación de productos, a la recomendación de medios de consumo, o incluso a la *recomendación* de anuncios para mostrar a un usuario. kNN no es tan popular como las redes neuronales o las SVM, y por lo general funciona más lentamente y tiene menor precisión que estas otras aproximaciones, pero tiene algunas buenas cualidades prácticas: es fácil de entrenar (porque no hay entrenamiento), fácil de usar, y es fácil interpretar sus resultados (porque nos puede dar las muestras más similares que determinan el resultado de un ejemplo). De hecho, se utiliza más en la industria de lo que podría pensarse inicialmente. Por ejemplo, algunas empresas utilizan algoritmos de aprendizaje profundo para generar vectores de características que representan los rostros de personas... luego, usan kNN para identificar a una persona comparando su vector de características con la lista de vectores que tienen almacenadas e identificadas. ¿La razón? kNN es lo suficientemente bueno y no sería práctico entrenar un clasificador separado para cada persona de la lista de vigilancia. Hoy en día se usa una técnica similar para clasificar de forma sencilla la huella digital de los usuarios de un dispositivo. # Algoritmo de Aprendizaje No Supervisado: K-Medias  Como ejemplo de algoritmo de aprendizaje no supervisado vamos a explicar brevemente el que, posiblemente, sea el más sencillo y extendido de todos ellos, el **Algoritmo de $K$-medias**, que, al igual que el anterior, es aplicable en los casos en que tengamos una representación de nuestros datos como elementos en un espacio métrico. En [esta otra entrada](http://www.cs.us.es/~fsancho/?e=230) se puede ver un repaso más general de otros métodos de clustering, de los que $K$-medias es solo un ejemplo (sencillo, pero limitado). El algoritmo de $K$-medias intenta encontrar una partición de las muestras en $K$ agrupaciones, de forma que cada ejemplo pertenezca a una de ellas, concretamente a aquella cuyo centroide esté más cerca. El mejor valor de $K$ para que la clasificación separe lo mejor posible los ejemplos no se conoce a priori, y depende completamente de los datos con los que trabajemos. Aunque se puede parecer al problema planteado en la sección anterior, aquí se ve claramente la diferencia con un algoritmo supervisado: en este caso, **no tenemos un conocimiento a priori que nos indique cómo deben agruparse ninguno de los datos de que disponemos**, es decir, no hay un protocolo externo que nos indique lo bien o mal que vamos a realizar la tarea... **ningún criterio supervisa la bondad de nuestras soluciones**. Pero eso no significa que nosotros no podamos introducir una medida de bondad, aunque sea artificial y subjetiva. En este caso, el algoritmo de las $K$-medias va a intentar minimizar la varianza total del sistema, es decir, si $c_i$ es el centroide de la agrupación $i$-ésima, y $\{x_j^i\}_j$ es el conjunto de ejemplos clasificados en esa agrupación, entonces intentamos minimizar la función: $$ \sum_i \sum_j d(x_j^i,c_i)^2$$ Intuitivamente, cuanto más pequeña sea esta cantidad, más agrupados están los ejemplos en esas bolsas. Pero observemos que el número de bolsas no viene dado por el algoritmo, sino que hemos de decidirlo antes de ejecutarlo. ![](./img/hqdefault.jpg align="right")A pesar de que el problema se plantea como una optimización (minimización de un potencial) que puede resultar relativamente compleja, existe un algoritmo muy sencillo que devuelve el mismo resultado (en la mayoría de las ocasiones). Fijado $K$, los pasos que sigue el algoritmo son los siguientes: 1. Seleccionar al azar $K$ puntos del conjunto de datos como **centros** iniciales de los grupos. 2. Asignar el resto de ejemplos al centro más cercano (ya tenemos $K$ agrupaciones iniciales). 3. Calcular el **centroide** de los grupos obtenidos. 4. Reasignar los centros a estos centroides. 5. Repetir desde el paso 2 hasta que no haya reasignación de centros (o los últimos desplazamientos estén por debajo de un umbral). El algoritmo anterior es relativamente eficiente, y normalmente se requieren pocos pasos para que el proceso se estabilice pero, en contra, es necesario determinar el número de agrupaciones a priori. Además, como ocurre en muchos problemas de optimización por aproximaciones sucesivas, el sistema es sensible a la posición inicial de los $K$ centros, haciendo que no consigan un mínimo global, sino que se sitúe en un mínimo local (algo muy común cuando se trabaja con un problema de optimización no convexo). Por desgracia, no existe un método teórico global que permita encontrar el valor óptimo de grupos iniciales ni las posiciones en las que debemos situar los centros, por lo que se suele hacer una aproximación experimental repitiendo el algoritmo con diversos valores y posiciones de centros. Un valor elevado de $K$ hace que el error disminuya, pero a cambio se tiene un sobre entrenamiento que disminuye la cantidad de información que la agrupación resultante da. De hecho, si se toma $K$ igual al tamaño del conjunto de entrenamiento, es decir, tantas agrupaciones como puntos, el potencial anterior resulta ser $0$, y aunque es un mínimo real del potencial, es poco informativo, ya que no produce agrupamientos que enriquezcan la información sobre cada ejemplo indicando cuáles son similares a él, sino que considera que cada elemento es un grupo independiente. (insert menu.md.html here)