Instance-based — học theo mẫu

Ý tưởng. Để dự đoán nhãn cho một điểm mới \(x\), kNN tìm \(k\) điểm trong tập huấn luyện gần \(x\) nhất (theo một độ đo khoảng cách), rồi cho chúng bầu chọn: nhãn nào chiếm đa số trong \(k\) láng giềng thì gán cho \(x\). Với bài toán hồi quy, ta lấy trung bình giá trị của \(k\) láng giềng.

Lazy learning. kNN gần như không có giai đoạn "huấn luyện" — nó chỉ lưu lại toàn bộ dữ liệu. Mọi tính toán bị dồn sang lúc dự đoán (phải đo khoảng cách từ điểm mới tới mọi điểm đã lưu). Vì vậy kNN được gọi là lazy learner (học lười), trái với các mô hình eager như hồi quy hay cây quyết định vốn tốn công lúc huấn luyện nhưng dự đoán rất nhanh.

Các độ đo khoảng cách

"Gần nhất" phụ thuộc vào cách ta định nghĩa khoảng cách giữa hai vector đặc trưng \(x=(x_1,\dots,x_n)\) và \(x'=(x_1',\dots,x_n')\):

Chọn k như thế nào

Giá trị \(k\) là siêu tham số quan trọng nhất:

• \(k\) nhỏ (ví dụ \(k=1\)): mô hình rất linh hoạt, bám sát từng điểm → dễ nhiễu / overfit, một điểm ngoại lai cũng đủ làm sai dự đoán.
• \(k\) lớn: biên quyết định mượt hơn, ít nhạy nhiễu, nhưng nếu quá lớn sẽ bỏ qua cấu trúc cục bộ → underfit (xu hướng dự đoán về lớp đa số).
• Với bài toán 2 lớp, thường chọn \(k\) lẻ để tránh hoà phiếu. Giá trị tốt thường tìm bằng kiểm định chéo (cross-validation).

Weighted kNN

Trong bản kNN cơ bản, mọi láng giềng có phiếu bầu như nhau. Weighted kNN cho láng giềng ở gần có trọng số lớn hơn, thường theo nghịch đảo khoảng cách:

$$ w_i=\frac{1}{d(x,x_i)+\varepsilon} \qquad \hat{y}=\frac{\sum_i w_i\,y_i}{\sum_i w_i} $$

Nhờ vậy điểm sát ngay cạnh \(x\) ảnh hưởng mạnh hơn điểm ở rìa của \(k\) láng giềng, giúp dự đoán ổn định hơn khi \(k\) lớn (\(\varepsilon\) là số nhỏ để tránh chia cho 0).

Ưu — nhược điểm

Ý tưởng prototype-based. Điểm yếu lớn nhất của kNN là phải giữ toàn bộ dữ liệu. LVQ giải quyết điều này bằng cách học một tập nhỏ các vector đại diện — gọi là codebook hoặc prototype — mỗi vector được gắn sẵn một nhãn. Sau khi huấn luyện, ta chỉ cần giữ vài prototype thay vì hàng nghìn điểm dữ liệu.

Luật cập nhật. LVQ học các prototype theo kiểu lặp. Với mỗi mẫu huấn luyện \(x\) (có nhãn thật), ta tìm prototype gần nó nhất — gọi là BMU (Best Matching Unit), ký hiệu \(w\) — rồi điều chỉnh:

• Nếu BMU cùng nhãn với \(x\): kéo prototype lại gần mẫu   $$ w := w + \eta\,(x - w) $$
• Nếu BMU khác nhãn với \(x\): đẩy prototype ra xa mẫu   $$ w := w - \eta\,(x - w) $$

Trong đó \(\eta\) (\(0\lt\eta\lt 1\)) là tốc độ học, thường giảm dần qua các vòng lặp. Sau nhiều lần lặp, các prototype "trôi" tới những vị trí phản ánh đúng vùng của từng lớp, tạo nên biên quyết định gọn gàng. Khi dự đoán: gán cho điểm mới nhãn của prototype gần nó nhất.

So với kNN

LVQ thực chất nén dữ liệu thành một số ít prototype. Nhờ đó dự đoán nhanh hơn nhiều (chỉ so với vài prototype thay vì toàn bộ dữ liệu) và nhẹ bộ nhớ. Cái giá phải trả là cần một giai đoạn huấn luyện thật sự và kết quả phụ thuộc vào số prototype, cách khởi tạo, và \(\eta\).

scikit-learn cung cấp sẵn KNeighborsClassifier. Lưu ý đặt scaler và mô hình trong một Pipeline để việc chuẩn hoá được áp dụng nhất quán:

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

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)

# chuẩn hoá rồi mới kNN — rất quan trọng vì kNN dựa trên khoảng cách
clf = make_pipeline(
    StandardScaler(),
    KNeighborsClassifier(
        n_neighbors=5,        # k = 5 (số lẻ cho bài 2 lớp)
        weights="distance",    # weighted kNN theo nghịch đảo khoảng cách
        metric="minkowski", p=2  # p=2 -> Euclid
    )
)

clf.fit(X_train, y_train)
print(clf.score(X_test, y_test))