Как определить критерии остановки forward-backward selection?

Критерии остановки Forward-Backward Selection

Forward-Backward Selection (пошаговая селекция признаков) — это алгоритм выбора подмножества признаков для модели. Критерии остановки определяют, когда алгоритм должен прекратить добавлять или удалять признаки.

1. Виды пошаговой селекции и их критерии

1.1 Forward Selection (добавление признаков)

from sklearn.feature_selection import SelectKBest, f_classif
from sklearn.datasets import load_breast_cancer
import numpy as np

# Загружаем данные
X, y = load_breast_cancer(return_X_y=True)
print(f"Всего признаков: {X.shape[1]}")

# Forward selection: добавляем признаки один за другим
# Критерий остановки: когда метрика перестаёт улучшаться

from sklearn.model_selection import cross_val_score
from sklearn.linear_model import LogisticRegression

selected_features = []
best_score = -np.inf
scores = []

for i in range(X.shape[1]):
    best_new_score = -np.inf
    best_feature = -1
    
    for j in range(X.shape[1]):
        if j in selected_features or j == -1:
            continue
        
        # Пытаемся добавить признак j
        features = selected_features + [j]
        model = LogisticRegression(max_iter=1000)
        score = cross_val_score(
            model, X[:, features], y, 
            cv=5, scoring='accuracy'
        ).mean()
        
        if score > best_new_score:
            best_new_score = score
            best_feature = j
    
    # Критерий остановки 1: улучшение меньше threshold
    if best_new_score - best_score < 0.001:
        print(f"Остановка: улучшение < 0.1%")
        break
    
    selected_features.append(best_feature)
    best_score = best_new_score
    scores.append(best_score)
    print(f"Итерация {len(selected_features)}: добавлен признак {best_feature}, score={best_new_score:.4f}")

1.2 Backward Elimination (удаление признаков)

# Backward elimination: убираем худшие признаки
from sklearn.preprocessing import StandardScaler

selected_features = list(range(X.shape[1]))  # Начинаем со всех
best_score = -np.inf
scores = []

for iteration in range(X.shape[1]):
    # Вычисляем score текущего набора
    model = LogisticRegression(max_iter=1000)
    current_score = cross_val_score(
        model, X[:, selected_features], y,
        cv=5, scoring='accuracy'
    ).mean()
    scores.append(current_score)
    
    # Критерий остановки 1: если убавление признаков ухудшает модель
    if iteration > 0 and current_score < scores[-2] - 0.001:
        print(f"Остановка: удаление признака ухудшает модель")
        break
    
    if len(selected_features) == 1:
        print(f"Остановка: остался 1 признак")
        break
    
    # Пробуем удалить каждый признак
    worst_feature = -1
    worst_score = current_score
    
    for feature in selected_features:
        features_without = [f for f in selected_features if f != feature]
        model = LogisticRegression(max_iter=1000)
        score = cross_val_score(
            model, X[:, features_without], y,
            cv=5, scoring='accuracy'
        ).mean()
        
        # Худший признак — тот, удаление которого лучше всего сказывается на score
        if score > worst_score:
            worst_score = score
            worst_feature = feature
    
    if worst_feature != -1:
        selected_features.remove(worst_feature)
        print(f"Итерация {iteration}: удалён признак {worst_feature}")

2. Типовые критерии остановки

# Критерий 1: Минимальный прирост метрики
def stop_criterion_min_improvement(previous_score, current_score, threshold=0.001):
    """
    Остановка если улучшение меньше threshold
    """
    improvement = current_score - previous_score
    return improvement < threshold

# Критерий 2: Максимальное количество признаков
def stop_criterion_max_features(num_features, max_features=20):
    """
    Остановка если добавили max_features признаков
    """
    return num_features >= max_features

# Критерий 3: Статистическая значимость
from scipy.stats import f_oneway

def stop_criterion_statistical_significance(p_value, alpha=0.05):
    """
    Остановка если p-value > alpha (не статистически значим)
    """
    return p_value > alpha

# Критерий 4: Информационный критерий (AIC, BIC)
def stop_criterion_aic(model, X, y):
    """
    Используем AIC: ниже — лучше
    AIC = 2k - 2*ln(L)
    k = количество параметров
    L = максимальное значение likelihood
    """
    from sklearn.metrics import log_loss
    
    k = X.shape[1]  # Количество признаков
    n = X.shape[0]  # Количество наблюдений
    
    y_pred = model.predict_proba(X)[:, 1]
    log_likelihood = -n * log_loss(y, y_pred)
    
    aic = 2 * k - 2 * log_likelihood
    return aic

# Критерий 5: Раннее остановление (Early Stopping)
def stop_criterion_early_stopping(train_score, val_score, patience=3):
    """
    Если val_score не улучшается patience итераций подряд
    """
    return patience <= 0  # Счётчик обнулился

3. Полный пример с несколькими критериями

from sklearn.model_selection import StratifiedKFold
from sklearn.preprocessing import StandardScaler

class ForwardSelectionWithStoppingCriteria:
    def __init__(self, 
                 min_improvement=0.001,
                 max_features=None,
                 cv=5,
                 patience=3):
        self.min_improvement = min_improvement
        self.max_features = max_features or float('inf')
        self.cv = cv
        self.patience = patience
        self.selected_features = []
        self.scores_history = []
    
    def fit(self, X, y):
        n_features = X.shape[1]
        patience_counter = self.patience
        best_score = -np.inf
        
        for iteration in range(n_features):
            # Критерий 1: Достигнули max_features
            if len(self.selected_features) >= self.max_features:
                print(f"STOP: Достигнут максимум {self.max_features} признаков")
                break
            
            # Критерий 2: Patience исчерпана
            if patience_counter <= 0:
                print(f"STOP: Early stopping (no improvement for {self.patience} iterations)")
                break
            
            best_new_feature = -1
            best_new_score = best_score
            
            # Пробуем добавить каждый оставшийся признак
            for feature_idx in range(n_features):
                if feature_idx in self.selected_features:
                    continue
                
                features_to_test = self.selected_features + [feature_idx]
                model = LogisticRegression(max_iter=1000, random_state=42)
                
                scores = cross_val_score(
                    model, X[:, features_to_test], y,
                    cv=self.cv, scoring='f1_weighted'
                )
                cv_score = scores.mean()
                
                if cv_score > best_new_score:
                    best_new_score = cv_score
                    best_new_feature = feature_idx
            
            # Критерий 3: Минимальное улучшение
            improvement = best_new_score - best_score
            if improvement < self.min_improvement:
                print(f"STOP: Улучшение {improvement:.4f} < {self.min_improvement}")
                break
            
            if best_new_feature == -1:
                print(f"STOP: Нет новых признаков для добавления")
                break
            
            # Добавляем лучший признак
            self.selected_features.append(best_new_feature)
            best_score = best_new_score
            self.scores_history.append(best_score)
            
            print(f"Итерация {iteration+1}: добавлен признак {best_new_feature}, "
                  f"улучшение={improvement:.4f}, текущий score={best_score:.4f}")
            
            # Обновляем patience counter
            if improvement > self.min_improvement:
                patience_counter = self.patience
            else:
                patience_counter -= 1
        
        return self

# Использование
from sklearn.datasets import make_classification

X, y = make_classification(n_samples=200, n_features=20, n_informative=10, random_state=42)

fs = ForwardSelectionWithStoppingCriteria(
    min_improvement=0.005,
    max_features=10,
    patience=3,
    cv=5
)
fs.fit(X, y)

print(f"\nВыбранные признаки: {fs.selected_features}")
print(f"История scores: {fs.scores_history}")

4. Критерии, основанные на информационных мерах

# AIC (Akaike Information Criterion)
def calculate_aic(n_samples, n_features, rss):
    """
    AIC = n*log(RSS/n) + 2*p
    p = количество параметров (признаков + intercept)
    """
    p = n_features + 1
    return n_samples * np.log(rss / n_samples) + 2 * p

# BIC (Bayesian Information Criterion)
def calculate_bic(n_samples, n_features, rss):
    """
    BIC = n*log(RSS/n) + p*log(n)
    BIC строже штрафует сложность, чем AIC
    """
    p = n_features + 1
    return n_samples * np.log(rss / n_samples) + p * np.log(n_samples)

# Регуляризированные модели: используют встроенные критерии
from sklearn.linear_model import LinearRegression, Ridge, Lasso

# Ridge/Lasso автоматически выбирают alpha на основе cross-validation
from sklearn.linear_model import RidgeCV

model = RidgeCV(alphas=[0.1, 1.0, 10.0], cv=5)
model.fit(X, y)
print(f"Optimal alpha: {model.alpha_}")

5. Практические рекомендации

Выбор критериев остановки зависит от задачи:

1. Для быстрого результата:
   └─ min_improvement = 0.01 (1%)
   └─ max_features = 5-10
   └─ cv = 3

2. Для аккуратного анализа:
   └─ min_improvement = 0.001 (0.1%)
   └─ max_features = количество_признаков / 2
   └─ cv = 10
   └─ patience = 5

3. Для production:
   └─ Используй p_value (статистическая значимость)
   └─ Используй AIC/BIC (информационные критерии)
   └─ Лучше недообучиться, чем переобучиться

4. Для интерпретируемости:
   └─ max_features = 3-7 (можно интерпретировать)
   └─ min_improvement = 0.005 (значимое улучшение)

6. Сравнение с регуляризацией

# Вместо forward selection можно использовать:

# 1. L1 регуляризация (Lasso) — автоматически зануляет признаки
from sklearn.linear_model import LassoCV

lasso = LassoCV(cv=5)
lasso.fit(X_scaled, y)

selected_lasso = np.where(lasso.coef_ != 0)[0]
print(f"Признаки с Lasso: {selected_lasso}")

# 2. Tree-based feature importance
from sklearn.ensemble import RandomForestClassifier

rf = RandomForestClassifier(n_estimators=100, random_state=42)
rf.fit(X, y)

feature_importance = rf.feature_importances_
selected_rf = np.argsort(feature_importance)[-10:]  # Top 10
print(f"Top признаки (Random Forest): {selected_rf}")

# 3. Permutation importance
from sklearn.inspection import permutation_importance

perm_importance = permutation_importance(rf, X, y, n_repeats=10)
selected_perm = np.argsort(perm_importance.importances_mean)[-10:]
print(f"Top признаки (Permutation): {selected_perm}")

Заключение

Критерии остановки Forward-Backward Selection:

1. Минимальное улучшение метрики — самый частый (0.1-1%)
2. Максимальное количество признаков — для интерпретируемости
3. Статистическая значимость (p-value) — для формальной статистики
4. Информационные критерии (AIC/BIC) — для моделей с likelihood
5. Early Stopping (Patience) — когда улучшение застопорилось
6. Без улучшения валидационной метрики — защита от переобучения

Рекомендуемый подход:

• Используй комбинацию критериев
• Начни с простого (min_improvement + max_features)
• Визуализируй кривую scores для анализа
• Проверь результаты на валидационном сете
• Рассмотри альтернативы (Lasso, Tree-based selection)