« Una introducción a Pr… « || Inicio || » Mapas Auto-Organizado… »

Aprendizaje Supervisado y No Supervisado

Última modificación: 18 de Diciembre de 2019, y ha tenido 35534 vistas

Etiquetas utilizadas: || || ||

Como se ha comentado brevemente en la entrada de Introducción al Aprendizaje Automático, los modelos de aprendizaje supervisado son aquellos en los que producen funciones a partir de un conjunto de ejemplos de los que conocemos la salida deseada (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, y modelos de regresión, si la salida es un valor de un espacio continuo). En contra, los modelos de aprendizaje no supervisado son aquellos en los que no estamos interesados en producir una función que se ajuste a una salida deseada obtenida a priori, sino en aumentar el conocimiento de los datos disponibles (y posibles datos futuros), por ejemplo, dando una agrupación de los ejemplos según su similaridad (clustering), o simplificando las estructura de los mismos manteniendo sus características fundamentales (como en reducción de la dimensionalidad).

Aunque estas definiciones son generales y contienen entre las dos la prática totalidad de los algoritmos de aprendizaje más comunes, a modo de ejemplo y para fijar las ideas principales en lo que sigue nos vamos a centrar en dos algoritmos concretos, uno de cada tipo, que pueden servir de representación para entender su comportamiento más general, y que nos permitirán también introducir en entradas posteriores los conceptos generales de matriz de confusión, error, sobre-aprendizaje, etc.

Algoritmo de Aprendizaje Supervisado: K-NN

El algoritmo de los k vecinos más cercanos (k-NN, o k Nearest Neighbour) es un algoritmo de clasificación supervisado basado en criterios de vecindad. En particular, k-NN se basa en la idea de que los nuevos ejemplos serán clasificados según la clase a la cual pertenezca la mayor cantidad de vecinos más cercanos a ellos del conjunto de entrenamiento.

En particular, el algoritmo del vecino más cercano (aquel que asigna a una nueva muestra la clasificación de la muestra más cercana) 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 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 regla de los k vecinos más cercanos (k-NN), que es una extensión en la que se utiliza la información suministrada por los k ejemplos del conjunto de entrenamiento más cercanos al que queremos clasificar.

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 (aunque esta decisión solo resueve el problema en clasificaciones binarias). 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 se produce un empate, siempre se puede decidir aleatoriamente entre las clases con mayor representación.

Una posible variante de este algoritmo consiste en ponderar la contribución de cada vecino de acuerdo a la distancia entre él y el ejemplar a ser clasificado, 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_i\}\) es el conjunto de los \(k\) ejemplos de entrenamiento más cercanos, definimos

\[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:

\[argmax_{v \in V} \sum_{i=1...k,\ x_i\in v} 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 fundamental que presenta este algoritmo es que no proporciona un mecanismo independiente de los datos, sino que precisa del conjunto de entrenamiento completo 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 hay variantes que permiten optimizar el proceso y disminuir el conjunto de datos para aligerar la dependencia de este conjunto, 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).

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.

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 las K-medias, que es aplicable en los casos en que tengamos una inmersión de nuestros ejemplos en un espacio métrico.

En esta otra entrada 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. Este algoritmo intenta minimizar la varianza total del sistema, es decir, si \(c_i\) es el centroide de la agrupación \(i\)-ésima, y \(\{x_j^i\}\) 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\]

El algoritmo que se sigue es el siguiente:

  1. Seleccionar al azar \(K\) puntos como centros de los grupos.
  2. Asignar los ejemplos al centro más cercano.
  3. Calcular el centroide de los ejemplos asociados a cada grupo.
  4. Repetir desde el paso 2 hasta que no haya reasignación de centros (o su último desplazamiento esté 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, y 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 unn 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. En general, 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.

 

Para saber más...

Tutorial clustering K-medias

Wikipedia: K vecinos más cercanos

Clasificadores KNN

Cluster: K-medias

« Una introducción a Pr… « || Inicio || » Mapas Auto-Organizado… »