Problema de Clasificación Supervisada
Sean \(\mathcal{X} = \mathbb{R}^p\) el espacio de características y \(\mathcal{Y} = \{1, 2, \ldots, K\}\) el conjunto de clases discretas. Un conjunto de entrenamiento está compuesto por observaciones \(\mathcal{D} = \{(x_i, y_i)\}_{i=1}^{n}\) donde \(x_i \in \mathcal{X}\) e \(y_i \in \mathcal{Y}\).
El objetivo es encontrar una función de clasificación \(f: \mathcal{X} \rightarrow \mathcal{Y}\) que minimice el riesgo empírico:
\[ \mathcal{R}_{emp}(f) = \frac{1}{n} \sum_{i=1}^{n} \mathcal{L}(f(x_i), y_i) \]
donde \(\mathcal{L}\) es una función de pérdida que penaliza las predicciones incorrectas.
Matriz de Confusión (Multiclase)
Para un problema con \(K\) clases:
\[ \text{Precisión}_k = \frac{TP_k}{TP_k + FP_k}, \quad \text{Exhaustividad}_k = \frac{TP_k}{TP_k + FN_k} \]
Medida F1 Ponderada
\[ F1_{ponderada} = \frac{2}{n} \sum_{k=1}^{K} \frac{n_k}{n} \frac{\text{Precisión}_k \cdot \text{Exhaustividad}_k}{\text{Precisión}_k + \text{Exhaustividad}_k} \]
donde \(n_k\) es el número de muestras de la clase \(k\).
Función Logística
Para clasificación binaria, se utiliza la función sigmoide:
\[ p(Y=1|X=x) = \frac{1}{1 + e^{-(\beta_0 + \beta_1 x_1 + \cdots + \beta_p x_p)}} = \sigma(\beta^T x) \]
donde \(\beta = (\beta_0, \beta_1, \ldots, \beta_p)^T\) son los parámetros del modelo.
Odds y Log-Odds
\[ \text{odds} = \frac{p(Y=1|X)}{1 - p(Y=1|X)} \quad \Rightarrow \quad \log(\text{odds}) = \beta_0 + \beta_1 x_1 + \cdots + \beta_p x_p \]
Función de Verosimilitud
\[ L(\beta) = \prod_{i=1}^{n} p(y_i|x_i; \beta)^{y_i}(1 - p(y_i|x_i; \beta))^{1-y_i} \]
Log-Verosimilitud
\[ \ell(\beta) = \sum_{i=1}^{n} \left[ y_i \log p(x_i) + (1-y_i) \log(1 - p(x_i)) \right] \]
Los parámetros óptimos \(\hat{\beta}\) se obtienen resolviendo:
\[ \nabla \ell(\beta) = 0 \quad \Rightarrow \quad \sum_{i=1}^{n} (y_i - p(x_i)) x_i = 0 \]
Extensión Multiclase: Regresión Logística Multinomial
\[ P(Y=k|X=x) = \frac{e^{\beta_k^T x}}{\sum_{j=1}^{K} e^{\beta_j^T x}} \]
Se emplean métodos iterativos como Newton-Raphson o Descenso de Gradiente Estocástico. El Hessiano de la función log-verosimilitud es:
\[ H = -\sum_{i=1}^{n} p(x_i)(1 - p(x_i)) x_i x_i^T \]
Problema de Optimización Original
Dadas clases separables, se desea encontrar el hiperplano separador que maximiza el margen:
\[ \min_{\mathbf{w}, b} \frac{1}{2} \|\mathbf{w}\|^2 \]
sujeto a:
\[ y_i (w^T x_i + b) \geq 1 \quad \forall i = 1, \ldots, n \]
Condiciones de Karush-Kuhn-Tucker (KKT)
\[ \alpha_i [y_i (w^T x_i + b) - 1] = 0 \quad \text{(complementariedad)} \]
El problema dual es:
\[ \max_{\alpha} \sum_{i=1}^{n} \alpha_i - \frac{1}{2} \sum_{i,j=1}^{n} \alpha_i \alpha_j y_i y_j x_i^T x_j \]
sujeto a:
\[ \sum_{i=1}^{n} \alpha_i y_i = 0, \quad 0 \leq \alpha_i \leq C \quad \forall i \]
Para datos no separables linealmente, se mapea a un espacio de mayor dimensión mediante una función \(\phi: \mathcal{X} \rightarrow \mathcal{H}\):
\[ K(x_i, x_j) = \langle \phi(x_i), \phi(x_j) \rangle \]
Kernels Comunes
Kernel Lineal: \(K(x_i, x_j) = x_i^T x_j\)
Kernel Polinomial: \(K(x_i, x_j) = (x_i^T x_j + r)^d\)
Kernel RBF (Gaussiano): \(K(x_i, x_j) = \exp(-\gamma \|x_i - x_j\|^2)\)
Kernel Sigmoide: \(K(x_i, x_j) = \tanh(\kappa x_i^T x_j + \theta)\)
Esquema Uno-vs-Todos
Se entrena \(K\) clasificadores binarios SVM. Para clasificar un nuevo punto \(x\):
\[ \hat{y} = \arg\max_{k=1,\ldots,K} f_k(x) \]
Esquema Uno-vs-Uno
Se entrena \(\binom{K}{2}\) clasificadores. Se utiliza un esquema de votación.
Un árbol de decisión es un grafo dirigido acíclico donde:
Entropía de Shannon (ver Parte III para definición completa)
\[ H(Y) = -\sum_{k=1}^{K} p(Y=k) \log_2 p(Y=k) \]
Ganancia de Información
\[ IG(Y, X) = H(Y) - \sum_{v} \frac{|S_v|}{|S|} H(Y|X=v) \]
donde \(S_v\) es el subconjunto de muestras donde \(X=v\).
Alternativa a la entropía, más computacionalmente eficiente:
\[ \text{Gini}(Y) = 1 - \sum_{k=1}^{K} p(Y=k)^2 \]
Impureza de Gini Ponderada
\[ \text{Gini}_{\text{ponderado}}(S) = \sum_{v} \frac{|S_v|}{|S|} \text{Gini}(Y|X=v) \]
La ganancia de Gini es \(\text{Gini}(Y) - \text{Gini}_{\text{ponderado}}(S)\).
Búsqueda Binaria Greedy
Poda de Costo-Complejidad
\[ R_{\alpha}(T) = R(T) + \alpha |T| \]
donde \(R(T)\) es el error en datos de validación, \(|T|\) es el número de hojas, y \(\alpha\) es el parámetro de complejidad.
\[ P(Y=k|X_1, \ldots, X_p) = \frac{P(X_1, \ldots, X_p|Y=k) P(Y=k)}{P(X_1, \ldots, X_p)} \]
Naive Bayes asume:
\[ P(X_1, \ldots, X_p|Y=k) = \prod_{j=1}^{p} P(X_j|Y=k) \]
Por tanto:
\[ P(Y=k|X_1, \ldots, X_p) \propto P(Y=k) \prod_{j=1}^{p} P(X_j|Y=k) \]
\[ \hat{y} = \arg\max_{k} P(Y=k) \prod_{j=1}^{p} P(X_j|Y=k) \]
Para atributos discretos:
\[ P(X_j = v|Y=k) = \frac{\text{count}(X_j = v, Y=k) + \alpha}{n_k + \alpha \cdot |V_j|} \]
donde \(\alpha\) es el parámetro de suavizado de Laplace, \(n_k\) es el número de muestras de clase \(k\), y \(|V_j|\) es el número de valores posibles de \(X_j\).
Para atributos continuos:
Se asume distribución gaussiana:
\[ P(X_j|Y=k) = \frac{1}{\sqrt{2\pi\sigma_k^2}} \exp\left(-\frac{(X_j - \mu_k)^2}{2\sigma_k^2}\right) \]
Para clasificar un punto \(x\), se identifican los \(k\) puntos de entrenamiento más cercanos según una métrica de distancia \(d(\cdot, \cdot)\).
Distancia Euclidiana
\[ d_E(x, x') = \sqrt{\sum_{j=1}^{p} (x_j - x'_j)^2} \]
Distancia Manhattan
\[ d_M(x, x') = \sum_{j=1}^{p} |x_j - x'_j| \]
Distancia de Minkowski
\[ d_{\text{Mink}}(x, x') = \left(\sum_{j=1}^{p} |x_j - x'_j|^q\right)^{1/q} \]
Métrica de Mahalanobis
\[ d_{\text{Mah}}(x, x') = \sqrt{(x - x')^T \Sigma^{-1} (x - x')} \]
donde \(\Sigma\) es la matriz de covarianza.
\[ \hat{y} = \arg\max_{k} \sum_{i \in N_k(x)} \mathbf{1}[y_i = k] \]
donde \(N_k(x)\) es el conjunto de \(k\) vecinos más cercanos.
Ponderación por Distancia
\[ \hat{y} = \arg\max_{k} \sum_{i \in N_k(x)} w_i \cdot \mathbf{1}[y_i = k] \]
con \(w_i = \frac{1}{d(x, x_i) + \epsilon}\).
Algoritmo
Análisis de Varianza
Para predicciones correlacionadas:
\[ \text{Var}_{\text{bagged}}(f) = \rho \sigma^2 + (1-\rho) \frac{\sigma^2}{B} \]
donde \(\rho\) es la correlación entre predictores y \(\sigma^2\) es la varianza individual.
Modificación de Bagging
En cada división de árbol, se considera un subconjunto aleatorio \(m\) de \(p\) características:
\[ m = \left\lfloor \sqrt{p} \right\rfloor \quad \text{(clasificación típica)} \]
Importancia de Variables
\[ \text{Importancia}_j = \frac{1}{B} \sum_{b=1}^{B} \text{IG}_b(j) \]
donde \(\text{IG}_b(j)\) es la ganancia de información total del atributo \(j\) en el árbol \(b\).
Algoritmo AdaBoost
Inicializar pesos: \(w_i^{(1)} = \frac{1}{n}\)
Para \(t = 1, \ldots, T\):
donde \(Z_t = \sum_{i=1}^{n} w_i^{(t)} \exp(-\alpha_t y_i f^{(t)}(x_i))\)
Predicción final: \(\hat{y} = \text{sign}\left(\sum_{t=1}^{T} \alpha_t f^{(t)}(x)\right)\)
Marco General
Se minimiza una función de pérdida \(L(y, f(x))\) mediante aproximaciones funcionales iterativas.
Pseudorresiduo en iteración \(t\):
\[ r_i^{(t)} = -\frac{\partial L(y_i, f^{(t-1)}(x_i))}{\partial f^{(t-1)}(x_i)} \]
Se entrena un árbol débil \(h^{(t)}\) para predecir \(r_i^{(t)}\):
\[ f^{(t)}(x) = f^{(t-1)}(x) + \eta h^{(t)}(x) \]
donde \(\eta \in (0, 1]\) es la tasa de aprendizaje.
Definición
La entropía de una variable aleatoria discreta \(X\) con distribución de probabilidad \(P(X)\) es:
\[ H(X) = -\sum_{x \in \mathcal{X}} P(x) \log_2 P(x) = \mathbb{E}[-\log_2 P(X)] \]
donde se define \(0 \log_2 0 = 0\) por continuidad.
Interpretación
Propiedades Fundamentales
No negatividad: \(H(X) \geq 0\)
Máxima entropía: \(H(X) = \log_2 K\) cuando \(P(x) = \frac{1}{K}\) (uniforme)
Entropía nula: \(H(X) = 0\) si \(P(x_i) = 1\) para algún \(x_i\)
Simetría: \(H(X, Y) = H(Y, X)\)
Para dos variables aleatorias \(X\) e \(Y\):
\[ H(X, Y) = -\sum_{x \in \mathcal{X}} \sum_{y \in \mathcal{Y}} P(x, y) \log_2 P(x, y) \]
Generalización Multivariada
\[ H(X_1, X_2, \ldots, X_n) = -\sum_{x_1 \in \mathcal{X}_1} \cdots \sum_{x_n \in \mathcal{X}_n} P(x_1, \ldots, x_n) \log_2 P(x_1, \ldots, x_n) \]
La entropía de \(Y\) dado que se conoce \(X\):
\[ H(Y|X) = \sum_{x \in \mathcal{X}} P(x) H(Y|X=x) = -\sum_{x, y} P(x, y) \log_2 P(y|x) \]
Interpretación: Promedio ponderado de la incertidumbre residual sobre \(Y\) tras conocer \(X\).
Propiedad de Reducción
\[ H(Y|X) \leq H(Y) \]
con igualdad si y solo si \(X\) e \(Y\) son independientes.
\[ H(X, Y) = H(X) + H(Y|X) = H(Y) + H(X|Y) \]
Generalización
\[ H(X_1, X_2, \ldots, X_n) = H(X_1) + H(X_2|X_1) + H(X_3|X_1, X_2) + \cdots + H(X_n|X_1, \ldots, X_{n-1}) \]
Para una variable continua \(X\) con densidad de probabilidad \(f(x)\):
\[ h(X) = -\int_{\mathcal{X}} f(x) \log_2 f(x) \, dx \]
Diferencias con el caso discreto
La información mutua entre \(X\) e \(Y\) es:
\[ I(X; Y) = \sum_{x, y} P(x, y) \log_2 \frac{P(x, y)}{P(x)P(y)} \]
Definiciones Equivalentes
En términos de entropías: \[ I(X; Y) = H(X) - H(X|Y) = H(Y) - H(Y|X) \]
Divergencia de Kullback-Leibler: \[ I(X; Y) = D_{KL}(P(X, Y) \| P(X) \cdot P(Y)) \]
Covarianza de log-probabilidades: \[ I(X; Y) = \mathbb{E}[\log_2 P(X|Y)] - \mathbb{E}[\log_2 P(X)] \]
\[ I(X; Y) = I(Y; X) \]
\[ I(X; Y) = H(X) + H(Y) - H(X, Y) \]
Esta relación muestra que la información mutua es la “sobreposición” entre los espacios de incertidumbre de \(X\) e \(Y\).
La información mutua entre \(X\) e \(Y\) condicionada a \(Z\):
\[ I(X; Y|Z) = \sum_{x, y, z} P(x, y, z) \log_2 \frac{P(x, y|z)}{P(x|z)P(y|z)} \]
Expresión en Términos de Entropías
\[ I(X; Y|Z) = H(X|Z) - H(X|Y, Z) = H(Y|Z) - H(Y|X, Z) \]
\[ I(X_1, X_2, \ldots, X_n; Y) = \sum_{i=1}^{n} I(X_i; Y | X_1, \ldots, X_{i-1}) \]
Esta regla es crucial para entender dependencias de orden superior.
No negatividad: \(I(X; Y|Z) \geq 0\)
Independencia condicional: \(I(X; Y|Z) = 0\) si \(X \perp Y | Z\)
Descomposición: \[ I(X; Y, Z) = I(X; Y) + I(X; Z|Y) \]
La divergencia KL (entropía relativa) de la distribución \(Q\) respecto a \(P\):
\[ D_{KL}(P \| Q) = \sum_{x} P(x) \log_2 \frac{P(x)}{Q(x)} \]
Para distribuciones continuas:
\[ D_{KL}(p \| q) = \int p(x) \log_2 \frac{p(x)}{q(x)} \, dx \]
No negatividad: \(D_{KL}(P \| Q) \geq 0\) (Desigualdad de Gibbs)
Semimétricas:
Interpretación probabilística: \[ D_{KL}(P \| Q) \approx \text{log-verosimilitud esperado al usar } Q \text{ en lugar de } P \]
\[ H(P, Q) = \frac{1}{2} \left[ D_{KL}(P \| Q) + D_{KL}(Q \| P) \right] \]
O más comúnmente:
\[ H(P, Q) = \sqrt{\frac{1}{2} \left[ D_{KL}(P \| Q) + D_{KL}(Q \| P) \right]} \]
\[ I(X; Y) = D_{KL}(P(X, Y) \| P(X) P(Y)) \]
Para atributo discreto \(X\) y clase \(Y\)
\[ IG(Y; X) = H(Y) - H(Y|X) = \sum_{x} P(x) H(Y|X=x) \]
Algoritmo Greedy (Forward Selection)
Problema: Favorece atributos con muchos valores discretos.
\[ \text{GainRatio}(Y; X) = \frac{IG(Y; X)}{H(X)} \]
donde \(H(X)\) es la entropía intrínseca del atributo.
Ventaja: Penaliza atributos con excesiva fragmentación.
\[ I_{\text{norm}}(X; Y) = \frac{I(X; Y)}{\min(H(X), H(Y))} \]
Rango: \([0, 1]\).
Marco Greedy
Inicializar conjunto de características seleccionadas: \(S = \emptyset\)
Para \(t = 1, \ldots, k\):
donde \(\beta \in [0.5, 1.0]\) regula el balance entre relevancia e independencia.
Justificación Teórica
Definición del Score
\[ \text{Score}_j = I(X_j; Y | S) - \beta \sum_{X_i \in S} I(X_j; X_i | Y) \]
donde \(I(X_j; Y | S) = H(Y|S) - H(Y|S \cup \{X_j\})\).
Ventaja: Considera dependencias condicionales a la clase.
\[ \text{Score}_j = I(X_j; Y | X_1, \ldots, X_{j-1}) \]
A cada paso se selecciona la característica que maximiza la información después de conocer el resto.
Complejidad: Orden exponencial en el número de características seleccionadas previas.
Para tres variables \(X_1, X_2, Y\), la información mutua conjunta se descompone:
\[ I(X_1, X_2; Y) = U_1 + U_2 + R + S \]
donde:
Información disponible en múltiples fuentes de forma duplicada:
\[ \text{Redundancia} = \min_i I(X_i; Y) \]
O más precisamente (Williams-Beer):
\[ I^{\cap}(X_1, X_2; Y) = \max_{x_1, x_2} \min(I(X_1; Y | X_2 = x_2), I(X_2; Y | X_1 = x_1)) \]
Información que emerge solo de la combinación conjunta de variables:
\[ I_{\text{syn}}(X_1, X_2; Y) = I(X_1, X_2; Y) - I(X_1; Y) - I(X_2; Y) + I^{\cap}(X_1, X_2; Y) \]
Una característica presentasinergía cuando:
\[ I(X_1, X_2; Y) > I(X_1; Y) + I(X_2; Y) \]
\[ \Omega(X_1, \ldots, X_n; Y) = TC(X_1, \ldots, X_n) - DTC(X_1, \ldots, X_n) \]
donde:
Interpretación:
Para \(K\) clases con distribuciones potencialmente desbalanceadas:
\[ H_w(Y) = -\sum_{k=1}^{K} \frac{n_k}{n} \log_2\left(\frac{n_k}{n}\right) \]
donde \(n_k\) es el número de muestras de la clase \(k\).
Macro-promedio (todas las clases tienen igual peso):
\[ I_{\text{macro}}(X; Y) = \frac{1}{K} \sum_{k=1}^{K} I(X; Y=k) \]
Micro-promedio (ponderada por tamaño de clase):
\[ I_{\text{micro}}(X; Y) = \sum_{k=1}^{K} \frac{n_k}{n} I(X; Y=k) \]
Para seleccionar \(m\) características de \(p\):
Inicializar \(S = \emptyset\), \(\text{scores} = [0, \ldots, 0]\)
Para \(t = 1, \ldots, m\):
Retornar \(S\)
Ponderación por Frecuencia Inversa
\[ w_k = \frac{1}{\sqrt{p_k}} \]
donde \(p_k = \frac{n_k}{n}\).
Término de Corrección de Entropía
\[ H_{\text{corr}}(Y) = H(Y) + \lambda \sum_{k: n_k < n/K} (n/K - n_k) \]
Nodos: Variables \(X_1, \ldots, X_p, Y\)
Aristas Ponderadas: \(I(X_i; X_j | Y)\) o \(I(X_i; Y | X_j)\)
Algoritmo de Detección:
Sea \(M_{ij} = I(X_i; X_j | Y)\).
Propiedades:
Descomposición de autovalores:
\[ M = U \Lambda U^T \]
Donde \(\Lambda = \text{diag}(\lambda_1, \ldots, \lambda_p)\) con \(\lambda_1 \geq \lambda_2 \geq \cdots\)
Varianza de Información Explicada
\[ \text{VIE}_k = \frac{\sum_{i=1}^{k} \lambda_i}{\sum_{i=1}^{p} \lambda_i} \]
Se retienen componentes hasta \(\text{VIE}_k > 0.95\).
Dadas restricciones sobre los momentos de una distribución:
\[ \mathbb{E}[f_i(X)] = a_i \quad i = 1, \ldots, m \]
La distribución que mejor representa el conocimiento con mínima asunción adicional es:
\[ P^*(x) = \frac{1}{Z(\lambda)} \exp\left(-\sum_{i=1}^{m} \lambda_i f_i(x)\right) \]
donde \(Z(\lambda) = \sum_x \exp(-\sum_i \lambda_i f_i(x))\) es la función de partición.
Distribución Condicional
\[ P(Y=k|X=x) = \frac{1}{Z(x, \lambda)} \exp\left(\sum_{j=1}^{m} \lambda_{kj} f_j(x)\right) \]
donde \(f_j(x)\) son características.
Estimación de Parámetros
\[ \lambda_{kj} = \arg\min_{\lambda} \left[ -\sum_i \log P(y_i|x_i; \lambda) + \frac{\alpha}{2} \|\lambda\|^2 \right] \]
(regularización L2).
Para características binarias y modelo de máxima entropía:
\[ P(Y|X) = \text{Softmax}(\lambda \cdot X) \]
equivale a regresión logística multinomial.
La estimación directa de \(I(X; Y)\) desde datos finitos es problemática:
\[ \hat{I}(X; Y) = \sum_{x, y} \hat{P}(x, y) \log_2 \frac{\hat{P}(x, y)}{\hat{P}(x) \hat{P}(y)} \]
Sesgos
\[ \hat{I}_{\text{MM}} = \hat{I} - \frac{(K_x K_y - K_x - K_y + 1)}{2n \ln 2} \]
donde \(K_x, K_y\) son el número de símbolos en \(X, Y\).
Estimador de Kraskov-Stögbauer-Grassberger (KSG)
Basado en distancias a k-ésimo vecino:
\[ \hat{I}(X; Y) \approx \psi(k) + \psi(n) - \langle \psi(n_x) + \psi(n_y) \rangle \]
donde \(\psi\) es la función digamma y \(n_x, n_y\) son los conteos en direcciones marginales.
Ventajas
Se busca el número de bins \(k\) que minimiza:
\[ H(X_{\text{disc}}) + \lambda \cdot k \]
donde el término de penalización evita sobrefragmentación.
\[ \text{MDL}(\text{partition}) = \sum_i n_i H(Y|X \in \text{bin}_i) + \text{costo de codificación} \]
Discretización afecta:
Calcular para cada característica \(X_i\):
\[ I(X_i; Y) \quad \text{y} \quad H(X_i) \]
Usando discretización en 10 bins.
Información Mutua Conjunta
\[ I(X_1, X_2, X_3, X_4; Y) \]
Comparar con suma univariada para detectar sinergía:
\[ S = I(X_1, X_2, X_3, X_4; Y) - \sum_{i} I(X_i; Y) \]
Análisis de Redundancia por Pares
Para cada par \((X_i, X_j)\):
\[ R_{ij} = I(X_i; X_j) \]
Construir matriz de redundancia \(4 \times 4\).
Usar algoritmo MIFS con \(\beta = 0.7\):
Iteración 1: Seleccionar \(X_* = \arg\max_i I(X_i; Y)\)
Iteración 2: \[ \text{Score}_j = I(X_j; Y) - 0.7 \cdot I(X_j; X_*) \] Seleccionar el máximo
Continuar hasta 3 características
Entrenar en \(\mathcal{D}_{\text{train}}\) (100 muestras):
Métricas en \(\mathcal{D}_{\text{test}}\) (50 muestras):
Dataset médico con:
Usar información mutua ponderada:
\[ I_w(X_i; Y) = \sum_{k=1}^{5} w_k \cdot I(X_i; Y=k) \]
donde \(w_k = \frac{1}{\sqrt{n_k}}\) normalizado.
Triplas \((X_i, X_j, X_k)\) con máxima sinergía:
\[ S_{ijk} = I(X_i, X_j, X_k; Y) - I(X_i; Y) - I(X_j; Y) - I(X_k; Y) + \text{correcciones} \]
Retener triplas con \(S_{ijk} > 0.5\) bits.
Combinar variables sinérgicas:
\[ Z = \text{PCA}([X_i, X_j, X_k]) \quad \text{(primera componente)} \]
O simplemente concatenar: \(Z = (X_i, X_j, X_k)\).
Verificar que \(I(Z; Y) > \sum I(X_*; Y)\).
Configuración 1: Voting Ensemble
\[ \hat{Y} = \text{mode}\{f_{\text{LR}}(X), f_{\text{SVM}}(X), f_{\text{RF}}(X), f_{\text{KNN}}(X)\} \]
Configuración 2: Soft Voting
\[ \hat{p}_k = \frac{1}{4} \sum_{m=1}^{4} P_m(Y=k|X) \]
Configuración 3: Stacking
Entrenar meta-aprendiz sobre predicciones de base:
\[ f_{\text{meta}}([f_1(X), f_2(X), f_3(X), f_4(X)]) \rightarrow \hat{Y} \]
Fase 1: Filtrado Univariado
Retener top-100 características por \(I(X_i; Y)\).
Fase 2: Refinamiento Multivariado
Sobre las 100 características, aplicar MIFS con búsqueda greedy.
Fase 3: Validación Cruzada
Entrenar clasificadores en 30-50 características seleccionadas.
Usar estimador KSG en lugar de histogramas:
Para cada par (X_i, Y):
1. Calcular k-NN en espacio (X_i, Y) combinado
2. Contar vecinos en direcciones marginales
3. Aplicar fórmula KSGComplejidad: \(O(n p \log n)\).
Para SVM: Usar parámetro \(C\) pequeño o \(L_2\):
\[ \min_w \frac{1}{2} \|w\|^2 + C \sum_i \max(0, 1 - y_i w^T x_i) \]
Para Regresión Logística: Penalización Ridge:
\[ \min_\beta \left[ -\sum_i \log P(y_i|x_i; \beta) + \frac{\lambda}{2} \|\beta\|^2 \right] \]
Para Random Forest: Limitar profundidad y requerir muestras mínimas por hoja.
FUNCIÓN Entropía(X, n_bins=10)
// Discretizar X si es continua
X_disc ← Discretizar(X, n_bins)
// Calcular distribución de probabilidad
PARA cada valor v en X_disc:
p[v] ← Contar(X_disc == v) / len(X)
FIN PARA
// Aplicar fórmula
H ← 0
PARA cada p_v en p:
SI p_v > 0:
H ← H - p_v * log2(p_v)
FIN SI
FIN PARA
RETORNAR H
FUNCIÓN FINFUNCIÓN InformaciónMutua(X, Y, n_bins=10)
// Discretizar si es necesario
X_disc ← Discretizar(X, n_bins)
Y_disc ← Discretizar(Y, n_bins)
// Entropías marginales
H_X ← Entropía(X_disc)
H_Y ← Entropía(Y_disc)
// Entropía conjunta
H_XY ← Entropía_Conjunta(X_disc, Y_disc)
// Información Mutua
I_XY ← H_X + H_Y - H_XY
RETORNAR I_XY
FUNCIÓN FINFUNCIÓN SeleccionMIFS(X, Y, k_features, beta=0.7)
// X: matriz n×p de características
// Y: vector n de clases
// k_features: número de características a seleccionar
S ← Conjunto vacío // características seleccionadas
scores ← [0, 0, ..., 0] // para cada característica
PARA t = 1 HASTA k_features:
PARA cada característica j no en S:
I_jY ← InformaciónMutua(X[:, j], Y)
redundancia ← 0
PARA cada característica i en S:
I_ji ← InformaciónMutua(X[:, j], X[:, i])
redundancia ← redundancia + I_ji
FIN PARA
scores[j] ← I_jY - beta * redundancia
FIN PARA
j_star ← arg max_j scores[j]
S ← S ∪ {j_star}
FIN PARA
RETORNAR S
FUNCIÓN FINFUNCIÓN ConstruirArbol(X, Y, profundidad_max)
// Caso base: todas muestras de la misma clase
SI TodasDelaMismaClase(Y):
RETORNAR Hoja(clase_mayoritaria)
FIN SI
// Caso base: profundidad máxima alcanzada
SI profundidad == profundidad_max:
RETORNAR Hoja(clase_mayoritaria)
FIN SI
// Encontrar mejor división
mejor_ganancia ← 0
mejor_atributo ← -1
mejor_umbral ← 0
PARA cada atributo j:
SI X[:, j] es continuo:
PARA cada umbral t en valores ordenados de X[:, j]:
izq ← X[:, j] <= t
der ← X[:, j] > t
ganancia ← IG(Y, izq, der)
SI ganancia > mejor_ganancia:
mejor_ganancia ← ganancia
mejor_atributo ← j
mejor_umbral ← t
FIN SI
FIN PARA
SINO (atributo discreto):
PARA cada valor v de X[:, j]:
subconjunto ← X[:, j] == v
ganancia ← IG(Y, subconjunto)
SI ganancia > mejor_ganancia:
mejor_ganancia ← ganancia
mejor_atributo ← j
mejor_valor ← v
FIN SI
FIN PARA
FIN SI
FIN PARA
// Crear nodos hijos
SI mejor_atributo == -1:
RETORNAR Hoja(clase_mayoritaria)
FIN SI
izq_subset ← Filtrar por (mejor_atributo, mejor_umbral, <=)
der_subset ← Filtrar por (mejor_atributo, mejor_umbral, >)
nodo ← NodoInterno(mejor_atributo, mejor_umbral)
nodo.izq ← ConstruirArbol(izq_subset, Y_izq, profundidad + 1)
nodo.der ← ConstruirArbol(der_subset, Y_der, profundidad + 1)
RETORNAR nodo
FUNCIÓN FINFUNCIÓN RandomForest(X, Y, n_trees=100, max_features=sqrt(p))
forest ← Lista vacía
PARA t = 1 HASTA n_trees:
// Bootstrap sampling
indices ← SampleConReemplazo(1:n, n)
X_boot ← X[indices, :]
Y_boot ← Y[indices]
// Construcción del árbol con características aleatorias
arbol ← ConstruirArbolConFeaturesAleatorias(
X_boot, Y_boot,
max_features,
profundidad_max=30
)
forest.Añadir(arbol)
FIN PARA
RETORNAR forest
FUNCIÓN FIN
FUNCIÓN Predicción_RF(forest, x_nuevo)
predicciones ← []
PARA cada árbol en forest:
pred ← ArbolPredict(árbol, x_nuevo)
predicciones.Añadir(pred)
FIN PARA
RETORNAR Mode(predicciones) // clase más frecuente
FUNCIÓN FIN| Algoritmo | Entrenamiento | Predicción |
|---|---|---|
| Regresión Logística | \(O(n p^2 t)\) | \(O(p)\) |
| SVM (kernel RBF) | \(O(n^2 p + n^3)\) | \(O(n_{\text{sv}} p)\) |
| Árbol de Decisión | \(O(np \log n)\) | \(O(\log n)\) |
| Random Forest | \(O(B \cdot np \log n)\) | \(O(B \log n)\) |
| KNN | \(O(n p)\) (construcción índice) | \(O(kp \log n)\) |
| Naive Bayes | \(O(np)\) | \(O(kp)\) |
donde \(n\) = muestras, \(p\) = características, \(B\) = árboles, \(t\) = iteraciones, \(k\) = vecinos.
| Algoritmo | Requerimiento |
|---|---|
| Regresión Logística | \(O(p)\) |
| SVM | \(O(n_{\text{sv}} \cdot p)\) |
| Árbol | \(O(n)\) (en el peor caso) |
| Random Forest | \(O(B \cdot n)\) |
| KNN | \(O(np)\) |
| Naive Bayes | \(O(Kp)\) para atributos discretos |
Selección de Características: - Reduce \(p\) significativamente - Acelera entrenamiento: \(O(np) \rightarrow O(n m)\) si \(m \ll p\)
Normalización de Datos: - Escalar características a \([0, 1]\) o \(\mathbb{N}(0, 1)\) - Mejora convergencia en métodos de gradiente
Paralelización: - Random Forest: Entrenar árboles en paralelo - SVM: Usar libsvm con soporte multi-core - Información Mutua: Calcular para cada par en paralelo
La teoría de la información de Shannon proporciona herramientas fundamentales para clasificación:
Árboles de Decisión
↓ (ensemble)
Random Forest / Gradient Boosting
↓ (generalización probabilística)
Modelos de Máxima Entropía
↓ (discretización + información)
Selección de CaracterísticasCover, T. M., & Thomas, J. A. (2006). Elements of Information Theory (2nd ed.). Wiley-Interscience.
Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed.). Springer.
Battiti, R. (1994). “Using mutual information for selecting features in supervised neural net learning.” IEEE Transactions on Neural Networks, 5(4), 537-550.
Williams, P. L., & Beer, R. D. (2010). “Nonnegative decomposition of multivariate information.” arXiv preprint arXiv:1004.2515.
Shannon, C. E. (1948). “A mathematical theory of communication.” The Bell System Technical Journal, 27(3), 379-423.
Temario preparado para Curso Avanzado de Estadística y Minería de Datos | Nivel: Postgrado
Última actualización: Diciembre 2025