k-Nearest Neighbors

Thuật toán

Cho tập huấn luyện $\{(\mathbf{x}_i, y_i)\}_{i=1}^n$ và một điểm cần dự đoán $\mathbf{q}$:

1. Tính khoảng cách $d(\mathbf{q}, \mathbf{x}_i)$ đến mọi điểm.
2. Lấy tập $N_k(\mathbf{q})$ gồm $k$ điểm gần nhất.
3. Phân loại: chọn nhãn xuất hiện nhiều nhất trong $N_k$. Hồi quy: lấy trung bình $y$ của $N_k$.

Ví dụ năm điểm $A(1, 1)$ nhãn đỏ, $B(2, 1)$ đỏ, $C(4, 3)$ xanh, $D(5, 4)$ xanh, $E(3, 2)$ xanh. Truy vấn $\mathbf{q} = (2, 2)$, $k = 3$, khoảng cách Euclid bình phương:

Ba láng giềng gần nhất là $B$, $E$, $A$: hai đỏ, một xanh, nên dự đoán đỏ. Với $k = 1$ thì $B$ và $E$ cùng khoảng cách, nên cần quy tắc phá hòa, chẳng hạn chọn điểm có chỉ số nhỏ hơn. Đề chấm tự động thường ghi rõ quy tắc phá hòa; đọc sót nó là đủ để kết quả lệch đáp án.

Biến thể có trọng số cho láng giềng càng gần càng có tiếng nói lớn, ví dụ trọng số $1/d$. Một láng giềng lớp A cách 1 và hai láng giềng lớp B cách 2, 3: bỏ phiếu đều thì B thắng 2–1, còn theo $1/d$ thì A được 1, B chỉ được $1/2 + 1/3 \approx 0.83$. Hồi quy cũng vậy: giá trị 10, 20, 40 ở khoảng cách 1, 2, 4 cho $(10 + 10 + 10)/1.75 \approx 17.1$, gần láng giềng sát nhất hơn trung bình thường $23.3$.

kNN là học lười (lazy learning): “huấn luyện” chỉ là cất dữ liệu đi, mọi công việc dồn vào lúc dự đoán. Ngược lại, mô hình tuyến tính là học chăm (eager): học xong chỉ giữ $\mathbf{w}$, dữ liệu gốc có thể bỏ. kNN vẫn là học có giám sát, vì các láng giềng phải có nhãn mới bỏ phiếu được. Chữ $k$ ở đây là số láng giềng, khác hẳn $K$ của K-means ở bài 2.10, là số cụm.

Khoảng cách

Với vector đã chuẩn hóa về độ dài 1, $\lVert\mathbf{q} - \mathbf{x}\rVert^2 = 2 - 2\cos(\mathbf{q}, \mathbf{x})$, nên xếp hạng theo Euclid và theo cosine là như nhau. Thư viện tìm kiếm embedding dùng đúng mẹo này. Đổi cách đo có thể đổi láng giềng: từ $(0, 0)$, điểm $(3, 0)$ cách 3 theo cả hai cách, còn $(2, 2)$ cách $\sqrt 8 \approx 2.83$ theo Euclid nhưng cách 4 theo Manhattan. Muốn một cột nặng ký hơn thì đánh trọng số ngay trong khoảng cách, $\sqrt{\sum_j w_j (q_j - x_j)^2}$.

Thang đo quyết định tất cả. Hai đặc trưng “tuổi” (20 đến 60) và “thu nhập tháng” tính bằng đồng (5 triệu đến 50 triệu): khoảng cách gần như chỉ còn là chênh lệch thu nhập, tuổi chẳng còn tiếng nói nào. Khi đơn vị các cột không so sánh được, chuẩn hóa hoặc thiết kế trọng số khoảng cách là bước cần kiểm bằng validation.

Chọn k

• $k = 1$: lỗi trên train thường bằng 0 nếu không có hồ sơ trùng nhau mang nhãn mâu thuẫn, ranh giới lởm chởm theo từng điểm nhiễu. Variance cao.
• $k$ lớn: ranh giới mượt, nhưng $k = n$ thì đoán mọi điểm là lớp đông nhất. Bias cao.

Chọn $k$ bằng cross-validation. Với phân loại nhị phân, $k$ lẻ tránh hòa phiếu. Leave-one-out (bài 1.3) rất rẻ với kNN: bỏ từng điểm ra rồi hỏi láng giềng trong phần còn lại, không phải học lại gì. Trên một trục số, 1-NN chỉ đổi dự đoán ở trung điểm giữa hai điểm liền kề khác nhãn, nên nó chính là một dãy ngưỡng.

Lời nguyền số chiều

Khi số chiều tăng, với dữ liệu trải đều, điểm gần nhất và điểm xa nhất cách truy vấn gần bằng nhau, nên “láng giềng” mất ý nghĩa. Dữ liệu thật thường nằm gần một cấu trúc ít chiều hơn nhiều, nên mức độ tệ còn tùy số chiều thực chất của nó. Một phép tính nhỏ cho thấy hiện tượng này. Dữ liệu rải đều trong khối lập phương đơn vị $d$ chiều. Muốn một khối lập phương nhỏ chứa 10% dữ liệu thì cạnh của nó phải dài $0.1^{1/d}$:

• $d = 1$: cạnh $0.1$, đúng là “lân cận”.
• $d = 10$: cạnh $0.79$, gần hết cả khoảng.
• $d = 100$: cạnh $0.98$.

Láng giềng gần nhất trong 100 chiều thực chất chẳng gần chút nào. Nhìn theo chiều ngược lại: khối lập phương đồng tâm cạnh $0.9$ chỉ chứa $0.9^{100} \approx 0.003\%$ thể tích, gần như mọi điểm nằm sát biên. Muốn láng giềng gần nhất gần gấp đôi thì mỗi điểm phải phủ một quả cầu bán kính bằng nửa, thể tích nhỏ đi $2^d$ lần, nên cần khoảng $2^d$ lần số điểm. Vì vậy kNN chạy tốt trên đặc trưng ít chiều, hoặc trên embedding mà mô hình đã học sẵn để những thứ giống nhau nằm gần nhau, thường kèm giảm chiều bằng PCA (bài 2.9).

Chi phí

Dự đoán một điểm tốn $O(nd)$. Với $n$ lớn, có ba cách tăng tốc:

• Cây không gian (KD-tree, Ball tree): nhanh khi $d$ nhỏ, dưới khoảng 20.
• Vector hóa bằng phép nhân ma trận trên GPU: tính một lần khoảng cách giữa cả lô truy vấn và cả tập dữ liệu.
• Tìm gần đúng (approximate nearest neighbor) như FAISS, HNSW: chấp nhận đôi khi sót láng giềng thật để nhanh hơn hàng trăm lần. Đây là nền của các hệ thống tìm kiếm ảnh và văn bản. Chúng có núm đổi tốc độ lấy độ đúng, như ef_search của HNSW: giữ nhiều ứng viên hơn khi duyệt thì ít sót láng giềng thật nhưng chậm hơn.

Vài lưu ý khi tự cài:

• Chọn $k$ phần tử nhỏ nhất: sort toàn bộ tốn $O(n \log n)$; np.argpartition chọn trước rồi chỉ sort $k$ phần tử thì rẻ hơn.
• Với $m$ truy vấn một lúc, ma trận khoảng cách $m \times n$ có thể hết RAM dù code chỉ một dòng; chia truy vấn thành từng batch.
• KD-tree không phải lúc nào cũng $O(\log n)$: ở nhiều chiều nó có thể phải duyệt gần hết cây.

Cài kNN bằng NumPy

Cài lại ví dụ năm điểm ở mục Thuật toán, chưa cần thư viện. Mỗi hàng là một hồ sơ, hai cột là hai đặc trưng. Trừ truy vấn khỏi từng hàng bằng broadcasting, bình phương từng độ lệch, rồi cộng theo axis=1 để được một khoảng cách cho mỗi hàng. Không lấy căn vì căn bậc hai tăng theo đối số: xếp hạng khoảng cách bình phương cho cùng thứ tự, tránh thêm một phép tính.

import numpy as np

points = np.array([[1, 1], [2, 1], [4, 3], [5, 4], [3, 2]], dtype=float)
labels = np.array([0, 0, 1, 1, 1])
query = np.array([2, 2], dtype=float)
distance2 = np.sum((points - query) ** 2, axis=1)
order = np.argsort(distance2, kind="stable")
neighbors = order[:3]
counts = np.bincount(labels[neighbors], minlength=2)
print(distance2.astype(int).tolist())
print(neighbors.tolist(), counts.tolist(), int(np.argmax(counts)))
assert neighbors.tolist() == [1, 4, 0]

Kết quả[2, 1, 5, 13, 1]
[1, 4, 0] [2, 1] 0

Chỉ số trong code bắt đầu từ 0, nên [1, 4, 0] chính là B, E, A. stable giữ thứ tự ban đầu khi khoảng cách bằng nhau; argmax chọn nhãn có chỉ số nhỏ nhất khi số phiếu hòa. Đây là hai quy tắc của bản cài này, không phải quy tắc chung của mọi thư viện. Với k=1, đổi thứ tự dữ liệu có thể đổi dự đoán ở điểm hòa khoảng cách. Trong đề chấm chính xác, phải cài quy ước đề yêu cầu.

Thang đo thay đổi người hàng xóm

Xét hồ sơ truy vấn (8 điểm, 5 giờ), hai hồ sơ A (9, 5) và B (8, 6). Trong đơn vị hiện tại cả hai cách truy vấn 1. Nếu đổi giờ thành phút, B cách 60 còn A vẫn cách 1; thông tin thực tế không đổi mà thuật toán đã thiên hẳn về A. Hình dưới cho thấy đổi đơn vị kéo một trục dài ra. StandardScaler đưa các cột về cùng thang đo; còn nếu biết một cột quan trọng hơn, có thể nhân cột đó với một hệ số lớn hơn, rồi kiểm bằng validation.

Cần phân biệt chuẩn hóa theo cột với chuẩn hóa độ dài từng vector. StandardScaler thường dùng cho các đặc trưng số khác đơn vị. Với embedding dùng cosine, ta thường chia mỗi hàng cho norm của chính hàng đó. Vector toàn 0 không có hướng, nên cosine chưa xác định; cần quy tắc xử lý riêng trước khi tính.

Dùng thư viện

from sklearn.datasets import load_wine
from sklearn.model_selection import GridSearchCV
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

X, y = load_wine(return_X_y=True)
for scale in [False, True]:
    steps = [StandardScaler()] if scale else []
    model = make_pipeline(*steps, KNeighborsClassifier())
    grid = GridSearchCV(model, {"kneighborsclassifier__n_neighbors": [1, 3, 5, 9, 15]}, cv=5)
    grid.fit(X, y)
    print("chuẩn hóa" if scale else "không chuẩn hóa", round(grid.best_score_, 3), grid.best_params_)

Kết quảkhông chuẩn hóa 0.725 {'kneighborsclassifier__n_neighbors': 1}
chuẩn hóa 0.966 {'kneighborsclassifier__n_neighbors': 9}

Chênh lệch lớn có lý do cụ thể: cột proline chạy từ 278 đến 1680, trong khi phần lớn các cột khác chỉ cỡ 0.1 đến 30. Chưa chuẩn hóa, proline chiếm khoảng 99.8% bình phương khoảng cách, nên kNN gần như chỉ so một cột và phải dùng $k=1$ để vớt vát.