Desequilibrio de Clases Desde SMOTE hasta SMOTE-NC y SMOTE-N

Desequilibrio de Clases con SMOTE, SMOTE-NC y SMOTE-N

Explorando tres algoritmos para abordar el problema de desequilibrio de clases

En la historia anterior explicamos cómo funcionan los algoritmos de sobremuestreo aleatorio ingenuo y sobremuestreo aleatorio con ejemplos (ROSE). Más importante aún, también definimos el problema de desequilibrio de clases y derivamos soluciones para él con intuición. Recomiendo encarecidamente revisar esa historia para asegurar una comprensión clara del desequilibrio de clases.

En esta historia, continuaremos considerando los algoritmos SMOTE, SMOTE-NC y SMOTE-N. Pero antes de hacerlo, es importante señalar que los dos algoritmos que consideramos en la última historia se ajustan al siguiente marco de implementación:

1. Definir cómo el algoritmo toma los datos pertenecientes a la clase X que necesita Nx ejemplos y calcula dichos ejemplos mediante sobremuestreo
2. Dado un hiperparámetro de proporciones, calcular la cantidad de puntos que deben agregarse para cada clase
3. Para cada clase, ejecutar el algoritmo y luego combinar todos los puntos recién agregados junto con los datos originales para formar el conjunto de datos sobremuestreado final

Tanto para los algoritmos de sobremuestreo aleatorio como para los algoritmos ROSE, también fue cierto que para generar Nx ejemplos para la clase X, el algoritmo hace lo siguiente:

• Elegir Nx puntos al azar con reemplazo de los datos pertenecientes a la clase X
• Realizar una lógica en cada uno de los puntos elegidos para generar un nuevo punto (por ejemplo, replicación o colocación de una distribución gaussiana y muestreo de ella)

Se mantiene que el resto de los algoritmos que consideraremos en esta historia también se ajustan al mismo marco.

SMOTE (Técnica de Sobremuestreo de Minorías Sintéticas)

• Ingeniería de datos geoespaciales Indexación espacial
• Google marca con marcas de agua las imágenes generadas por intelige...
• Esta investigación de IA aborda el problema de la pérdida de plasti...

Por lo tanto, para explicar lo que SMOTE hace, solo necesitamos responder una pregunta: ¿Qué lógica se realiza en cada uno de los Nx ejemplos elegidos al azar con reemplazo de la clase X para generar Nx ejemplos nuevos?

La respuesta es la siguiente:

• Encontrar los k-vecinos más cercanos del punto (k es un hiperparámetro del algoritmo)
• Elegir uno de ellos al azar
• Dibujar un segmento de línea desde el punto hasta ese vecino elegido al azar
• Elegir al azar un punto en ese segmento de línea
• Devolverlo como el nuevo punto

Matemáticamente,

• Si el punto x_i tiene como vecinos más cercanos a z_i1, z_i2, …, z_ik
• Y si j es un número aleatorio en [1,k]
• Y r es un número aleatorio en [0, 1]

entonces para cada punto x_i, SMOTE genera un nuevo punto x_i’ simplemente aplicando:

Esto es realmente todo lo que hace el algoritmo SMOTE. Desde el punto x_i, camina una distancia r a lo largo del vector z_ij — x_i y coloca un nuevo punto.

Una pequeña nota al margen es que hay una pequeña diferencia en cómo opera el algoritmo en comparación con cómo se presenta en el artículo. En particular, los autores asumen que las proporciones son enteros (y los redondean hacia abajo si no lo son). Si la proporción para la clase X es un número entero C, entonces para cada punto en ella se elige un vecino aleatorio con reemplazo C veces y luego se aplica la lógica de SMOTE que describimos. En la práctica, cuando se implementa SMOTE, generalmente se generaliza para trabajar con proporciones de punto flotante como describimos, eligiendo Nx puntos al azar y luego aplicando SMOTE a cada uno. Para proporciones enteras como C=2, se sigue que cada punto se elige en promedio dos veces y volvemos al algoritmo original. Esto debería tener sentido, ya que es la misma transición del sobremuestreo mediante repetición con proporciones enteras al sobremuestreo aleatorio que se explicó en la última historia.

Esta animación muestra cómo cambian las regiones de decisión de un SVM al cambiar la proporción de sobremuestreo para la clase versicolor en un subconjunto desequilibrado del conjunto de datos Iris. La proporción aquí se refiere al tamaño de la clase mayoritaria. Es decir, una proporción de 1.0 establecería Nx de manera que la clase versicolor tenga tantos ejemplos como la clase virginica.

Puede que estés pensando por qué SMOTE es mejor que ROSE. Después de todo, la lógica de generación de puntos de SMOTE no ha sido justificada en el artículo; mientras tanto, muestrear a partir de una estimación de P(x|y) como se hace en ROSE es mucho más racional e intuitivo. Un problema es posiblemente que obtener una buena estimación de P(x|y) requiere muchos datos; sin embargo, sabemos que las clases minoritarias a menudo tienen pocos datos. Si no tenemos muchos datos, tenemos dos opciones:

1. Elegir el ancho de banda demasiado pequeño, donde volvemos a posibles sobreajustes como en el sobremuestreo aleatorio
2. Elegirlo demasiado grande, lo que en el caso extremo equivale a simplemente agregar puntos aleatorios uniformemente desde el espacio de características (es decir, ejemplos poco realistas)

Si lo piensas, deberíamos preocuparnos menos por este problema en SMOTE. Si existe un hiperplano que separa perfectamente los datos, esa solución aún existe después de aplicar SMOTE. De hecho, la forma en que SMOTE genera puntos puede hacer que una hipersuperficie no lineal se vuelva más lineal, por lo que parece estar en un riesgo mucho menor de causar que el modelo se sobreajuste.

SMOTE-NC (SMOTE-Nominal Continuous)

Aunque tanto ROSE como SMOTE parecen ofrecer una mejora significativa sobre el sobremuestreo aleatorio ingenuo, tienen la desventaja de perder la capacidad de manejar variables categóricas, lo cual no era un problema para el sobremuestreo aleatorio ingenuo. Los autores de SMOTE fueron lo suficientemente inteligentes como para pensar en una forma de evitar esto desarrollando una extensión para el algoritmo SMOTE que maneje casos en los que también estén presentes características categóricas.

Puede que pienses que codificar las características categóricas sería una forma de solucionar esto; sin embargo, no estás totalmente en lo correcto porque SMOTE o ROSE las tratarán como continuas y generarán valores inválidos para ellas. Por ejemplo, si una característica es binaria, entonces el punto elegido a lo largo de la línea puede ser 0.57 para el nuevo punto, que no es 0 ni 1. Redondearlo es una mala idea porque eso equivale a elegir al azar si es 0 o 1.

Recuerda que esto es cómo SMOTE genera un nuevo punto:

• Supongamos que el punto x_i tiene vecinos más cercanos z_i1, z_i2, …, z_ik
• sea j un número aleatorio en [1,k]
• sea r un número aleatorio en [0, 1]

entonces para cada punto x_i, SMOTE genera un nuevo punto x_i’ simplemente aplicando

Debe ser obvio que no podemos aplicar el mismo método en presencia de características categóricas a menos que lo ampliemos respondiendo las siguientes dos preguntas

1. ¿Cómo se encuentran los k-vecinos más cercanos? La métrica de distancia euclidiana solo opera en características continuas.
2. ¿Cómo se genera el nuevo punto? No podemos aplicar la ecuación de SMOTE para generar la parte categórica de x_i’

Para la primera pregunta, los autores sugirieron una modificación a la distancia euclidiana para tener en cuenta la parte categórica. Supongamos que tanto x_i como z_ij involucran m características continuas y n características categóricas, entonces en la métrica modificada, las características continuas se restan y se elevan al cuadrado de forma natural, y luego se agrega una penalización constante por cada par de características categóricas diferentes. Esta penalización es en particular la mediana de las varianzas de todas las características continuas, que se puede calcular al comienzo del algoritmo.

Como ejemplo, para medir la distancia entre dos puntos x_1 y x_2

entonces si la mediana de las desviaciones estándar es m, la distancia está dada por

los últimos dos términos tienen en cuenta cómo las dos últimas características categóricas son diferentes.

Aunque los autores no proporcionan justificación para la métrica, puede tener sentido después de observar que una de las formas más comunes de medir distancias entre características categóricas es la distancia de Hamming. Simplemente se agrega 1 por cada par de características categóricas diferentes. Una distancia de Hamming de 6 sugiere que los dos puntos tienen valores diferentes en 6 de las características categóricas. Es obvio en nuestro caso que establecer la penalización como 1 como en la distancia de Hamming no es intuitivo porque si las características continuas varían mucho, los 1 serán muy insignificantes en la suma, lo que equivale a ignorar las características categóricas en la medida. Debería tener sentido que usar la diferencia promedio al cuadrado entre dos características continuas como penalización solucionaría este problema porque, en ese caso, si la varianza de las características continuas es a menudo grande, la penalización también es grande y no es insignificante. La única precaución es que los autores usaron la mediana de las varianzas y no su media, lo cual puede justificarse por su robustez frente a valores atípicos.

Responder la segunda pregunta es mucho más simple, ahora que hemos encontrado los k-vecinos más cercanos utilizando la métrica modificada, podemos generar la parte continua del nuevo punto utilizando la ecuación SMOTE como de costumbre. Para generar la parte categórica del nuevo punto, tiene sentido tomar simplemente la moda de las partes categóricas de los k-vecinos más cercanos. Es decir, permitir que los vecinos voten sobre los valores en la parte categórica donde los valores más comunes dominarán.

Se sigue que lo que SMOTE-NC hace para generar un nuevo punto es…

• Encontrar los k-vecinos más cercanos del punto (k es un hiperparámetro del algoritmo) utilizando la métrica Euclidiana modificada
• Elegir uno de ellos al azar
• Dibujar un segmento de línea desde el punto hasta ese vecino en el espacio de características continuas
• Elegir al azar un punto en ese segmento de línea
• Dejar que sea la parte continua del nuevo punto
• Para la parte categórica del nuevo punto, tomar la moda de las partes categóricas de los k-vecinos más cercanos.

SMOTE-N (SMOTE-Nominal)

Debería ser obvio que SMOTE-NC se convierte en SMOTE cuando no hay características categóricas involucradas, porque entonces la penalización es cero y se salta el paso de la moda en la generación. Sin embargo, si no hay características continuas involucradas, entonces el algoritmo se encuentra en una posición precaria porque no hay una penalización definida ya que no hay características continuas. Una solución alternativa podría ser establecerla como 1 o algo así y operar el algoritmo como de costumbre, pero eso no es ideal porque habrá fácilmente muchas coincidencias al calcular los vecinos más cercanos. Si la distancia de Hamming entre un punto y otros 10 puntos es 7, ¿realmente están todos igualmente cerca de ese punto? ¿O simplemente comparten en común que difieren del punto en 7 de las características?

SMOTE-N es otro algoritmo que los autores presentan en el artículo para tratar con datos que son puramente categóricos. Responde negativamente a la pregunta en cursiva anterior al emplear otra métrica de distancia sobre las características categóricas. Una vez que se encuentran los k vecinos más cercanos, la generación de los nuevos puntos se decide mediante el cálculo de la moda; sin embargo, esta vez el propio punto también participa en el cálculo.

Por lo tanto, basta explicar la métrica de distancia utilizada en SMOTE-N para realizar K-NN. La métrica se llama “métrica de distancia de valor modificada” (Cost & Salzberg, 1993) y opera de la siguiente manera, dados dos vectores de características con q valores categóricos y p_1, p_2, …, p_q posibles valores para cada una de las características categóricas respectivamente.

1. Codificar cada uno de los valores categóricos a través de un vector V de longitud K, donde K es el número de clases. V[i] debería ser la frecuencia de ese valor para la i_ésima clase dividida por su frecuencia en todas las clases.
2. Ahora cualquier vector categórico se representa por un tensor de q vectores, cada uno de longitud k
3. Calcular la distancia entre dos vectores categóricos representados por ese tensor, calculando la distancia de Manhattan entre cada par de vectores de longitud k y luego tomar la norma L2 del resultado

A modo de ejemplo, supongamos que queremos encontrar la distancia entre los siguientes dos vectores categóricos

entonces, dado que hay 3 clases, después de codificarlos supongamos que obtenemos

Después de calcular la distancia de Manhattan entre cada par de vectores, tenemos

lo cual equivale a 1.428 después de tomar la norma L2.

Para ser precisos, el artículo señala que es posible utilizar tanto la norma L1 como la L2 para la magnitud, pero no decide cuál utilizar para el algoritmo (aquí elegimos L2).

Puede que te preguntes por qué esto sería mejor que usar la distancia de Hamming simple. La respuesta definitiva es que los autores no lo han justificado. Sin embargo, solo para introducir una ligera intuición, argumentamos antes que la distancia de Hamming puede resultar a menudo en muchas coincidencias durante el cálculo de la distancia para KNN. Supongamos que tenemos tres vectores categóricos

Aquí, la distancia de Hamming sugeriría que x_2 y x_3 están tan cerca de x_1 como en ambos casos la distancia de Hamming es 1. Mientras tanto, la métrica de diferencia de valor modificada analizaría cómo se distribuye cada valor sobre las clases antes de decidir cuál es más cercano. Supongamos que las frecuencias por clase para B2 son [0.3, 0.2, 0.5] y para B3 son [0.1, 0.9, 0] y para B1 es [0.25, 0.25, 0.5]. En este caso, MVDM sugeriría que x_3 está mucho más cerca de x_1 porque B1 está mucho más cerca de B2 que de B3. Desde una perspectiva probabilística, si recogiéramos un nuevo punto con una clase desconocida, saber si la categoría es B2 o B3 no ayuda mucho a predecir la clase y en este sentido son similares o intercambiables.

Por lo tanto, en resumen, el algoritmo SMOTE-N funciona de la siguiente manera para generar un nuevo punto:

• Encuentra los k-vecinos más cercanos del punto (k es un hiperparámetro del algoritmo) utilizando la métrica de diferencia de valor modificada
• Devuelve la moda de los valores categóricos de los vecinos (incluyendo el propio punto) para generar el nuevo punto

¡Eso es todo! Ahora debería estar claro como el cristal cómo funcionan SMOTE, SMOTE-N y SMOTE-NC. Hasta la próxima, au revoir.

Referencias:

[1] N. V. Chawla, K. W. Bowyer, L. O.Hall, W. P. Kegelmeyer, “SMOTE: synthetic minority over-sampling technique,” Journal of artificial intelligence research, 321–357, 2002.

• Class Imbalance
• classification
• Imbalanced Data
• Machine Learning
• Smote