Hands-on lab — Day 174: Handling Missing Data

"""
Handling Missing Data reference library implementation.
"""
import numpy as np


def compute_nan_euclidean_distance(u: np.ndarray, v: np.ndarray) -> float:
    """
    NaN-Euclidean Distance formula:
    d(u, v) = sqrt( (D_total / D_valid) * sum_{j in valid} (u_j - v_j)^2 )
    If no coordinates overlap, returns infinity.
    """
    u = np.asarray(u, dtype=float)
    v = np.asarray(v, dtype=float)
    total_dim = len(u)
    
    valid_mask = ~np.isnan(u) & ~np.isnan(v)
    valid_count = np.sum(valid_mask)
    
    if valid_count == 0:
        return float("inf")
        
    diffs_sq = (u[valid_mask] - v[valid_mask]) ** 2
    scaled_sq_sum = (total_dim / valid_count) * np.sum(diffs_sq)
    return float(np.sqrt(scaled_sq_sum))


def generate_missing_indicator(X: np.ndarray) -> np.ndarray:
    """
    Returns boolean matrix of shape (N, D) where True indicates NaN.
    """
    X = np.asarray(X)
    return np.isnan(X)


def knn_imputer_scratch(X: np.ndarray, n_neighbors: int = 3) -> np.ndarray:
    """
    KNN Imputation from scratch:
    For each row with NaNs, finds k nearest neighbors based on NaN-Euclidean distance
    over observed features, and imputes missing coordinates using uniform neighbor mean.
    """
    X = np.asarray(X, dtype=float).copy()
    n_samples, n_features = X.shape
    
    # Precompute column means for extreme fallback
    col_means = np.nanmean(X, axis=0)
    # If a column is entirely NaN, fill with 0.0
    col_means = np.nan_to_num(col_means, nan=0.0)
    
    for i in range(n_samples):
        row = X[i]
        nan_cols = np.where(np.isnan(row))[0]
        if len(nan_cols) == 0:
            continue
            
        # Compute distances to all other samples
        distances = []
        for j in range(n_samples):
            if i == j:
                distances.append((float("inf"), j))
            else:
                dist = compute_nan_euclidean_distance(row, X[j])
                distances.append((dist, j))
                
        distances.sort(key=lambda item: item[0])
        neighbor_indices = [idx for d, idx in distances if not np.isinf(d)][:n_neighbors]
        
        for c in nan_cols:
            vals = [X[nbr, c] for nbr in neighbor_indices if not np.isnan(X[nbr, c])]
            if len(vals) > 0:
                X[i, c] = float(np.mean(vals))
            else:
                X[i, c] = col_means[c]
                
    return X

"""
Tests for reference imputation implementation.
"""
import pytest
import numpy as np
import imputation_lib as mi


def test_nan_euclidean_distance_math():
    # u = [1, NaN, 3], v = [4, 5, 7]
    # Overlapping indices: 0 and 2. diffs: (1-4)^2=9, (3-7)^2=16. sum=25.
    # Total dim = 3, Valid dim = 2. Scaled sum = 3/2 * 25 = 37.5.
    # Distance = sqrt(37.5) = 6.1237
    u = np.array([1.0, np.nan, 3.0])
    v = np.array([4.0, 5.0, 7.0])
    dist = mi.compute_nan_euclidean_distance(u, v)
    assert np.isclose(dist, np.sqrt(37.5), atol=1e-5)


def test_missing_indicator_shape():
    X = np.array([
        [1.0, np.nan],
        [np.nan, 2.0],
        [3.0, 4.0]
    ])
    indicator = mi.generate_missing_indicator(X)
    assert np.array_equal(indicator, [[False, True], [True, False], [False, False]])


def test_knn_imputation_reconstruction():
    # Sample 0 and Sample 1 are identical twins except sample 0 is missing col 1
    X = np.array([
        [10.0, np.nan, 100.0],
        [10.0, 50.0, 100.0],
        [10.0, 50.0, 100.0],
        [90.0, 900.0, 900.0]
    ])
    X_imp = mi.knn_imputer_scratch(X, n_neighbors=2)
    # The imputed value for row 0 col 1 should be 50.0
    assert np.isclose(X_imp[0, 1], 50.0, atol=1e-5)
    assert not np.isnan(X_imp).any()

lesson_id: D174
day: 174
kind: missing-data-imputation
languages:
  - python
setup_commands:
  - python3 -m venv .venv
  - .venv/bin/pip install -r requirements/requirements.txt
run_commands:
  - .venv/bin/python examples/imputation_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 NaN-Euclidean metric distance, MissingIndicator mask extraction, and KNNImputer from scratch.

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

"""
Handling Missing Data starter library.
"""
import numpy as np


def compute_nan_euclidean_distance(u: np.ndarray, v: np.ndarray) -> float:
    """Compute NaN-aware Euclidean distance between two vectors with missing coordinates."""
    raise NotImplementedError("Implement compute_nan_euclidean_distance")


def generate_missing_indicator(X: np.ndarray) -> np.ndarray:
    """Generate binary indicator matrix I_{mis} where 1 indicates missing (NaN) and 0 indicates observed."""
    raise NotImplementedError("Implement generate_missing_indicator")


def knn_imputer_scratch(X: np.ndarray, n_neighbors: int = 3) -> np.ndarray:
    """Impute missing values using distance-weighted K-Nearest Neighbors."""
    raise NotImplementedError("Implement knn_imputer_scratch")

"""
Tests for starter missing data handling.
"""
import pytest
import numpy as np
import imputation_lib as mi


def test_nan_dist_stub():
    with pytest.raises(NotImplementedError):
        mi.compute_nan_euclidean_distance(np.array([1.0, np.nan]), np.array([2.0, 3.0]))


def test_knn_imputer_stub():
    with pytest.raises(NotImplementedError):
        mi.knn_imputer_scratch(np.array([[1.0, np.nan], [2.0, 3.0]]))

#!/usr/bin/env bash
# Day 174 lab harness: "Handling Missing Data"
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 imputation_lib as mi

# NaN-Euclidean distance scaling invariant
u = np.array([2.0, np.nan])
v = np.array([5.0, np.nan])
# Overlap dim=1, total dim=2 -> diff^2 = 9 -> scaled = (2/1)*9 = 18 -> sqrt(18) = 4.2426
d = mi.compute_nan_euclidean_distance(u, v)
assert np.isclose(d, np.sqrt(18.0)), "NaN Euclidean scaling invariant failed"

print("MATH_OK")
PYEOF
)

if [ "$MATH_CHECK" = "MATH_OK" ]; then
  ok "NaN-Euclidean distance scaling 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