KNN — Unscaled Features Crashed Accuracy from 92% to 58%

import numpy as np
from collections import Counter

# --- KNN implemented from scratch so you can see every decision ---

def euclidean_distance(point_a, point_b):
    """Calculate straight-line distance between two points in N-dimensional space."""
    # Subtract coordinates, square them, sum them up, take the square root
    return np.sqrt(np.sum((np.array(point_a) - np.array(point_b)) ** 2))

def knn_predict(training_features, training_labels, new_point, k):
    """
    Predict the class label for a single new data point.
    
    training_features : list of lists — each inner list is one training example
    training_labels   : list of class labels, one per training example
    new_point         : the unlabelled point we want to classify
    k                 : how many neighbours get a vote
    """
    # Step 1: Calculate distance from new_point to EVERY training example
    distances = []
    for index, training_point in enumerate(training_features):
        dist = euclidean_distance(training_point, new_point)
        distances.append((dist, training_labels[index]))  # store (distance, label) pair

    # Step 2: Sort by distance ascending — closest neighbours come first
    distances.sort(key=lambda pair: pair[0])

    # Step 3: Take the K closest neighbours and collect their labels
    k_nearest_labels = [label for (_, label) in distances[:k]]

    # Step 4: Majority vote — most common label wins
    vote_counts = Counter(k_nearest_labels)
    predicted_label = vote_counts.most_common(1)[0][0]  # [0] = top result, [0] = the label itself

    return predicted_label, k_nearest_labels


# --- Toy dataset: classifying fruit by (weight_grams, sweetness_score) ---
# Label 0 = apple, Label 1 = orange
training_features = [
    [182, 7],   # apple
    [167, 6],   # apple
    [190, 8],   # apple
    [155, 9],   # orange
    [140, 10],  # orange
    [160, 8],   # orange
]
training_labels = [0, 0, 0, 1, 1, 1]  # 0=apple, 1=orange

# New fruit: 170 grams, sweetness 8 — is it an apple or orange?
unknown_fruit = [170, 8]
k_value = 3

prediction, neighbours_used = knn_predict(
    training_features, training_labels, unknown_fruit, k=k_value
)

label_names = {0: 'Apple', 1: 'Orange'}
print(f"Unknown fruit features: weight={unknown_fruit[0]}g, sweetness={unknown_fruit[1]}")
print(f"K = {k_value}")
print(f"Neighbour labels chosen: {[label_names[l] for l in neighbours_used]}")
print(f"Predicted class: {label_names[prediction]}")

import numpy as np
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
import matplotlib
matplotlib.use('Agg')  # non-interactive backend for running in scripts
import matplotlib.pyplot as plt

# --- Load a real dataset: wine classification (13 chemical features, 3 classes) ---
wine_data = load_wine()
feature_matrix = wine_data.data    # shape: (178, 13)
target_labels  = wine_data.target  # 0, 1, or 2 (three wine cultivars)

# Split into training and test sets — stratify ensures class balance is preserved
X_train, X_test, y_train, y_test = train_test_split(
    feature_matrix, target_labels,
    test_size=0.25,
    random_state=42,
    stratify=target_labels
)

# --- Experiment 1: KNN WITHOUT scaling (the wrong way) ---
# Raw features have wildly different scales (e.g., 'proline' ranges 0-1680, 'nonflavanoid_phenols' 0-0.66)
unscaled_knn = KNeighborsClassifier(n_neighbors=5)
unscaled_knn.fit(X_train, y_train)
unscaled_accuracy = unscaled_knn.score(X_test, y_test)

# --- Experiment 2: KNN WITH scaling (the right way) ---
# Pipeline ensures the scaler is fitted ONLY on training data — prevents data leakage
scaled_knn_pipeline = Pipeline(steps=[
    ('scaler', StandardScaler()),          # zero mean, unit variance per feature
    ('knn',    KNeighborsClassifier(n_neighbors=5))
])
scaled_knn_pipeline.fit(X_train, y_train)
scaled_accuracy = scaled_knn_pipeline.score(X_test, y_test)

# --- Experiment 3: Find optimal K using cross-validation on the TRAINING set only ---
k_values_to_test = range(1, 31)  # try K from 1 to 30
mean_cv_scores = []

for k in k_values_to_test:
    pipeline_for_k = Pipeline(steps=[
        ('scaler', StandardScaler()),
        ('knn',    KNeighborsClassifier(n_neighbors=k))
    ])
    # 5-fold cross-validation — returns 5 accuracy scores, one per fold
    cv_scores = cross_val_score(pipeline_for_k, X_train, y_train, cv=5, scoring='accuracy')
    mean_cv_scores.append(cv_scores.mean())

best_k = k_values_to_test[np.argmax(mean_cv_scores)]  # K with highest mean CV accuracy
best_cv_accuracy = max(mean_cv_scores)

# --- Results ---
print("=== KNN on Wine Dataset (178 samples, 13 features, 3 classes) ===")
print(f"\nTest Accuracy WITHOUT scaling  : {unscaled_accuracy:.2%}")
print(f"Test Accuracy WITH scaling     : {scaled_accuracy:.2%}")
print(f"\nBest K found via cross-val     : K = {best_k}")
print(f"Best CV accuracy at K={best_k}     : {best_cv_accuracy:.2%}")

# Retrain with best K on full training set, evaluate on held-out test set
best_pipeline = Pipeline(steps=[
    ('scaler', StandardScaler()),
    ('knn',    KNeighborsClassifier(n_neighbors=best_k))
])
best_pipeline.fit(X_train, y_train)
final_test_accuracy = best_pipeline.score(X_test, y_test)
print(f"Final test accuracy at K={best_k}    : {final_test_accuracy:.2%}")

# --- Save the K vs accuracy plot ---
plt.figure(figsize=(10, 5))
plt.plot(list(k_values_to_test), mean_cv_scores, marker='o', color='steelblue', linewidth=2)
plt.axvline(x=best_k, color='crimson', linestyle='--', label=f'Best K = {best_k}')
plt.xlabel('K (Number of Neighbours)')
plt.ylabel('Mean CV Accuracy')
plt.title('KNN: Cross-Validation Accuracy vs K (Wine Dataset)')
plt.legend()
plt.tight_layout()
plt.savefig('knn_k_selection.png')
print("\nPlot saved as knn_k_selection.png")

import numpy as np
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
from sklearn.metrics import classification_report

# --- Simulate an imbalanced medical dataset ---
# 2000 patients: 90% healthy (class 0), 10% at-risk (class 1)
patient_features, patient_labels = make_classification(
    n_samples=2000,
    n_features=8,
    n_informative=5,
    n_redundant=2,
    weights=[0.90, 0.10],  # 90/10 class imbalance
    random_state=42
)

X_train, X_test, y_train, y_test = train_test_split(
    patient_features, patient_labels,
    test_size=0.3,
    random_state=42,
    stratify=patient_labels
)

# --- Option A: Uniform voting — every neighbour has equal say ---
uniform_pipeline = Pipeline([
    ('scaler', StandardScaler()),
    ('knn', KNeighborsClassifier(n_neighbors=9, weights='uniform'))
])
uniform_pipeline.fit(X_train, y_train)
uniform_predictions = uniform_pipeline.predict(X_test)

# --- Option B: Distance-weighted voting — closer neighbours shout louder ---
# A neighbour at distance 0.5 has 4x more influence than one at distance 1.0
# This naturally reduces the dominance of majority-class outliers
distance_pipeline = Pipeline([
    ('scaler', StandardScaler()),
    ('knn', KNeighborsClassifier(n_neighbors=9, weights='distance'))
])
distance_pipeline.fit(X_train, y_train)
distance_predictions = distance_pipeline.predict(X_test)

# --- Compare results — pay attention to recall for class 1 (the at-risk minority) ---
print("=== UNIFORM VOTING (weights='uniform') ===")
print(classification_report(y_test, uniform_predictions,
                             target_names=['Healthy', 'At-Risk']))

print("=== DISTANCE-WEIGHTED VOTING (weights='distance') ===")
print(classification_report(y_test, distance_predictions,
                             target_names=['Healthy', 'At-Risk']))

# --- Show the actual distribution of the test set ---
unique, counts = np.unique(y_test, return_counts=True)
print("Test set class distribution:")
for label, count in zip(['Healthy', 'At-Risk'], counts):
    print(f"  {label}: {count} patients ({count/len(y_test)*100:.1f}%)")

import numpy as np
import matplotlib.pyplot as plt

# --- Demonstrate how distances become uniform as dimensions increase ---
np.random.seed(42)

# Generate random points in increasing dimensions
num_points = 1000
dimensions = [2, 5, 10, 20, 50, 100]
ratio_list = []

for D in dimensions:
    # Random points in [0, 1]^D
    points = np.random.rand(num_points, D)
    # Pick a query point also uniform random
    query = np.random.rand(D)
    # Compute Euclidean distances
    dists = np.linalg.norm(points - query, axis=1)
    nearest = np.min(dists)
    farthest = np.max(dists)
    ratio = nearest / farthest
    ratio_list.append(ratio)
    print(f"Dimensions: {D:3d} -> nearest/farthest ratio: {ratio:.4f}")

# Plot
plt.figure(figsize=(8,5))
plt.plot(dimensions, ratio_list, marker='o', color='darkred', linewidth=2)
plt.xlabel('Number of Dimensions')
plt.ylabel('Nearest / Farthest Distance Ratio')
plt.title('Curse of Dimensionality: Nearest Neighbour Becomes Meaningless')
plt.axhline(y=0.95, color='gray', linestyle='--', label='near-uniform threshold')
plt.legend()
plt.tight_layout()
plt.savefig('curse_of_dimensionality.png')
print("\nPlot saved as curse_of_dimensionality.png")

import numpy as np
import time
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets._samples_generator import make_blobs

# --- Generate larger dataset: 50k samples, 10 features, 5 classes ---
N = 50000
D = 10
X, y = make_blobs(n_samples=N, n_features=D, centers=5, random_state=42)

# --- Brute-force KNN ---
knn_brute = KNeighborsClassifier(n_neighbors=5, algorithm='brute')
knn_brute.fit(X, y)

# Time brute force on a single query
query = X[0].reshape(1, -1)
start = time.perf_counter()
for _ in range(100):
    pred = knn_brute.predict(query)
brute_time = (time.perf_counter() - start) / 100
print(f"Brute-force KNN: {brute_time*1000:.2f} ms per query")

# --- KD-tree KNN ---
knn_kd = KNeighborsClassifier(n_neighbors=5, algorithm='kd_tree', leaf_size=30)
knn_kd.fit(X, y)
start = time.perf_counter()
for _ in range(100):
    pred = knn_kd.predict(query)
kd_time = (time.perf_counter() - start) / 100
print(f"KD-tree KNN:      {kd_time*1000:.2f} ms per query")

# --- If you had FAISS installed, you'd get even faster: ---
# faiss.IndexFlatL2(D) then search
print("\nWith FAISS (approximate), expect 0.1-0.5 ms per query at 95% recall.")
print("For production with >1M vectors, ANN is the only viable path.")