ONE is preparing: 01 / INITIALIZING MODEL ROUTER. Evaluating routing across providers.
Current state
01 / INITIALIZING MODEL ROUTER.

Evaluating routing across providers.

Start learning
← ML cơ bản

AI Foundation

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

Vietnamese onlyThe learning content is available in Vietnamese only. The surrounding interface follows your language.

Muốn biết một điểm thuộc nhóm nào? Hỏi k láng giềng gần nhất rồi lấy theo đa số. Đơn giản, trực quan — và đủ mạnh để làm nền cho nhiều hệ thống gợi ý.

lesson46 minML cơ bảnAI Foundation

Hook

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ì?

Ba thứ cần hiểu

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.

Lựa chọnÝ nghĩa
1 · Dữ liệuTậ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áchEuclid (đườ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 kk = 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.

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á). Điểm mới được phân loại theo đa số trong k láng giềng gần nhất.

Khi k nhỏ, biên quyết định sát từng điểm. Khi k lớn, biên mượt ra.

Euclid vs Manhattan

Cùng một điểm truy vấn, cùng k, nhưng hai thước đo khác nhau có thể cho ra hai tập hàng xóm khác nhau.

Hai thước đo phổ biến

1 / 2
  1. 1. Euclid — đường chim bay

    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.

Khoảnh khắc hiểu

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ữ.

Thử thách

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?

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)=∑j=1d(xj−yj)2d(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.

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

y^=mode{yi:i∈Nk(x)}\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).

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

Bốn bước

1 / 4
  1. 1. 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

Thước đoKhi nào dùng
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.
Cosine1 − cos(góc) giữa hai vector. Quan tâm hướng, không độ lớn → chuẩn cho văn bản/embeddings.
MahalanobisTí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ế).

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).

Tóm tắt

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.

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.

Continue the path

Lesson 46 of 106