K-Nearest Neighbors

k láng giềng gần nhất (k-NN)

Trung bìnhclassic-ml

1Hook1/8

Hỏi 5 người bạn gần nhất

Bạn vừa chuyển đến một khu mới ở Sài Gòn và muốn biết quán nào ngon. Cách nhanh nhất: hỏi 5 người bạn ở gần nhất. Nếu 3/5 bảo “cơm tấm Bà Sáu”, bạn đi cơm tấm Bà Sáu. Không cần nghiên cứu, không cần cân đo công thức — chỉ cần hỏi hàng xóm.

k-NN (k láng giềng gần nhất) hoạt động đúng như vậy. Có một điểm mới cần phân loại → tìm k điểm gần nó nhất trong dữ liệu cũ → lấy theo đa số. Đơn giản đến không ngờ, nhưng đủ mạnh để làm nền cho nhiều hệ thống gợi ý và kiểm tra thực tế.

Vẫn ẩn dụ hỏi hàng xóm, nhưng đẩy tới cực hạn: bạn chỉ hỏi k = 1 người (người gần nhất) cho mọi câu. Rủi ro lớn nhất là gì?

2Ba thứ cần hiểu2/8

k-NN chỉ có ba lựa chọn quan trọng — nắm được ba cái này là bạn hiểu 90% thuật toán.

1 · Dữ liệu

Tập các điểm đã biết nhãn. k-NN không “học” gì — nó chỉ giữ lại toàn bộ tập này.

2 · Thước đo khoảng cách

Euclid (đường chim bay) là mặc định. Manhattan (đi theo ô bàn cờ) và Cosine (đo hướng, dùng cho văn bản) là hai lựa chọn phổ biến khác.

3 · Số láng giềng k

k = 1 → dự đoán cực sát nhưng dễ bị nhiễu. k lớn → mượt nhưng dễ nuốt cụm nhỏ. Thông thường k ≈ √N và dùng CV để chọn.

k-NN không có bước train

Khác với hầu hết thuật toán ML, k-NN không có bước “học” nào cả. Toàn bộ “model” của nó chính là tập dữ liệu đã dán nhãn. Mọi phép tính được dồn vào lúc dự đoán — đó là lý do k-NN được gọi là “lazy learner” (thuật toán lười).

3Khám phá3/8

Hình minh họa

1Thử nghiệm 1 · Canvas k-NN

45 điểm ở ba cụm là ba kiểu quán: cơm tấm (đỏ), phở (xanh dương), bánh mì(xanh lá). Click vào canvas để đặt “điểm mới” — bạn sẽ thấy k láng giềng được nối bằng đường màu, và màu điểm truy vấn = dự đoán theo đa số.

k = 5

Hiện biên quyết định

Click bất kỳ đâu trên canvas để đặt điểm mới

Dự đoán

Bánh mì (xanh lá)

Phiếu trong k = 5

A: 1B: 0C: 4

Toạ độ & thước đo

(210, 170) · Euclid

2Thử nghiệm 2 · k nhỏ vs k lớn

Chỉ kéo thanh k và xem toàn bộ “bản đồ quyết định” thay đổi theo. Để biên mượt ra, tăng k. Để biên “sát” từng điểm, giảm k.

Biên quyết định mượt ra sao khi thay đổi k?

k = 1 → biên lởm chởm, nhạy với từng điểm. k = 15–21 → biên mượt, đôi chỗ nuốt mất cụm nhỏ.

k (số hàng xóm hỏi ý kiến)1

121

3Thử nghiệm 3 · Euclid vs Manhattan

Cùng một điểm truy vấn, cùng k. Nhưng thay thước đo khoảng cách, hàng xóm thay đổi → dự đoán có thể khác. Mở cả hai tab để so sánh.

Cùng một điểm truy vấn, cùng k=5, nhưng hai thước đo khác nhau cho ra hai tập hàng xóm khác nhau. Kết quả: Bánh mì (xanh lá) (Euclid) vs Bánh mì (xanh lá) (Manhattan).

Euclid đo khoảng cách đường thẳng — phù hợp khi hai trục có cùng đơn vị và đặc trưng liên tục.

4Khoảnh khắc hiểu4/8

k-NN không phải là một thuật toán học. Nó là một quy ước bỏ phiếu đơn giản trên dữ liệu gốc. Tất cả sự khôn ngoan nằm ở hai lựa chọn: đo khoảng cách thế nào và k bằng bao nhiêu. Đổi một trong hai, bạn có model khác — dù dữ liệu không thay đổi một chữ.

5Thử thách5/8

Bạn có 10 triệu khách hàng trong database. Chạy k-NN để phân loại sản phẩm gợi ý real-time. Tại sao mô hình kém khi k quá lớn?

6Giải thích6/8

Giải thích

k-NN là thuật toán học có giám sát dựa trên một nguyên lý cực đơn giản: nhãn của điểm mới = đa số nhãn của k điểm gần nó nhất. Mọi thứ sau đây chỉ là cách viết chính xác của ý tưởng đó.

Công thức 1 — Khoảng cách Euclid

d(x, y) = \sqrt{\sum_{j=1}^{d} (x_j - y_j)^2}

Nói bằng tiếng Việt đời thường: “Đo đường chim bay từ điểm này đến điểm kia trong không gian d chiều”. Trong 2D bạn đã học từ cấp 3: d = √( (x₁ − x₂)² + (y₁ − y₂)² ). k-NN 2D dùng chính công thức đó, k-NN trên 100 đặc trưng thì cộng thêm các bình phương nữa.

Kéo điểm xanh/đỏ để thử. Euclid = cạnh huyền của tam giác vuông (chấm gạch).

Δx = 160 · Δy = 70 → d = √(Δx² + Δy²) = 174.6

Công thức 2 — Quy tắc đa số

\hat{y} = \text{mode}\{y_i : i \in \mathcal{N}_k(x)\}

Dịch ra: “Dự đoán ŷ bằng nhãn xuất hiện nhiều nhất trong tập k điểm gần nhất”. Nâng cấp hay gặp: thay vì “mỗi hàng xóm 1 phiếu”, cho hàng xóm gần hơn phiếu nặng hơn (weighted vote, trọng số 1/d).

Cạm bẫy thường gặp: lời nguyền nhiều chiều

Khi số đặc trưng d rất lớn (ví dụ ảnh 224×224 = 50.000 chiều), khoảng cách giữa mọicặp điểm có xu hướng bằng nhau — khái niệm “gần” mất nghĩa. Đây là “curse of dimensionality” (lời nguyền nhiều chiều). Với dữ liệu nhiều chiều, giảm chiều bằng PCA/UMAP hoặc dùng embedding deep learning trước khi áp k-NN.

Quy trình dự đoán một điểm — 4 bước

1 · Đo khoảng cách

Đo khoảng cách từ điểm truy vấn đến TẤT CẢ điểm trong tập huấn luyện. Với N = 100.000 điểm, là 100.000 phép đo. Đây là lý do k-NN chậm trên dữ liệu lớn — tăng tốc bằng KD-tree, Ball-tree, hoặc approximate NN (HNSW, FAISS).

Các thước đo khoảng cách phổ biến

Euclid (L2)

Đường chim bay. Mặc định khi đặc trưng có ý nghĩa hình học (tuổi, thu nhập sau chuẩn hoá, vị trí).

Manhattan (L1)

Đi theo ô lưới. Ít nhạy outlier hơn Euclid, phù hợp đặc trưng rời rạc hoặc thưa.

Cosine

1 − cos(góc) giữa hai vector. Quan tâm hướng, không độ lớn → chuẩn cho văn bản/embeddings.

Mahalanobis

Tính tới hiệp phương sai — khi các đặc trưng tương quan với nhau (dữ liệu tài chính, y tế).

Luôn chuẩn hoá trước khi dùng k-NN

Đặc trưng có thang giá trị lớn sẽ “nuốt” đặc trưng có thang nhỏ trong khoảng cách Euclid. Luôn dùng StandardScaler (về trung bình 0, độ lệch 1) hoặc MinMaxScaler (về [0,1]) trước k-NN. Đây là lý do hay nhất vì sao k-NN nên nằm trong một pipeline — để scaler và model được fit cùng nhau và tránh rò rỉ dữ liệu khi cross-validate.

Khi nào KHÔNG nên dùng k-NN

Tập huấn luyện lớn (triệu+ điểm) và cần dự đoán real-time — chi phí O(N · d) mỗi query quá đắt (dùng ANN như HNSW, FAISS để tăng tốc).
Số chiều cao (d > 20) mà không giảm chiều — khoảng cách mất nghĩa.
Đặc trưng không đồng đơn vị và không chuẩn hoá được.
Dữ liệu lớp mất cân bằng nặng — k-NN thiên về lớp đa số (dùng class_weight hoặc oversampling).

Trong thực tế, k-NN toả sáng khi: (1) bạn cần một baseline nhanhđể so sánh với mô hình phức tạp hơn; (2) dữ liệu có hình học rõ ràng (cảm biến đã chuẩn hoá, embeddings); (3) cần giải thích cho người ngoài kỹ thuật — “model này gợi ý vì có 5 trường hợp lịch sử giống bạn” dễ hiểu hơn nhiều so với “vì trọng số của layer 7 bằng...”.

Hai khái niệm bạn nên đọc cùng: k-means (anh em không giám sát: thay vì phân loại, nó tự gom cụm), và Cây quyết định (đối thủ chính trên dữ liệu bảng — không cần chuẩn hoá, chạy nhanh hơn khi N lớn).

7Tóm tắt7/8

4 điều cần nhớ về k-NN

k-NN = bỏ phiếu đa số của k điểm gần nhất. Không có bước train — 'model' chính là dữ liệu.
k nhỏ → biên lởm chởm, nhạy nhiễu. k lớn → biên mượt, bỏ qua cụm nhỏ. Chọn k ≈ √N + cross-validation.
LUÔN chuẩn hoá đặc trưng trước khi dùng — nếu không, đặc trưng thang lớn sẽ nuốt các đặc trưng khác.
Nhanh cho dữ liệu vừa phải (d < 20, N vừa). Với N triệu / d lớn, dùng KD-tree, Ball-tree, HNSW hoặc đổi sang cây quyết định.

Xem k-NN ngoài đời thật

Ứng dụng kiểm tra triệu chứng y tế: k-NN trong kiểm tra triệu chứng. Bạn nhập triệu chứng → app so với hàng ngàn bệnh nhân cũ → tìm ca giống nhất → gợi ý bệnh phổ biến trong các ca gần nhất.

Nếu bạn còn nhớ nguyên lý “hỏi hàng xóm” và biết khi nào phải chuẩn hoá, bạn đã nắm k-NN đủ dùng.

8Kiểm tra8/8

Kiểm tra hiểu biết

Câu 1/5

Với k-NN, khi tăng k từ 1 lên 15, điều gì thường xảy ra với biên quyết định?

Chủ đề liên quan

K-Means Clustering — Phân cụm k-means Support Vector Machine — Máy vector hỗ trợ Decision Trees — Cây quyết định