Anteriormente exploramos algoritmos como LARS e Lasso para problemas de regressão esparsa. Analogamente, a Busca por Correspondência Ortogonal (OMP) é outro algoritmo eficiente para aproximação esparsa que seleciona iterativamente as features mais correlacionadas com o resíduo atual.
Conceito Fundamental do OMP
Primordialmente, o OMP é um algoritmo guloso que resolve problemas de aproximação esparsa. Decerto, ele busca encontrar uma representação esparsa dos dados usando um número limitado de features (átomos) de um dicionário.
Conforme a documentação do scikit-learn, o OMP é particularmente útil quando sabemos antecipadamente o número de features que desejamos selecionar. Similarmente ao LARS, ele constrói a solução de forma incremental, mas com uma abordagem de projeção ortogonal.
Algoritmo OMP
O algoritmo opera através dos seguintes passos iterativos:
- Inicializar o resíduo com o target original
- Encontrar a feature mais correlacionada com o resíduo atual
- Adicionar essa feature ao conjunto ativo
- Resolver o problema de mínimos quadrados usando apenas as features ativas
- Atualizar o resíduo subtraindo a contribuição das features selecionadas
- Repetir até atingir o critério de parada
Formulação Matemática
O objetivo do OMP é resolver:
\(\min_{w} ||Xw – y||_2^2\)Sujeito a:
\(||w||_0 \leq k\)Onde:
- X é a matriz de features
- y é o vetor target
- w são os coeficientes esparsos
- k é o número máximo de features não-zero
- ||w||₀ é a norma L0 (número de elementos não-zero)
Implementações no Scikit-learn
Atualmente, o scikit-learn oferece duas implementações principais:
- OrthogonalMatchingPursuit: Implementação padrão do OMP
- OrthogonalMatchingPursuitCV: Versão com validação cruzada para seleção automática do parâmetro n_nonzero_coefs
Parâmetros Principais
Os principais parâmetros para ajuste no OMP são:
- n_nonzero_coefs: Número máximo de coeficientes não-zero
- tol: Tolerância para erro de aproximação
- fit_intercept: Se deve calcular intercept
- normalize: Se deve normalizar as features
Exemplo Prático: OMP em Ação
Ademais, vejamos um exemplo completo demonstrando o uso do Orthogonal Matching Pursuit:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 |
''' Aplicação do Orthogonal Matching Pursuit (OMP) para Regressão com Seleção de Features CÓDIGO CORRIGIDO - Problema com OrthogonalMatchingPursuitCV ''' import numpy as np import matplotlib.pyplot as plt from sklearn.datasets import make_regression from sklearn.linear_model import OrthogonalMatchingPursuit from sklearn.linear_model import Lasso, LassoLars from sklearn.model_selection import train_test_split, cross_val_score from sklearn.preprocessing import StandardScaler from sklearn.metrics import mean_squared_error, r2_score # Gerar dataset com features esparsas n_samples = 200 n_features = 50 n_informative = 10 print("Configuração do Dataset:") print(f"Número de amostras: {n_samples}") print(f"Número de features: {n_features}") print(f"Features informativas: {n_informative}") # Gerar dados com estrutura esparsa X, y, true_coef = make_regression(n_samples=n_samples, n_features=n_features, n_informative=n_informative, noise=20, coef=True, random_state=42) print(f"\nDimensões: X {X.shape}, y {y.shape}") # Dividir em treino e teste X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42) # Normalizar os dados scaler = StandardScaler() X_train_scaled = scaler.fit_transform(X_train) X_test_scaled = scaler.transform(X_test) print(f"\n--- Comparação: OMP vs Outros Algoritmos Esparsos ---") # Orthogonal Matching Pursuit com diferentes números de features omp_5 = OrthogonalMatchingPursuit(n_nonzero_coefs=5) omp_5.fit(X_train_scaled, y_train) y_pred_omp_5 = omp_5.predict(X_test_scaled) mse_omp_5 = mean_squared_error(y_test, y_pred_omp_5) r2_omp_5 = r2_score(y_test, y_pred_omp_5) omp_10 = OrthogonalMatchingPursuit(n_nonzero_coefs=10) omp_10.fit(X_train_scaled, y_train) y_pred_omp_10 = omp_10.predict(X_test_scaled) mse_omp_10 = mean_squared_error(y_test, y_pred_omp_10) r2_omp_10 = r2_score(y_test, y_pred_omp_10) # Lasso para comparação lasso = Lasso(alpha=0.1, max_iter=10000, random_state=42) lasso.fit(X_train_scaled, y_train) y_pred_lasso = lasso.predict(X_test_scaled) mse_lasso = mean_squared_error(y_test, y_pred_lasso) r2_lasso = r2_score(y_test, y_pred_lasso) # LassoLars para comparação lassolars = LassoLars(alpha=0.1, max_iter=1000) lassolars.fit(X_train_scaled, y_train) y_pred_lassolars = lassolars.predict(X_test_scaled) mse_lassolars = mean_squared_error(y_test, y_pred_lassolars) r2_lassolars = r2_score(y_test, y_pred_lassolars) print(f"\nOMP (5 features):") print(f"MSE: {mse_omp_5:.2f}, R²: {r2_omp_5:.4f}") print(f"Features selecionadas: {np.sum(omp_5.coef_ != 0)}") print(f"\nOMP (10 features):") print(f"MSE: {mse_omp_10:.2f}, R²: {r2_omp_10:.4f}") print(f"Features selecionadas: {np.sum(omp_10.coef_ != 0)}") print(f"\nLasso:") print(f"MSE: {mse_lasso:.2f}, R²: {r2_lasso:.4f}") print(f"Features selecionadas: {np.sum(lasso.coef_ != 0)}") print(f"\nLassoLars:") print(f"MSE: {mse_lassolars:.2f}, R²: {r2_lassolars:.4f}") print(f"Features selecionadas: {np.sum(lassolars.coef_ != 0)}") # Implementação manual de validação cruzada para OMP print(f"\n--- Validação Cruzada Manual para OMP ---") n_features_range = range(1, 16) # Limitado para evitar o erro cv_scores = [] for n_feat in n_features_range: omp_cv = OrthogonalMatchingPursuit(n_nonzero_coefs=n_feat) scores = cross_val_score(omp_cv, X_train_scaled, y_train, cv=5, scoring='neg_mean_squared_error') cv_scores.append(-scores.mean()) print(f"n_nonzero_coefs = {n_feat}: MSE CV = {-scores.mean():.2f}") best_n_features = n_features_range[np.argmin(cv_scores)] print(f"\nMelhor n_nonzero_coefs: {best_n_features}") # Treinar OMP com melhor parâmetro omp_best = OrthogonalMatchingPursuit(n_nonzero_coefs=best_n_features) omp_best.fit(X_train_scaled, y_train) y_pred_omp_best = omp_best.predict(X_test_scaled) mse_omp_best = mean_squared_error(y_test, y_pred_omp_best) r2_omp_best = r2_score(y_test, y_pred_omp_best) print(f"\nOMP (Melhor - {best_n_features} features):") print(f"MSE: {mse_omp_best:.2f}, R²: {r2_omp_best:.4f}") # Visualização dos resultados plt.figure(figsize=(15, 10)) # Gráfico 1: Comparação de coeficientes plt.subplot(2, 3, 1) features = range(len(true_coef)) n_plot = min(30, len(true_coef)) plt.plot(features[:n_plot], true_coef[:n_plot], 'o-', label='Verdadeiro', linewidth=2, markersize=4, alpha=0.7) plt.plot(features[:n_plot], omp_best.coef_[:n_plot], 's-', label='OMP Melhor', alpha=0.8, markersize=3) plt.plot(features[:n_plot], lasso.coef_[:n_plot], '^-', label='Lasso', alpha=0.8, markersize=3) plt.plot(features[:n_plot], lassolars.coef_[:n_plot], 'd-', label='LassoLars', alpha=0.8, markersize=3) plt.xlabel('Feature Index') plt.ylabel('Valor do Coeficiente') plt.title('Comparação dos Coeficientes') plt.legend() plt.grid(True, alpha=0.3) # Gráfico 2: Validação Cruzada - MSE vs Número de Features plt.subplot(2, 3, 2) plt.plot(n_features_range, cv_scores, 'o-', linewidth=2, markersize=6) plt.axvline(x=best_n_features, color='red', linestyle='--', label=f'Melhor: {best_n_features}') plt.xlabel('Número de Features (n_nonzero_coefs)') plt.ylabel('MSE (Validação Cruzada)') plt.title('Validação Cruzada - OMP') plt.legend() plt.grid(True, alpha=0.3) # Gráfico 3: Features selecionadas plt.subplot(2, 3, 3) methods = ['OMP (5)', 'OMP (10)', 'OMP (Melhor)', 'Lasso', 'LassoLars'] n_selected = [np.sum(omp_5.coef_ != 0), np.sum(omp_10.coef_ != 0), np.sum(omp_best.coef_ != 0), np.sum(lasso.coef_ != 0), np.sum(lassolars.coef_ != 0)] colors = ['lightcoral', 'lightcoral', 'red', 'lightgreen', 'skyblue'] plt.bar(methods, n_selected, color=colors, alpha=0.7) plt.ylabel('Número de Features Selecionadas') plt.title('Seleção de Features') plt.xticks(rotation=45) for i, v in enumerate(n_selected): plt.text(i, v + 0.5, str(v), ha='center', va='bottom') # Gráfico 4: Comparação de performance plt.subplot(2, 3, 4) mses = [mse_omp_5, mse_omp_10, mse_omp_best, mse_lasso, mse_lassolars] plt.bar(methods, mses, color=colors, alpha=0.7) plt.ylabel('MSE') plt.title('Comparação de Performance') plt.xticks(rotation=45) for i, v in enumerate(mses): plt.text(i, v + 0.5, f'{v:.1f}', ha='center', va='bottom') # Gráfico 5: Ordem de seleção das features no OMP plt.subplot(2, 3, 5) # Para OMP, podemos analisar a ordem através da reconstrução residual = y_train.copy() selected_features = [] correlations_history = [] for step in range(omp_best.n_nonzero_coefs): correlations = np.abs(X_train_scaled.T @ residual) best_feature = np.argmax(correlations) selected_features.append(best_feature) correlations_history.append(correlations[best_feature]) # Atualizar usando apenas features selecionadas X_active = X_train_scaled[:, selected_features] coef_active = np.linalg.lstsq(X_active, y_train, rcond=None)[0] residual = y_train - X_active @ coef_active plt.plot(range(1, len(selected_features) + 1), selected_features, 'o-', linewidth=2) plt.xlabel('Ordem de Seleção') plt.ylabel('Índice da Feature') plt.title('Ordem de Seleção das Features no OMP') plt.grid(True, alpha=0.3) # Gráfico 6: Correlação das features selecionadas plt.subplot(2, 3, 6) plt.plot(range(1, len(correlations_history) + 1), correlations_history, 's-', linewidth=2, color='purple') plt.xlabel('Ordem de Seleção') plt.ylabel('Correlação com Resíduo') plt.title('Correlação das Features Selecionadas') plt.grid(True, alpha=0.3) plt.tight_layout() plt.show() # Análise detalhada print(f"\n--- Análise Detalhada ---") true_informative = np.where(true_coef != 0)[0] omp_selected = np.where(omp_best.coef_ != 0)[0] print(f"Features informativas verdadeiras: {len(true_informative)}") print(f"Features selecionadas pelo OMP: {len(omp_selected)}") print(f"Features corretamente selecionadas: {len(np.intersect1d(true_informative, omp_selected))}") print(f"Features informativas perdidas: {len(np.setdiff1d(true_informative, omp_selected))}") # Métricas de seleção def calculate_selection_metrics(true_idx, selected_idx): tp = len(np.intersect1d(true_idx, selected_idx)) fp = len(np.setdiff1d(selected_idx, true_idx)) fn = len(np.setdiff1d(true_idx, selected_idx)) precision = tp / (tp + fp) if (tp + fp) > 0 else 0 recall = tp / (tp + fn) if (tp + fn) > 0 else 0 f1 = 2 * precision * recall / (precision + recall) if (precision + recall) > 0 else 0 return precision, recall, f1 precision, recall, f1 = calculate_selection_metrics(true_informative, omp_selected) print(f"\nMétricas de Seleção - OMP:") print(f"Precisão: {precision:.3f}") print(f"Recall: {recall:.3f}") print(f"F1-Score: {f1:.3f}") # Resumo final print(f"\n--- Resumo Final ---") best_model_idx = np.argmin([mse_omp_5, mse_omp_10, mse_omp_best, mse_lasso, mse_lassolars]) best_model_name = methods[best_model_idx] print(f"Melhor modelo: {best_model_name} (MSE: {[mse_omp_5, mse_omp_10, mse_omp_best, mse_lasso, mse_lassolars][best_model_idx]:.2f})") print(f"OMP com validação cruzada escolheu {best_n_features} features") print(f"F1-Score do OMP: {f1:.3f}") |
Vantagens do OMP
Embora existam vários algoritmos para regressão esparsa, o OMP oferece vantagens específicas:
Vantagens Principais
- Controle direto: Especificação explícita do número de features
- Eficiência computacional: Algoritmo guloso com complexidade controlada
- Garantias teóricas: Boas propriedades de recuperação sob condições específicas
- Interpretabilidade: Ordem de seleção fornece insights sobre importância
Casos de Uso Recomendados
O Orthogonal Matching Pursuit é particularmente eficaz em:
- Compressed sensing: Recuperação de sinais esparsos
- Seleção de features com orçamento fixo: Quando há limite no número de features
- Problemas com dicionários grandes: Onde apenas poucos átomos são relevantes
- Aplicações em tempo real: Onde eficiência computacional é crucial
Considerações Práticas
Algumas recomendações importantes para uso eficaz:
- Use OrthogonalMatchingPursuitCV quando não souber o número ideal de features
- Normalize os dados antes de aplicar OMP para melhor performance
- Considere a correlação entre features, pois pode afetar a ordem de seleção
- Para problemas muito grandes, verifique a escalabilidade do algoritmo
Enfim, o Orthogonal Matching Pursuit representa uma abordagem elegante e eficiente para problemas de aproximação esparsa, oferecendo controle direto sobre a esparsidade da solução e boas propriedades teóricas de recuperação.
Referência: https://scikit-learn.org/0.21/modules/linear_model.html#orthogonal-matching-pursuit-omp