Bài 27: K-Nearest Neighbors (KNN) — phân loại theo láng giềng

K-Nearest Neighbors (KNN) là một classifier non-parametric, instance-based. Hai tính từ này định hình toàn bộ cách model hoạt động:

• Non-parametric — không giả định dạng hàm cố định cho mối quan hệ giữa feature và label (Logistic Regression giả định decision boundary tuyến tính, Linear Regression giả định quan hệ tuyến tính — KNN không giả định gì). Số "tham số" mà model lưu tăng theo kích thước train set, không phải hằng số.
• Instance-based — model không "học" ra tập weight; nó nhớ toàn bộ train set và quyết định mỗi query bằng cách so sánh trực tiếp với các điểm đã nhớ.

Quy tắc dự đoán cực ngắn: với một điểm query \( \mathbf{x} \), tìm \( K \) điểm gần nhất trong train set theo một distance metric, rồi:

• Classification: vote majority — class nào chiếm đa số trong \( K \) láng giềng thì \( \mathbf{x} \) thuộc class đó.
• Regression: trung bình target của \( K \) láng giềng.

Triết lý nền tảng có thể tóm bằng câu quen thuộc: "bạn là trung bình của 5 người thân nhất". KNN dùng đúng nguyên lý đó — một điểm sẽ giống các điểm xung quanh nó trong không gian feature.

KNN được xếp vào nhóm lazy learning (học lười). Hai đặc tính phân biệt với eager learning (Logistic Regression, Decision Tree, Neural Network):

• Train gần như rỗng — gọi fit(X_train, y_train) chỉ lưu lại con trỏ tới X_train, y_train (và build index như KD-Tree nếu chọn). Không có gradient descent, không có loss function tối ưu, không có closed-form. Train time gần bằng O(1) nếu dùng brute force.
• Inference đắt — mỗi lần predict một sample, phải tính distance từ sample đó tới mọi điểm train, sort lấy K điểm gần nhất, rồi vote. Brute force: \( O(n \cdot d) \) per query với \( n \) sample và \( d \) feature.

Đối nghịch với eager learner: train chậm (cần tối ưu), nhưng inference chỉ là dot product hay vài lần lookup. KNN đảo ngược cấu trúc chi phí.

Hệ quả thực tế: KNN không phù hợp khi train set lớn và yêu cầu latency thấp khi predict (vd realtime API). Phù hợp khi train set nhỏ vừa và dataset không thay đổi liên tục.

Pseudo-code cho một query point \( \mathbf{x} \):

1. Với mỗi điểm train \( \mathbf{x}_i \) (\( i = 1, \ldots, n \)), tính khoảng cách \( d(\mathbf{x}, \mathbf{x}_i) \).
2. Sort theo \( d \) tăng dần, lấy chỉ số \( K \) điểm đầu: tập \( \mathcal{N}_K(\mathbf{x}) \).
3. Classification — vote majority: \[ \hat{y} = \arg\max_{c} \sum_{i \in \mathcal{N}_K(\mathbf{x})} \mathbb{1}[y_i = c] \]
4. Regression — trung bình: \[ \hat{y} = \frac{1}{K} \sum_{i \in \mathcal{N}_K(\mathbf{x})} y_i \]

Biến thể distance-weighted vote: thay vì đếm thô, mỗi láng giềng đóng góp một trọng số tỉ lệ nghịch với khoảng cách (\( w_i = 1/d_i \)). Láng giềng càng gần càng có tiếng nói nặng hơn. sklearn bật bằng weights="distance".

Với binary classification, người ta thường chọn \( K \) lẻ để loại bỏ khả năng hoà phiếu (3, 5, 7...). Với multi-class, hoà vẫn có thể xảy ra; sklearn xử lý tie bằng cách chọn class có index nhỏ hơn (deterministic nhưng tuỳ tiện).

"Gần nhất" cần một định nghĩa khoảng cách. Các lựa chọn phổ biến:

• Euclidean (L2) — mặc định, hợp lý cho feature liên tục đã scale: \[ d_2(\mathbf{x}, \mathbf{y}) = \sqrt{\sum_{j=1}^d (x_j - y_j)^2} \]
• Manhattan (L1) — tổng chênh lệch tuyệt đối, ít nhạy outlier hơn L2, hợp cho không gian "lưới đường phố": \[ d_1(\mathbf{x}, \mathbf{y}) = \sum_{j=1}^d |x_j - y_j| \]
• Minkowski — tổng quát hoá hai cái trên qua tham số \( p \): \[ d_p(\mathbf{x}, \mathbf{y}) = \left( \sum_{j=1}^d |x_j - y_j|^p \right)^{1/p} \] \( p = 1 \) → Manhattan; \( p = 2 \) → Euclidean. sklearn dùng Minkowski làm mặc định với \( p = 2 \).
• Cosine — đo góc giữa hai vector, độc lập với độ dài. Hợp cho text embedding, TF-IDF, biểu diễn ngữ nghĩa. \( d_\cos = 1 - \frac{\mathbf{x} \cdot \mathbf{y}}{\|\mathbf{x}\| \|\mathbf{y}\|} \).
• Hamming — đếm số vị trí khác nhau giữa hai vector. Hợp cho feature nhị phân hoặc categorical đã one-hot.

Chọn metric theo bản chất feature, không "thử" ngẫu nhiên. Feature liên tục đã scale → Euclidean là mặc định an toàn. Vector embedding → Cosine. Feature nhị phân/categorical → Hamming.

\( K \) là hyperparameter duy nhất quan trọng của KNN. Chọn sai \( K \) → model hoặc quá nhạy, hoặc quá phẳng.

• K = 1 — predict bằng đúng 1 điểm gần nhất. Train accuracy = 100% (mỗi điểm tự khớp với chính nó). Decision boundary cực kỳ "răng cưa", bám sát mọi điểm nhiễu → variance cao, dễ overfit.
• K nhỏ (3, 5) — boundary còn linh hoạt nhưng đã giảm độ nhạy với nhiễu cá biệt.
• K lớn — boundary trơn (smoother), bias tăng. Khi \( K \to n \), model degenerate thành "predict class phổ biến nhất trong train set" — bias cực đại, vô dụng.
• K lẻ cho binary — tránh hoà phiếu. Với multi-class, hoà vẫn xảy ra dù K lẻ.
• Quy tắc khởi đầu — \( K \in \{3, 5, 7\} \) hoặc \( K \approx \sqrt{n} \) thường được nhắc làm điểm bắt đầu. Đây là điểm xuất phát, không phải đáp án.
• Cách chọn đúng — cross-validation (Bài 39): quét một dải \( K \) (vd 1–30), chọn giá trị tối ưu metric trên validation fold.

K thể hiện trực tiếp trade-off bias–variance (Bài 38): K nhỏ = variance cao, K lớn = bias cao.

Đây là điểm không thoả hiệp với KNN. Mọi distance metric dùng phép cộng trên các chênh lệch \( (x_j - y_j)^2 \) hoặc \( |x_j - y_j| \). Feature có range lớn sẽ nuốt trọn distance, các feature khác trở nên vô nghĩa.

Ví dụ điển hình: dataset có hai feature

• age: 20–60 (range 40).
• salary: 1.000–100.000 (range 99.000).

Với Euclidean, chênh lệch tuổi 10 năm đóng góp \( 10^2 = 100 \) vào tổng bình phương; chênh lệch lương 10.000 đóng góp \( 10000^2 = 10^8 \). Distance gần như hoàn toàn quyết định bởi salary; age bị xoá khỏi quyết định.

Bắt buộc dùng StandardScaler (hoặc MinMaxScaler) trước KNN. Phải gói vào Pipeline để khi cross-validation, scaler chỉ fit trên fold train (tránh data leakage):

from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier

pipe = make_pipeline(
    StandardScaler(),
    KNeighborsClassifier(n_neighbors=5),
)
pipe.fit(X_train, y_train)

Quên scale là lỗi #1 khiến KNN cho accuracy thấp bất ngờ. Bài tập mục 15 sẽ minh hoạ trực tiếp.

API giống mọi classifier khác trong sklearn:

from sklearn.neighbors import KNeighborsClassifier

model = KNeighborsClassifier(
    n_neighbors=5,
    metric="minkowski",
    p=2,                # Minkowski p=2 => Euclidean
    weights="uniform",  # hoac "distance"
)
model.fit(X_train, y_train)

y_pred = model.predict(X_test)
y_proba = model.predict_proba(X_test)
# y_proba la ti le vote trong K lang gieng cho moi class

Lưu ý predict_proba của KNN không phải probability "đúng nghĩa" — chỉ là tỉ lệ vote (vd 3/5 láng giềng vote class 1 → \( P(y=1) = 0.6 \)). Calibration của xác suất này thường kém hơn Logistic Regression. Khi cần probability calibrated, dùng CalibratedClassifierCV bọc ngoài.

• n_neighbors (mặc định 5) — chính là \( K \). Tune bằng cross-validation.
• weights — "uniform" (mặc định, mỗi láng giềng đếm như nhau) hoặc "distance" (trọng số tỉ lệ nghịch với khoảng cách). "distance" thường tốt hơn khi K lớn và mật độ điểm không đồng đều.
• metric — mặc định "minkowski". Có thể truyền "euclidean", "manhattan", "chebyshev", "cosine", "hamming" hoặc callable tự định nghĩa.
• p — tham số của Minkowski. p=1 → Manhattan, p=2 → Euclidean. Bỏ qua nếu metric đã chỉ định khác.
• algorithm — chiến lược tìm láng giềng: "auto" (mặc định, tự chọn dựa trên dữ liệu), "ball_tree", "kd_tree", "brute".
• leaf_size (mặc định 30) — kiểm soát điểm cắt giữa duyệt cây và brute force trong lá. Ảnh hưởng tốc độ và bộ nhớ, không ảnh hưởng kết quả.
• n_jobs — số CPU dùng cho query song song. Đặt -1 để dùng tất cả core.

Combo mặc định an toàn cho baseline: KNeighborsClassifier(n_neighbors=5, weights="distance", metric="minkowski", p=2), kèm StandardScaler trong Pipeline.

Tham số algorithm chọn cách tổ chức train set để tìm K láng giềng nhanh hơn so với duyệt tuyến tính.

• Brute force — tính distance tới mọi điểm train, sort. Độ phức tạp \( O(n \cdot d) \) cho mỗi query. Đơn giản, không cần build trước, hợp khi \( n \) nhỏ hoặc \( d \) rất lớn.
• KD-Tree — chia không gian feature dọc theo các trục, mỗi nút cây chia theo một chiều. Tìm láng giềng có thể cắt nhánh xa → \( O(\log n) \) per query trong điều kiện lý tưởng. Hiệu quả khi \( d \lesssim 20 \).
• Ball-Tree — chia không gian thành các "quả bóng" (hyperspheres) lồng nhau. Hoạt động tốt hơn KD-Tree khi số chiều trung bình–cao, hoặc khi metric không phải Euclidean.
• auto — sklearn heuristic: chọn brute khi \( d > 15 \), KD-Tree với metric phù hợp, hoặc Ball-Tree nếu KD-Tree không hỗ trợ metric.

Lưu ý quan trọng: cả KD-Tree và Ball-Tree đều xuống cấp khi \( d \) lớn (\( d > 20\text{–}30 \)). Cấu trúc cây không cắt được nhánh nào → trở lại gần như brute force. Đây là biểu hiện của curse of dimensionality.

Đây là vấn đề cốt yếu của KNN. Trong không gian số chiều lớn, khái niệm "gần" mất ý nghĩa.

Trực giác: lấy \( n \) điểm phân bố đều trong hypercube đơn vị \( [0, 1]^d \). Khi \( d \) tăng, khoảng cách giữa điểm gần nhất và điểm xa nhất đến một query bất kỳ tiến lại sát nhau:

\[ \lim_{d \to \infty} \frac{\max_i d(\mathbf{x}, \mathbf{x}_i) - \min_i d(\mathbf{x}, \mathbf{x}_i)}{\min_i d(\mathbf{x}, \mathbf{x}_i)} \to 0 \]

Nghĩa là mọi điểm "gần như cách đều" query. K điểm "gần nhất" không còn ý nghĩa thực sự gần — chúng chỉ tình cờ gần hơn một chút.

Hệ quả với KNN:

• Accuracy sụt mạnh khi \( d \) vượt ngưỡng 20–30 feature.
• Cấu trúc cây KD/Ball không cắt được nhánh → tốc độ = brute force.
• Cần lượng data tăng theo hàm mũ của \( d \) để giữ mật độ điểm — thực tế bất khả thi.

Giải pháp:

• Giảm chiều — PCA (Bài 36), t-SNE, UMAP trước khi đưa vào KNN.
• Feature selection — chỉ giữ feature có signal, vứt feature nhiễu.
• Dùng metric phù hợp với high-dim — Cosine cho embedding thường ổn định hơn Euclidean.
• Đổi model — tree-based (Random Forest, Bài 29) hoặc linear model robust hơn với high-dim.

Cùng ý tưởng, đổi rule từ vote sang trung bình:

\[ \hat{y} = \frac{1}{K} \sum_{i \in \mathcal{N}_K(\mathbf{x})} y_i \quad \text{(uniform)} \]

Hoặc trung bình có trọng số khi weights="distance":

\[ \hat{y} = \frac{\sum_{i \in \mathcal{N}_K} w_i \, y_i}{\sum_{i \in \mathcal{N}_K} w_i}, \quad w_i = \frac{1}{d(\mathbf{x}, \mathbf{x}_i)} \]

API trong sklearn:

from sklearn.neighbors import KNeighborsRegressor

reg = KNeighborsRegressor(n_neighbors=5, weights="distance")
reg.fit(X_train, y_train)
y_pred = reg.predict(X_test)

Đặc điểm so với KNN classification:

• Output liên tục, không có vote tie issue.
• Predict cho điểm ngoài bao lồi của train set (extrapolation) thường tệ — KNN chỉ trung bình các điểm đã thấy, không "ngoại suy" như Linear Regression.
• Mọi yêu cầu về scale, distance metric, K, curse of dim đều giống classification.

Ưu điểm:

• Cực đơn giản về khái niệm, ít hyperparameter (chỉ K + metric).
• Không có "training" → fit gần như tức thời.
• Tự nhiên hỗ trợ multi-class, không cần OvR hay softmax.
• Decision boundary có thể phi tuyến tuỳ ý, không bị ép tuyến tính.
• Hoạt động với bất kỳ distance metric nào, kể cả metric tự định nghĩa.

Nhược điểm:

• Inference chậm, tốn RAM (lưu toàn train set).
• Nhạy với scale feature → bắt buộc scale.
• Sụp đổ với high-dimensional data (curse of dim).
• Không interpretable — không có coefficient, không có feature importance trực tiếp.
• Nhạy với nhiễu khi K nhỏ; nhạy với imbalance khi K lớn (vote bị class đa số chiếm).
• Không có khái niệm "model size" cố định — model size = train size.

• Recommendation system — item-based hoặc user-based collaborative filtering thực chất là KNN trong không gian user × item, thường dùng Cosine.
• Anomaly detection — điểm có \( K \) láng giềng xa bất thường được đánh dấu là anomaly (biến thể: LOF — Local Outlier Factor).
• Image retrieval và similarity search — query bằng embedding (CNN, CLIP), tìm K ảnh gần nhất trong cơ sở dữ liệu. Vector database (FAISS, Milvus, Pinecone) là KNN ở quy mô tỉ vector.
• Baseline — trước khi đầu tư model phức tạp, train KNN nhanh để có điểm chuẩn. Nếu KNN đã đủ tốt, đôi khi không cần thêm.
• Missing value imputation — KNNImputer điền giá trị thiếu bằng trung bình K láng giềng có giá trị.

KNN trên iris (binary subset + multi-class), tích hợp Pipeline với StandardScaler:

import numpy as np
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split, cross_val_score
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import make_pipeline
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score

iris = load_iris()
X, y = iris.data, iris.target

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42, stratify=y
)

pipe = make_pipeline(
    StandardScaler(),
    KNeighborsClassifier(n_neighbors=5),
)
pipe.fit(X_train, y_train)

y_pred = pipe.predict(X_test)
print(f"accuracy K=5: {accuracy_score(y_test, y_pred):.4f}")

# predict_proba la ti le vote trong 5 lang gieng
proba = pipe.predict_proba(X_test[:3])
print("proba (vote ratio):\n", proba)

Quét K từ 1 đến 30 bằng cross-validation để chọn K tốt nhất:

scores = []
ks = range(1, 31)
for k in ks:
    pipe_k = make_pipeline(
        StandardScaler(),
        KNeighborsClassifier(n_neighbors=k),
    )
    cv = cross_val_score(pipe_k, X_train, y_train, cv=5, scoring="accuracy")
    scores.append(cv.mean())

best_k = ks[int(np.argmax(scores))]
print(f"best K = {best_k}, CV accuracy = {max(scores):.4f}")

# Plot accuracy theo K (matplotlib)
# import matplotlib.pyplot as plt
# plt.plot(list(ks), scores, marker="o")
# plt.xlabel("K"); plt.ylabel("CV accuracy"); plt.show()
# Quan sat: K=1 thuong overfit (CV accuracy thap hon), K vua phai dat dinh,
# K rat lon thi CV accuracy giam dan do bias tang.

KNN regression trên California housing (subset nhỏ để chạy nhanh):

from sklearn.datasets import fetch_california_housing
from sklearn.neighbors import KNeighborsRegressor
from sklearn.metrics import mean_squared_error, r2_score

data = fetch_california_housing()
X, y = data.data[:2000], data.target[:2000]  # subset 2000 sample

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.3, random_state=42
)

reg = make_pipeline(
    StandardScaler(),
    KNeighborsRegressor(n_neighbors=5, weights="distance"),
)
reg.fit(X_train, y_train)
y_pred = reg.predict(X_test)

rmse = np.sqrt(mean_squared_error(y_test, y_pred))
print(f"RMSE: {rmse:.4f}, R^2: {r2_score(y_test, y_pred):.4f}")

Quan sát: trên California housing đầy đủ, KNN regression thường thua Random Forest / Gradient Boosting (Bài 29, 30) vì \( d = 8 \) feature và mật độ điểm không đồng đều ở các vùng. Là baseline hợp lý, không phải lựa chọn tối ưu.

Bài 1 — Ảnh hưởng của K. Load load_iris(), split 70/30 với stratify=y, scale bằng StandardScaler. Train ba model KNeighborsClassifier với n_neighbors lần lượt là 1, 5, 50. So sánh accuracy trên cả train và test. K nào overfit (train cao hơn test nhiều)? K nào underfit (cả hai cùng thấp)?

Bài 2 — Standardize có và không. Trên Breast Cancer (load_breast_cancer(), 30 feature có range chênh lệch lớn), train hai pipeline:

• A: KNeighborsClassifier(n_neighbors=5) trên raw X_train.
• B: StandardScaler + KNeighborsClassifier(n_neighbors=5).

So sánh accuracy test. Chênh lệch có lớn không? In ra X_train.std(axis=0) để thấy range các feature.

Bài 3 — Implement KNN bằng numpy. Cho train set X_train, y_train (numpy array) và một query x_query (shape (d,)). Viết hàm knn_predict(X_train, y_train, x_query, k):

1. Tính Euclidean distance từ x_query tới mỗi hàng của X_train (gợi ý: np.linalg.norm(X_train - x_query, axis=1)).
2. Lấy chỉ số K điểm gần nhất bằng np.argsort hoặc np.argpartition.
3. Vote majority bằng np.bincount hoặc collections.Counter.

So sánh kết quả với KNeighborsClassifier trên cùng dữ liệu — phải khớp.

Bài 4 — Distance metric khác nhau. Trên iris đã scale, so sánh accuracy của KNeighborsClassifier(n_neighbors=5) với metric = "euclidean", "manhattan", "chebyshev". Có metric nào tốt hơn rõ rệt không?

Bài 5 — Curse of dimensionality demo. Tạo dataset giả: 500 sample, label nhị phân từ 2 feature có signal. Thêm dần các feature noise (random từ np.random.randn) thành các phiên bản 2, 10, 50, 200 feature. Train KNeighborsClassifier(n_neighbors=5) sau khi scale, ghi nhận accuracy test. Accuracy thay đổi thế nào khi số feature noise tăng?

Bài 28: Decision Tree — model phi tuyến không cần scale, decision boundary dạng axis-aligned. Tách dữ liệu bằng các câu hỏi if-else trên feature, đo độ "thuần" của nhóm bằng entropy hoặc Gini. Là tiền đề cho Random Forest và Gradient Boosting.