- Phương pháp học lười (Lazy Learning): Không có giai đoạn huấn luyện tham số tường minh; toàn bộ quá trình tính toán diễn ra tại thời điểm suy luận (Inference Time).
- Nguyên lý láng giềng: Các điểm dữ liệu có đặc trưng tương đồng sẽ nằm gần nhau trong không gian biểu diễn và có xu hướng thuộc về cùng một lớp nhãn.
- Các độ đo khoảng cách: Khoảng cách Euclidean (chuẩn L2), Manhattan (chuẩn L1) và Minkowski tổng quát.
- Bắt buộc chuẩn hóa đặc trưng: Nếu không chuẩn hóa về cùng dải giá trị, đặc trưng có thang đo lớn sẽ lấn át hoàn toàn khoảng cách hình học.
KNN là gì?
"Gần mực thì đen, gần đèn thì rạng" là câu tục ngữ phản ánh chính xác nhất trực giác của thuật toán K-Nearest Neighbors (KNN). Trong cuộc sống, chúng ta thường phỏng đoán tính cách, sở thích hoặc thói quen của một người dựa trên những người bạn thân thiết xung quanh họ.
Trong học máy, KNN là thuật toán phi tham số (Non-parametric) được sử dụng cho cả bài toán phân loại và hồi quy. Nó không đưa ra bất kỳ giả định nào về hình dạng phân phối của dữ liệu (như tính tuyến tính trong Hồi quy tuyến tính hay tính chuẩn trong Naive Bayes). Thay vào đó, nó ghi nhớ toàn bộ tập dữ liệu huấn luyện vào bộ nhớ. Khi có một điểm dữ liệu mới cần dự đoán, nó quét toàn bộ cơ sở dữ liệu để tìm ra \(K\) điểm nằm gần điểm đó nhất.
Nhờ cấu trúc phi tham số này, KNN có khả năng học các đường biên phân loại cực kỳ phức tạp và uốn lượn linh hoạt theo dữ liệu mà không bị bó hẹp trong bất kỳ công thức toán học cố định nào.
Các hàm đo khoảng cách trong không gian
Chất lượng dự đoán của KNN phụ thuộc hoàn toàn vào cách chúng ta định nghĩa "thế nào là gần nhau". Xét hai vector điểm \(x = [x_1, \dots, x_D]\) và \(y = [y_1, \dots, y_D]\) trong không gian \(D\) chiều:
1. Khoảng cách Euclidean (Chuẩn L2)
Độ đo đường chim bay kinh điển và thông dụng nhất:
\[d_{\text{Euclid}}(x, y) = \|x - y\|_2 = \sqrt{\sum_{j=1}^D (x_j - y_j)^2}\]
Thích hợp khi các đặc trưng là các biến vật lý liên tục có cùng bản chất hình học.
2. Khoảng cách Manhattan (Chuẩn L1 / City Block)
Khoảng cách di chuyển dọc theo các trục tọa độ trực giao (giống như quãng đường xe taxi di chuyển trên các ô bàn cờ đường phố):
\[d_{\text{Manhattan}}(x, y) = \|x - y\|_1 = \sum_{j=1}^D |x_j - y_j|\]
Khoảng cách Manhattan bền bỉ hơn trước các điểm ngoại lai (outliers) so với khoảng cách Euclidean vì không có phép lũy thừa bậc hai.
3. Khoảng cách Minkowski tổng quát (Chuẩn Lp)
Trường hợp tổng quát hóa với tham số bậc \(p \ge 1\):
\[d_{\text{Minkowski}}(x, y) = \left( \sum_{j=1}^D |x_j - y_j|^p \right)^{\frac{1}{p}}\]
Khi \(p = 1\), ta thu được khoảng cách Manhattan; khi \(p = 2\), ta thu được khoảng cách Euclidean.
Tầm quan trọng sống còn của Chuẩn hóa dữ liệu
Đây là lỗi sơ đẳng và phổ biến nhất của người mới học khi cài đặt KNN: quên chuẩn hóa dữ liệu.
Hãy xem xét một ví dụ thực tế trong phân tích khách hàng với 2 đặc trưng:
- Thu nhập hàng tháng: từ \(10.000.000\) đến \(50.000.000\) VNĐ (chênh lệch hàng chục triệu).
- Tuổi: từ \(18\) đến \(65\) tuổi (chênh lệch vài chục đơn vị).
Khi tính khoảng cách Euclid:
\[d = \sqrt{(\text{Thu nhập}_1 - \text{Thu nhập}_2)^2 + (\text{Tuổi}_1 - \text{Tuổi}_2)^2}\]
Chênh lệch tuổi tác chỉ là vài chục (bình phương lên vài ngàn), trong khi chênh lệch thu nhập là hàng triệu (bình phương lên hàng ngàn tỷ). Kết quả là đặc trưng Tuổi bị vô hiệu hóa hoàn toàn 100%! Mô hình sẽ cư xử như thể bài toán chỉ có duy nhất một đặc trưng thu nhập.
Giải pháp: Luôn luôn đưa các đặc trưng về cùng một thang đo trước khi nạp vào KNN:
- Chuẩn hóa Z-Score (StandardScaler): \(z = \frac{x - \mu}{\sigma}\) (đưa về trung bình 0, phương sai 1).
- Chuẩn hóa Min-Max (MinMaxScaler): \(x_{\text{new}} = \frac{x - x_{\min}}{x_{\max} - x_{\min}}\) (đưa toàn bộ giá trị về đoạn \([0, 1]\)).
Cách lựa chọn siêu tham số K tối ưu
Tham số \(K\) (số lượng láng giềng) kiểm soát trực tiếp ranh giới quyết định của mô hình:
- Nếu \(K\) quá nhỏ (ví dụ \(K = 1\)): Mô hình cực kỳ nhạy cảm với từng điểm nhiễu đơn lẻ. Ranh giới quyết định sẽ gồ ghề, ngoằn ngoèo bao quanh từng điểm cá biệt \(\implies\) Overfitting (High Variance).
- Nếu \(K\) quá lớn (ví dụ \(K = N\)): Mô hình luôn dự đoán lớp chiếm đa số trong toàn bộ tập dữ liệu, bỏ qua mọi thông tin cục bộ của điểm truy vấn \(\implies\) Underfitting (High Bias).
- Quy tắc chọn K:
- Đối với bài toán phân loại 2 lớp, nên luôn chọn \(K\) là số lẻ (ví dụ \(K \in \{3, 5, 7, 9, 11\}\)) để đảm bảo không bao giờ xảy ra trường hợp hòa phiếu.
- Sử dụng kỹ thuật kiểm định chéo K-Fold Cross Validation trên tập huấn luyện để vẽ đồ thị sai số theo \(K\) và chọn giá trị \(K\) có điểm số tốt nhất.
Trọng số khoảng cách và Tăng tốc tìm kiếm lân cận
Trong thuật toán KNN cổ điển, mọi điểm lân cận trong nhóm \(K\) đều có tiếng nói ngang bằng nhau bất kể điểm đó ở sát nút hay nằm tít ngoài rìa của bán kính. Trong thực tế, kỹ thuật gán trọng số theo khoảng cách (Distance-weighted KNN) mang lại hiệu quả vượt bậc:
- Gán trọng số nghịch đảo khoảng cách: Mỗi lân cận \(i\) được gán một trọng số \(w_i = \frac{1}{d(\mathbf{x}, \mathbf{x}_i) + \epsilon}\). Điểm dữ liệu càng gần mẫu truy vấn sẽ có ảnh hưởng quyết định lớn hơn tới kết quả dự đoán, giúp làm mượt biên giới phân loại một cách tự nhiên.
- Tăng tốc tìm kiếm với KD-Tree và Ball-Tree: Nếu duyệt tuyến tính qua toàn bộ tập huấn luyện, độ phức tạp \(O(N \cdot D)\) sẽ trở thành thảm họa khi dữ liệu lên tới hàng triệu bản ghi. Việc tổ chức không gian dữ liệu bằng cây phân cấp nhị phân như KD-Tree hoặc Ball-Tree giúp giảm độ phức tạp tìm kiếm xuống xấp xỉ \(O(D \log N)\) ở các không gian số chiều vừa phải.
- Approximate Nearest Neighbors (ANN): Trong các hệ thống gợi ý hiện đại (Recommendation Systems) với vector nhúng hàng trăm chiều, các thuật toán xấp xỉ như Hierarchical Navigable Small World (HNSW) hoặc thư viện FAISS được áp dụng để trả về lân cận trong thời gian mili-giây với độ chính xác trên \(95\%\).
Chủ đề này nằm trong Lecture 02 - K-Nearest Neighbors (KNN) của Khóa AI. Xem đề cương
Cài đặt thuật toán hoàn chỉnh
Dưới đây là mã nguồn cài đặt thuật toán KNN 2 chiều hoàn chỉnh bằng Python và C++17. Chương trình nạp tập huấn luyện, tính khoảng cách Euclid tới các điểm truy vấn, sắp xếp tìm \(K\) láng giềng gần nhất và biểu quyết nhãn lớp.
# Thuat toan K-Nearest Neighbors (KNN) trong khong gian 2D
import sys
import math
def dist(x1, y1, x2, y2):
return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
def main():
data = sys.stdin.read().split()
if not data: return
it = iter(data)
n = int(next(it))
k = int(next(it))
pts = []
for _ in range(n):
x = float(next(it))
y = float(next(it))
c = int(next(it))
pts.append((x, y, c))
q = int(next(it))
queries = []
for _ in range(q):
qx = float(next(it))
qy = float(next(it))
queries.append((qx, qy))
print(f"k={k}")
for qx, qy in queries:
dists = [(dist(qx, qy, p[0], p[1]), p[2]) for p in pts]
dists.sort(key=lambda item: item[0])
neighbors = dists[:k]
votes = [cls for _, cls in neighbors]
pred = 1 if sum(votes) * 2 >= len(votes) else 0
print(f"{pred}")
if __name__ == "__main__":
main()
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
struct Point {
double x, y;
int c;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
if (!(cin >> n >> k)) return 0;
vector<Point> pts(n);
for (int i = 0; i < n; ++i) cin >> pts[i].x >> pts[i].y >> pts[i].c;
int q;
cin >> q;
vector<pair<double, double>> queries(q);
for (int i = 0; i < q; ++i) cin >> queries[i].first >> queries[i].second;
cout << "k=" << k << "\n";
for (int i = 0; i < q; ++i) {
double qx = queries[i].first;
double qy = queries[i].second;
vector<pair<double, int>> dists(n);
for (int j = 0; j < n; ++j) {
double d = sqrt((qx - pts[j].x)*(qx - pts[j].x) + (qy - pts[j].y)*(qy - pts[j].y));
dists[j] = {d, pts[j].c};
}
// Sap xep theo khoang cach; hai diem cach deu thi giu thu tu nhap
// (giong ban Python) nen hai ban luon cho cung ket qua
stable_sort(dists.begin(), dists.end(),
[](const pair<double, int>& a, const pair<double, int>& b) { return a.first < b.first; });
int kk = min(k, n);
int sum_votes = 0;
for (int j = 0; j < kk; ++j) {
sum_votes += dists[j].second;
}
int pred = (sum_votes * 2 >= kk) ? 1 : 0;
cout << pred << "\n";
}
return 0;
}
Lời nguyền chiều dữ liệu cao (Curse of Dimensionality)
Mặc dù rất trực quan và thanh lịch trong không gian 2D hoặc 3D, KNN gặp phải trở ngại to lớn khi số chiều dữ liệu \(D\) tăng cao (ví dụ phân loại văn bản với \(10.000\) từ hoặc ảnh với \(100.000\) pixel):
Trong không gian nhiều chiều, thể tích của không gian tăng theo hàm mũ của số chiều. Dữ liệu trở nên cực kỳ thưa thớt (sparse), các điểm dữ liệu nằm cách rất xa nhau và khoảng cách từ một điểm bất kỳ đến láng giềng gần nhất xấp xỉ bằng khoảng cách đến láng giềng xa nhất:
\[\lim_{D \to \infty} \frac{d_{\max} - d_{\min}}{d_{\min}} = 0\]
Khi mọi điểm đều cách đều nhau một khoảng xấp xỉ bằng nhau, khái niệm "láng giềng gần nhất" mất đi hoàn toàn ý nghĩa hình học. Do đó, trước khi áp dụng KNN cho dữ liệu nhiều chiều, nên giảm chiều dữ liệu bằng một phép biến đổi áp dụng được cho cả điểm truy vấn mới, như PCA. Không dùng t-SNE cho việc này: t-SNE không biến đổi được điểm mới (lớp TSNE của scikit-learn chỉ có fit_transform, không có transform).
- Chi phí thời gian suy luận đắt đỏ: Vì là thuật toán học lười, mỗi truy vấn mới đòi hỏi tính khoảng cách tới toàn bộ \(N\) điểm trong cơ sở dữ liệu với độ phức tạp \(O(N \cdot D)\). Khi tập dữ liệu có hàng triệu mẫu, thời gian phản hồi sẽ rất chậm.
- Cấu trúc dữ liệu tăng tốc: Trong thực tế, thay vì vét cạn tuyến tính (Brute-force search), người ta sử dụng các cấu trúc cây không gian như KD-Tree hoặc Ball-Tree, hoặc các thuật toán tìm kiếm láng giềng gần đúng (Approximate Nearest Neighbors - ANN như FAISS, HNSW) để giảm độ phức tạp xuống \(O(\log N)\).
Câu hỏi thường gặp
KNN có dùng được cho bài toán Hồi quy (Regression) không?
Có! Với KNN Regression, giá trị dự đoán của điểm mới không phải là biểu quyết nhãn, mà là giá trị trung bình cộng (hoặc trung bình có trọng số theo nghịch đảo khoảng cách \(w_i = \frac{1}{d_i}\)) của các giá trị mục tiêu của \(K\) láng giềng gần nhất: \(\hat{y} = \frac{\sum w_i y_i}{\sum w_i}\).
KNN có tham số huấn luyện (Trainable Parameters) không?
Không. KNN là thuật toán phi tham số (Non-parametric learning). Quá trình "huấn luyện" thực chất chỉ là việc lưu trữ tập dữ liệu vào bộ nhớ hoặc tổ chức thành cây KD-Tree. Toàn bộ trọng tâm tính toán dồn vào pha dự đoán.
Khi xảy ra hòa phiếu trong KNN thì xử lý thế nào?
Có ba cách giải quyết phổ biến:
- Luôn chọn \(K\) lẻ khi số lớp là 2.
- Giảm \(K\) đi 1 cho đến khi phá vỡ thế hòa.
- Sử dụng trọng số khoảng cách: lớp nào có tổng nghịch đảo khoảng cách lớn hơn (các láng giềng nằm sát điểm truy vấn hơn) sẽ giành chiến thắng.
Khóa AI – Introduction to Machine Learning: nền tảng Máy học từ thuật toán cơ bản đến Neural Networks và LLM, học bằng Python. Học thử buổi 1 miễn phí.


