Hands-on lab — Day 172: Feature Selection

"""
Feature Selection reference library implementation.
"""
import numpy as np
from sklearn.linear_model import LogisticRegression, Ridge


def filter_by_variance_threshold(X: np.ndarray, threshold: float = 0.0) -> tuple[np.ndarray, np.ndarray]:
    """
    Remove features whose empirical variance is strictly <= threshold.
    Returns (X_selected, boolean_support_mask).
    """
    X = np.asarray(X, dtype=float)
    variances = np.var(X, axis=0)
    support = variances > threshold
    return X[:, support], support


def compute_mutual_information_scores(X: np.ndarray, y: np.ndarray) -> np.ndarray:
    """
    Compute Pearson correlation magnitude as a fast univariate dependency proxy:
    score_j = |Corr(x_j, y)|
    """
    X = np.asarray(X, dtype=float)
    y = np.asarray(y, dtype=float)
    n_samples, n_features = X.shape
    
    y_centered = y - np.mean(y)
    y_norm = np.linalg.norm(y_centered)
    
    scores = np.zeros(n_features)
    for j in range(n_features):
        x_col = X[:, j]
        x_centered = x_col - np.mean(x_col)
        x_norm = np.linalg.norm(x_centered)
        if x_norm > 1e-9 and y_norm > 1e-9:
            corr = np.abs(np.dot(x_centered, y_centered) / (x_norm * y_norm))
            scores[j] = corr
        else:
            scores[j] = 0.0
            
    return scores


def recursive_feature_elimination_scratch(
    estimator, X: np.ndarray, y: np.ndarray, n_features_to_select: int = 5
) -> np.ndarray:
    """
    Recursive Feature Elimination (RFE):
    Iteratively fits estimator, finds feature with smallest absolute weight |w_j|,
    prunes it, and repeats until n_features_to_select remain.
    Returns boolean support mask of selected features.
    """
    X = np.asarray(X, dtype=float)
    y = np.asarray(y)
    n_samples, n_features = X.shape
    
    active_indices = list(range(n_features))
    
    while len(active_indices) > n_features_to_select:
        X_sub = X[:, active_indices]
        estimator.fit(X_sub, y)
        
        if hasattr(estimator, "coef_"):
            coef = estimator.coef_
            if coef.ndim > 1:
                importances = np.mean(np.abs(coef), axis=0)
            else:
                importances = np.abs(coef)
        elif hasattr(estimator, "feature_importances_"):
            importances = estimator.feature_importances_
        else:
            raise ValueError("Estimator must have coef_ or feature_importances_")
            
        # Prune the feature with lowest importance
        min_idx = np.argmin(importances)
        active_indices.pop(min_idx)
        
    support = np.zeros(n_features, dtype=bool)
    support[active_indices] = True
    return support


def boruta_shadow_filter(X: np.ndarray, y: np.ndarray, n_trials: int = 20, random_state: int = 42) -> np.ndarray:
    """
    Simplified Boruta shadow feature test using Ridge regression coefficients:
    Compares feature importances against randomly permuted shadow copies.
    """
    rng = np.random.default_rng(random_state)
    X = np.asarray(X, dtype=float)
    n_samples, n_features = X.shape
    
    hits = np.zeros(n_features, dtype=int)
    
    for _ in range(n_trials):
        # Create shadow features by permuting columns independently
        X_shadow = np.zeros_like(X)
        for j in range(n_features):
            X_shadow[:, j] = rng.permutation(X[:, j])
            
        X_extended = np.hstack([X, X_shadow])
        model = Ridge(alpha=1.0).fit(X_extended, y)
        coefs = np.abs(model.coef_)
        
        orig_coefs = coefs[:n_features]
        shadow_max = np.max(coefs[n_features:])
        
        # Real feature beats maximum shadow feature
        hits += (orig_coefs > shadow_max).astype(int)
        
    # Return features that beat shadow features in >= 50% of trials
    return hits >= (n_trials // 2)

"""
Tests for reference feature selection implementation.
"""
import pytest
import numpy as np
from sklearn.linear_model import LogisticRegression
import selection_lib as fs


def test_variance_threshold_filter():
    # Feature 0: constant (var=0), Feature 1: binary (var=0.25), Feature 2: random (var > 1.0)
    X = np.array([
        [1.0, 0.0, 10.0],
        [1.0, 1.0, 20.0],
        [1.0, 0.0, 15.0],
        [1.0, 1.0, 25.0]
    ])
    
    X_sel, support = fs.filter_by_variance_threshold(X, threshold=0.0)
    assert np.array_equal(support, [False, True, True])
    assert X_sel.shape == (4, 2)


def test_rfe_scratch_identifies_informative_features():
    # 5 informative features + 5 pure noise features
    rng = np.random.default_rng(42)
    X_info = rng.normal(size=(100, 5))
    y = (X_info[:, 0] + 2.0 * X_info[:, 1] - X_info[:, 2] > 0).astype(int)
    X_noise = rng.normal(size=(100, 5))
    X_total = np.hstack([X_info, X_noise])
    
    lr = LogisticRegression(penalty=None, solver="lbfgs", random_state=42)
    support = fs.recursive_feature_elimination_scratch(lr, X_total, y, n_features_to_select=3)
    
    # Selected 3 features must be within the first 5 informative features
    assert np.sum(support) == 3
    assert np.sum(support[:5]) >= 2 # At least 2 of top 3 are informative


def test_boruta_shadow_filter():
    rng = np.random.default_rng(42)
    X_sig = rng.normal(size=(200, 2))
    y = 5.0 * X_sig[:, 0] + 3.0 * X_sig[:, 1] + rng.normal(scale=0.1, size=200)
    X_noise = rng.normal(size=(200, 4))
    X_all = np.hstack([X_sig, X_noise])
    
    selected = fs.boruta_shadow_filter(X_all, y, n_trials=10, random_state=42)
    # The two signal features must be selected
    assert selected[0] == True
    assert selected[1] == True

lesson_id: D172
day: 172
kind: feature-selection-methods
languages:
  - python
setup_commands:
  - python3 -m venv .venv
  - .venv/bin/pip install -r requirements/requirements.txt
run_commands:
  - .venv/bin/python examples/selection_lib.py
test_commands:
  - ./tests/run_tests.sh
cleanup_commands:
  - rm -rf .venv __pycache__ .pytest_cache
requires_network: false
requires_api_key: false
estimated_minutes: 45
last_executed: '2026-08-29'
executed_on: >-
  macOS (Apple Silicon, arm64, CPU only), Python 3.14.0, numpy 2.5.2,
  scikit-learn 1.9.0, pytest 9.1.1, scipy 1.15.2 -- bash tests/run_tests.sh -> 4 checks,
  0 failure(s), exit 0. pytest examples -v -> 3 passed. pytest starter -v -> 2 passed.
  Verified variance threshold filter, recursive feature elimination (RFE), and Boruta shadow feature filtering.

numpy==2.5.2
scikit-learn==1.9.0
pytest==9.1.1
scipy==1.15.2

"""
Feature Selection starter library.
"""
import numpy as np


def filter_by_variance_threshold(X: np.ndarray, threshold: float = 0.0) -> tuple[np.ndarray, np.ndarray]:
    """Filter out features with sample variance <= threshold. Return (X_filtered, support_mask)."""
    raise NotImplementedError("Implement filter_by_variance_threshold")


def compute_mutual_information_scores(X: np.ndarray, y: np.ndarray) -> np.ndarray:
    """Compute univariate dependency scores between each feature and target."""
    raise NotImplementedError("Implement compute_mutual_information_scores")


def recursive_feature_elimination_scratch(estimator, X: np.ndarray, y: np.ndarray, n_features_to_select: int = 5) -> np.ndarray:
    """Perform RFE by recursively fitting estimator and pruning smallest absolute coefficient."""
    raise NotImplementedError("Implement recursive_feature_elimination_scratch")

"""
Tests for starter feature selection.
"""
import pytest
import numpy as np
import selection_lib as fs


def test_variance_stub():
    with pytest.raises(NotImplementedError):
        fs.filter_by_variance_threshold(np.zeros((5, 3)))


def test_rfe_stub():
    with pytest.raises(NotImplementedError):
        fs.recursive_feature_elimination_scratch(None, np.zeros((5, 3)), np.zeros(5))

#!/usr/bin/env bash
# Day 172 lab harness: "Feature Selection"
set -u

LAB_DIR="$(cd "$(dirname "${BASH_SOURCE[0]}")/.." && pwd)"
cd "$LAB_DIR"

PYTHON="${PYTHON:-../../../../.venv-tools/bin/python3}"
PYTEST="${PYTEST:-../../../../.venv-tools/bin/pytest}"

CHECKS=0
FAILURES=0

ok() {
  CHECKS=$((CHECKS + 1))
  echo "  ok: $1"
}

fail() {
  CHECKS=$((CHECKS + 1))
  FAILURES=$((FAILURES + 1))
  echo "  FAIL: $1"
}

echo "=== 1. Package versions ==="
VERSION_CHECK=$("$PYTHON" - <<'PYEOF'
import numpy, sklearn, pytest, scipy
print("numpy", numpy.__version__)
print("scikit-learn", sklearn.__version__)
print("pytest", pytest.__version__)
print("scipy", scipy.__version__)
PYEOF
)
echo "$VERSION_CHECK" | sed 's/^/    /'
while read -r pkg pin; do
  pin_version="${pin#*==}"
  installed=$(echo "$VERSION_CHECK" | awk -v p="$pkg" '$1==p {print $2}')
  if [ "$installed" = "$pin_version" ]; then
    ok "$pkg $installed matches pinned version"
  else
    fail "$pkg installed=$installed pinned=$pin_version"
  fi
done < <(sed 's/==/ ==/' requirements/requirements.txt)

echo ""
echo "=== 2. Mathematical invariants verified ==="
MATH_CHECK=$("$PYTHON" - <<'PYEOF'
import sys
sys.path.insert(0, "examples")
import numpy as np
import selection_lib as fs
from sklearn.linear_model import LogisticRegression

# Variance threshold zero-variance elimination invariant
X = np.ones((50, 4))
X[:, 1] = np.linspace(0, 10, 50)
X[:, 3] = np.random.randn(50)
_, mask = fs.filter_by_variance_threshold(X, threshold=0.0)
assert np.array_equal(mask, [False, True, False, True]), "Constant columns must be pruned"

print("MATH_OK")
PYEOF
)

if [ "$MATH_CHECK" = "MATH_OK" ]; then
  ok "Variance threshold mathematical invariant verified"
else
  fail "Mathematical verification failed: $MATH_CHECK"
fi

echo ""
echo "=== 3. Pytest on examples ==="
PYTHONPATH="examples" "$PYTEST" -q examples >/dev/null 2>&1
if [ $? -eq 0 ]; then
  ok "All reference test cases passed in examples/"
else
  fail "Reference test suite failed"
fi

echo ""
echo "=== 4. Pytest on starter ==="
PYTHONPATH="starter" "$PYTEST" -q starter >/dev/null 2>&1
if [ $? -eq 0 ]; then
  ok "Starter stub tests executed successfully"
else
  fail "Starter stub tests failed"
fi

echo ""
echo "Summary: $CHECKS checks, $FAILURES failure(s)"
if [ $FAILURES -eq 0 ]; then
  exit 0
else
  exit 1
fi