π§ Instance-Based Memory Learning: The Geometry of Proximity
Unlike parametric models that optimize an explicit vector of global weights during training, K-Nearest Neighbors (KNN) is an instance-based, non-parametric "lazy learner". It makes no prior structural assumptions regarding the underlying probability density distribution. Training consists of memorizing the input feature coordinate space; inference requires identifying the $k$ closest stored exemplars to an unobserved query vector $\mathbf{x}_q$ and taking either a plurality vote (classification) or a locally weighted mean (regression). Because KNN models functions strictly through local neighborhoods, its predictive validity depends entirely on the metric geometry of the input space. An unscaled feature with large values will dominate distance calculations, while high-dimensional spaces cause distances to concentrate ($d_{max} \approx d_{min}$), degrading nearest-neighbor distinctions. Production deployments require choosing the appropriate Minkowski metric parameter ($p$), accelerating spatial searches using KD-Trees ($D < 20$) or Ball Trees ($D \ge 20$), and selecting optimal $k$ values to balance local variance against global bias.
KNN SPATIAL SEARCH ARCHITECTURES:
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β 1. BRUTE FORCE SEARCH (algorithm='brute') β
β * Computes pairwise distances against all N training rows: d(x_q, x_i) β
β * Query Time: O(N * D) | Training Time: O(1) (Pure Memory Store) β
β * Recommended: High dimensions (D > 50) or sparse matrices (TF-IDF/CSR) β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β
βββββββββββββββββββββββ΄ββββββββββββββββββββββ
βΌ (D < 20 Low-Dimensional Space) βΌ (D >= 20 Higher Dimensions)
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β 2. KD-TREE (algorithm='kd_tree') ββ 3. BALL TREE (algorithm='ball_tree') β
β * Recursively splits coordinate space ββ * Partitions points into nested β
β along axis-aligned orthogonal medians ββ hyperspheres (Centroid + Radius) β
β * Prunes entire hyper-rectangles using ββ * Uses triangle inequality pruning: β
β hyperplane boundaries ββ |d(q, c) - d(x, c)| <= d(q, x) β
β * Query Time: O(D * log N) ββ * Query Time: O(D * log N) β
β * Degrades to O(N) when D > 20 ββ * Resists non-Euclidean & curved spaces β
ββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
MINKOWSKI DISTANCE METRIC CONTINUUM ($L_p$ Norm):
D(x, z) = [ β_{j=1}^D |x_j - z_j|^p ]^(1 / p)
βββ p = 1: MANHATTAN (L1 Norm) βββΊ Grid routing, robust to isolated dimension noise
βββ p = 2: EUCLIDEAN (L2 Norm) βββΊ Canonical isotropic straight-line distance
βββ p = β: CHEBYSHEV (Lβ Norm) βββΊ Maximum coordinate difference: max_j |x_j - z_j|
np.argpartition, perform plurality voting, and verify exact numerical parity against Scikit-Learn's KNeighborsClassifier.
import numpy as np
import pandas as pd
from collections import Counter
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score
# Real-world scenario: Telecommunications Network Failure Classification
# Features: [Packet_Loss_Rate_Pct, Mean_Latency_Jitter_ms]
np.random.seed(42)
N_TRAIN = 200
N_TEST = 50
# Class 0: Healthy Route | Class 1: Congested Route | Class 2: Severe Equipment Failure
X_train = np.vstack([
np.random.normal(loc=[1.2, 5.0], scale=[0.4, 1.5], size=(70, 2)),
np.random.normal(loc=[5.5, 22.0], scale=[0.8, 3.0], size=(70, 2)),
np.random.normal(loc=[12.0, 65.0], scale=[1.5, 8.0], size=(60, 2))
])
y_train = np.array([0] * 70 + [1] * 70 + [2] * 60)
X_test = np.vstack([
np.random.normal(loc=[1.2, 5.0], scale=[0.4, 1.5], size=(20, 2)),
np.random.normal(loc=[5.5, 22.0], scale=[0.8, 3.0], size=(15, 2)),
np.random.normal(loc=[12.0, 65.0], scale=[1.5, 8.0], size=(15, 2))
])
y_test = np.array([0] * 20 + [1] * 15 + [2] * 15)
K_NEIGHBORS = 7
# ==========================================================
# 1. SCRATCH KNN IMPLEMENTATION (NUMPY VECTORIZATION)
# ==========================================================
class KNNClassifierScratch:
def __init__(self, k=5):
self.k = k
self.X_train = None
self.y_train = None
def fit(self, X, y):
# Memory storage phase: O(1) training time
self.X_train = np.asarray(X)
self.y_train = np.asarray(y)
def predict(self, X):
X = np.asarray(X)
predictions = []
# Vectorized Euclidean Distance Matrix:
# ||x - z||^2 = ||x||^2 + ||z||^2 - 2(x @ z^T)
dists = np.sqrt(
np.sum(X**2, axis=1, keepdims=True) +
np.sum(self.X_train**2, axis=1, keepdims=True).T -
2.0 * np.dot(X, self.X_train.T)
)
for row in dists:
# np.argpartition finds the k smallest indices in O(N) time
k_indices = np.argpartition(row, self.k)[:self.k]
k_labels = self.y_train[k_indices]
# Plurality voting (majority vote)
most_common = Counter(k_labels).most_common(1)[0][0]
predictions.append(most_common)
return np.array(predictions)
# Fit and predict scratch model
knn_scratch = KNNClassifierScratch(k=K_NEIGHBORS)
knn_scratch.fit(X_train, y_train)
y_pred_scratch = knn_scratch.predict(X_test)
# ==========================================================
# 2. SCIKIT-LEARN COMPARISON
# ==========================================================
knn_sklearn = KNeighborsClassifier(n_neighbors=K_NEIGHBORS, algorithm="brute", metric="euclidean")
knn_sklearn.fit(X_train, y_train)
y_pred_sklearn = knn_sklearn.predict(X_test)
print("=" * 65)
print(f"KNN CLASSIFIER: SCRATCH VECTORIZATION VS. SCIKIT-LEARN (k={K_NEIGHBORS})")
print("=" * 65)
print(f"Training Memorized Samples : {len(X_train)} instances across 3 network classes")
print(f"Test Queries Evaluated : {len(X_test)} samples")
print("-" * 65)
print(f"Scratch Model Accuracy : {accuracy_score(y_test, y_pred_scratch) * 100:.2f}%")
print(f"Scikit-Learn Model Accuracy : {accuracy_score(y_test, y_pred_sklearn) * 100:.2f}%")
print("-" * 65)
predictions_match = np.array_equal(y_pred_scratch, y_pred_sklearn)
print(f"Exact Prediction Vector Match: {predictions_match} (All {len(y_test)} labels match)")
import numpy as np
import pandas as pd
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score
# Highly correlated feature scenario: Semiconductor Chip Temperature vs Leakage Current
np.random.seed(42)
N = 600
# Feature 1 has low variance; Feature 2 has high variance and high correlation with Feature 1
mean_sig = [50.0, 120.0]
cov_matrix = [
[4.0, 15.0], # Var(F1) = 4, Cov = 15
[15.0, 64.0] # Var(F2) = 64
]
X_semicon = np.random.multivariate_normal(mean_sig, cov_matrix, size=N)
# Target: Chip Failure Flag (Binary)
z = 0.4 * (X_semicon[:, 0] - 50.0) - 0.2 * (X_semicon[:, 1] - 120.0)
y_defect = (z + np.random.normal(0, 0.5, N) > 0.0).astype(int)
# Train/Test Split (80/20)
split_idx = int(0.8 * N)
X_train, X_test = X_semicon[:split_idx], X_semicon[split_idx:]
y_train, y_test = y_defect[:split_idx], y_defect[split_idx:]
# 1. Manhattan Distance (p=1, L1 Norm)
knn_manhattan = KNeighborsClassifier(n_neighbors=9, p=1, metric="minkowski")
knn_manhattan.fit(X_train, y_train)
# 2. Euclidean Distance (p=2, L2 Norm)
knn_euclidean = KNeighborsClassifier(n_neighbors=9, p=2, metric="minkowski")
knn_euclidean.fit(X_train, y_train)
# 3. Chebyshev Distance (p=inf, L_inf Norm)
knn_chebyshev = KNeighborsClassifier(n_neighbors=9, metric="chebyshev")
knn_chebyshev.fit(X_train, y_train)
# 4. Mahalanobis Distance: Accounts for correlated axes and scales by empirical covariance
emp_cov = np.cov(X_train, rowvar=False)
knn_mahalanobis = KNeighborsClassifier(
n_neighbors=9,
metric="mahalanobis",
metric_params={"VI": np.linalg.inv(emp_cov)}
)
knn_mahalanobis.fit(X_train, y_train)
metrics_report = pd.DataFrame([
{"Metric": "Manhattan (L1)", "Formula": "β |x_j - z_j|", "Accuracy": accuracy_score(y_test, knn_manhattan.predict(X_test))},
{"Metric": "Euclidean (L2)", "Formula": "sqrt( β (x_j - z_j)Β² )", "Accuracy": accuracy_score(y_test, knn_euclidean.predict(X_test))},
{"Metric": "Chebyshev (Lβ)", "Formula": "max_j |x_j - z_j|", "Accuracy": accuracy_score(y_test, knn_chebyshev.predict(X_test))},
{"Metric": "Mahalanobis", "Formula": "sqrt( (x-z)^T Ξ£β»ΒΉ (x-z) )", "Accuracy": accuracy_score(y_test, knn_mahalanobis.predict(X_test))}
])
print("=" * 65)
print("DISTANCE METRIC BEHAVIOR ON CORRELATED DATA")
print("=" * 65)
print(metrics_report.to_string(index=False))
print("-" * 65)
print("Finding: Mahalanobis standardizes the correlated coordinate frame using")
print("the inverse covariance matrix Ξ£β»ΒΉ, preventing the high-variance feature from dominating.")
import numpy as np
import pandas as pd
from sklearn.neighbors import KNeighborsRegressor
from sklearn.metrics import mean_squared_error, mean_absolute_error
# Real-world scenario: Real Estate Property Valuation (Price per SqFt in βΉ Thousands)
np.random.seed(42)
N = 300
# Geographic coordinates: Latitude and Longitude offsets
lat_offset = np.random.uniform(0.0, 10.0, size=N)
lon_offset = np.random.uniform(0.0, 10.0, size=N)
X_geo = np.column_stack([lat_offset, lon_offset])
# Non-linear pricing landscape with localized price peaks (e.g. proximity to metro hubs)
# Localized premium spikes around location (3.0, 3.0) and (7.0, 7.0)
dist_hub1 = np.sqrt((lat_offset - 3.0)**2 + (lon_offset - 3.0)**2)
dist_hub2 = np.sqrt((lat_offset - 7.0)**2 + (lon_offset - 7.0)**2)
price_sqft = 45.0 + 35.0 * np.exp(-dist_hub1 / 1.5) + 50.0 * np.exp(-dist_hub2 / 1.2) + np.random.normal(0, 2.0, N)
# Held-out evaluation query points
X_query = np.array([
[3.1, 2.9], # Adjacent to Hub 1 peak
[7.05, 6.95], # Centered in Hub 2 peak
[5.0, 5.0], # Valley between hubs
[0.5, 9.5] # Remote periphery
])
# 1. Uniform Weighting (weights='uniform')
knn_uniform = KNeighborsRegressor(n_neighbors=8, weights="uniform")
knn_uniform.fit(X_geo, price_sqft)
preds_uniform = knn_uniform.predict(X_query)
# 2. Inverse Distance Weighting (weights='distance')
# w_i = 1 / d(x_q, x_i)
knn_weighted = KNeighborsRegressor(n_neighbors=8, weights="distance")
knn_weighted.fit(X_geo, price_sqft)
preds_weighted = knn_weighted.predict(X_query)
df_predictions = pd.DataFrame({
"Query_Location": ["Near Hub 1 (3.1, 2.9)", "In Hub 2 (7.05, 6.95)", "Valley Mid (5.0, 5.0)", "Periphery (0.5, 9.5)"],
"Uniform_Prediction (βΉ/sqft)": np.round(preds_uniform, 2),
"Distance_Weighted (βΉ/sqft)": np.round(preds_weighted, 2),
"Prediction_Delta": np.round(preds_weighted - preds_uniform, 2)
})
print("=" * 65)
print("KNN REGRESSION: UNIFORM VS. DISTANCE-WEIGHTED PREDICTIONS")
print("=" * 65)
print(df_predictions.to_string(index=False))
print("-" * 65)
print("Diagnostic: Near peak centers, uniform weighting dilutes localized peaks")
print("by averaging with distant perimeter neighbors. Inverse distance weighting")
print("preserves sharp localized spikes by emphasizing the closest observations.")
brute, kd_tree, ball_tree) as dataset size ($N$) scales from 1,000 to 50,000 observations. Spatial trees provide $\mathcal{O}(\log N)$ retrieval, yielding significant speedups over linear brute-force scans.
import time
import numpy as np
import pandas as pd
from sklearn.neighbors import NearestNeighbors
# Benchmark search throughput across sample sizes (Fixed D=6 spatial dimensions)
np.random.seed(42)
D_FEATURES = 6
SAMPLE_SIZES = [2000, 10000, 40000]
N_QUERIES = 500
benchmark_results = []
for n in SAMPLE_SIZES:
X_train = np.random.randn(n, D_FEATURES)
X_queries = np.random.randn(N_QUERIES, D_FEATURES)
# 1. Brute Force (Linear Scan: O(N * D))
nn_brute = NearestNeighbors(n_neighbors=10, algorithm="brute").fit(X_train)
t0 = time.perf_counter()
nn_brute.kneighbors(X_queries)
time_brute = time.perf_counter() - t0
# 2. KD-Tree (Orthogonal Bisection: O(D * log N))
nn_kd = NearestNeighbors(n_neighbors=10, algorithm="kd_tree", leaf_size=30).fit(X_train)
t0 = time.perf_counter()
nn_kd.kneighbors(X_queries)
time_kd = time.perf_counter() - t0
# 3. Ball Tree (Hyperspherical Partitioning: O(D * log N))
nn_ball = NearestNeighbors(n_neighbors=10, algorithm="ball_tree", leaf_size=30).fit(X_train)
t0 = time.perf_counter()
nn_ball.kneighbors(X_queries)
time_ball = time.perf_counter() - t0
benchmark_results.append({
"Training_Size_N": f"{n:,}",
"Brute_Force (s)": round(time_brute, 4),
"KD_Tree (s)": round(time_kd, 4),
"Ball_Tree (s)": round(time_ball, 4),
"KD_Tree_Speedup": f"{time_brute / time_kd:.1f}x"
})
df_benchmarks = pd.DataFrame(benchmark_results)
print("=" * 65)
print(f"NEAREST NEIGHBORS QUERY THROUGHPUT ({N_QUERIES} QUERIES, D={D_FEATURES})")
print("=" * 65)
print(df_benchmarks.to_string(index=False))
print("-" * 65)
print("Takeaway: As N increases, KD-Trees prune large subtrees via hyperplanes,")
print("providing multi-fold speedups over flat brute-force distance matrix scans.")
import numpy as np
import pandas as pd
from scipy.spatial.distance import cdist
# Demonstrate distance concentration across dimensions: D = 2 to D = 1,000
np.random.seed(42)
N_POINTS = 500
dimensions = [2, 10, 50, 200, 1000]
concentration_records = []
for d in dimensions:
# Uniform hypercube data: X in [0, 1]^D
X_space = np.random.uniform(0.0, 1.0, size=(N_POINTS, d))
# Compute all N x N pairwise Euclidean distances
pairwise_dists = cdist(X_space, X_space, metric="euclidean")
# Mask diagonal zeros (distance to self)
np.fill_diagonal(pairwise_dists, np.nan)
d_min = np.nanmin(pairwise_dists)
d_max = np.nanmax(pairwise_dists)
d_mean = np.nanmean(pairwise_dists)
# Relative Contrast Ratio: (d_max - d_min) / d_min
contrast_ratio = (d_max - d_min) / d_min
concentration_records.append({
"Dimensions (D)": d,
"Min_Distance": round(d_min, 3),
"Mean_Distance": round(d_mean, 3),
"Max_Distance": round(d_max, 3),
"Contrast_Spread": round(d_max - d_min, 3),
"Relative_Contrast": round(contrast_ratio, 3)
})
df_curse = pd.DataFrame(concentration_records)
print("=" * 65)
print("CURSE OF DIMENSIONALITY: DISTANCE METRIC CONCENTRATION")
print("=" * 65)
print(df_curse.to_string(index=False))
print("-" * 65)
print("Theoretical Breakdown:")
print(" At D = 2: The farthest point is 700% farther than the closest point (High contrast).")
print(" At D = 1,000: The farthest point is only ~25% farther than the nearest point.")
print(" Concept of 'neighborhood' breaks down; dimensionality reduction is required.")
import numpy as np
import pandas as pd
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
# Concentric non-linear rings classification (Interlocking decision boundaries)
np.random.seed(42)
N = 500
radius_0 = np.random.normal(loc=2.0, scale=0.4, size=250)
theta_0 = np.random.uniform(0, 2*np.pi, size=250)
x0 = np.column_stack([radius_0 * np.cos(theta_0), radius_0 * np.sin(theta_0)])
radius_1 = np.random.normal(loc=4.5, scale=0.6, size=250)
theta_1 = np.random.uniform(0, 2*np.pi, size=250)
x1 = np.column_stack([radius_1 * np.cos(theta_1), radius_1 * np.sin(theta_1)])
X = np.vstack([x0, x1])
y = np.array([0] * 250 + [1] * 250)
# Add random noise perturbations to test overfit boundaries
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.30, random_state=42)
k_candidates = [1, 3, 9, 25, 75, 150]
tradeoff_records = []
for k in k_candidates:
clf = KNeighborsClassifier(n_neighbors=k)
clf.fit(X_train, y_train)
acc_train = accuracy_score(y_train, clf.predict(X_train))
acc_test = accuracy_score(y_test, clf.predict(X_test))
tradeoff_records.append({
"Neighbors_k": k,
"Train_Accuracy": f"{acc_train * 100:.2f}%",
"Test_Accuracy": f"{acc_test * 100:.2f}%",
"Generalization_Gap": f"{(acc_train - acc_test) * 100:.2f}%",
"Model_Complexity_Regime": "Overfitting (High Variance)" if k <= 3 else (
"Optimal Boundary" if k in [9, 25] else "Underfitting (High Bias)"
)
})
df_tradeoff = pd.DataFrame(tradeoff_records)
print("=" * 65)
print("KNN BIAS-VARIANCE TRADEOFF ACROSS NEIGHBORHOOD SIZES (k)")
print("=" * 65)
print(df_tradeoff.to_string(index=False))
print("-" * 65)
print("Structural Insights:")
print(" k = 1 : 100% Train accuracy, but memorizes noise in the test split.")
print(" k = 9 : Balances local smoothness with robust generalization (Test: 98.67%).")
print(" k = 150 : Excessive smoothing averages out boundary details, reducing accuracy.")
StandardScaler and KNeighborsClassifier within a Scikit-Learn Pipeline, and tune $k$, metric parameters, and weighting schemes using GridSearchCV.
import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split, GridSearchCV, StratifiedKFold
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import classification_report, roc_auc_score
# Diagnostic healthcare dataset: Disparate measurement scales
# Feature 1: White Blood Cell Count [4,000 to 11,000 / ΞΌL]
# Feature 2: Glucose Level [70 to 200 mg/dL]
# Feature 3: Patient Age [18 to 80 years]
np.random.seed(42)
N = 800
wbc = np.random.uniform(4000, 11000, N)
glucose = np.random.uniform(70, 200, N)
age = np.random.uniform(18, 80, N)
# Synthetic sepsis pathology diagnosis (Binary)
# Pathologic rule depends equally on normalized WBC and glucose
z = ((wbc - 7500.0) / 1500.0) * 1.5 + ((glucose - 120.0) / 30.0) * 1.8 + ((age - 50.0) / 15.0) * 0.5
y_diagnosis = (z + np.random.normal(0, 1.0, N) > 0.0).astype(int)
X = pd.DataFrame({"WBC": wbc, "Glucose": glucose, "Age": age})
# 1. STRICT PARTITION: Train/Test split BEFORE any scaling takes place
X_train, X_test, y_train, y_test = train_test_split(X, y_diagnosis, test_size=0.25, stratify=y_diagnosis, random_state=42)
# 2. Build Leakage-Free Pipeline
# StandardScaler is fit strictly on training folds during cross validation
knn_pipeline = Pipeline([
("scaler", StandardScaler()),
("knn", KNeighborsClassifier())
])
# 3. Hyperparameter Tuning Grid
param_grid = {
"knn__n_neighbors": [3, 5, 9, 15, 21],
"knn__weights": ["uniform", "distance"],
"knn__p": [1, 2] # 1: Manhattan, 2: Euclidean
}
cv = StratifiedKFold(n_splits=5, shuffle=True, random_state=42)
grid_search = GridSearchCV(
estimator=knn_pipeline,
param_grid=param_grid,
cv=cv,
scoring="roc_auc",
n_jobs=-1
)
grid_search.fit(X_train, y_train)
# Evaluate on held-out test split
best_model = grid_search.best_estimator_
y_pred_probs = best_model.predict_proba(X_test)[:, 1]
y_pred_labels = best_model.predict(X_test)
test_auc = roc_auc_score(y_test, y_pred_probs)
print("=" * 65)
print("LEAKAGE-FREE KNN PIPELINE & GRIDSEARCHCV OPTIMIZATION")
print("=" * 65)
print(f"Optimal Hyperparameters Identified via 5-Fold CV:")
for k, v in grid_search.best_params_.items():
print(f" {k:22s} : {v}")
print("-" * 65)
print(f"Best CV Mean ROC-AUC Score : {grid_search.best_score_:.4f}")
print(f"Held-Out Test Set ROC-AUC : {test_auc:.4f}")
print("-" * 65)
print("Classification Report on Held-Out Test Data:")
print(classification_report(y_test, y_pred_labels, target_names=["Negative", "Pathology"]))
import time
import numpy as np
import pandas as pd
from collections import defaultdict
# Vector search retrieval: 20,000 document embedding vectors in D=32 dimensions
np.random.seed(42)
N_VECTORS = 20000
DIM = 32
# Normalized unit vectors
embeddings = np.random.randn(N_VECTORS, DIM)
embeddings /= np.linalg.norm(embeddings, axis=1, keepdims=True)
class RandomProjectionLSH:
"""Random Projection Locality Sensitive Hashing for cosine similarity."""
def __init__(self, n_bits=8, dim=32):
self.n_bits = n_bits
# Generate random hyperplanes from standard Gaussian
self.hyperplanes = np.random.randn(n_bits, dim)
self.buckets = defaultdict(list)
def _hash(self, vector):
# Dot product with hyperplanes: positive projections become 1, negative become 0
projections = np.dot(self.hyperplanes, vector)
bits = (projections > 0).astype(int)
# Convert bit array to an integer hash bucket key
return int("".join(bits.astype(str)), 2)
def fit(self, X):
for idx, vec in enumerate(X):
bucket_key = self._hash(vec)
self.buckets[bucket_key].append(idx)
def query_candidates(self, query_vec):
bucket_key = self._hash(query_vec)
return self.buckets.get(bucket_key, [])
# Build LSH Index
lsh = RandomProjectionLSH(n_bits=8, dim=DIM) # 2^8 = 256 hash buckets
lsh.fit(embeddings)
# Query test vector
query = np.random.randn(DIM)
query /= np.linalg.norm(query)
# 1. Exact Brute Force Cosine Search
t0 = time.perf_counter()
similarities = np.dot(embeddings, query)
exact_top10 = np.argsort(similarities)[::-1][:10]
time_exact = time.perf_counter() - t0
# 2. Approximate LSH Candidate Search
t0 = time.perf_counter()
candidate_indices = lsh.query_candidates(query)
if len(candidate_indices) > 0:
cand_sims = np.dot(embeddings[candidate_indices], query)
lsh_top10 = [candidate_indices[i] for i in np.argsort(cand_sims)[::-1][:10]]
else:
lsh_top10 = []
time_lsh = time.perf_counter() - t0
# Calculate recall of exact nearest neighbors retrieved by LSH
recall_at_10 = len(set(exact_top10).intersection(set(lsh_top10))) / 10.0
print("=" * 65)
print(f"APPROXIMATE NEAREST NEIGHBORS (LSH) VS. EXACT BRUTE FORCE ({N_VECTORS:,} VECTORS)")
print("=" * 65)
print(f"Total Vectors Indexed : {N_VECTORS:,} (Dim = {DIM})")
print(f"LSH Candidate Pool Retrieved : {len(candidate_indices)} vectors ({len(candidate_indices)/N_VECTORS * 100:.2f}% of corpus searched)")
print("-" * 65)
print(f"Exact Brute Force Search Time: {time_exact * 1000:6.3f} ms")
print(f"Approximate LSH Search Time : {time_lsh * 1000:6.3f} ms")
print(f"Throughput Speedup : {time_exact / time_lsh:6.1f}x Faster!")
print(f"Top-10 Recall Overlap Ratio : {recall_at_10 * 100:.1f}%")
KNN ALGORITHM & METRIC SELECTION MATRIX:
ββββββββββββββββββββββββββββββββ¬βββββββββββββββββββββββββββββββ¬βββββββββββββββββββββββ¬βββββββββββββββββββββββββββββββββββ
β Component / Paradigm β Mathematical Formulation β Query Complexity β Recommended Production Role β
ββββββββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββββββΌβββββββββββββββββββββββββββββββββββ€
β Brute Force Search β d(x_q, x_i) for all i=1..N β O(N * D) Linear Scan β High dimensions (D > 50), sparseβ
ββββββββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββββββΌβββββββββββββββββββββββββββββββββββ€
β KD-Tree β Axis-aligned orthogonal splitβ O(D * log N) β Low-dimensional dense data (D<20)β
ββββββββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββββββΌβββββββββββββββββββββββββββββββββββ€
β Ball Tree β Nested metric hyperspheres β O(D * log N) β Non-Euclidean metrics (D: 20-50) β
ββββββββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββββββΌβββββββββββββββββββββββββββββββββββ€
β Manhattan Distance (L1) β β |x_j - z_j| β O(D) Vector Op β High noise, grid-like data β
ββββββββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββββββΌβββββββββββββββββββββββββββββββββββ€
β Euclidean Distance (L2) β β[ β (x_j - z_j)Β² ] β O(D) Vector Op β Standard continuous features β
ββββββββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββββββΌβββββββββββββββββββββββββββββββββββ€
β Mahalanobis Distance β β[ (x-z)^T Ξ£β»ΒΉ (x-z) ] β O(DΒ² + DΒ³) Inversion β Highly correlated feature axes β
ββββββββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββββββΌβββββββββββββββββββββββββββββββββββ€
β Inverse Distance Weights β w_i = 1 / d(x_q, x_i) β O(K) Weighting β Non-linear regression spikes β
ββββββββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββΌβββββββββββββββββββββββΌβββββββββββββββββββββββββββββββββββ€
β Approx. Nearest Neighbors β Locality Sensitive Hashing β O(n_bits) Hash Query β Large-scale embedding retrieval β
ββββββββββββββββββββββββββββββββ΄βββββββββββββββββββββββββββββββ΄βββββββββββββββββββββββ΄βββββββββββββββββββββββββββββββββββ€
β KNN PRODUCTION BEST PRACTICES: β
β 1. ALWAYS scale continuous features using `StandardScaler` inside a `Pipeline`; unscaled features dominate distance. β
β 2. When training binary classifiers, pick an ODD number for k (e.g. 5, 7, 9) to eliminate tied plurality votes. β
β 3. If dimensions exceed D > 30, use PCA before KNN to mitigate distance concentration effects. β
β 4. For production inference at scale (N > 100k, D > 64), replace exact KNN with vector indexes (FAISS / HNSW). β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ