K-Nearest Neighbors (KNN)

K láng giềng gần nhất (KNN) là thuật toán học có giám sát, dự đoán nhãn của một mẫu mới dựa trên k mẫu đã gán nhãn gần nó nhất: phân loại dùng biểu quyết đa số giữa các láng giềng đó, còn hồi quy dùng giá trị trung bình của chúng. KNN phi tham số và "lười": thuật toán không học trọng số, chỉ lưu dữ liệu huấn luyện và chỉ thực hiện toàn bộ tính toán khi có yêu cầu dự đoán. Evelyn Fix và Joseph Hodges giới thiệu phương pháp này năm 1951; đến năm 1967, Thomas Cover và Peter Hart chứng minh rằng với dữ liệu không giới hạn, quy tắc láng giềng gần nhất duy nhất có tỷ lệ lỗi không quá gấp đôi bộ phân loại tốt nhất có thể. Ngày nay, cùng một phép tìm láng giềng gần nhất được chạy ở quy mô lớn trong cơ sở dữ liệu vector và các hệ thống truy xuất ảnh so sánh embedding từ mạng neural.

Cách KNN đưa ra dự đoán#

Với mỗi điểm truy vấn, KNN thực hiện ba bước:

1. Đo khoảng cách: Thuật toán tính khoảng cách từ điểm truy vấn đến mọi mẫu đã lưu. Khoảng cách Euclid là mặc định, khoảng cách Manhattan và Minkowski là các lựa chọn phổ biến, còn độ tương đồng cosine là chuẩn dùng cho embedding, trong đó hướng của vector mang ý nghĩa.
2. Chọn láng giềng: Giữ lại k mẫu có khoảng cách nhỏ nhất.
3. Kết hợp nhãn của chúng: Phân loại chọn lớp xuất hiện nhiều nhất trong các láng giềng, còn hồi quy lấy trung bình các giá trị của chúng. Khi dùng trọng số theo khoảng cách (weights="distance" trong scikit-learn), các láng giềng gần hơn có ảnh hưởng lớn hơn.

Mọi đặc trưng đều góp phần vào khoảng cách, vì vậy các đặc trưng có thang giá trị lớn sẽ chi phối: thu nhập tính bằng đô la sẽ lấn át tuổi tính bằng năm. Do đó, pipeline KNN thường chuẩn hóa đặc trưng trước, hoặc so sánh embedding từ model trích xuất đặc trưng, để mỗi chiều đóng góp ở thang giá trị tương đương.

Chọn k#

Giá trị k quyết định sự cân bằng giữa overfitting và underfitting. Với k = 1, mỗi điểm huấn luyện, kể cả điểm nhiễu và bị gán nhãn sai, đều chiếm một vùng riêng khiến ranh giới quyết định trở nên gồ ghề. Với k rất lớn, mỗi lượt biểu quyết vươn xa khỏi điểm truy vấn và làm mờ các ranh giới lớp thực. Với hai lớp, k lẻ giúp tránh phiếu hòa, còn cross-validation là cách tiêu chuẩn để chọn k. Trên tập dữ liệu hai mặt trăng có nhiễu của scikit-learn, sự đánh đổi thể hiện qua ba giá trị:

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

# Two interleaving half-moons with overlapping, noisy points
X, y = make_moons(n_samples=1000, noise=0.35, random_state=0)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)

# Fitting only stores the points; each prediction is a vote among the k nearest ones
for k in (1, 15, 300):
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_train, y_train)
    print(f"k={k}: train {knn.score(X_train, y_train):.2f}, test {knn.score(X_test, y_test):.2f}")

Với k = 1, bộ phân loại ghi nhớ các điểm huấn luyện, đạt 1.00 trên các điểm đó và 0.83 trên các điểm giữ lại. Với k = 15, điểm số lần lượt là 0.90 và 0.89, kết quả kiểm thử tốt nhất trong ba trường hợp; còn k = 300, gần bằng một nửa trong số 700 điểm huấn luyện, làm mượt ranh giới đến mức cả hai điểm số đều giảm xuống 0.84 và 0.81.

Tăng tốc tìm kiếm láng giềng#

Tìm kiếm vét cạn so sánh điểm truy vấn với tất cả n điểm đã lưu trong không gian d chiều, vì vậy mỗi lần dự đoán tốn số phép toán tỷ lệ với n × d và mức sử dụng bộ nhớ tăng theo kích thước tập dữ liệu. Các cấu trúc phân hoạch không gian như cây k-d và cây cầu giúp bỏ qua phần lớn phép so sánh trong không gian ít chiều; algorithm="auto" của scikit-learn chọn giữa tìm kiếm vét cạn, cây k-d và cây cầu. Trong không gian nhiều chiều, lời nguyền số chiều khiến khoảng cách giữa các điểm gần như bằng nhau, việc cắt tỉa cây không còn hiệu quả, và các hệ thống lớn chuyển sang chỉ mục láng giềng gần nhất xấp xỉ (ANN), chẳng hạn đồ thị HNSW và chỉ mục tệp đảo (IVF) dùng lượng tử hóa tích, được triển khai trong các thư viện như FAISS. Các chỉ mục này trả về phần lớn láng giềng gần nhất thực sự trong khi chỉ so sánh truy vấn với một phần nhỏ các vector đã lưu:

KNN và các phương pháp liên quan#

• Phân cụm K-means: Thuật toán không giám sát nhóm các điểm chưa gán nhãn thành k cụm quanh các tâm cụm đã học. Tên gọi có chung một chữ cái chỉ là trùng hợp: trong k-means, k là số cụm.
• Tìm kiếm vector: Dạng truy xuất của cùng phép toán này: phương pháp trả về các mục đã lưu gần embedding truy vấn nhất, thường thông qua chỉ mục xấp xỉ, và ứng dụng sử dụng trực tiếp các mục đó.
• Máy vector hỗ trợ và hồi quy logistic: Các model tham số học ranh giới quyết định trong quá trình huấn luyện, vì vậy chi phí dự đoán không đổi khi tập huấn luyện tăng lên.

Ứng dụng thực tế#

• Hệ thống đề xuất: Lọc cộng tác dựa trên mục đề xuất các sản phẩm có vector đánh giá hoặc vector mua hàng gần nhất với những mục mà người dùng đã thích.
• Phát hiện bất thường: Khoảng cách từ một điểm đến láng giềng gần thứ k được dùng làm điểm bất thường, nhờ đó các giao dịch hoặc số đo cảm biến cách xa mọi mẫu bình thường sẽ dễ nhận ra.
• Điền giá trị thiếu: KNNImputer của scikit-learn điền mỗi ô trống bằng giá trị trung bình của đặc trưng đó trên k hàng tương tự nhất.
• Truy xuất ảnh và tái nhận dạng: Các hệ thống so sánh embedding của ảnh với một thư viện ảnh để tìm cùng sản phẩm, khuôn mặt hoặc người được camera khác ghi lại. Giải pháp tìm kiếm tương đồng của Ultralytics tạo embedding cho một thư mục ảnh bằng CLIP của OpenAI, chấm điểm từng ảnh đã lập chỉ mục so với truy vấn văn bản như "xe màu đỏ" bằng độ tương đồng cosine trong phép tìm kiếm vét cạn chính xác, rồi trả về các ảnh gần nhất, mặc định tối đa 30 ảnh.