Modelos de Clasificación y Regresión: Árboles de Decisión, SVM y Más

Árboles de Decisión: Fundamentos y Aplicaciones

Los árboles de decisión son modelos ampliamente utilizados para resolver problemas de clasificación y regresión, tanto en tareas binarias como multiclase. Ofrecen un enfoque estructurado y condicional, basado en la estrategia de "divide y vencerás".

Estructura de un Árbol de Decisión

1. Nodos: Representan preguntas o pruebas sobre los atributos. Pueden ser:
   • Nodos simbólicos: Tienen tantas ramas como valores posibles del atributo.
   • Nodos continuos: Crean ramas basadas en un umbral (por ejemplo, <, >).
2. Hojas: Asignan una predicción o clasificación a todas las instancias que llegan a esa hoja.

Un árbol de decisión puede representarse como un conjunto de reglas.

Generación de Reglas en Árboles de Decisión

Cada ruta desde la raíz hasta una hoja forma una regla. El antecedente de la regla incluye las condiciones de los nodos, y el consecuente es la clase asignada. Estas reglas a menudo se simplifican mediante la poda (pruning) para eliminar redundancias.

Desafíos Comunes en Árboles de Decisión

• Subárboles replicados o reglas redundantes.
• Reglas contradictorias en ejemplos ambiguos.
• Dificultad para expresar disyunciones.

Construcción de Árboles de Decisión

La construcción se realiza de forma recursiva:

1. Seleccionar el atributo raíz: Se elige el atributo que mejor divide los datos, maximizando la ganancia de información.
2. Crear ramas: Se generan ramas para cada valor posible del atributo.
3. Dividir el conjunto: Los datos se dividen en subconjuntos según cada rama.
4. Repetir el proceso: Se repite el proceso para cada rama, utilizando solo los datos que alcanzan esa división.
5. Criterios de parada:
   • Todas las instancias de un nodo pertenecen a la misma clase.
   • No quedan atributos disponibles.

Criterios para la Selección de Atributos

Se utiliza un enfoque heurístico para maximizar la pureza de los nodos. Se prefieren los atributos que generan divisiones con nodos de clases homogéneas.

Ganancia de Información y Entropía

La ganancia de información mide el aumento de pureza después de dividir los datos según un atributo.

Fórmula: Ganancia = Entropía(E) - Entropía Ponderada(X)

La entropía mide el desorden en un conjunto de datos E. Si todas las instancias pertenecen a la misma clase, la entropía es 0.

Fórmula: Entropía(E) = -∑(j=1,k) p_j log₂(p_j), donde k es el número de clases y p_j es la proporción de instancias en la clase j.

Ratio de Ganancia

El ratio de ganancia normaliza la ganancia de información para evitar favorecer atributos con muchos valores.

Fórmula: Ratio de Ganancia = Ganancia / Información Intrínseca

Clasificación de Atributos en Árboles de Decisión

1. Atributos Nominales: Cada valor genera una rama. Un atributo puede probarse más de una vez si sus valores se dividen en subconjuntos.
2. Atributos Numéricos: Se realizan pruebas basadas en umbrales (<, ≤, >, ≥). Las divisiones pueden considerar números enteros (menor, igual o mayor) o reales (rango).

Los valores desconocidos pueden tratarse de varias maneras:

• Asignar el valor más común.
• Dividir la instancia en partes ponderadas, asignando un peso numérico a cada rama.

Tipos de Árboles de Decisión

1. Árbol Funcional: Los nodos de opción dividen las instancias en varias hojas, generando predicciones alternativas (por ejemplo, clasificaciones combinadas mediante votación).
2. Árboles de Regresión: Las hojas contienen valores numéricos promedio. Son más precisos para datos continuos y capturan mejor patrones simples.
3. Árboles de Modelo: Las hojas contienen expresiones lineales en lugar de valores concretos, aproximando funciones continuas mediante combinaciones lineales.

Algoritmo C4.5

El algoritmo C4.5 es una evolución del ID3, utilizado para construir árboles de decisión. Divide los datos para maximizar la pureza en los subconjuntos.

Pasos Principales de C4.5:

1. Calcular la entropía del conjunto original.
2. Dividir el conjunto según un atributo X, calculando la entropía ponderada.
3. Calcular la ganancia de información y el ratio de ganancia.
4. Elegir el atributo con mayor ratio de ganancia como el mejor para dividir en ese nodo.

Ventajas de los Árboles de Decisión

• Producen modelos visuales y fácilmente interpretables.
• Funcionan con datos categóricos y numéricos.
• Pueden ajustarse para evitar el sobreajuste, por ejemplo, mediante la poda.

Problemas Multiclase: Estrategias One vs One y One vs Rest

En el aprendizaje supervisado, algunos problemas requieren predecir una clase entre múltiples opciones. Dos enfoques comunes son:

One vs One (Uno contra Uno)

• Se crean modelos individuales para cada par de clases, enfrentándolas dos a dos.
• Proceso: El conjunto de datos se divide en N(N-1)/2 subconjuntos para N clases. Cada modelo se entrena para distinguir entre un par específico de clases.
• Predicción: Se utiliza un sistema de votación; la clase con más votos es la predicción final.

One vs Rest (Uno contra el Resto, OvR)

• Se entrena un modelo binario para cada clase.
• Proceso: Cada modelo separa los ejemplos de una clase específica del resto.
• Ventajas: Es más eficiente computacionalmente y más interpretable que One vs One.

Máquinas de Vectores Soporte (SVM)

Las Máquinas de Vectores Soporte (SVM) son un método basado en kernels, inicialmente diseñado para clasificación binaria.

Características de las SVM:

• Utilizan funciones kernel para transformar los datos de entrada, permitiendo soluciones no lineales en un espacio transformado.
• Ventajas: Se pueden aplicar a diferentes tipos de datos (numéricos, texto, imágenes, etc.) y manejan problemas no lineales eficientemente.

Kernelización de Algoritmos

Es el proceso de reformular algoritmos lineales para operar en un espacio de características mediante funciones kernel. Las operaciones dependen de las similitudes transformadas, no de los datos originales.

Definición de Función Kernel

Una función kernel asigna a cada par de objetos del espacio de entrada X un valor que equivale al producto escalar entre las imágenes de esos objetos en un espacio de características F.

Expresión formal: k(x,y) = ⟨ϕ(x), ϕ(y)⟩, donde ϕ: X → F es una función de mapeo a un espacio de características.

Kernel de Cadenas

En aplicaciones como análisis de texto o secuencias, se utilizan kernels diseñados para cadenas. La idea principal es comparar secuencias según las subcadenas que contienen. Cuantas más subcadenas compartan dos cadenas, mayor será su similitud.

Extensiones de las SVM a Problemas de Regresión

Aunque las SVM se diseñaron para clasificación binaria, sus principios se pueden aplicar a la regresión. En lugar de separar clases, las SVM de regresión ajustan un modelo que predice valores continuos.

Ventajas:

• Proporcionan soluciones robustas.
• Pueden manejar datos complejos gracias al uso de funciones kernel.

Algoritmos Elementales: Clasificadores Zero-R y One-R

• Zero-R: Un algoritmo simple que siempre predice la clase mayoritaria. Sirve como referencia para evaluar algoritmos más complejos.
• One-R: Utiliza un único atributo para construir reglas de decisión. Para cada valor del atributo, crea una rama asignando la clase más frecuente. Se selecciona el atributo con la menor tasa de error. Solo se aplica a atributos categóricos.

Aprendizaje Basado en Instancias

Este enfoque se basa en memorizar ejemplos y predecir utilizando la similitud entre instancias. Los métodos más comunes son:

1. Vecino más próximo (NN): Clasifica según la instancia más cercana.
2. K vecinos más cercanos (KNN): Considera las K instancias más cercanas.

La Función de Distancia

La distancia mide la similitud entre instancias. Algunas métricas comunes son:

1. Atributos numéricos: Distancia euclídea (normalizada para evitar sesgos).
2. Atributos nominales: Distancia es 0 si los valores son iguales, y 1 si son diferentes.

Evaluación y Comparación de Modelos

Las métricas son esenciales para medir y comparar el rendimiento de los modelos. Sirven para:

1. Evaluación del Rendimiento: Cuantifican la precisión de las predicciones.
2. Comparación: Determinan qué modelo es mejor.
3. Optimización: Guían el ajuste de hiperparámetros.

Clasificación Binaria

La salida tiene dos clases posibles (0 o 1). Hay dos tipos de modelos:

• Los que devuelven un valor real (por ejemplo, una probabilidad), que requiere un umbral.
• Los que devuelven directamente una clase categórica.

La tasa de error mide la proporción de predicciones incorrectas. Se recomienda dividir los datos en tres conjuntos:

1. Entrenamiento: Construye el modelo.
2. Validación: Optimiza parámetros.
3. Test: Estima el error en datos no vistos.

Métodos de Evaluación

1. Holdout: Divide los datos en entrenamiento y test.
2. Holdout Repetido: Repite la división varias veces y promedia los errores.
3. Validación Cruzada: Divide los datos en "folds". Cada partición actúa como test una vez.
4. Leave-One-Out: Variante de validación cruzada donde cada iteración utiliza una sola instancia como test (costoso en tiempo).

Matriz de Confusión

Permite evaluar modelos que devuelven clases categóricas. Los elementos en la diagonal representan predicciones correctas. Métricas derivadas:

1. Accuracy: Proporción de predicciones correctas.
2. Precision: Fiabilidad de las predicciones positivas.
3. Recall (positivo y negativo): Capacidad para identificar correctamente instancias positivas o negativas.
4. F1 Score: Media armónica entre precisión y recall positivo.

Support Vector Machines (SVM): Detalles del Modelo

Las Support Vector Machines (SVM) son un modelo supervisado de clasificación que busca un hiperplano óptimo para separar dos clases, maximizando el margen entre ellas.

El hiperplano se define como θ^Tx = 0, donde θ define la orientación.

La función de decisión es: h_w,b(x) = g(w^Tx + b), donde w es el vector de pesos, b es el término de sesgo, y g(z) es una función que devuelve 1 si z ≥ 0 y -1 si z < 0.

El margen funcional para un ejemplo (x_i, y_i) es: γ_i = y_i(w^Tx_i + b). Un modelo clasifica correctamente si γ_i > 0.

El margen geométrico es la distancia real entre un punto y el hiperplano: γ_i = y_i(w^Tx_i + b) / ∥w∥. Maximizar el margen geométrico mejora la generalización.

Problema de Optimización en SVM

El objetivo es encontrar el hiperplano que maximiza el margen geométrico. Se formula como:

min 1/2 ∥w∥², sujeto a: y_i(w^Tx_i + b) ≥ 1, ∀i.

Esta es una formulación convexa que se puede resolver eficientemente.

Variables de Holgura (Slack Variables)

Para datos no separables linealmente, se introducen variables de holgura ϵ_i:

min 1/2 ∥w∥² + C∑(i=1,n)ϵ_i, sujeto a: y_i(w^Tx_i + b) ≥ 1 - ϵ_i, ϵ_i ≥ 0.

El parámetro C controla el equilibrio entre maximizar el margen y minimizar el error.

Formulación Dual y Multiplicadores de Lagrange

Se utiliza la formulación dual con multiplicadores de Lagrange (α_i):

• α_i = 0: El ejemplo no influye en la posición del hiperplano.
• 0 < α_i < C: El ejemplo está en el margen (vector soporte).
• α_i = C: El ejemplo está mal clasificado o dentro del margen.

El Truco del Kernel (Kernel Trick)

Las SVM pueden manejar datos no lineales usando el "Kernel Trick". En lugar de calcular explícitamente el mapeo ϕ(x), se utiliza una función kernel K(x,z) para medir similitudes en el espacio transformado. Esto reduce el costo computacional.

Kernels comunes:

• Polinomial
• Radial Basis Function (RBF): Especialmente útil para estructuras complejas.