Aprendizaje supervisado - Clasificación

Contenido:

Regresión logística LOGR
Arboles de decisión
1. Índice Gini
Support Vector Machine SVM
Bagging – Bootstrap aggregating
Boosting

Regresión logística

LOGR o regresión logit, a pesar de su nombre no tiene nada que ver con algoritmos de regresión, si no que es un algoritmo de clasificación. Funciona creando una frontera lineal entre dos clases, es decir que nos da una probabilidad de que la predicción pertenezca a una determinada clase, suele ser $P>0.5=1$ pero podemos fijar este criterio de decisión dependiendo de nuestra necesidad.

Una de las métricas mas utilizadas para medir la bondad de los clasificadores es la métrica AUC(área bajo la curva). La curva ROC mide la relación entre las tasas de aciertos y de falsos positivos en función del umbral de clasificación. Cuanto mayor sea el área bajo la curva ROC, mejor será el clasificador. Un clasificador perfecto tendrá un valor de AUC = 1.

Como mencionamos anteriormente, este algoritmo separa en dos clases, es decir que cuando tenemos un problema multiclase lo que hace es validar una clase frente a todos los demás, si no corresponde toma la siguiente clase y vuelve a comparar, algo como un switch case iterativo, separa todos los items de una clase, luego la siguiente y así sucesivamente hasta que crea una línea de separación por cada clase, lo que significa que tenemos un subproblema por cada clase a predecir; con cada línea(corete de frontera) se calculan las bisectrices.

Para llevar a cabo el entrenamiento utilizamos una función matemática que permite devolver predicciones a partir de la transformación exponencial de una combinación lineal de los atributos.

$\hat{y}=\frac{1}{1+e^{-W_0-W_1\cdot X_1-\cdots -W_p\cdot X_p}}$

Como mencionamos es un proceso iterativo, en donde cada época los coeficientes se van actualizando para acercarse al resultado deseado(separar la clase de las demás). El valor optimo de estos coeficientes son aquellos que maximizan la siguiente función objetivo(función de verosimilitud):

$f(W_0,\cdots,W_p)=\sum_{i=1}^{n}y_i\cdot ln(\hat{y_i})+(1-y_i)\cdot ln(1-\hat{y_i})$

Ventajas:

Simplicidad
Fácil de interpretar las predicciones
Tiempo de entrenamiento razonable
Tiempo de predicción casi instantáneo

Desventajas:

Se asume que los atributos son independientes, no tienen una correlación significativa
Modelo muy simple, solo permite crear una línea de decisión entre dos clases

Árboles de decisión

Es un modelo de conocimiento que puede generarse a partir de datos y puede usarse tanto para clasificación como regresión. Se divide el conjunto de datos de manera jerárquica en trozos menores hasta lograr llegar a una única clase.

A Tutorial to Understand Decision Tree ID3 Learning Algorithm

Una introducción visual al machine learning

Antes de ver la implementación vamos a conocer el índice de Gini, veamos un ejemplo.

En este caso vamos a calcular el índice Gini por género.

$p_g=\frac{9}{16}=0.56$

$q_g=1-p_g=0.44$

$G_g=p_{g}^2+q_{g}^2=0.50$

$p_b=\frac{6}{14}=0.42$

$q_b=1-p_b=0.58$

$G_b=p_{b}^2+q_{b}^2=0.51$

Tenemos el índice de Gini para las chicas y los chicos, ahora para sacar el ponderado por genero lo que hacemos es sumar ambos índices por la frecuencia de las posibilidades.

$Gini_G=\frac{16}{30}\cdot G_g+\frac{14}{30}\cdot G_b$

$Gini_G=\frac{16}{30}\cdot 0.50+\frac{14}{30}\cdot 0.51$

$Gini_G=0.50$

En este caso solo lo hicimos con un atributo, pero la idea es hacerlo por todos los atributos, por ejemplo altura, edad, etc. Este valor nos sirve para detectar los atributos mas discriminativos, es decir calculamos el índice Gini para cada condición y la que tenga mas valor es la que tiene mayor rango en la jerarquía.

Tree Based Algorithms: A Complete Tutorial from Scratch (in R & Python)

Ventajas:

Simplicidad
Fácil de interpretar las predicciones
Tiempo de entrenamiento razonable
Tiempo de predicción muy rápido
Flexibilidad en la características de los datos

Desventajas:

Riesgo de sobreajuste
Sensibilidad al desbalanceo de las clases

Support Vector Machine(SVN)

Este algoritmo funciona a partir de funciones discriminales lineales, es decir que se limita a discriminar entre dos clases, sin embargo no significa que debamos huir a problemas multiclase, lo que hacemos es un one vs all para abordar estos problemas.

Consiste en hallar un hiperplano optimo capaz de separar el espacio muestral en dos regiones de manera que cada región pertenezca a una clase, donde el optimo es el que maximiza el margen.

A los dos puntos mas cercanos que tocan el limite del margen se les llama vectores de soporte. Definiendo un hiperplano positivo y uno negativo.

Dada una muestra $(x_i,y_i)$ y un hiperplano denotado por un vector $w$ y un bias $b$ , el objetivo es determinar la distancia de $x_i$ al hiperplano.

$\beta =w\cdot x +b$

$D=\{|(x_i,y_i)|x_i\in\mathbb{R}^{n}, y_1\in\{-1,1\}\}_{i=1}^{m}\to \textrm{}_{i=1\cdots m}^{B=\textrm{min}\beta_i}$

Al utilizar esta función nos encontramos con el problema del signo negativo, donde en la anterior imagen al minimizar $\beta$ pareciera que cualquiera de las dos opciones funciona pero solo hay un hiperplano optimo.

Para solucionar esto se introduce la variable $y$ de manera que:

Si el resultado es positivo la clasificación es correcta
Si el resultado es negativo la clasificacion es incorrecta

Ahora el objetivo a minimizar es:

$F=\textrm{}_{i=1\cdots m}^{B=\textrm{min }y_i(w\cdot x_i+b)}$

Tenemos adicionalmente otro problema, por ejemplo, un vector $w_1=(2,1)$ y $b_1=5$ representa el mismo hiperplano que el vector $w_2=(20,10)$ y $b_2=50$ . Vemos que en el caso de $w_2$ tenemos una $F$ diez veces mayor. A esto se le conoce como problema de escala. La solucion es dividir el vector $w$ y el bias $b$ , por su norma; por lo que la función objetivo a minimizar seria:

$M=\textrm{}_{i=1\cdots m}^{B=\textrm{min}}y_i(\frac{w}{||w||}\cdot x+\frac{b}{||w||})$

Minimizando:

$\textrm{min}\frac{1}{2}||w||^2$ donde $y_i(w\cdot x_i)+b\geq 1,i=1,\cdots,m$

Hasta ahora este proceso me genera un hard margin SVN que requiere que mis datos sean linealmente separables y que no haya distorcion en los datos; para solventar esto surge soft margin SVN.

El soft margin SVN introduce una variable de holgura capaz de minimizar los errores de predicción, permitiendo cometer mas errores de clasificación durante el entrenamiento, su función a minimizar es:

$\textrm{min}\frac{1}{2}||w||^2+C\sum_{i=1}^{m}\zeta_i$

Donde

$y_i(w\cdot x_i+b)\geq 1-\zeta_i$
$\zeta_i\geq0$ para cualquier $i=1,\cdots,m$

$C$ (box constraint) es un parámetro de regularización que controla la compensación entre la penalización de las clasificaciones erróneas(teniendo en cuenta las variables de holgura) y el ancho del margen.

Usando hard margin SVN podemos generar un problema de overfiting, ya que el hiperplano optimo se ajustara a nuestros datos.

Usando la librería de SKlearn al colocar la $C$ , entre mas alto menos importancia le damos a los errores y por lo tanto hay mas permisividad pero puedo caer en underfiting.

Mencionamos que se puede utilizar en datos linealmente separables, pero cuando no lo son podemos aplicar el kernel trick usando una función kernel(cuadrático, gaussiano, etc); esto permite proyectar un espacio muestral D-dimensional a otro espacio M-dimensional, donde $M>D$

$\varnothing:\mathbb{R}^{D}\to\mathbb{R}^{M}$

Esto permite separar de manera lineal aquellos datos que originalmente no eran separables.

Cuando trabajamos con kernel otro hiperparámetro que podemos usar es Gamma, se utiliza con la función RBF(radial basiss function) de kernel gaussiano. Este permite definir el grado de curvatura de la frontera de decisión. Normalmente se usan valores de gamma entre 0.01 y 100

$\gamma=\frac{1}{2\sigma^2}$

$RBF=e^{-\gamma\cdot||x-x'||}$

menos permisivo –> más importancia a errores de entrenamiento

más permisivo –> menos importancia a errores de entrenamiento

Bagging - Bootstrap aggregating

Divide en varios subconjuntos los datos de entrenamiento.
Se crea un modelo(clasificador) por cada subdataset. Se puede utilizar cualquier clasificador pero el mas usado son los arboles de decisión dando el método mas conocido, random forest. Se utilizan también distinto numero de características en cada subdataset. El uso del modelo se basa en weak learners (clasificadores con al menos un 51% de éxito) para construir el strong learner
La clasificación final se obtiene del promedio de todos los clasificadores. De esta manera este algoritmo reduce la varianza y minimiza el overfitting.

Árboles de decisión, random forest, gradient boosting y C5.0

Ventajas:

Eficiente sin ajustar hiperparámetros en problemas de clasificación y regresión
Estabilidad y robustez en la predicción, ya que al utilizar muchos árboles prevalece el promedio de las votaciones.
Posibilidad de utilizar gran cantidad de características
Tiende a reducir el riesgo de overfitting.

Desventajas:

Coste computacional más elevado que construir un solo árbol de decisión.
Inconsistencia cuando se utilizan datasets pequeños.

RandomForestClassifier

BOOSTING

El entrenamiento se realiza creando también varios modelos, pero en esta ocasión lo hace en serie y en cada iteración conserva el error cometido en la anterior iteración para mejorar el modelo actual.

Aquí también se utiliza mucho los arboles de decisión como método de decisión. Y su método mas conocido es Adaboost.

Adaboost solo se crea árboles compuestos por un solo nodo, es decir evaluá una característica y saca dos posibles predicciones, lo que se denomina stump; de esta manera, se crea lo que se conoce como Forest of Stumps. Los stumps no son buenos clasificadores por sí solos, por eso son weak learners. La idea es utilizar el stump que tenga un menor índice Gini.
Adaboost aplica la técnica de majority voting de manera ponderada, por lo que algunos árboles contribuyen más que otros en la decisión final. Esta ponderación se hace con la siguiente ecuación:
$\textrm{Importancia}=\frac{1}{2}log(\frac{1-\textrm{Total Error}}{\textrm{Total Error}})$
*El error es igual al número de fallos cometidos entre el total de los registros

$E_\gamma =\frac{1}{8}=0.125$

$\textrm{Importancia}=\frac{1}{2}log(\frac{1-0.125}{0.125})=0.973$

En los registros donde se cometen errores otorgamos mayor peso $\textrm{weight}_{t+1}=\textrm{weight}_t\cdot e^{\textrm{importancia}}$
Donde no se cometen errores $\textrm{weight}_{t+1}=\textrm{weight}_t\cdot e^{-\textrm{importancia}}$
Tomando el ejemplo anterior:
$\textrm{weight}_{2}=\frac{1}{8}\cdot e^{0.97}=0.33$ para el caso incorrecto
$\textrm{weight}_{2}=\frac{1}{8}\cdot e^{-0.97}=0.05$ para los casos correctos
Se normalizan los pesos dividiendo cada valor entre el sumatorio de los nuevos pesos. Los pesos normalizados constituirán el nuevo sample weight.
Se define un conjunto de datos vacío de las mismas dimensiones que el original. Después, se selecciona aleatoriamente un valor entre 0 y 1, y se añade el registro correspondiente en función de la suma ponderada de la columna de sample weight.