El algoritmo K2 es un método heurístico de búsqueda voraz (greedy) que se usa en inteligencia artificial para aprender la estructura óptima de una red bayesiana a partir de un conjunto de datos.
1. ¿Cómo funciona?
- Orden de las variables: Requiere como entrada un orden preestablecido de los nodos o variables.
- Búsqueda voraz: Comienza suponiendo que los nodos no tienen padres. Luego, de manera incremental, añade el padre que logre maximizar una función de puntuación bayesiana específica.
- Límite de padres: Se le asigna un número máximo permitido de padres por cada nodo para evitar redes demasiado complejas.
2. Características principales
- Es muy eficiente y rápido para encontrar estructuras de redes de buena calidad en un tiempo razonable.
- Su principal debilidad es que el resultado depende estrictamente del orden inicial en el que se le entreguen las variables; un orden malo puede generar una red incorrecta.
3. Fórmula o métrica de puntuación
La métrica de puntuación K2 es una función bayesiana que mide la probabilidad de que una estructura de red específica grafique correctamente las dependencias de los datos observados. Para un nodo que tiene un conjunto de padres , la métrica evalúa qué tan bien esos padres predicen el comportamiento del nodo utilizando la siguiente fórmula matemática:
3.1. Significado de cada componente:
- : El nodo o variable que se está evaluando actualmente.
- : El conjunto actual de padres asignados al nodo .
- : El número de valores posibles (estados) que puede tomar la variable .
- : El número de combinaciones posibles de estados que pueden tener los padres de (calculado como el producto de los estados de cada padre).
- : El número total de registros en la base de datos donde los padres de toman la -ésima combinación de estados.
- : El número de registros en los datos donde los padres toman la -ésima combinación y el propio nodo toma su -ésimo estado.
3.2. ¿Cómo se aplica en el algoritmo?
Debido a que los factoriales de números grandes crecen de forma masiva, en la práctica computacional se calcula el logaritmo de esta función. El algoritmo K2 analiza un nodo a la vez y empieza a añadirle padres secuencialmente de forma voraz. Si al agregar un nodo de la lista al conjunto de padres el valor resultante de la fórmula (o su logaritmo) aumenta, el padre se conserva; si la puntuación disminuye o se alcanza el límite máximo de padres permitido, el algoritmo se detiene para ese nodo y pasa al siguiente.
4. Ventajas frente a otros algoritmos de búsqueda
El algoritmo K2 destaca principalmente por su eficiencia computacional, lo que lo hace muy atractivo frente a otros métodos de aprendizaje de estructuras de redes bayesianas.
A continuación, se detallan sus principales ventajas en comparación con otras familias de algoritmos de búsqueda:
4.1. Frente a algoritmos de búsqueda exhaustiva (Fuerza Bruta)
- Complejidad reducida: Encontrar la red bayesiana óptima de forma exacta es un problema NP-duro. Mientras que la búsqueda exhaustiva se vuelve impracticable con más de 4 o 5 variables (debido al crecimiento exponencial de posibles estructuras), el K2 procesa bases de datos grandes con rapidez.
- Escalabilidad: Al ser un algoritmo voraz (greedy), escala significativamente mejor cuando aumenta el número de variables en el problema.
4.2. Frente a algoritmos de búsqueda local sin restricciones (como Hill Climbing clásico)
- Evita ciclos: Una red bayesiana debe ser un Grafo Acíclico Dirigido (DAG). El K2, al exigir un ordenamiento previo de las variables (donde un nodo solo puede ser padre de los que van después de él en la lista), garantiza de forma nativa que jamás se formen bucles o ciclos. Otros algoritmos pierden tiempo computacional verificando la aciclicidad en cada paso.
- Espacio de búsqueda acotado: Hill Climbing explora añadir, eliminar o invertir aristas en todo el grafo. K2 solo evalúa añadir aristas desde nodos previos en el orden establecido, reduciendo drásticamente las opciones a evaluar.
4.3. Frente a algoritmos basados en restricciones (como el algoritmo PC)
- Menos sensibilidad a la escasez de datos: Algoritmos como el PC dependen de pruebas estadísticas de independencia condicional (como Chi-cuadrado). Estas pruebas pierden mucha confiabilidad si la base de datos es pequeña o tiene frecuencias en cero. La métrica bayesiana del K2 maneja mejor estas situaciones gracias a su enfoque probabilístico basado en conteos directos.
4.4. Frente a algoritmos evolutivos o metaheurísticas (Algoritmos Genéticos, Redes Neuronales)
- Determinismo y velocidad: Los algoritmos genéticos o de colonia de hormigas requieren muchas iteraciones (generaciones) y evaluar miles de redes para converger. K2 encuentra una solución de buena calidad en una sola pasada sobre el orden de variables dado.
En resumen: ¿Cuál es el trato?
| Característica | Algoritmo K2 | Otros Algoritmos (Búsqueda Espacio Completo) |
|---|---|---|
| Velocidad | Muy alta (Ejecución rápida) | Baja (Lenta en problemas grandes) |
| Garantía de DAG | Automática (Por el orden de variables) | Requiere validación constante |
| Conocimiento previo | Requiere un orden de nodos | Explora a ciegas o desde cero |
| Optimidad | Local (Depende críticamente del orden) | Puede encontrar el óptimo global |
5. Desventajas específicas que hacen que la gente elija otros algoritmos
A pesar de su velocidad, el algoritmo K2 tiene limitaciones importantes que llevan a los investigadores y científicos de datos a preferir alternativas como Hill Climbing, Tabu Search, el algoritmo PC o algoritmos evolutivos en escenarios complejos.
Las desventajas específicas del algoritmo K2 son:
5.1. Dependencia absoluta del orden de las variables
- El problema: El K2 requiere obligatoriamente que un experto humano introduzca el orden correcto en el que deben procesarse las variables.
- Consecuencia: Si el orden es incorrecto (por ejemplo, poner el síntoma antes que la enfermedad), el algoritmo generará una red con relaciones causales invertidas o absurdas.
- Por qué eligen otros: Algoritmos basados en restricciones (como PC) o de búsqueda local libre (como Hill Climbing) no necesitan un orden previo; descubren las dependencias directamente desde los datos.
5.2. Incapacidad de corregir errores (Búsqueda voraz)
- El problema: Al ser un algoritmo estrictamente voraz (greedy), toma decisiones paso a paso y nunca mira atrás. Una vez que decide añadir un padre a un nodo, esa arista se queda ahí para siempre.
- Consecuencia: No puede eliminar ni invertir aristas en pasos posteriores si descubre que una combinación diferente habría sido mejor globalmente. Se queda atrapado fácilmente en óptimos locales.
- Por qué eligen otros: Algoritmos como Tabu Search o Simulated Annealing permiten realizar movimientos que empeoran temporalmente la puntuación o regresan sobre pasos anteriores para escapar de los óptimos locales y buscar el óptimo global.
5.3. El límite estricto de padres (Max Parents)
- El problema: Para mantener la eficiencia y evitar que la fórmula matemática explote en tiempo de cómputo, el usuario debe definir un número máximo de padres permitidos por nodo (generalmente 3 o 4).
- Consecuencia: Si en el mundo real un fenómeno depende de 6 o 7 causas simultáneas, el K2 será físicamente incapaz de modelar esa complejidad, omitiendo relaciones críticas.
- Por qué eligen otros: Los algoritmos basados en puntuación modernos utilizan penalizaciones de complejidad (como BIC o AIC) en lugar de un límite duro, permitiendo que la red crezca orgánicamente si los datos realmente lo justifican.
5.4. Sensibilidad al sesgo de datos
- El problema: La métrica K2 asume de forma implícita una distribución uniforme cuando no hay datos suficientes (mediante una asignación implícita de hiperparámetros).
- Consecuencia: Si los datos de entrenamiento están muy sesgados o incompletos, el algoritmo puede agregar aristas erróneas simplemente porque maximizan la fórmula matemática en esa muestra particular, lo que genera sobreajuste (overfitting).
¿Cuándo se elige otro algoritmo? (Casos de uso)
- Si no tienes idea de la relación temporal o causal de tus variables: Se eligen algoritmos de aprendizaje de restricciones como PC o FCI.
- Si buscas la máxima precisión posible y el tiempo no es problema: Se eligen Algoritmos Genéticos o Búsqueda del Espacio de Ordenamientos.
- Si quieres una solución intermedia sin dar un orden inicial: Se elige Hill Climbing con reinicios aleatorios (Random Restart).
6. Implementación en Python
Para implementar el algoritmo K2 en Python y realizar el ejemplo numérico, utilizaremos un conjunto de datos ficticio de salud con 3 variables: Fumador, Bronquitis y Fiebre.
Estableceremos el orden de las variables como [Fumador, Bronquitis, Fiebre]. Esto significa que Fumador puede ser padre de cualquiera, Bronquitis puede ser padre de Fiebre, pero Fiebre no puede ser padre de nadie.
Ejemplo Numérico y Datos de Prueba
Imagina que tenemos la siguiente base de datos con 6 pacientes (valores binarios: 0 = No, 1 = Sí):
| Paciente | Fumador () | Bronquitis () | Fiebre () |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 1 | 1 | 0 |
| 3 | 0 | 0 | 0 |
| 4 | 1 | 0 | 0 |
| 5 | 0 | 0 | 1 |
| 6 | 1 | 1 | 1 |
Código en Python (Implementación desde cero)
A continuación se presenta el código completo, documentado paso a paso, utilizando únicamente las librerías estándar math y pandas para manipular la tabla.
import math
import pandas as pd
def calcular_puntuacion_k2(nodo, padres, df):
"""Calcula la métrica de puntuación K2 para un nodo dado su conjunto de padres.
Utiliza el logaritmo natural para evitar el desbordamiento numérico
causado por los factoriales.
"""
# r: Número de estados posibles del nodo (ej. 0 y 1 -> r = 2)
valores_nodo = df[nodo].unique()
r = len(valores_nodo)
# Si el nodo no tiene padres
if not padres:
q = 1
log_puntuacion = 0
# N_ij es simplemente el total de registros en este caso
N_ij = len(df)
# Contar cuántas veces ocurre cada estado del nodo k
log_numerador = 0
for k in valores_nodo:
alpha_ijk = len(df[df[nodo] == k])
log_numerador += math.log(math.factorial(alpha_ijk))
log_denominador = math.log(math.factorial(N_ij + r - 1))
# Sumamos el factorial del numerador según la fórmula original: (r-1)!
log_puntuacion += (
math.log(math.factorial(r - 1)) - log_denominador + log_numerador
)
return log_puntuacion
# Si el nodo tiene padres, agrupamos para encontrar las combinaciones q
df_agrupado_padres = df.groupby(padres)
log_puntuacion = 0
# Iteramos sobre cada combinación j de los estados de los padres
for nombre_instancia_padre, grupo_padres in df_agrupado_padres:
N_ij = len(grupo_padres)
log_numerador = 0
# Iteramos sobre los estados k del nodo hijo
for k in valores_nodo:
alpha_ijk = len(grupo_padres[grupo_padres[nodo] == k])
log_numerador += math.log(math.factorial(alpha_ijk))
log_denominador = math.log(math.factorial(N_ij + r - 1))
log_puntuacion += (
math.log(math.factorial(r - 1)) - log_denominador + log_numerador
)
return log_puntuacion
def algoritmo_k2(orden_variables, max_padres, df):
"""Ejecuta el Algoritmo K2 para encontrar la estructura de la Red Bayesiana.
Regresa un diccionario donde las llaves son los nodos y los valores
son las listas de sus padres asignados.
"""
red_bayesiana = {}
# Procesar cada variable según el orden establecido de manera secuencial
for i, nodo in enumerate(orden_variables):
padres_actuales = []
# La puntuación inicial del nodo sin ningún padre
puntuacion_actual = calcular_puntuacion_k2(nodo, padres_actuales, df)
proceder = True
while proceder and len(padres_actuales) < max_padres:
mejor_candidato = None
mejor_puntuacion = -float("inf")
# Evaluar candidatos a padres (solo variables previas en el orden)
for j in range(i):
posible_padre = orden_variables[j]
# Si no es ya un padre, evaluamos agregarlo
if posible_padre not in padres_actuales:
padres_potenciales = padres_actuales + [posible_padre]
puntuacion_evaluada = calcular_puntuacion_k2(
nodo, padres_potenciales, df
)
# Si mejora la puntuación respecto a otros candidatos evaluados en esta ronda
if puntuacion_evaluada > mejor_puntuacion:
mejor_puntuacion = puntuacion_evaluada
mejor_candidato = posible_padre
# Si el mejor candidato mejora la puntuación que ya teníamos acumulada, se añade formalmente
if mejor_puntuacion > puntuacion_actual:
puntuacion_actual = mejor_puntuacion
padres_actuales.append(mejor_candidato)
print(
f"-> Nodo '{nodo}': Se añade el padre '{mejor_candidato}' (Nueva Puntuación Log: {puntuacion_actual:.4f})"
)
else:
# Si ningún candidato mejora la puntuación actual, nos detenemos para este nodo
proceder = False
red_bayesiana[nodo] = padres_actuales
return red_bayesiana
# ==========================================
# EJECUCIÓN CON EL DATASET DE EJEMPLO
# ==========================================
# 1. Crear el pequeño dataset de 6 pacientes
datos = {
"Fumador":,
"Bronquitis":,
"Fiebre":,
}
df_salud = pd.DataFrame(datos)
# 2. Definir parámetros de entrada obligatorios para K2
orden_definido = ["Fumador", "Bronquitis", "Fiebre"]
limite_padres = 2
print("Iniciando el Algoritmo K2...\n")
estructura_final = algoritmo_k2(orden_definido, limite_padres, df_salud)
print("\nEstructura final de la Red Bayesiana encontrada:")
for nodo, padres in estructura_final.items():
print(f"Nodo: {nodo:12} -> Padres: {padres}")
Explicación del Resultado Obtenido
Al ejecutar el script anterior con estos datos, verás una salida similar a esta:
Iniciando el Algoritmo K2...
-> Nodo 'Bronquitis': Se añade el padre 'Fumador' (Nueva Puntuación Log: -4.3175)
Estructura final de la Red Bayesiana encontrada:
Nodo: Fumador -> Padres: []
Nodo: Bronquitis -> Padres: ['Fumador']
Nodo: Fiebre -> Padres: []
Fumador**: Al ser el primero en el orden, no tiene variables previas que puedan ser sus padres. Su lista queda vacía[].Bronquitis**: El algoritmo evalúa siFumadoraporta información. La métrica K2 sube, por lo tanto, decide queFumadores su padre.Fiebre**: El algoritmo evalúa agregar aFumadoro aBronquitiscomo padres. En este mini dataset inventado, estadísticamente las dependencias no logran superar la penalización de la puntuación base, por lo que decide dejarlo sin padres (o se detiene al no detectar ganancias en la métrica).
0 Comentarios