Machine Learning Academy · درس

KNN للانحدار وحدود قابلية التوسع

طبّق KNeighborsRegressor على هدف مستمر، ثم قِس زمن التنبؤ على مجموعات بيانات كبيرة لفهم تكلفة الاستدلال في KNN، وهي O(n)

KNN للانحدار وحدود قابلية التوسع درس مجاني في Machine Learning Academy على CoddyKit. هذا هو الدرس 4 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Machine Learning Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Machine Learning Academy 4 دروس في المجموع.

بعض أجزاء هذا الدرس لم تُترجم بعد وتظهر باللغة الإنجليزية.

KNN for Regression: Averaging Neighbors

KNN is not limited to classification — it can also predict continuous values. In KNN regression, the prediction for a new point is the average of the target values of its k nearest neighbors. For example, to predict the price of a house, KNN finds the k most similar houses in the training set and averages their prices. This produces a non-parametric, local regression model that can capture complex patterns without assuming any functional form between features and the target.

import numpy as np

# Training data: house sizes (sqm) -> prices (thousands)
X_train = np.array([[50], [70], [90], [110], [130]])
y_train = np.array([150, 200, 260, 310, 380])

# Query: predict price for 80 sqm house
x_new = np.array([[80]])

# k=3: find 3 nearest neighbors
dists = np.abs(X_train - x_new).flatten()
nearest_idx = np.argsort(dists)[:3]
neighbor_prices = y_train[nearest_idx]

prediction = neighbor_prices.mean()
print('Neighbor prices:', neighbor_prices)
print('KNN regression prediction:', prediction)

KNeighborsRegressor in scikit-learn

Scikit-learn's KNeighborsRegressor implements KNN for continuous targets with the same API as the classifier. It supports the same parameters: n_neighbors, metric, weights, and algorithm. Distance-weighted regression (weights='distance') is often beneficial: closer neighbors contribute more to the predicted value than farther ones, which is especially useful at the edges of the training data distribution where a distant neighbor might introduce significant bias.

from sklearn.neighbors import KNeighborsRegressor
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
from sklearn.datasets import fetch_california_housing
from sklearn.model_selection import train_test_split
from sklearn.metrics import mean_squared_error
import numpy as np

X, y = fetch_california_housing(return_X_y=True)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.2, random_state=42)

pipe = Pipeline([
    ('sc', StandardScaler()),
    ('knn', KNeighborsRegressor(n_neighbors=10, weights='distance'))
])
pipe.fit(X_tr, y_tr)
rmse = mean_squared_error(y_te, pipe.predict(X_te), squared=False)
print('RMSE:', rmse.round(3))

Choosing k for Regression

The same bias-variance logic applies to KNN regression: small k = high variance, wiggly predictions; large k = high bias, over-smoothed predictions. You can visualise this by plotting the predicted function over a 1D input range. With k=1, the prediction line jumps to each training point's exact value. As k increases, the line becomes smoother. The optimal k minimises cross-validated RMSE (or MAE). For regression, there is no tie-breaking concern, so even k values are fine.

from sklearn.neighbors import KNeighborsRegressor
from sklearn.model_selection import cross_val_score
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
import numpy as np

best_k, best_score = 1, float('inf')

for k in range(1, 31):
    pipe = Pipeline([
        ('sc', StandardScaler()),
        ('knn', KNeighborsRegressor(n_neighbors=k))
    ])
    scores = -cross_val_score(pipe, X_tr, y_tr, cv=5, scoring='neg_root_mean_squared_error')
    mean_rmse = scores.mean()
    if mean_rmse < best_score:
        best_score, best_k = mean_rmse, k

print(f'Best k={best_k} with CV RMSE={best_score:.3f}')

KNN Prediction Time: O(N * d) Per Query

Unlike trained parametric models (linear regression, neural networks) that make predictions in O(d) time with stored parameters, KNN must scan all N training points at inference time. Each prediction requires computing distances to every training sample — an O(N * d) operation. For N=1,000,000 and d=100, that is 100 million operations per prediction. At 1 millisecond per operation, a single prediction takes 100 seconds. This makes naive KNN completely unsuitable for real-time production systems with large training sets.

import numpy as np
import time

np.random.seed(42)

for N in [1000, 10000, 100000, 1000000]:
    X_big = np.random.randn(N, 10)
    query = np.random.randn(1, 10)
    
    start = time.time()
    dists = np.linalg.norm(X_big - query, axis=1)
    _ = np.argsort(dists)[:5]
    elapsed = time.time() - start
    
    print(f'N={N:>8}: {elapsed*1000:.1f} ms')
# Prediction time scales linearly with N

Approximate Nearest Neighbors: KD-Tree and Ball Tree

Scikit-learn offers two spatial indexing structures to speed up neighbor searches. A KD-Tree partitions the feature space by recursively splitting along the dimension with the largest variance, allowing O(log N) neighbor searches for low-dimensional data. A Ball Tree partitions data into nested hyperspheres, which is more efficient for high-dimensional or non-Euclidean metric data. Both reduce average prediction time significantly. Set the algorithm parameter in KNeighborsClassifier to 'kd_tree', 'ball_tree', or 'auto' (scikit-learn chooses).

from sklearn.neighbors import KNeighborsClassifier
import time, numpy as np

X = np.random.randn(50000, 5)
y = (X[:, 0] > 0).astype(int)

algorithms = ['brute', 'kd_tree', 'ball_tree']
for alg in algorithms:
    knn = KNeighborsClassifier(n_neighbors=5, algorithm=alg)
    knn.fit(X, y)
    start = time.time()
    knn.predict(X[:100])
    print(f'{alg:10}: {(time.time()-start)*1000:.1f} ms for 100 predictions')

Memory Requirements of KNN

KNN must store the entire training set in memory at all times because predictions require accessing training samples. For N=1 million samples with d=100 float64 features, the data matrix alone requires 800 MB of RAM. At N=10 million, that is 8 GB — too much for many deployment environments. Parametric models like linear regression or neural networks compress N samples into a fixed number of parameters, making them far more memory-efficient at inference time. KNN's memory cost is O(N * d) regardless of problem complexity.

import numpy as np

def memory_mb(N, d, dtype=np.float64):
    bytes_per_value = np.dtype(dtype).itemsize
    total_bytes = N * d * bytes_per_value
    return total_bytes / (1024**2)

for N in [1000, 10000, 100000, 1000000]:
    mb = memory_mb(N, d=100)
    print(f'N={N:>8}, d=100: {mb:.1f} MB')

# 1,000:      0.8 MB (fine)
# 1,000,000: 762.9 MB (borderline)
# A linear model: same O(d) parameters regardless of N

FAISS: Approximate Nearest Neighbors at Scale

For large-scale production use cases, Approximate Nearest Neighbor (ANN) libraries dramatically reduce search time at the cost of occasionally missing the true nearest neighbor. FAISS (Facebook AI Similarity Search) can query a billion vectors in milliseconds using GPU-accelerated index structures. Annoy (Spotify) builds a forest of random projection trees for approximate searches. HNSW (Hierarchical Navigable Small World) graphs achieve sub-millisecond queries. These libraries are used in recommendation systems and semantic search at production scale.

# Conceptual FAISS usage (requires: pip install faiss-cpu)
import numpy as np

# import faiss  # not available in standard envs

# Conceptual workflow:
# N = 1_000_000  # 1 million vectors
# d = 128        # dimensionality

# X = np.random.randn(N, d).astype('float32')
# index = faiss.IndexFlatL2(d)   # Exact L2 search
# index.add(X)                   # Index all vectors

# Query 10 vectors
# query = np.random.randn(10, d).astype('float32')
# distances, indices = index.search(query, k=5)
# print(indices.shape)  # (10, 5)

When KNN Is Practical vs When to Use Alternatives

KNN is practical when: N < 100,000, predictions are batch (not real-time), and interpretability is needed (you can show the actual similar examples). KNN struggles when: N is very large, real-time predictions are needed (<100ms latency), or the feature space is high-dimensional (>50 features). Better alternatives for large N: Random Forests and Gradient Boosting for tabular data; neural networks for images and text. KNN remains valuable as a strong baseline for recommendation systems and anomaly detection when the dataset fits comfortably in memory.

# Decision guide: KNN vs alternatives

def should_use_knn(N, d, latency_ms_required):
    if N > 500_000:
        return 'Too large for KNN -- use Random Forest or XGBoost'
    elif d > 50:
        return 'Too high-dimensional -- apply PCA first or use tree models'
    elif latency_ms_required < 50:
        return 'Too strict latency -- use parametric model'
    else:
        return 'KNN is suitable as a baseline'

print(should_use_knn(10000, 10, 500))   # KNN is suitable
print(should_use_knn(1000000, 10, 500)) # Too large
print(should_use_knn(10000, 100, 500))  # Too high-dimensional

Profiling KNN vs Linear Regression

Comparing KNN and linear regression on the same regression task reveals the scalability trade-off. Linear regression fits in seconds regardless of N (O(N*d^2) training but O(d) prediction). KNN training is instantaneous (no computation) but prediction scales with N. This makes KNN a deferred computation model — it pays all costs at prediction time. For a one-time batch prediction job on 100k rows, KNN may be acceptable. For an API serving 1000 requests per second, linear regression or a neural network is orders of magnitude faster.

import numpy as np
import time
from sklearn.neighbors import KNeighborsRegressor
from sklearn.linear_model import LinearRegression

X = np.random.randn(50000, 10)
y = X[:, 0] * 3 + np.random.randn(50000)
X_test = np.random.randn(1000, 10)

knn = KNeighborsRegressor(n_neighbors=5)
lr  = LinearRegression()

knn.fit(X, y); lr.fit(X, y)

for name, model in [('KNN', knn), ('LinearReg', lr)]:
    t0 = time.time()
    model.predict(X_test)
    dt = (time.time() - t0) * 1000
    print(f'{name}: {dt:.1f} ms for 1000 predictions')

Using KNN Outputs in Pipelines

Even when KNN is too slow for direct production use, its output distances can serve as informative features for other models. For example, computing the average distance to the k nearest training neighbors for each test point creates a single feature that measures how unusual the point is. Unusual points (far from their neighbors) are potential anomalies. This pattern — using KNN as a feature extractor rather than a final predictor — lets you leverage nearest-neighbor information inside fast ensemble models.

from sklearn.neighbors import KNeighborsClassifier
import numpy as np

X_train = np.random.randn(500, 10)
y_train = (X_train[:, 0] > 0).astype(int)
X_test  = np.random.randn(50, 10)

knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train, y_train)

# Extract neighbor distances as an anomaly score
dists, _ = knn.kneighbors(X_test)
avg_dist = dists.mean(axis=1)

print('Average neighbor distances (anomaly score):')
print(avg_dist.round(2))
# High values indicate potential anomalies

Dimensionality Reduction Before KNN

To make KNN practical on high-dimensional data, apply PCA before the KNeighborsRegressor to reduce dimensionality while preserving the most variance. This addresses two problems simultaneously: it reduces prediction time (fewer dimensions = faster distance computation) and mitigates the curse of dimensionality (distances become more meaningful in lower-dimensional space). PCA + KNN inside a single Pipeline keeps the preprocessing leak-free during cross-validation.

from sklearn.pipeline import Pipeline
from sklearn.decomposition import PCA
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsRegressor
from sklearn.model_selection import cross_val_score
import numpy as np

X_high_d = np.random.randn(1000, 100)  # 100 features
y = X_high_d[:, :5].sum(axis=1)       # Only first 5 matter

pipe = Pipeline([
    ('sc', StandardScaler()),
    ('pca', PCA(n_components=10)),      # Reduce to 10 components
    ('knn', KNeighborsRegressor(n_neighbors=5))
])

scores = -cross_val_score(pipe, X_high_d, y, cv=5,
                          scoring='neg_root_mean_squared_error')
print('CV RMSE with PCA:', scores.mean().round(3))

Quick Check

Test your understanding of Machine Learning with Python concepts from this lesson.

Lesson Recap

In this lesson you learned: how KNN regression predicts continuous targets by averaging neighbor values, the critical O(N * d) prediction cost that limits KNN scalability, and how KD-Tree, Ball Tree, and FAISS speed up neighbor search for larger datasets. Next up we explore Decision Trees — a fundamentally different approach that learns explicit rules through recursive data partitioning.

الأسئلة الشائعة

هل درس «KNN للانحدار وحدود قابلية التوسع» مجاني؟

نعم — نص درس «KNN للانحدار وحدود قابلية التوسع» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Machine Learning Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Machine Learning Academy 4 دروس في المجموع.

ماذا ستتعلم في «KNN للانحدار وحدود قابلية التوسع»؟

طبّق KNeighborsRegressor على هدف مستمر، ثم قِس زمن التنبؤ على مجموعات بيانات كبيرة لفهم تكلفة الاستدلال في KNN، وهي O(n) تتمرن على Machine Learning Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.

هل أحتاج إلى خبرة سابقة لأبدأ Machine Learning Academy؟

لا تُشترط خبرة سابقة. Machine Learning Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 4 من أصل 4.

كم من الوقت يستغرق درس «KNN للانحدار وحدود قابلية التوسع»؟

معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.

هل يمكنني كتابة وتشغيل أكواد في درس Machine Learning Academy هذا؟

نعم. كل درس في Machine Learning Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.

جميع الدروس في هذه الدورة

كيفية عمل KNN: المسافة والجيران والتصويت
اختيار k: طريقة الكوع ومنحنيات التحقق
مقاييس المسافة: الإقليدية ومانهاتن ومينكوفسكي
KNN للانحدار وحدود قابلية التوسع

← العودة إلى Machine Learning Academy